Gregory Kehne

AAAI Conference 2026 Conference Paper

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 explicit utilities for these options, however, using preference rankings may lead to suboptimal outcomes vis-a-vis utilitarian social welfare. Distortion is a measure of this suboptimality, and an extensive literature uses it to develop and analyze voting rules when utilities have minimal structure. However, in many settings, such as common paradigms for value alignment, available options admit a vector representation, and it is natural to suppose that utilities are parametric functions thereof. We undertake the first study of distortion for linear utility functions. Our theoretical contributions are organized into two parts: randomized and deterministic voting rules. We obtain bounds that depend only on dimension of the candidate embedding, and are independent of the numbers of candidates or voters. Additionally, we introduce poly-time instance-optimal algorithms for minimizing distortion given a collection of candidates and votes. We empirically evaluate these in two real-world domains: recommendation systems using collaborative filtering embeddings, and opinion surveys utilizing language model embeddings. Our results benchmark the distortion bounds of several standard rules against our instance-optimal algorithms.

SODA Conference 2025 Conference Paper

A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization

• Shuchi Chawla 0001
• Dimitris Christou
• Trung Dang 0001
• Zhiyi Huang
• Gregory Kehne
• Rojin Rezvan

SODA Conference 2024 Conference Paper

Set Covering with Our Eyes Wide Shut

• Anupam Gupta 0001
• Gregory Kehne
• Roie Levin

AAAI Conference 2023 Conference Paper

Representation with Incomplete Votes

• Daniel Halpern
• Gregory Kehne
• Ariel D. Procaccia
• Jamie Tucker-Foltz
• Manuel Wüthrich

Platforms for online civic participation rely heavily on methods for condensing thousands of comments into a relevant handful, based on whether participants agree or disagree with them. These methods should guarantee fair representation of the participants, as their outcomes may affect the health of the conversation and inform impactful downstream decisions. To that end, we draw on the literature on approval-based committee elections. Our setting is novel in that the approval votes are incomplete since participants will typically not vote on all comments. We prove that this complication renders non-adaptive algorithms impractical in terms of the amount of information they must gather. Therefore, we develop an adaptive algorithm that uses information more efficiently by presenting incoming participants with statements that appear promising based on votes by previous participants. We prove that this method satisfies commonly used notions of fair representation, even when participants only vote on a small fraction of comments. Finally, an empirical evaluation using real data shows that the proposed algorithm provides representative outcomes in practice.

NeurIPS Conference 2023 Conference Paper

The Distortion of Binomial Voting Defies Expectation

• Yannai A. Gonczarowski
• Gregory Kehne
• Ariel D. Procaccia
• Ben Schiffer
• Shirley Zhang

In computational social choice, the distortion of a voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outcome. This concept has been investigated extensively, but only through a worst-case lens. Instead, we study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting, which provides strong distribution-independent guarantees for both expected distortion and expected welfare.

IJCAI Conference 2022 Conference Paper

Can Buyers Reveal for a Better Deal?

• Daniel Halpern
• Gregory Kehne
• Jamie Tucker-Foltz

We study market interactions in which buyers are allowed to credibly reveal partial information about their types to the seller. Previous recent work has studied the special case of one buyer and one good, showing that such communication can simultaneously improve social welfare and ex ante buyer utility. However, with multiple buyers, we find that the buyer-optimal signalling schemes from the one-buyer case are actually harmful to buyer welfare. Moreover, we prove several impossibility results showing that, with either multiple i. i. d. buyers or multiple i. i. d. goods, maximizing buyer utility can be at odds with social efficiency, which is surprising in contrast with the one-buyer, one-good case. Finally, we investigate the computational tractability of implementing desirable equilibrium outcomes. We find that, even with one buyer and one good, optimizing buyer utility is generally NP-hard but tractable in a practical restricted setting.

NeurIPS Conference 2022 Conference Paper

Is Sortition Both Representative and Fair?

• Soroush Ebadian
• Gregory Kehne
• Evi Micha
• Ariel D. Procaccia
• Nisarg Shah

Sortition is a form of democracy built on random selection of representatives. Two of the key arguments in favor of sortition are that it provides representation (a random panel reflects the composition of the population) and fairness (everyone has a chance to participate). Uniformly random selection is perfectly fair, but is it representative? Towards answering this question, we introduce the notion of a representation metric on the space of individuals, and assume that the cost of an individual for a panel is determined by the $q$-th closest representative; the representation of a (random) panel is measured by the ratio between the (expected) sum of costs of the optimal panel for the individuals and that of the given panel. For $k/2 < q \le k-\Omega(k)$, where $k$ is the panel size, we show that uniform random selection is indeed representative by establishing a constant lower bound on this ratio. By contrast, for $q \leq k/2$, no random selection algorithm that is almost fair can give such a guarantee. We therefore consider relaxed fairness guarantees and develop a new random selection algorithm that sheds light on the tradeoff between representation and fairness.

NeurIPS Conference 2022 Conference Paper

Recruitment Strategies That Take a Chance

• Gregory Kehne
• Ariel D. Procaccia
• Jingyan Wang

In academic recruitment settings, including faculty hiring and PhD admissions, committees aim to maximize the overall quality of recruited candidates, but there is uncertainty about whether a candidate would accept an offer if given one. Previous work has considered algorithms that make offers sequentially and are subject to a hard budget constraint. We argue that these modeling choices may be inconsistent with the practice of academic recruitment. Instead, we restrict ourselves to a single batch of offers, and we treat the target number of positions as a soft constraint, so we risk overshooting or undershooting the target. Specifically, our objective is to select a subset of candidates that maximizes the overall expected value associated with candidates who accept, minus an expected penalty for deviating from the target. We first analyze the guarantees provided by natural greedy heuristics, showing their desirable properties despite the simplicity. Depending on the structure of the penalty function, we further develop algorithms that provide fully polynomial-time approximation schemes and constant-factor approximations to this objective. Empirical evaluation of our algorithms corroborates these theoretical results.

AAAI Conference 2022 Conference Paper

Worst-Case Voting When the Stakes Are High

• Anson Kahng
• Gregory Kehne

We study the additive distortion of social choice functions in the implicit utilitarian model, and argue that it is a more appropriate metric than multiplicative distortion when an alternative that confers significant social welfare may exist (i. e. , when the stakes are high). We define a randomized analog of positional scoring rules, and present a rule which is asymptotically optimal within this class as the number of alternatives increases. We then show that the instance-optimal social choice function can be efficiently computed. Next, we take a beyond-worst-case view, bounding the additive distortion of prominent voting rules as a function of the best welfare attainable in an instance. Lastly, we evaluate the additive distortion of a range of rules on real-world election data.

AAAI Conference 2021 Conference Paper

Aggregating Binary Judgments Ranked by Accuracy

• Daniel Halpern
• Gregory Kehne
• Dominik Peters
• Ariel D. Procaccia
• Nisarg Shah
• Piotr Skowron

We revisit the fundamental problem of predicting a binary ground truth based on independent binary judgments provided by experts. When the accuracy levels of the experts are known, the problem can be solved easily through maximum likelihood estimation. We consider, however, a setting in which we are given only a ranking of the experts by their accuracy. Motivated by the worst-case approach to handle the missing information, we consider three objective functions and design efficient algorithms for optimizing them. In particular, the recently popular distortion objective leads to an intuitive new rule. We show that our algorithms perform well empirically using real and synthetic data in collaborative filtering and political prediction domains.

NeurIPS Conference 2021 Conference Paper

Fair Sortition Made Transparent

• Bailey Flanigan
• Gregory Kehne
• Ariel D. Procaccia

Sortition is an age-old democratic paradigm, widely manifested today through the random selection of citizens' assemblies. Recently-deployed algorithms select assemblies \textit{maximally fairly}, meaning that subject to demographic quotas, they give all potential participants as equal a chance as possible of being chosen. While these fairness gains can bolster the legitimacy of citizens' assemblies and facilitate their uptake, existing algorithms remain limited by their lack of transparency. To overcome this hurdle, in this work we focus on panel selection by uniform lottery, which is easy to realize in an observable way. By this approach, the final assembly is selected by uniformly sampling some pre-selected set of $m$ possible assemblies. We provide theoretical guarantees on the fairness attainable via this type of uniform lottery, as compared to the existing maximally fair but opaque algorithms, for two different fairness objectives. We complement these results with experiments on real-world instances that demonstrate the viability of the uniform lottery approach as a method of selecting assemblies both fairly and transparently.

FOCS Conference 2021 Conference Paper

Random Order Online Set Cover is as Easy as Offline

• Anupam Gupta 0001
• Gregory Kehne
• Roie Levin

We give a polynomial-time algorithm for Online-SetCover with a competitive ratio of $O(\log mn)$ when the elements are revealed in random order, matching the best possible offline bound of $O(\log n)$ when the number of sets $m$ is polynomial in the number of elements $n$, and circumventing the $\Omega(\log m \log n)$ lower bound known in adversarial order. We also extend the result to solving pure covering IPs when constraints arrive in random order. The algorithm is a multiplicative-weights-based round-and-solve approach we call LearnOrCover. We maintain a coarse fractional solution that is neither feasible nor monotone increasing, but can nevertheless be rounded online to achieve the claimed guarantee (in the random order model). This gives a new offline algorithm for Setcover that performs a single pass through the elements, which may be of independent interest.

ICML Conference 2020 Conference Paper

Strategyproof Mean Estimation from Multiple-Choice Questions

• Anson Kahng
• Gregory Kehne
• Ariel D. Procaccia

Given n values possessed by n agents, we study the problem of estimating the mean by truthfully eliciting agents’ answers to multiple-choice questions about their values. We consider two natural candidates for estimation error: mean squared error (MSE) and mean absolute error (MAE). We design a randomized estimator which is asymptotically optimal for both measures in the worst case. In the case where prior distributions over the agents’ values are known, we give an optimal, polynomial-time algorithm for MSE, and show that the task of computing an optimal estimate for MAE is #P-hard. Finally, we demonstrate empirically that knowledge of prior distributions gives a significant edge.