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.
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:
- 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.
- Serial Dictatorship (Position Preferences): When only candidate-to-position fitness rankings are known, positions take turns selecting their "best" available candidate.
- 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.
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