TL;DR
This paper investigates the vulnerability of algorithms used to select participants for citizens' assemblies to manipulation. They demonstrate that commonly used "fair" algorithms like Leximin are surprisingly easy to game, and introduce a new class of algorithms based on Lp norms that offer significantly improved robustness against such manipulation, especially as the pool size grows.
What Problem Does This Paper Address?
Citizens' assemblies are increasingly used to inform policy decisions, bringing together a diverse group of citizens. A crucial step is selecting these participants to ensure the assembly is "descriptively representative" of the broader population (e.g., in terms of gender, age, location). However, a key challenge is "self-selection bias": people with certain characteristics are more or less likely to volunteer. This means the pool of volunteers isn't representative. Algorithms are used to select a panel from this biased pool to meet representation goals. This paper tackles a previously unstudied problem: manipulability. Can individuals or groups strategically misreport their characteristics (e.g., lie about their age or opinion) to increase their chances of being selected, or to disadvantage others? This is a significant concern because it undermines the fairness and trustworthiness of the assembly's recommendations.
Methods
The authors introduce a formal model for three types of manipulation:
- Internal Manipulability: Increasing one's own selection probability.
- External Manipulability: Decreasing another's selection probability.
- Composition Manipulability: Misappropriating seats from other demographic groups.
They then analyze a class of "rounding-based" selection algorithms. These algorithms first compute ideal selection probabilities that satisfy representation constraints and fairness objectives, and then use a randomized rounding procedure to select the final panel. The core of their contribution lies in analyzing the manipulability of different objective functions used in this first step. They show that popular objectives like Leximin and Nash Welfare are highly manipulable. To address this, they propose and analyze algorithms based on Lp norms as objective functions. These norms, particularly as p approaches infinity (l∞ norm), penalize high selection probabilities more heavily, leading to increased robustness.
Datasets
The paper uses eight real-world panel selection datasets obtained from citizen assembly organizers in the UK and US. They do not introduce new benchmark datasets but rather use existing instances to evaluate their theoretical findings empirically.
Key Insights and Ideas
- Fairness vs. Robustness Trade-off: Algorithms that prioritize making selection probabilities as equal as possible (like Leximin and Nash Welfare) are highly susceptible to manipulation. This is because they allow for very high individual selection probabilities, which can be exploited.
- The Power of Lp Norms: Using Lp norms as objective functions, especially as p increases, significantly reduces manipulability. The l∞ norm, which minimizes the maximum selection probability, offers the best theoretical convergence rate for robustness.
- Pool Size Matters: Increasing the size of the volunteer pool (n) generally decreases manipulability, as it dilutes the impact of any single misreported feature.
- Self-Selection Bias is Inherent to Manipulation: The paper proves a fundamental impossibility: when there's self-selection bias, achieving descriptive representation necessarily creates incentives for manipulation. No algorithm can achieve both representation and eliminate manipulation incentives simultaneously.
- Practical Implications: The findings suggest that to reduce manipulation, organizers should aim for larger pools and consider algorithms that penalize high selection probabilities.
Key Results
- Leximin and Nash Welfare are Highly Manipulable: An individual can gain a selection probability of 1 by misreporting, and coalitions can misappropriate a significant fraction of panel seats. This holds even for large pool sizes.
- Lp-Norm Algorithms are Robust: The manipulability of Lp-norm based algorithms decreases as O(1/n^(1-1/p)), approaching the optimal rate of O(1/n) as p → ∞.
- Empirical Validation: Experiments on eight real-world datasets confirm that Leximin and Nash Welfare remain highly manipulable, while l2 and l∞ norms show quickly declining manipulability as the pool size increases.
- Self-Selection Bias Impact: The degree of self-selection bias in an instance is a strong predictor of manipulability. Reducing this bias (e.g., by dropping features with high self-selection bias) also reduces manipulation.
Limitations and Future Work
- Focus on Individual Manipulation: While the paper models coalition manipulation, the empirical evaluation primarily focuses on individual manipulators and heuristic strategies.
- Quota-Based Algorithms: The theoretical analysis primarily uses a continuous relaxation of quota-based algorithms. Future work could directly analyze quota-based algorithms, which are more common in practice, though they might be more complex to analyze due to their combinatorial nature.
- Finding the "Perfect" Objective: The paper highlights a trade-off between preventing low selection probabilities (fairness) and preventing high ones (robustness). Future work could explore objectives that balance both desiderata, aiming for a Θ(1/n) selection probability for all agents.
- Strategic Classification Connection: The authors note the connection to strategic classification and suggest further research in this area, particularly on the technical aspects of convex program stability.
Summary updated