1 citations · 1 across the 13 of their papers we have counts for
14 papers
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…
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…
A Geometric Analysis of Gains from Trade
Jason Hartline, Kangning Wang
We provide a geometric proof that the random proposer mechanism is a -approximation to the first-best gains from trade in bilateral exchange. We then refine this geometric analy…
Metric Distortion for Tournament Voting and Beyond
Moses Charikar, Prasanna Ramakrishnan, Zihan Tan +1
In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that se…
Approximately Dominating Sets in Elections
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
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…
Approximately Efficient Bilateral Trade with Samples
Yuan Deng, Jieming Mao, Balasubramanian Sivan +2
We study the social efficiency of bilateral trade between a seller and a buyer. In the classical Bayesian setting, the celebrated Myerson-Satterthwaite impossibility theorem states…
Six Candidates Suffice to Win a Voter Majority
Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan +2
A cornerstone of social choice theory is Condorcet's paradox which says that in an election where voters rank candidates it is possible that, no matter which candidate is d…
An Lower Bound for Online Matching on the Line
Kangning Wang
For online matching with the line metric, we present a lower bound of on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous…