2025/04/29 by Moses Charikar, Charikar, Moses, Prasanna Ramakrishnan +3 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #Constant (computer programming) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Fraction (chemistry) #Game Theory and Applications #Game Theory and Voting Systems #Logarithm #Nash equilibrium #Probabilistic logic #Simple (philosophy) #Social choice theory
paper · pdf · doi:10.48550/arxiv.2504.20372
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.