Approximately Dominating Sets in Elections
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
Abstract
Condorcet's paradox is a fundamental result in social choice theory which states that there exist elections in which, no matter which candidate wins, a majority of voters prefer a different candidate. In fact, even if we can select any k winners, there still may exist another candidate that would beat each of the winners in a majority vote. That is, elections may require arbitrarily large dominating sets.
We show that approximately dominating sets of constant size always exist. In particular, for every ε > 0, every election (irrespective of the number of voters or candidates) can select O( 1ε 2 ) winners such that no other candidate beats each of the winners by a margin of more than ε fraction of voters.
Our proof uses a simple probabilistic construction using samples from a maximal lottery, a well-studied distribution over candidates derived from the Nash equilibrium of a two-player game. In stark contrast to general approximate equilibria, which may require support logarithmic in the number of pure strategies, we show that maximal lotteries can be approximated with constant support size. These approximate maximal lotteries may be of independent interest.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Axioms for AI Alignment from Human Feedback cites A Minimaximalist Approach to Reinforcement Learning from Human Feedback
- REBEL: Reinforcement Learning via Regressing Relative Rewards cites A Minimaximalist Approach to Reinforcement Learning from Human Feedback
- A Few Good Choices cites Approximately stable committee selection
- A Few Good Choices cites A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Cited by top-tier papers2
Builds on9
- A Minimaximalist Approach to Reinforcement Learning from Human FeedbackGokul Swamy, Christoph Dann, Rahul Kidambi, Steven Wu et al.ICML 2024 · 147 citations
- REBEL: Reinforcement Learning via Regressing Relative RewardsZhaolin Gao, Jonathan D. Chang, Wenhao Zhan, Owen Oertell et al.NeurIPS 2024 · 82 citations
- Axioms for AI Alignment from Human FeedbackLuise Ge, Daniel Halpern, Evi Micha, Ariel D. Procaccia et al.NeurIPS 2024 · 64 citations
- Approximately stable committee selectionZhihao Jiang, Kamesh Munagala, Kangning WangSTOC 2020 · 29 citations
- A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic NumberRomain Bourneuf, Pierre Charbit, Stéphan ThomasséFOCS 2025 · 13 citations
Related papers
- Six Candidates Suffice to Win a Voter MajorityMoses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta et al.STOC 2025 · 1 citation
- On Condorcet's Jury Theorem with AbstentionReshef Meir, Ganesh GhalmeAAAI 2026
- Breaking the Metric Voting Distortion BarrierMoses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun WuSODA 2024 · 10 citations
- Preserving Condorcet Winners under Strategic ManipulationSirin Botan, Ulle EndrissAAAI 2021 · 2 citations
- Comparing Election Methods Where Each Voter Ranks Only Few CandidatesMatthias Bentert, Piotr SkowronAAAI 2020 · 21 citations
