Research map / Learning theory and algorithms / Submodular and game algorithms
Approval-Based Committee Voting in Practice: A Case Study of (over-)Representation in the Polkadot Blockchain
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.
Collects 496 real-world approval-based committee elections from the Polkadot blockchain and empirically compares six ABC voting rules on representation and overrepresentation (security) measures.
Problem
Empirical behavior of approval-based committee (ABC) voting rules is rarely studied on real-world data, and classic binary proportionality axioms fail to discriminate rules in practice; blockchain validator elections (Polkadot NPoS) raise overrepresentation/security concerns that are under-studied.
Approach
Uses weekly-to-daily Polkadot validator elections as real-world ABC data and evaluates voting rules with quantitative proportionality measures (average satisfaction, priceability gap) and new overrepresentation measures (stake lost, exogenous cost of replacing committee members) tied to blockchain security.
Key results
- Proportional rules (seq-PAV, Phragmms, seq-Phragmén, MES) all return EJR+ committees on every tested Polkadot instance, while AV violates JR and EJR+ on all instances.
- Replacing one-third of the committee under seq-Phragmén or Phragmms requires about 40% of total stake, versus about 14% for AV and 24% for SAV.
- Changing committee size from 300 to 200 or 400 only marginally affects overrepresentation measures, whereas allowing copies of candidates has a larger beneficial impact.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a proportional rule (seq-PAV, Phragmms, seq-Phragmén, or MES) instead of AV | Polkadot committee elections · Polkadot elections | JR violations: 28.347 -> 0 | Helped |
| Use a proportional rule instead of AV | Polkadot committee elections · Polkadot elections | EJR+ violations: 32.343 -> 0 | Helped |
| Use a proportional rule instead of AV | Polkadot committee elections · Polkadot elections | priceability violations: 124.341 -> 0.000 | Helped |
| Use seq-PAV instead of AV | Polkadot committee elections · Polkadot elections | PAV score: 2.502 -> 2.585 | Helped |
| Use AV instead of seq-PAV | Polkadot committee elections · Polkadot elections | weighted satisfaction: 8.672 -> 9.055 | Helped |
| Use seq-Phragmén or Phragmms instead of AV | Polkadot committee elections · Polkadot elections | cost of replacing one-third of the committee: 0.14 -> 0.40 | Helped |
| Increase committee size from 300 to 400 | Voting rules in Polkadot elections · Polkadot elections | minimum approval weight: around 15% | Hurt |
| Increase committee size from 300 to 400 | Voting rules in Polkadot elections · Polkadot elections | minimum average satisfaction of supporting groups | Helped |
| Increase committee size from 300 to 400 | Voting rules in Polkadot elections · Polkadot elections | cost of replacing one-third or half of committee | No clear effect |
| Allow copies of candidates to be selected multiple times | Voting rules in Polkadot elections · Polkadot elections | variance of backing weights: around 80% | Helped |
| Allow copies of candidates to be selected multiple times | Voting rules in Polkadot elections · Polkadot elections | satisfaction of ℓ-supporting groups | Hurt |
| Use Phragmms instead of seq-Phragmén | Polkadot committee elections · Polkadot elections | maximin support value: 209 cases; 43 cases; at most 0.0002 | Mixed |
Surprising findings
- Classic binary proportionality axioms (JR, EJR+) fail to meaningfully distinguish voting rules on real-world data, with almost all rules outperforming their worst-case guarantees.
- AV achieves the highest cost of replacing a single candidate, yet becomes cheaper than proportional rules for larger replacements of committee members.
Limitations
- Some eras missing from the data (185 eras not correctly stored), causing gaps.
- Minimum approval weight computation is NP-hard, so only 15 instances were averaged for that measure.
- Maximin support method excluded due to computational complexity; seq-PAV replacement cost left partially unresolved.
Experimental setup
Datasets: Polkadot validator election data (496 elections, eras 398-1078) Kusama elections (1520, appendix)
Benchmarks: Polkadot elections (496)
Metrics: PAV score JR violations EJR+ violations priceability gap average satisfaction of l-supporting groups minimum approval weight maximin support value stake lost exogenous cost of replacing committee overlap
Baselines: AV SAV seq-PAV seq-Phragmén MES Phragmms
Builds on: Phragmén's sequential rule Method of Equal Shares Proportional Approval Voting Phragmms priceability
Closest papers by meaning
- An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections (AAAI 2021 · similarity 0.82)
- Understanding the Impact of Proportionality in Approval-Based Multiwinner Elections (AAAI 2026 · similarity 0.82)
- Temporal Fairness in Multiwinner Voting (AAAI 2024 · similarity 0.81)
- The Temporal Graph of Bitcoin Transactions (NeurIPS 2025 · similarity 0.80)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.79)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.79)
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.