Quadratic Voting With Multiple Alternatives

Jon X. Eguia, Nicole Immorlica, Katrina Ligett, E. Glen Weyl, Dimitrios XefterisSSRN 2019 · DOI

TL;DR

This paper introduces a novel "quadratic voting" mechanism designed for collective decision-making with multiple alternatives. It proves that this mechanism, even with budget-constrained agents, asymptotically leads to socially efficient outcomes in all equilibria, with minimal transfers and a simple message space.

What Problem Does This Paper Address?

The paper tackles the challenge of achieving efficient collective choice in a society with many agents and multiple alternatives, where the goal is to implement the utilitarian optimum (maximizing the sum of individual utilities). Existing mechanisms for Nash implementation are often too complex for practical use. While VCG mechanisms are simpler, they are not budget-balanced, require large transfers, and can have inefficient equilibria. Approximate VCG mechanisms improve on budget balance and asymptotic optimality but still suffer from inefficient equilibria and large transfers, posing issues for agents with tight budget constraints. The authors aim to bridge this gap by proposing a mechanism that is asymptotically optimal in all equilibria, budget-balanced, uses a simple message space, and requires only vanishing transfers.

Methods

The core of the paper is the proposal and analysis of a budget-balanced vote-buying mechanism with quadratic costs. In this mechanism, agents can express support or opposition for each alternative by casting votes, where the cost of casting $x$ votes is $x^2$. This cost is then redistributed to other agents, ensuring budget balance. The chosen alternative is determined by the net vote totals. The authors generalize the "quadratic voting" mechanism, previously developed for binary choices, to multiple alternatives. They then rigorously analyze the properties of this mechanism, focusing on asymptotic optimality (convergence to the utilitarian optimum as the number of agents grows large) and the behavior of equilibria. Key mathematical tools include the analysis of Nash equilibria, utility functions, and convergence properties using laws of large numbers and asymptotic analysis.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Quadratic Costs for Expressive Power: The $x^2$ cost function is crucial. It allows agents to express varying intensities of preference, and importantly, it leads to vanishing transfers in large societies, making the mechanism practical even for budget-constrained agents.
  • Asymptotic Optimality in All Equilibria: A significant finding is that the mechanism achieves asymptotic efficiency not just in a specific equilibrium, but in every equilibrium as the number of agents grows. This robustness is a major advantage over many existing mechanisms.
  • Ordering of Outcomes: Beyond just choosing the best alternative, the mechanism tends to order the alternatives by their social efficiency in the net vote totals. This provides a richer outcome than a simple binary choice.
  • Simplicity and Practicality: The mechanism requires a simple message space (dimension equal to the number of alternatives) and minimal information for the mechanism designer, making it more amenable to real-world applications.

Key Results

  • Asymptotic Optimality: The proposed quadratic voting mechanism is shown to be asymptotically optimal. This means that as the number of agents ($n$) approaches infinity, the probability that the chosen alternative is the socially efficient one converges to 1, for any equilibrium.
  • Vanishing Transfers: Equilibrium actions and monetary contributions of agents converge to zero as $n \to \infty$. This implies that even with budget constraints, agents can fully participate in large societies.
  • Ordered Vote Tally: The net vote tallies for alternatives are asymptotically ordered according to their social efficiency, meaning the best alternative receives the most net votes, the second best receives the second most, and so on.

Limitations and Future Work

  • Risk Neutrality Assumption: The primary assumption that limits the scope of applications is agent risk neutrality. While the authors note that transfers vanishing to zero makes this assumption less critical for agents with the same wealth, it can lead to disproportionate influence for wealthier agents if wealth distribution is unequal. They suggest that for risk-averse agents, alternative mechanisms like storable votes or a hybrid approach might be more suitable.
  • Common Knowledge of Valuations: The paper assumes agents' valuations are common knowledge. While they mention the result is robust to weakening this to only common knowledge of the distribution of value vectors, further exploration of information assumptions could be valuable.
  • Future Work: The authors' findings open avenues for exploring applications in areas like cryptocurrencies, corporate governance, and business associations where agents are often profit-maximizers (and thus closer to risk-neutral). Further research could investigate how to adapt the mechanism for risk-averse agents or explore its performance with different information structures.

Summary updated

BibTeX
@misc{eguia2019quadratic,
  author = {Jon X. Eguia and Nicole Immorlica and Katrina Ligett and E. Glen Weyl and Dimitrios Xefteris},
  title = {{Quadratic Voting With Multiple Alternatives}},
  year = {2019},
  doi = {10.2139/ssrn.3319508},
  howpublished = {SSRN},
}
Figure