1 citations · 1 across the 13 of their papers we have counts for
7 papers · 1 filter
Stable Voting Rules on the Edge of Optimal Metric Distortion
Ziyi Cai, Moses Charikar, Jabari Hastings +3
We prove the existence of a randomized voting rule with metric distortion at most , within of the lower bound of . Our rule comes from a generalization of…
Online Matching in Convex Bipartite Graphs
Yilong Feng, Zhihao Gavin Tang, Kangning Wang +1
Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where ea…
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…
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…
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…