4 citations · 7 across the 10 of their papers we have counts for
6 papers · 1 filter
Pareto Inefficiency of EFX
Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX)…
Optimal Shallow Circuits for Majority
Victor Lecomte, Prasanna Ramakrishnan
Four decades on, Håstad's classical lower bound for depth- circuits computing Parity remains the best known circuit lower bound for any expl…
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…
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.
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…