Abstract The existence of truthful social choice mechanisms strongly depends on whether monetary transfers are allowed. Without payments there are no truthful, non-dictatorial mechanisms under mild requirements, whereas the VCG mechanism guarantees truthfulness along with welfare maximization when there are payments and utility is quasi-linear in money. In this paper we study mechanisms in which we can use payments but where agents have non quasi-linear utility functions. Our main result extends the Gibbard-Satterthwaite impossibility result by showing that, for two agents, the only truthful mechanism for at least three alternatives under general decreasing utilities remains dictatorial. We then show how to extend the VCG mechanism to work under a more general utility space than quasilinear (the “parallel domain”) and show that the parallel domain is maximal—no mechanism with the VCG properties exists in any larger domain.