Abstract
We investigate the two-winner election problem with the goal of minimizing social cost. We focus on strategy-proof mechanisms where each voter reports only a single favorite candidate. In our model, candidates and voters are located in a Euclidean space where candidate locations are known to the mechanism. The quality of a mechanism is measured by its distortion—the worst-case ratio between the social cost of the mechanism's selection and the optimal selection. We identify that the ratio between the maximum and minimum distances among candidates ($\sigma$) is a critical factor in determining distortion. While the three-candidate case is largely understood, we focus on scenarios with four or more candidates, establishing lower bounds in 1D space and tight bounds in spaces of 3D or higher.
Introduction
In social choice theory, the "distortion" of a voting rule quantifies the efficiency lost due to limited information. When voters and candidates are embedded in a metric space, the social cost is typically defined as the sum of distances from each voter to their nearest winner in the selected committee. A significant challenge arises when voters only provide their single favorite candidate (plurality-style ballots). In such "black box" scenarios, previous research indicated that distortion could be infinite because the relative distances between candidates are unknown to the mechanism.
This paper addresses this gap by introducing the parameter $\sigma$: the ratio of the maximum distance to the minimum distance between any two candidates. By incorporating this geometric constraint, we can derive concrete bounds on distortion for multi-winner elections.
The Role of Candidate Spread ($\sigma$)
The introduction of $\sigma$ allows for a nuanced analysis of how candidate positioning affects election quality. The paper demonstrates that distortion is fundamentally linear in $\sigma$. If candidates are roughly equidistant ($\sigma \approx 1$), the election is inherently more efficient. However, as $\sigma$ increases—indicating a wide disparity in candidate spacing—the potential for high distortion grows. This parameter provides the first framework to quantify how the "spread" of candidates affects the quality of the election outcome.
Mechanism Analysis and Strategyproofness
The research evaluates three primary classes of mechanisms:
- General Mechanisms: Any rule mapping vote counts to a committee.
- Single Non-Transferable Vote (SNTV): A simple greedy approach selecting the $w$ candidates with the highest vote totals.
- Strategyproof Mechanisms: Rules where voters cannot benefit from misrepresenting their preferences. A key example is the Random Sequential Dictator (RSD), where voters are selected at random and their favorite candidates are added to the committee until it is full.
A major theoretical contribution is the proof that any truthful (strategyproof) mechanism must satisfy the Independence of Irrelevant Candidates (IIC). This implies that the probability of a specific committee winning should depend solely on the votes its members received, rather than the distribution of votes among losing candidates.
Key Results and the Price of Truthfulness
The study reveals a significant "price of truthfulness." While the simple SNTV mechanism achieves a distortion bound of approximately $1 + 2\sigma$, strategyproof mechanisms like RSD for two-winner elections ($w=2$) result in a higher distortion of $1 + 4\sigma$.
Furthermore, the authors establish a "no-go" theorem regarding anonymity and determinism. They prove that no deterministic, anonymous, and strategyproof mechanism can achieve finite distortion. To maintain finite distortion while remaining strategyproof, a mechanism must either incorporate randomization (like RSD) or sacrifice anonymity (treating voters differently).
Specific bounds established include:
- Universal Lower Bound: No randomized mechanism can achieve a distortion better than $1 + \frac{w-1}{w+1}(\sigma - 1)$.
- SNTV Performance: The common SNTV mechanism is surprisingly robust, with an upper bound distortion of $1 + 2\sigma$.
- Deterministic Sequential Dictator: By dropping the requirement that all voters be treated equally (anonymity), a sequential dictator can achieve a distortion of $2(n-w)\sigma + 1$, where $n$ is the number of voters.
Conclusion and Future Directions
This work provides the first comprehensive bounds for distortion in multi-winner elections using single-candidate ballots by leveraging the $\sigma$ parameter. While the two-winner case is now well-characterized, the general $w$-winner case for strategyproof mechanisms remains an open area for complex analysis. Future research may explore whether providing "top-$k$" ballots or using ranked preferences can significantly mitigate distortion, or how these results shift when the objective changes from minimizing total social cost to minimizing the maximum individual dissatisfaction.
Summary updated