Social Choice for Agents with General Utilities

Hongyao Ma, Reshef Meir, David C. Parkes

Abstract

The Gibbard-Satterthwaite theorem famously establishes that without monetary transfers, any truthful social choice mechanism with three or more alternatives must be dictatorial. While quasi-linear utilities allow for fair mechanisms like VCG, real-world preferences are often non-linear due to budget constraints or risk aversion. This paper extends the impossibility result to general utility functions and identifies the "parallel domain" as the unique maximal space where non-dictatorial, truthful mechanisms remain possible.

Introduction

Designing truthful mechanisms—where participants are incentivized to report their genuine preferences—is a cornerstone of multi-agent systems. Historically, a sharp divide existed: settings without money are plagued by the Gibbard-Satterthwaite impossibility (dictatorship), while settings with money and quasi-linear (QL) utilities ("value minus price") allow for efficient, fair VCG mechanisms. However, the QL assumption is frequently violated in practice. This research explores whether truthful, non-dictatorial mechanisms can survive when we allow for general, non-linear utilities for money.

The Impossibility of General Utilities

The authors prove a striking extension of the Gibbard-Satterthwaite theorem. If agent utilities are allowed to be any strictly decreasing function of payment (general utilities), the impossibility returns. For a system with at least three alternatives and two agents, any mechanism that is truthful, deterministic, and satisfies basic fairness properties (unanimity and no payments to agents) must be a dictatorship.

Figure 1: An example of general utilities where utility curves for different alternatives have varying slopes. This lack of structural consistency leads to the return of the dictatorship impossibility.

As shown in Figure 1, when the "willingness to pay" for one option over another changes depending on the current payment level, the mechanism cannot maintain truthfulness without resorting to a dictator.

The Parallel Domain: A Geometric Sweet Spot

To find a way out of this impossibility, the researchers identify a specific class of utility functions called the Parallel Domain. In this domain, while utility curves can be non-linear (e.g., curved or stepped), the horizontal distance between curves for different alternatives remains constant regardless of the payment level.

Figure 5: Formal definition and geometric representation of the Parallel Domain. The horizontal shift between utility curves is invariant to the payment $z$, which is the key property allowing for VCG-like mechanisms.

As defined in Figure 5, the "willingness to pay" for option $j$ over $j'$ is independent of the agent's current wealth or payment status. The authors prove that this domain is "tight"—it is the largest possible set of utilities that avoids the dictatorship result.

Key Results and Mechanisms

The paper introduces a new mechanism specifically designed for the parallel domain. By using "maximum willingness to pay" as a proxy for bids, this mechanism achieves truthfulness, efficiency, and fairness. Furthermore, the authors demonstrate that if the utility space includes even a single "non-parallel" type, the desired social choice properties can no longer be simultaneously satisfied.

Conclusion and Future Work

While the parallel domain offers a theoretical bridge between quasi-linear and general utilities, it remains a restrictive assumption. The current impossibility result is formally proven for two agents, and extending this to $n$ agents is a primary goal for future work. Additionally, the researchers suggest that relaxing the strict requirement for truthfulness might allow for more practical mechanisms in realistic, non-linear utility settings.

Summary updated

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 quasi-linear (the "parallel domain") and show that the parallel domain is maximal--no mechanism with the VCG properties exists in any larger domain.
BibTeX
@inproceedings{ma2016social,
  author = {Hongyao Ma and Reshef Meir and David C. Parkes},
  title = {{Social Choice for Agents with General Utilities}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure