Lune

SODA2026Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic NumberRomain Bourneuf, Pierre Charbit, Stéphan ThomasséFOCS 2025 · 13 citations
  2. A Few Good ChoicesHaoyu Song, Thành Nguyen, Young-San LinSODA 2026

Builds on9

  1. A Minimaximalist Approach to Reinforcement Learning from Human FeedbackGokul Swamy, Christoph Dann, Rahul Kidambi, Steven Wu et al.ICML 2024 · 147 citations
  2. REBEL: Reinforcement Learning via Regressing Relative RewardsZhaolin Gao, Jonathan D. Chang, Wenhao Zhan, Owen Oertell et al.NeurIPS 2024 · 82 citations
  3. Axioms for AI Alignment from Human FeedbackLuise Ge, Daniel Halpern, Evi Micha, Ariel D. Procaccia et al.NeurIPS 2024 · 64 citations
  4. Approximately stable committee selectionZhihao Jiang, Kamesh Munagala, Kangning WangSTOC 2020 · 29 citations
  5. 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

  1. Six Candidates Suffice to Win a Voter MajorityMoses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta et al.STOC 2025 · 1 citation
  2. On Condorcet's Jury Theorem with AbstentionReshef Meir, Ganesh GhalmeAAAI 2026
  3. Breaking the Metric Voting Distortion BarrierMoses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun WuSODA 2024 · 10 citations
  4. Preserving Condorcet Winners under Strategic ManipulationSirin Botan, Ulle EndrissAAAI 2021 · 2 citations
  5. Comparing Election Methods Where Each Voter Ranks Only Few CandidatesMatthias Bentert, Piotr SkowronAAAI 2020 · 21 citations
Dusk over the sea between two cliffs drawn in fine vertical lines