Metric Distortion of Line-up Elections: The Right Person for the Right Job

Christopher Jerrett, Yue Han, Elliot AnshelevichAAAI 2025 · DOI

Introduction

Traditional social choice theory often focuses on selecting a single "best" candidate or a fixed-size committee. However, many real-world scenarios require matching candidates to specific roles—such as assigning individuals to a sports team's positions or a corporate board's specialized committees. This paper introduces the framework of line-up elections, where candidates are not merely selected but are matched to distinct positions.

Structure of a line-up election involving voters (V), candidates (S), and positions (P).

The authors employ a spatial model where voters, candidates, and positions all reside in a shared metric space. The objective is to minimize the Social Cost, defined as the sum of distances from voters to their assigned candidates plus the distances from those candidates to their assigned positions. The primary challenge lies in the fact that exact metric distances are rarely known; instead, mechanisms must operate on ordinal information, such as voter preference rankings or candidate fitness for specific roles.

Methodology

The researchers analyze distortion—the worst-case ratio between the social cost of a mechanism using limited information and the absolute mathematical optimum—across several information settings:

  1. Iterative Election (Voter Preferences): To fill $\ell$ positions, the mechanism conducts $\ell$ consecutive single-winner elections. In each round, a candidate is selected for a position using a standard rule (e.g., Plurality Veto) and then removed from the pool.
  2. Serial Dictatorship (Position Preferences): When only candidate-to-position fitness rankings are known, positions take turns selecting their "best" available candidate.
  3. Location-Based Matching: If exact coordinates for candidates and positions are known but voter data is absent, the mechanism finds a matching that minimizes candidate-to-position distances.

The core theoretical contribution involves "charging arguments"—mathematical proofs that establish upper and lower bounds on distortion for any possible metric space.

Key Insights

  • The Primacy of Roles: Interestingly, knowing how candidates fit specific positions (fitness) is often more valuable than knowing voter preferences. Rankings based on position fitness yield a distortion bound of 5, compared to 7 for voter rankings.
  • The "Stuck" Principle: In "perfect matching" scenarios where the number of candidates equals the number of positions ($m = \ell$), distortion is capped at 3 regardless of the specific matching. This occurs because voters are essentially "stuck" with the entire candidate pool; the mechanism only determines the internal assignment.
  • Synergy in Optimization: Simultaneous optimization for voter preference and candidate fitness outperforms decoupled approaches (selection followed by matching).
  • Metric Space Necessity: The constant distortion bounds depend on all entities sharing a single metric space. If preferences and fitness were measured in unrelated spaces, distortion would increase exponentially.

Key Results

The paper provides a comprehensive "menu" of distortion bounds based on available information and election parameters $(m, \ell)$, where $m$ is the number of candidates and $\ell$ is the number of positions.

Summary of distortion bounds across different information settings and election parameters.

Notably, for $(m, m)$ elections (where every candidate is assigned a position), the authors achieved a distortion of $3 - \frac{1}{2^{m-2}}$, demonstrating that distortion can actually improve slightly as the candidate pool grows.

Discussion and Future Work

While this work establishes strong deterministic bounds, several avenues for future research remain. The current focus on deterministic mechanisms leaves open the possibility that randomized mechanisms could achieve even lower distortion. Additionally, the assumption of a common metric space, while suitable for physical distribution networks, may be more complex to justify in abstract ideological spaces where "fitness" and "preference" might operate on different scales. Future work could also explore more complex, multi-layered election structures.

Summary updated

BibTeX
@inproceedings{jerrett2025metric,
  author = {Christopher Jerrett and Yue Han and Elliot Anshelevich},
  title = {{Metric Distortion of Line-up Elections: The Right Person for the Right Job}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33526},
}
Figure