6 papers
Improved Parallel Algorithms for EF1 Allocations
Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang +1
Allocating indivisible goods among agents is a fundamental task in fair division. Recent work of Garg and Psomas [AAMAS 2025] initiated the study of parallel algorithms for…
Linear Social Choice with Few Queries: A Moment-Based Approach
Luise Ge, Daniel Halpern, Gregory Kehne +1
Most social choice rules assume access to full rankings, while current alignment practice -- despite aiming for diversity -- typically treats voters as anonymous and comparisons as…
Prophet and Secretary at the Same Time
Gregory Kehne, Thomas Kesselheim
Many online problems are studied in stochastic settings for which inputs are samples from a known distribution, given in advance, or from an unknown distribution. Such distribution…
Optimized Distortion in Linear Social Choice
Luise Ge, Gregory Kehne, Yevgeniy Vorobeychik
Social choice theory offers a wealth of approaches for selecting a candidate on behalf of voters based on their reported preference rankings over options. When voters have underlyi…
Robust Committee Voting, or The Other Side of Representation
Gregory Kehne, Ulrike Schmidt-Kraepelin, Krzysztof Sornat
We study approval-based committee voting from a novel perspective. While extant work largely centers around proportional representation of the voters, we shift our focus to the can…
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Shuchi Chawla, Dimitris Christou, Trung Dang +3
We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal re…