Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting

Basic Information

• Paper ID: 2509.17134
• Title: Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting
• Authors: MohammadAli Abam, Davoud Kareshki, Marzieh Nilipour, MohammadHossein Paydar, Masoud Seddighin
• Institutions: Sharif University of Technology (Tehran, Iran); Tehran Institute for Advanced Studies (TeIAS), Khatam University
• Classification: cs.GT (Game Theory)
• Publication Date: November 23, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2509.17134v2

Abstract

This paper investigates the metric distortion problem in distributed voting, where n voters are partitioned into k groups, each selecting a local representative, and a winner is subsequently chosen from these representatives (or all candidates). This setting models systems such as U.S. presidential elections. The paper proposes improved distortion bounds for four cost objectives (avg-avg, avg-max, max-avg, max-max). For deterministic mechanisms, it reduces the avg-max upper bound from 11 to 7, establishes a tight lower bound of 5 for max-avg (improving upon 2+√5), and tightens the max-max upper bound from 5 to 3. For randomized mechanisms, tight or near-tight bounds are established under both settings.

Research Background and Motivation

Problem Definition

In social choice theory, voting rules must aggregate agents' preferences into a final outcome. Traditional centralized voting assumes all voters' preferences can be directly aggregated, but in large-scale scenarios (such as U.S. presidential elections), decisions are typically made through a two-stage distributed process:

1. Intra-group stage: Each group independently selects a local representative
2. Inter-group stage: A final winner is selected from the representatives

Problem Significance

1. Broad practical applications: The U.S. Electoral College system, federal decision-making, and multi-level organizational voting all employ distributed structures
2. Information asymmetry: Voting rules can only access ordinal preferences (rankings), not true cardinal utility values
3. Theoretical challenges: Need to evaluate mechanism performance guarantees under limited information

Limitations of Existing Approaches

• Anshelevich et al. (2022) first systematically studied deterministic distributed voting distortion, but with significant gaps:
  • avg-max: 2+√5, 11
  • max-avg: 2+√5, 5
  • max-max: 3, 5
• Randomized mechanisms unexplored: Although randomization can break the distortion lower bound of 3 in centralized voting, randomized mechanisms in distributed settings were completely unstudied
• Special metric spaces: Linear metrics were resolved by Voudouris (2023), but general metric spaces remain open

Research Motivation

1. Explore whether randomization can improve distortion in distributed settings
2. Tighten known bounds for deterministic mechanisms
3. Provide a nearly complete characterization of distributed voting distortion

Core Contributions

1. First systematic study of randomized distributed mechanisms:
   • rand-det mechanism (randomization only in second stage): Establishes tight bounds for all four objectives
   • rand-rand mechanism (randomization in both stages): Establishes tight or near-tight bounds
2. Improved deterministic mechanism bounds:
   • avg-max: Upper bound reduced from 11 to 7
   • max-avg: Lower bound improved from 2+√5 to tight bound of 5
   • max-max: Upper bound tightened from 5 to 3
3. Introduction of new analytical tool—Bias Tournament:
   • Captures tie-breaking preferences of deterministic rules
   • Used for lower bound proofs constructing high-distortion instances
4. Specialized bounds for Euclidean spaces:
   • rand-rand: Lower bound √5-ε
   • rand-det: Lower bound 2+√5-ε
5. Byproduct results for centralized voting:
   • Proves that randomized voting rules have distortion at least 3-ε under max objectives (nearly matching known upper bound of 3)

Detailed Methodology

Task Definition

Input:

• Voter set V (|V|=n), partitioned into k groups G
• Candidate set C (|C|=m)
• Metric space d: V×C→ℝ⁺, satisfying triangle inequality
• Preference profile π: Each voter ranks candidates in increasing distance order

Output:

• Distributed mechanism Ψ=(f_in, f_ov) selects winner w

Objective: Minimize distortion D(Ψ) = sup_I Ecost(w|I) / min_c cost(c|I)

Four cost objectives:

1. avg-avg: Average within groups, then average across groups
2. avg-max: Maximum within groups, then average across groups
3. max-avg: Average within groups, then maximum across groups
4. max-max: Maximum within groups, then maximum across groups

Core Technical Framework

1. Bias Tournament

Definition: Given deterministic rule f and candidate ordering σ, construct directed complete graph T(f,C,σ):

• Vertices: Each candidate
• Edges: For candidate pair (u,w), if in elections where two voters have preferences σ↑w↑u and σ↑u↑w, f selects u, add edge u→w

Key Property (Observation 2.2): Any tournament on m vertices has at least one vertex with in-degree ≥⌈(m-1)/2⌉

Application:

• Identify "failing candidates" (high in-degree)
• Construct instances where such candidate is optimal but cannot be selected
• Used for lower bounds in rand-det and det-det

2. rand-det Mechanism Analysis

Mechanism Design: (f_pm-par, f_ur)

• First stage: Plurality Matching with Pareto Efficiency
• Second stage: Uniform random selection

Key Theorems:

Theorem 3.1 (max-avg): D((f_α, f_ur)) ≤ α+2

• Proof idea: Using Pareto efficiency, there exists voter v_g preferring w_g over o
• Chain expansion via triangle inequality:

  E[cost(w)] ≤ cost(o) + (1/k)Σ_g d(o,w_g)
               ≤ cost(o) + (1/k)Σ_g [d(o,v_g) + d(v_g,w_g)]
               ≤ cost(o) + 2(1/k)Σ_g d(v_g,o)  [since d(v_g,w_g)≤d(v_g,o)]
               ≤ (α+2)cost(o)
  

Theorem 3.3 (avg-avg): D((f_α, f_ur)) ≤ α+2-2/k

• Key: Separate intra-group and inter-group terms, intra-group terms contribute -2/k improvement

Theorem 3.5 (avg-max, max-max): D((f_par, f_ur)) ≤ 3

• Only Pareto efficiency needed to achieve 3 (no need for strong assumption α=3)

Lower Bound Construction:

Theorem 3.7 (max-avg, lower bound 5):

• Use bias tournament to find candidate c₁ with in-degree ≥2
• Construct linear metric instance with 4 candidates, 4 voters, 2 groups
• Ensure c₂ and c₃ as representatives, cost(c₁)=1/4, cost(c₂)=cost(c₃)=5/4

Theorem 3.8 (avg-avg, lower bound 5-2/k):

• Use graph shortest-path metric (non-linear)
• k groups with single voter each, 2k candidates
• Tree structure: central candidate c_2k is optimal, but each group's representative is c_i (1≤i≤k)

3. rand-rand Mechanism Analysis

Mechanism Design: (f_rd, f_ur)

• First stage: Random Dictatorship (uniformly randomly select voter's top choice)
• Second stage: Uniform random selection

Key Observation (Observation 2.6):

E[cost(w)] = (1/k)Σ_g (1/n_g)Σ_{v∈g} cost(top(v))

Upper Bound Proof Strategy:

Theorem 4.1 (max-max, upper bound 3): For any voter v:

cost(top(v)) = d(v**(top(v)), top(v))
             ≤ d(v**(top(v)), o) + d(o,v) + d(v,top(v))  [triangle inequality]
             ≤ d(v**(o), o) + d(v,o) + d(v,o)  [top(v) is v's nearest candidate]
             ≤ 3d(v**(o), o) = 3cost(o)

Theorem 4.4 (avg-avg, upper bound 3-2/(kn*)):

• Most complex proof, requires delicate handling of double summation
• Key: Separate v'=v terms, contributing -2/(kn*) improvement
• When all group sizes equal, bound becomes 3-2/n

Lower Bound Construction:

Theorem 4.6 (max-avg, max-max, lower bound 3):

• 2 voters, 3 candidates, 2 single-voter groups
• Linear metric: c₁(-1), c₂(0), c₃(1); v₁(-0.5), v₂(0.5)
• Must select c₁ or c₃, cost=3/2, while cost(c₂)=1/2

Theorem 4.7 (avg-max, lower bound 3-2/n):

• m candidates, m voters, single group
• Construct m instances I_i where c_i is optimal in I_i
• Cyclic preferences: π_i = (c_i, c_{i+1}, ..., c_m, c_1, ..., c_)
• Probabilistic argument: must exist i with p_i≤1/m

Corollary 4.8: This construction also proves 3-ε lower bound for centralized randomized voting under max objectives

Theorem 4.9 (avg-avg, lower bound 3-2/n):

• k single-voter groups, k+1 candidates
• Tree structure: central candidate c_m is optimal, but not any group's representative

4. det-det Mechanism Improvements

Theorem 5.1 (max-max, upper bound 3):

• Arbitrary Dictator mechanism achieves 3
• Improves upon Anshelevich et al.'s bound of 5

Theorem 5.2 (avg-max, upper bound 2β+3):

• (f_par, f_β) mechanism
• Key: Leverage Pareto efficiency, independent of α
• Setting β=2 (f_pm-par), yields upper bound 7

Theorem 5.4 (max-avg, lower bound 5):

• Use bias tournament and graph metric (non-linear)
• 4 candidates, 4 voters, 2 groups
• Construct two instances I₁ and I₂, ensuring at least one excludes optimal candidate

Technical Innovations

1. Introduction of Bias Tournament:
   • Formalizes tie-breaking behavior of deterministic rules as graph structure
   • Leverages combinatorial properties of tournaments (must have high in-degree vertex)
   • Enables systematic lower bound instance construction
2. Weakened exploitation of Pareto efficiency:
   • Proves avg-max achieves 3 with only Pareto efficiency (no need for α=3)
   • Decouples distortion dependencies between two stages
3. Refined analysis of double summation:
   • avg-avg objective requires handling nested averages
   • Obtain improvements by separating diagonal terms (v'=v, g'=g)
4. Use of non-linear metric spaces:
   • Many lower bounds require graph shortest-path metrics (non-embeddable in linear or Euclidean)
   • Demonstrates essential complexity of the problem
5. Euclidean supersimplex construction:
   • Construct symmetric instances in R^{l+1}
   • Leverage high-dimensional geometry to achieve √5 lower bound

Experimental Setup

Note: This is a pure theory paper with no experimental section. All results are established through mathematical proofs.

Theoretical Verification Methods

1. Constructive proofs:
   • Lower bounds: Construct concrete instances, compute distortion
   • Upper bounds: Analyze mechanism performance on arbitrary instances
2. Metric space types:
   • General metric spaces (satisfying triangle inequality)
   • Linear metrics (one-dimensional)
   • Euclidean spaces (high-dimensional)
   • Graph shortest-path metrics
3. Instance characteristics:
   • Symmetric instances (all groups equal size)
   • Single-voter groups
   • Small-scale instances (2-4 groups, 2-4 candidates)

Experimental Results

Summary of Main Results

Table 2: Complete Results Overview

Bold indicates new results in this paper; ↑/↓ indicates direction of improvement

Key Findings

1. Value of randomization:
   • rand-det achieves or approaches optimality on all objectives
   • rand-rand further improves avg-avg (from 5-2/k to 3-2/n)
   • But max-avg and max-max cannot break through 3
2. Limits of deterministic mechanisms:
   • max-avg tight bound is 5 (higher than centralized 3)
   • max-max achieves 3 (same as centralized)
   • avg-max still has gap (7 vs 2+√5)
3. Distributed vs. centralized:
   • Centralized randomized voting: max objective distortion ≥3-ε (Corollary 4.8)
   • Distribution adds complexity, certain objectives have higher distortion
4. Impact of metric space:
   • Linear metrics: many lower bounds achievable on line
   • General metrics: some lower bounds require graph metrics (e.g., max-avg bound of 5)
   • Euclidean: slightly lower bounds (√5 vs 3-2/n)

Technical Insights

1. Interaction of two stages:
   • avg-max: second stage dominant (2β+3 independent of α)
   • max-avg: both stages important (α+2)
   • avg-avg: subtle double-averaging effect (α+2-2/k)
2. Role of Pareto efficiency:
   • Sufficient to achieve 3 on certain objectives (no complete Plurality Matching needed)
   • Provides key constraint on voter-representative relationships
3. Challenges of probabilistic analysis:
   • rand-rand upper bound for avg-avg requires handling quadruple summation
   • Precise treatment of diagonal terms is critical

Related Work

Centralized Voting Distortion

1. Deterministic mechanisms:
   • Anshelevich et al. (2018): Lower bound 3
   • Gkatzelis et al. (2020): Plurality Matching achieves upper bound 3 (tight)
   • Kizilkaya & Kempe (2022): Simplified Plurality Veto achieves 3
2. Randomized mechanisms:
   • Anshelevich & Postl (2017): Random Dictatorship achieves 3-2/n
   • Charikar & Ramakrishnan (2022): Lower bound 2.112
   • Charikar et al. (2024): Upper bound 2.753 (current best)

Distributed Voting

1. Utility framework:
   • Filos-Ratsikas et al. (2020): First study of distributed distortion
   • Filos-Ratsikas & Voudouris (2024): Randomized mechanisms, distortion Θ(km²)
2. Metric framework:
   • Anshelevich et al. (2022): First systematic study of deterministic mechanisms
   • Voudouris (2023): Tight bounds for linear metrics
   • This paper: Randomized mechanisms for general metrics

Other Social Choice Problems

1. Facility location: Application of metric distortion framework
2. Matching problems: Approximation under ordinal preferences
3. Committee elections: Multi-winner settings

Advantages of This Paper

1. First complete study of randomized distributed mechanisms
2. Nearly all bounds are tight (9/12 tight, 3/12 near-tight)
3. Introduces new tools (Bias Tournament)
4. Covers multiple metric spaces (general, linear, Euclidean)

Conclusions and Discussion

Main Conclusions

1. Nearly complete characterization:
   • 9 of 12 bounds are tight, 3 are near-tight
   • Only det-det avg-avg has significant remaining gap (7 vs 11)
2. Effectiveness of randomization:
   • rand-det achieves tight bounds on all objectives
   • rand-rand further improves avg-avg
   • Simple mechanisms (Random Dictatorship + uniform selection) suffice for optimality
3. Improvements to deterministic mechanisms:
   • Resolves tight bounds for max-avg and max-max
   • avg-max reduced from 11 to 7
4. Methodological contributions:
   • Bias Tournament provides systematic lower bound construction framework
   • Weakened exploitation of Pareto efficiency

Limitations

1. Remaining gaps:
   • det-det avg-avg: 7, 11
   • rand-rand avg-avg: 3-2/n, 3-2/(kn*) (tight only when symmetric)
   • rand-rand avg-max: 3-2/n, 3
2. det-rand mechanism unstudied:
   • Deterministic first stage, randomized second stage
   • Bias Tournament inapplicable to randomized first stage
   • Currently only coarse bounds inherited from rand-rand and det-det
3. Metric space limitations:
   • Some lower bounds require general metrics (graph shortest-path)
   • Euclidean space bounds may be lower
4. Practical considerations:
   • Does not account for strategic behavior (not incentive-compatible)
   • Does not consider communication complexity
   • Does not consider computational complexity

Future Directions

1. det-rand mechanism:
   • Develop new analytical tools
   • May require techniques different from Bias Tournament
2. Tighten remaining gaps:
   • det-det avg-avg
   • rand-rand avg-avg (non-symmetric case)
3. Special metric spaces:
   • Linear metrics: some objectives still unresolved
   • Euclidean: potentially lower bounds
   • Tree metrics: intermediate complexity
4. Extended settings:
   • Committee elections (multi-winner)
   • Cardinal information (access to true distances)
   • Strategic voting (incentive-compatible mechanisms)
5. Computation and communication:
   • Efficient algorithm implementations
   • Communication complexity lower bounds
   • Online/streaming settings

In-Depth Evaluation

Strengths

1. Theoretical depth:
   • 9 of 12 bounds are tight, demonstrating deep problem understanding
   • Diverse and sophisticated proof techniques (Bias Tournament, double summation analysis, probabilistic arguments)
2. Systematicity:
   • Covers 3 mechanism types × 4 objectives = 12 problems
   • Unified framework and notation
   • Clear results comparison (Table 2)
3. Methodological innovation:
   • Bias Tournament: elegantly captures structure of deterministic rules
   • Weakened Pareto efficiency: decouples two-stage dependencies
   • Potentially independent value
4. Writing quality:
   • Clear structure, progressive complexity (simple to complex)
   • Sufficient intuitive explanations and illustrations
   • Complete proof details
5. Completeness:
   • Multiple metric spaces (general, linear, Euclidean)
   • Symmetric and asymmetric instances
   • Byproduct results for centralized voting

Weaknesses

1. det-rand gap:
   • Paper acknowledges this as main open problem
   • Current tools inapplicable, requires new methods
2. Some gaps untightened:
   • det-det avg-avg: 7, 11 still substantial
   • Though authors significantly improved, not completely resolved
3. Limited practical utility:
   • Pure theoretical results, no experimental validation
   • Does not account for real voting system constraints (strategic behavior, computation)
   • Worst-case analysis may be overly pessimistic
4. Metric space dependence:
   • Some lower bounds require complex graph metrics
   • Real-world metric spaces may be more structured
5. Mechanism complexity:
   • Plurality Matching computationally complex (matching problem)
   • Real systems may prefer simpler rules

Impact

1. Theoretical contribution:
   • Nearly completely resolves distributed voting distortion problem
   • Establishes benchmark results for the field
   • Bias Tournament may inspire research on other problems
2. Follow-up research:
   • Study of det-rand mechanisms
   • Distributed versions of other social choice problems
   • Extensions to strategic and computational aspects
3. Practical value:
   • Provides theoretical guidance for distributed voting system design
   • Quantifies performance guarantees of different mechanisms
   • But distance from practical deployment remains
4. Reproducibility:
   • Pure theoretical work, proofs verifiable
   • Constructed instances explicit, easily checked
   • No code or experiments, but does not affect reproducibility

Applicable Scenarios

1. Theoretical research:
   • Social choice theory
   • Algorithmic game theory
   • Approximation algorithms
2. System design:
   • Federal voting systems
   • Multi-level organizational decision-making
   • Distributed consensus protocols
3. Education:
   • Case studies in distortion theory
   • Applications of randomized algorithms
   • Combinatorial optimization techniques
4. Inapplicable scenarios:
   • Real elections requiring incentive compatibility
   • Online systems with computational constraints
   • Non-metric preference spaces

Key References

1. Anshelevich et al. (2022): "The distortion of distributed metric social choice" - Direct predecessor of this paper
2. Gkatzelis et al. (2020): "Resolving the optimal metric distortion conjecture" - Tight bound of 3 for centralized voting
3. Filos-Ratsikas et al. (2020): "The distortion of distributed voting" - Pioneering work on distributed voting
4. Charikar et al. (2024): "Breaking the metric voting distortion barrier" - Recent advances in randomized centralized voting
5. Voudouris (2023): "Tight distortion bounds for distributed metric voting on a line" - Complete resolution for linear metrics

Overall Assessment: This is a high-quality theoretical paper that nearly completely resolves the distributed voting distortion problem, introduces new analytical tools (Bias Tournament), and establishes 9 tight bounds and 3 near-tight bounds. While the det-rand mechanism remains unresolved and some gaps persist, the paper's systematicity, technical depth, and methodological innovation make it a significant contribution to the field. For theoretical researchers, this is essential reading; for practitioners, it provides valuable performance guarantee references.