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.
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.
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