Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.17981 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908463895937024 |
|---|---|
| author | Kizilkaya, Fatih Erdem Kempe, David |
| author_facet | Kizilkaya, Fatih Erdem Kempe, David |
| contents | In the context of single-winner ranked-choice elections between $m$ candidates, we explore the tradeoff between two competing goals in every democratic system: the majority principle (maximizing the social welfare) and the minority principle (safeguarding minority groups from overly bad outcomes).To measure the social welfare, we use the well-established framework of metric distortion subject to various objectives: utilitarian (i.e., total cost), $α$-percentile (e.g., median cost for $α= 1/2$), and egalitarian (i.e., max cost). To measure the protection of minorities, we introduce the $\ell$-mutual minority criterion, which requires that if a sufficiently large (parametrized by $\ell$) coalition $T$ of voters ranks all candidates in $S$ lower than all other candidates, then none of the candidates in $S$ should win. The highest $\ell$ for which the criterion is satisfied provides a well-defined measure of mutual minority protection (ranging from 1 to $m$).
Our main contribution is the analysis of a recently proposed class of voting rules called $k$-Approval Veto, offering a comprehensive range of trade-offs between the two principles. This class spans between Plurality Veto (for $k=1$) - a simple voting rule achieving optimal metric distortion - and Vote By Veto (for $k=m$) which picks a candidate from the proportional veto core. We show that $k$-Approval Veto has minority protection at least $k$, and thus, it accommodates any desired level of minority protection. However, this comes at the price of lower social welfare. For the utilitarian objective, the metric distortion increases linearly in $k$. For the $α$-percentile objective, the metric distortion is the optimal value of 5 for $α\ge k/(k+1)$ and unbounded for $α< k/(k+1)$. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17981 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $k$-Approval Veto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection Kizilkaya, Fatih Erdem Kempe, David Computer Science and Game Theory In the context of single-winner ranked-choice elections between $m$ candidates, we explore the tradeoff between two competing goals in every democratic system: the majority principle (maximizing the social welfare) and the minority principle (safeguarding minority groups from overly bad outcomes).To measure the social welfare, we use the well-established framework of metric distortion subject to various objectives: utilitarian (i.e., total cost), $α$-percentile (e.g., median cost for $α= 1/2$), and egalitarian (i.e., max cost). To measure the protection of minorities, we introduce the $\ell$-mutual minority criterion, which requires that if a sufficiently large (parametrized by $\ell$) coalition $T$ of voters ranks all candidates in $S$ lower than all other candidates, then none of the candidates in $S$ should win. The highest $\ell$ for which the criterion is satisfied provides a well-defined measure of mutual minority protection (ranging from 1 to $m$). Our main contribution is the analysis of a recently proposed class of voting rules called $k$-Approval Veto, offering a comprehensive range of trade-offs between the two principles. This class spans between Plurality Veto (for $k=1$) - a simple voting rule achieving optimal metric distortion - and Vote By Veto (for $k=m$) which picks a candidate from the proportional veto core. We show that $k$-Approval Veto has minority protection at least $k$, and thus, it accommodates any desired level of minority protection. However, this comes at the price of lower social welfare. For the utilitarian objective, the metric distortion increases linearly in $k$. For the $α$-percentile objective, the metric distortion is the optimal value of 5 for $α\ge k/(k+1)$ and unbounded for $α< k/(k+1)$. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of $k$. |
| title | $k$-Approval Veto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.17981 |