TL;DR
This paper introduces and analyzes "average distortion" for voting rules in a probabilistic setting, moving beyond traditional worst-case analysis. They show that even simple voting rules can have high average distortion, but surprisingly, a single cardinal query per agent can significantly reduce it, achieving near-optimal results for binary valuations.
What Problem Does This Paper Address?
In collective decision-making, voting rules aim to select an outcome that best reflects the preferences of a group of agents. A key challenge is that voting rules often only receive ordinal information (rankings) and not the underlying cardinal values (how much agents like each option). This can lead to outcomes that are far from optimal in terms of total social welfare, a phenomenon quantified by "distortion." Traditional analysis focuses on the worst-case scenario, which might not reflect real-world performance. This paper addresses this by studying voting rules in a stochastic setting where agent values are drawn from a probability distribution, and they introduce and analyze "average distortion." They also investigate how limited access to cardinal information (via queries) can mitigate distortion.
Methods
The authors introduce the concept of average distortion for voting rules in a stochastic setting. They model agent valuations as being drawn independently from a common probability distribution, creating "impartial culture electorates." They then analyze mechanisms that can make a limited number of "cardinal queries" to agents, asking for their specific value for an alternative.
Key mechanisms and techniques include:
- MEAN mechanism: A deterministic mechanism that makes a single query per agent to determine the value of an alternative at a specific rank. It then uses "implied social welfare" to select an outcome.
- RTMEAN mechanism: A randomized mechanism that uses MEAN as a building block, employing random thresholds to adapt to different distributions.
- RTSEARCH mechanism: A randomized mechanism designed for worst-case electorates that uses binary search to identify sets of alternatives above certain value thresholds.
The analysis heavily relies on probability theory, Chernoff bounds, and careful construction of adversarial scenarios to establish lower bounds.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated electorates based on probability distributions rather than real-world datasets.
Key Insights and Ideas
- Average distortion is surprisingly high: Even simple voting rules, like picking an alternative uniformly at random, have a high average distortion (Ω(m)) in impartial culture electorates. This suggests that worst-case analysis might not be the sole explanation for the success of some voting rules.
- Cardinal queries are powerful: A single cardinal query per agent can dramatically reduce average distortion, especially for binary valuations, achieving near-optimal results. This highlights the value of even limited cardinal information.
- Randomization helps: Randomized mechanisms can achieve better worst-case distortion guarantees than deterministic ones for a given number of queries.
- Lower bounds on queries: The paper establishes new lower bounds on the number of queries needed for constant worst-case distortion, showing that Ω(log m) queries are necessary for deterministic mechanisms.
Key Results
- Any voting rule has an average distortion of at least Ω(m) in impartial culture electorates.
- The MEAN mechanism achieves constant average distortion with a single query per agent for binary distributions.
- The RTMEAN mechanism achieves O(log m) average distortion for general distributions with a single query per agent.
- Deterministic mechanisms making A queries per agent require Ω(log m) queries to achieve constant worst-case distortion.
- The RTSEARCH mechanism achieves O(log m) worst-case distortion with O(log m) queries per agent.
Limitations and Future Work
The authors acknowledge that their analysis of average distortion relies on the assumption that the probability distribution of valuations is known. An interesting open problem is whether constant average distortion can be achieved without this strong assumption. They also suggest exploring other natural extensions, such as different distributions per alternative or distributions with unit-sum/unit-range assumptions, which would introduce correlations and require new techniques. For worst-case distortion, the conjecture that O(log m) deterministic queries are sufficient for constant distortion remains open, as does the exploration of the separation between deterministic and randomized mechanisms.
Summary updated