11 papers
Pessimal Elections for Approximately Dominating Sets
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
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…
An Exposition of Five Candidates Suffice for a Majority
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
We give a brief exposition of a result of Song, Nguyen, and Lin (2026) that every election (with ranked preferences) has a Condorcet winning set of at most five candidates.
Additively Competitive Secretaries
Mohammad Mahdian, Jieming Mao, Enze Sun +2
In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes…
Distortion of Metric Voting with Bounded Randomness
Ziyi Cai, D. D. Gao, Prasanna Ramakrishnan +1
We study the design of voting rules in the metric distortion framework. It is known that any deterministic rule suffers distortion of at least , and that randomized rules can ac…
Winning in the Limit: Average-Case Committee Selection with Many Candidates
Yifan Lin, Shenyu Qin, Kangning Wang +1
We study the committee selection problem in the canonical impartial culture model with a large number of voters and an even larger candidate set. Here, each voter independently rep…
Strategyproof Tournament Rules for Teams with a Constant Degree of Selfishness
David Pennock, Daniel Schoepflin, Kangning Wang
We revisit the well-studied problem of designing fair and manipulation-resistant tournament rules. In this problem, we seek a mechanism that (probabilistically) identifies the winn…