Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice

Brandon Fain, William Fan, Kamesh MunagalaIJCAI 2020 · DOI

TL;DR

This paper tackles the challenge of making fair and efficient decisions when there are many options and voters, but we can only ask voters to rank a few. They introduce new mechanisms that guarantee good decision-making even with limited voter input, by focusing on how "concentrated" the decision-making quality is, not just its average. This work provides theoretical guarantees and empirical evidence that even a small number of extra voter inputs can significantly improve decision quality.

What Problem Does This Paper Address?

In many real-world scenarios, like participatory budgeting, we need to make a collective decision from a vast number of alternatives. Eliciting full preferences (rankings of all options) from every voter is often impractical due to the sheer number of voters and alternatives. This paper focuses on "randomized social choice mechanisms" that address this by only asking voters to rank a small, constant number of their favorite alternatives.

The core problem is that while previous work focused on the average quality of decisions (measured by "Distortion"), this average can be misleading. A mechanism might perform well on average but have a small chance of making a very bad decision. This paper addresses this by analyzing "higher moments of Distortion," which essentially measure how concentrated the decision quality is. Bounding these higher moments provides strong guarantees about the probability of making a good decision, even in the worst-case scenario. They specifically investigate how the number of voters whose preferences are sampled affects these guarantees.

Methods

The paper introduces two families of randomized social choice mechanisms:

  • Partially Random Copeland (PRC$_k$): This mechanism samples $k$ voters, collects their favorite alternatives, and then uses the Copeland social choice rule on this subset of alternatives with all voters participating in the final vote.
  • Fully Random Copeland (FRC$_s$): This mechanism samples $s$ voters, collects their favorite alternatives, and then uses the Copeland social choice rule on this subset of alternatives with only the sampled voters participating in the final vote.

The key technical innovation lies in bounding the kth moment of Distortion. This is achieved by leveraging the "metric implicit utilitarian model," where voter costs are distances in a metric space. They use sophisticated probability inequalities (like Markov's inequality) and lemmas about the properties of minimums and medians of random variables to derive tight bounds on these higher moments. They also establish lower bounds to show that their proposed sample complexities are optimal.

Datasets

The paper uses data from the Participatory Budgeting project in Cambridge, MA, USA (2015). This dataset involves 945 voters and 23 projects, with a total budget constraint. They simulate their mechanisms on this data using two notions of distance: budget distance and Jaccard distance.

Key Insights and Ideas

  • Higher Moments for Robust Guarantees: Focusing on higher moments of Distortion is crucial for providing high-probability guarantees. A mechanism with a bounded $k$th moment of Distortion implies that it will produce a decision close to optimal with high probability.
  • The Value of Extra Voters: Even a small increase in the number of sampled voters can significantly improve the concentration of Distortion, leading to better high-probability guarantees. This is demonstrated by the tight bounds they derive.
  • Metric Assumption is Key: The metric nature of voter preferences is essential for deriving these tight bounds with a small number of samples. It allows them to relate distances and costs in a structured way.
  • PRC vs. FRC Trade-off: The "full participation" model (PRC) requires fewer samples but involves more communication overall, while the "limited participation" model (FRC) requires more samples but has lower communication complexity.

Key Results

  • Upper Bounds: They show that $k$ sampled voters are sufficient for the full participation model (PRC$_k$) and $2k-1$ sampled voters are sufficient for the limited participation model (FRC$_{2k-1}$) to achieve a constant $k$th moment of Distortion.
  • Lower Bounds: They prove that these sample complexities are tight, meaning that fewer samples would lead to unbounded Distortion for the $k$th moment.
  • Empirical Validation: Simulations on real-world Participatory Budgeting data show that their proposed mechanisms (PRC and FRC) achieve better concentration of social cost compared to Random Dictatorship, even though Random Dictatorship is theoretically optimal for the first moment of Distortion. The simulations qualitatively support their theoretical findings.

Limitations and Future Work

  • Metric Assumption: The current work relies on the metric implicit utilitarian model. Extending these results to non-metric settings or other preference structures would be valuable.
  • One-Shot Mechanisms: The current mechanisms involve sampling and then voting, which might require multiple stages. Investigating truly "one-shot" mechanisms that achieve similar guarantees with constant information elicitation per voter is an open question.
  • Improving Constants: While the sample complexities are shown to be tight, the exact constants in the Distortion bounds might be improvable.
  • Cardinal Information: Exploring the impact of allowing voters to express limited cardinal information (beyond just ordinal preferences) on sample complexity is another interesting avenue.
  • Interactive Mechanisms: Investigating whether interactive mechanisms, where voters can interact with each other or the system, could further reduce sample complexity is also suggested.

Summary updated

BibTeX
@inproceedings{fain2020concentration,
  author = {Brandon Fain and William Fan and Kamesh Munagala},
  title = {{Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/16},
}
Figure