Lune

SODA2026Top-tier venue

A Few Good Choices

Haoyu Song, Thành Nguyen, Young-San Lin

Abstract

A Condorcet winning set addresses the Condorcet paradox by selecting a few candidates-rather than a single winner-such that no unselected alternative is preferred to all of them by a majority of voters. This idea extends to α-undominated sets, which ensure the same property for any α-fraction of voters and are guaranteed to exist in constant size for any α. However, the requirement that an outsider be preferred to every member of the set can be overly restrictive and difficult to justify in many applications. Motivated by this, we introduce a more flexible notion: (t, α)-undominated sets. Here, each voter compares an outsider to their t-th most preferred member of the set, and the set is undominated if no outsider is preferred by more than an α-fraction of voters. This framework subsumes prior definitions, recovering Condorcet winning sets when (t = 1, α = 1/2) and α-undominated sets when t = 1, and introduces a new, tunable notion of collective acceptability for t > 1. We establish three main results:

• We prove that a (t, α)-undominated set of size O(t/α) exists for all values of t and α.

• We show that as t becomes large, the minimum size of such a set approaches t/α, which is asymptotically optimal.

• In the special case t = 1, we improve the bound on the size of an α-undominated set given by Charikar et al. (2025a). As a consequence, we show that a Condorcet winning set of five candidates exists, improving their bound of six.

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.

4 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

  • Six Candidates Suffice to Win a Voter Majority cites Approximately stable committee selection
  • Pluralistic Leaderboards cites Six Candidates Suffice to Win a Voter Majority
  • Pluralistic Leaderboards cites Approximately stable committee selection
  • Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling cites Six Candidates Suffice to Win a Voter Majority
  • Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling cites Approximately stable committee selection
  • A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number cites Six Candidates Suffice to Win a Voter Majority
  • A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number cites Approximately Dominating Sets in Elections
  • Approximately Dominating Sets in Elections cites A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
  • Approximately Dominating Sets in Elections cites Six Candidates Suffice to Win a Voter Majority
  • Approximately Dominating Sets in Elections cites Approximately stable committee selection
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Fisher Meets Lindahl: A Unified Duality Framework for Market EquilibriumYixin Tao, Weiqiang ZhengSTOC 2026 · 2 citations
  2. Pluralistic LeaderboardsNika Haghtalab, Ariel Procaccia, Han Shao, Serena Wang et al.ICML 2026
  3. Asymptotic Universal Alignment: A New Alignment Framework via Test-Time ScalingYang Cai, Weiqiang ZhengICML 2026
  4. Approximately Dominating Sets in ElectionsMoses Charikar, Prasanna Ramakrishnan, Kangning WangSODA 2026

Builds on4

  1. Approximately stable committee selectionZhihao Jiang, Kamesh Munagala, Kangning WangSTOC 2020 · 29 citations
  2. A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic NumberRomain Bourneuf, Pierre Charbit, Stéphan ThomasséFOCS 2025 · 13 citations
  3. Six Candidates Suffice to Win a Voter MajorityMoses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta et al.STOC 2025 · 1 citation
  4. Approximately Dominating Sets in ElectionsMoses Charikar, Prasanna Ramakrishnan, Kangning WangSODA 2026

Related papers

  1. Maintaining Proportional Committees with Dynamic Candidate SetsChris Dong, Jannik PetersICML 2025
  2. Resolving the Optimal Metric Distortion ConjectureVasilis Gkatzelis, Daniel Halpern, Nisarg ShahFOCS 2020 · 44 citations
  3. On Swap Convexity of Voting RulesSvetlana Obraztsova, Edith Elkind, Piotr FaliszewskiAAAI 2020 · 4 citations
  4. The Smoothed Possibility of Social ChoiceLirong XiaNeurIPS 2020 · 36 citations
  5. Representative Proxy VotingElliot Anshelevich, Zack Fitzsimmons, Rohit Vaish, Lirong XiaAAAI 2021 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines