Research map / Learning theory and algorithms / Fairness
Manipulation-Robust Selection of Citizens’ Assemblies
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that leximin and Nash Welfare selection algorithms for citizens' assemblies are highly manipulable by volunteers misreporting features, and proposes rounding-based l_p-norm selection algorithms whose manipulability decays as O(1/n^(1-1/p)), with experiments on eight real-world datasets.
Problem
Selection algorithms for citizens' assemblies pick panels representative of demographics from self-reported volunteer features, which creates incentives for strategic misreporting; the manipulability of these algorithms had not been studied.
Approach
Defines three manipulability measures (internal, external, composition) and shows that fairness objectives that allow very high selection probabilities (leximin, Nash) are arbitrarily manipulable, whereas strongly convex l_p-norm objectives limit maximum probability and thus manipulation, with rates approaching the optimal Theta(1/n) as p grows.
Key results
- Leximin and Nash Welfare allow an individual agent to gain selection probability 1 by misreporting, and coalitions can misappropriate nearly half of panel seats (Theorem 3.1).
- l_p-norm manipulability decays as O(k/n^(1-1/p)), approaching the Omega(1/n) lower bound as p grows; l_inf is optimal up to constants (Theorems 4.2, 4.3).
- In experiments on eight real-world instances, manipulation gain of l_2 and l_inf against OPT-1 declines quickly in n, while leximin and Nash remain highly manipulable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Leximin or Nash Welfare rather than an ℓp-norm objective | Rounding-based selection algorithms · Theorem 3.1 instances | internal manipulability: MANIPint(N, leximin, 1) = 1; MANIPint(N, nash, 1) = 1 | Hurt |
| Use Leximin or Nash Welfare rather than an ℓp-norm objective | Rounding-based selection algorithms · Theorem 3.1 instances | composition manipulability: MANIPcomp(N, leximin, c) = c; MANIPcomp(N, nash, c) = c | Hurt |
| Use an ℓp-norm objective, p > 1 | Rounding-based selection algorithms · Pools satisfying Assumption 4.1 | internal manipulability: O(k/n^{1−1/p}) | Helped |
| Use an ℓp-norm objective, p > 1 | Rounding-based selection algorithms · Pools satisfying Assumption 4.1 | external manipulability: O(k/n^{1−1/p}) | Helped |
| Use an ℓp-norm objective, p > 1 | Rounding-based selection algorithms · Pools satisfying Assumption 4.1 | composition manipulability: O(ck/n^{1−1/p}) | Helped |
| Increase the number of volunteers n | ℓ2 and ℓ∞ selection algorithms · Eight real-world panel selection datasets | manipulation gain | Helped |
| Increase the number of volunteers n | Leximin and Nash Welfare selection algorithms · Eight real-world panel selection datasets | manipulation gain | No clear effect |
Surprising findings
- Leximin and Nash, the fairness-optimal methods used in practice, are arbitrarily manipulable even when agents misreport only one feature.
- l_2 and l_inf give at least one agent zero selection probability in all eight instances, showing a tradeoff with low-probability fairness.
Limitations
- Analysis is for individual and coalition manipulation under heuristic strategies; optimal manipulation is computationally hard to compute.
- Results are for rounding-based algorithms with ex-ante representation, not the quota-based algorithms used in practice.
- Lp-norm algorithms give some agents zero selection probability, harming low-probability fairness.
Experimental setup
Datasets: eight real-world citizens' assembly pool datasets (sf(a)-(e), hd, cca, newd) from assembly organizers
Benchmarks: eight real-world panel selection instances
Metrics: internal manipulability external manipulability composition manipulability manipulation gain
Baselines: Leximin Nash Welfare
Builds on: Leximin (Flanigan et al. 2021) Flanigan et al. 2020 rounding algorithm Nash Welfare selection (Flanigan, Kehne, Procaccia 2021)
Closest papers by meaning
- Federated Assemblies (AAAI 2025 · similarity 0.87)
- Impartial Selection with Predictions (NeurIPS 2025 · similarity 0.85)
- Reducing Leximin Fairness to Utilitarian Optimization (AAAI 2025 · similarity 0.83)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.83)
- Fair Participation via Sequential Policies (AAAI 2024 · similarity 0.82)
- The Role of Learning Algorithms in Collective Action (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.