{"ID":2891551,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.17981","arxiv_id":"2507.17981","title":"$k$-Approval Veto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection","abstract":"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 $α\u003c k/(k+1)$. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of $k$.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2507.17981","url_pdf":"https://arxiv.org/pdf/2507.17981v1","authors":"[\"Fatih Erdem Kizilkaya\",\"David Kempe\"]","published":"2025-07-23T23:04:16Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}