Research map / Learning theory and algorithms / Submodular and game algorithms
Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting
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.
Tightens metric distortion bounds for distributed (two-stage, group-based) voting under four average/max cost objectives, for deterministic and randomized in-group/over-group rules in general metric spaces.
Problem
Distortion of distributed voting where n voters in k groups select local representatives that are then aggregated, under four cost objectives (avgavg, avgmax, maxavg, maxmax); prior bounds were loose or open, especially for randomized mechanisms.
Approach
Shows that a Pareto-efficient in-group rule yields an avgmax bound of 2β+3 independent of the in-group distortion, introduces a Bias Tournament construction for lower bounds, and analyzes random dictatorship / uniform selection mechanisms to obtain tight randomized bounds.
Key results
- Deterministic avgmax upper bound reduced from 11 to 7 via Pareto-efficient in-group rule giving 2β+3.
- Deterministic maxavg lower bound raised from 2+√5 to 5 on a shortest-path metric, matching the known upper bound.
- Randomized (in-group deterministic, over-group random) mechanisms give tight bounds: 5−2/k for avgavg, 3 for avgmax and maxmax, 5 for maxavg.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a Pareto-efficient in-group rule instead of the previous general in-group bound | Deterministic distributed voting · General metric spaces, avgmax | distortion upper bound: 11 to 7 | Helped |
| Use the Arbitrary Dictator mechanism for general metrics | Deterministic distributed voting · General metric spaces, maxmax | distortion upper bound: 5 to 3 | Helped |
| Use the Bias Tournament lower-bound construction | Deterministic distributed voting · General metric spaces, maxavg | distortion lower bound: $2 + \sqrt{5}$ to 5 | Helped |
| Use a deterministic in-group rule with distortion 3 and randomized uniform over-group selection | randdet · General metric spaces, avgavg | distortion: $5-\frac{2}{k}$ | Helped |
| Use a Pareto-efficient in-group rule and uniform over-group selection | randdet · General metric spaces, avgmax | distortion upper bound: 5 to 3 | Helped |
| Use Random Dictatorship in-group and uniform over-group selection | randrand · General metric spaces, avgavg | distortion upper bound: $3-\frac{2}{kn^*}$ | Helped |
Surprising findings
- For randomized mechanisms with both stages random, maxavg and maxmax reach tight distortion 3 even though randomized rules are generally expected to be better than deterministic ones in the single-stage setting.
Limitations
- Nearly tight rather than tight bounds for randomized avgavg and avgmax in the both-randomized setting.
- Euclidean results are only partial lower bounds, not matching upper bounds.
Experimental setup
Metrics: distortion
Baselines: Plurality Matching Arbitrary Dictator alpha-in-beta-over mechanism Random Dictatorship
Builds on: Plurality Matching Plurality Veto Random Dictatorship alpha-in-beta-over mechanism Arbitrary Dictator
Closest papers by meaning
- Communication, Distortion, and Randomness in Metric Voting (AAAI 2020 · similarity 0.92)
- An Analysis Framework for Metric Voting based on LP Duality (AAAI 2020 · similarity 0.90)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.90)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.89)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.87)
- The Distortion of Public-Spirited Participatory Budgeting (AAAI 2025 · similarity 0.85)
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.