{"id":"arxiv/2608.06872","url":"https://arxiv.org/abs/2608.06872","tags":["cs.GT","cs.DM","math.CO"],"score":0,"title":"Pessimal Elections for Approximately Dominating Sets","domain":"cs.GT","source":"arxiv","authors":["Moses Charikar","Prasanna Ramakrishnan","Kangning Wang"],"reviews":0,"subject":"cs.GT","summary":"Condorcet's paradox is a foundational result in social choice theory, showing that no matter which candidate wins an election, a majority of voters may prefer some losing candidate. Worse still, even if the election can choose a committee of $k$ winners, some loser may beat every winner in a majority vote. Recent work showed that this obstruction can be sidestepped by relaxing the majority threshold. For all $\\varepsilon > 0$, any election can select a committee of $O(1/\\varepsilon^2)$ winners such that no loser is preferred to every winner by $\\frac12 + \\varepsilon$ fraction of voters. We…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-07","reactions":{}}