Ariel Procaccia

NeurIPS Conference 2025 Conference Paper

Direct Alignment with Heterogeneous Preferences

• Ali Shirali
• Arash Nasr-Esfahany
• Abdullah Alomar
• Parsa Mirtaheri
• Rediet Abebe
• Ariel Procaccia

Alignment with human preferences is commonly framed using a universal reward function, even though human preferences are inherently heterogeneous. We formalize this heterogeneity by introducing user types and examine the limits of the homogeneity assumption. We show that aligning to heterogeneous preferences with a single policy is best achieved using the average reward across user types. However, this requires additional information about annotators. We examine improvements under different information settings, focusing on direct alignment methods. We find that minimal information can yield first-order improvements, while full feedback from each user type leads to consistent learning of the optimal policy. Surprisingly, however, no sample-efficient consistent direct loss exists in this latter setting. These results reveal a fundamental tension between consistency and sample efficiency in direct policy alignment.

NeurIPS Conference 2025 Conference Paper

Does Representation Guarantee Welfare?

• Jakob de Raaij
• Ariel Procaccia
• Alexandros Psomas

A panel satisfies descriptive representation when its composition reflects the population. We examine the role of descriptive representation in collective decision making through an optimization lens, asking whether representative panels make decisions that maximize social welfare for the underlying population. Our main results suggest that, in general, representation with respect to intersections of two or more features guarantees higher social welfare than that achieved by the status quo of proportionally representing individual features. Moreover, an analysis of real data suggests that representation with respect to pairs of features is feasible in practice. These results have significant implications for the design of citizens' assemblies, which are gaining prominence in AI governance.

NeurIPS Conference 2025 Conference Paper

Metritocracy: Representative Metrics for Lite Benchmarks

• Ariel Procaccia
• Ben Schiffer
• Serena Wang
• Shirley Zhang

A common problem in LLM evaluation is how to choose a subset of metrics from a full suite of possible metrics. Subset selection is usually done for efficiency or interpretability reasons, and the goal is often to select a "representative" subset of metrics. However, "representative" is rarely clearly defined. In this work, we use ideas from social choice theory to formalize two notions of representation for the selection of a subset of evaluation metrics. We first introduce positional representation, which guarantees every alternative is sufficiently represented at every position cutoff. We then introduce positional proportionality, which guarantees no alternative is proportionally over- or under-represented by more than a small error at any position. We prove upper and lower bounds on the smallest number of metrics needed to guarantee either of these properties in the worst case. We also study a generalized form of each property that allows for additional input on groups of metrics that must be represented. Finally, we tie theory to practice through real-world case studies on both LLM evaluation and hospital quality evaluation.

NeurIPS Conference 2025 Conference Paper

Pairwise Calibrated Rewards for Pluralistic Alignment

• Daniel Halpern
• Evi Micha
• Ariel Procaccia
• Itai Shapira

Current alignment pipelines presume a single, universal notion of desirable behavior. However, human preferences often diverge across users, contexts, and cultures. As a result, disagreement collapses into the majority signal and minority perspectives are discounted. To address this, we propose reflecting diverse human preferences through a distribution over multiple reward functions, each inducing a distinct aligned policy. The distribution is learned directly from pairwise preference without annotator identifiers or predefined groups. Instead, annotator disagreements are treated as informative soft labels. Our central criterion is \emph{pairwise calibration}: for every pair of candidate responses, the proportion of reward functions preferring one response matches the fraction of annotators with that preference. We prove that even a small outlier-free ensemble can accurately represent diverse preference distributions. Empirically, we introduce and validate a practical training heuristic to learn such ensembles, and demonstrate its effectiveness through improved calibration, implying a more faithful representation of pluralistic values.

JAIR Journal 2021 Journal Article

Loss Functions, Axioms, and Peer Review

• Ritesh Noothigattu
• Nihar Shah
• Ariel Procaccia

It is common to see a handful of reviewers reject a highly novel paper, because they view, say, extensive experiments as far more important than novelty, whereas the community as a whole would have embraced the paper. More generally, the disparate mapping of criteria scores to final recommendations by different reviewers is a major source of inconsistency in peer review. In this paper we present a framework inspired by empirical risk minimization (ERM) for learning the community's aggregate mapping. The key challenge that arises is the specification of a loss function for ERM. We consider the class of L(p,q) loss functions, which is a matrix-extension of the standard class of Lp losses on vectors; here the choice of the loss function amounts to choosing the hyperparameters p and q. To deal with the absence of ground truth in our problem, we instead draw on computational social choice to identify desirable values of the hyperparameters p and q. Specifically, we characterize p=q=1 as the only choice of these hyperparameters that satisfies three natural axiomatic properties. Finally, we implement and apply our approach to reviews from IJCAI 2017.

AAAI Conference 2020 Conference Paper

HirePeer: Impartial Peer-Assessed Hiring at Scale in Expert Crowdsourcing Markets

• Yasmine Kotturi
• Anson Kahng
• Ariel Procaccia
• Chinmay Kulkarni

Expert crowdsourcing (e. g. , Upwork. com) provides promising benefits such as productivity improvements for employers, and flexible working arrangements for workers. Yet to realize these benefits, a key persistent challenge is effective hiring at scale. Current approaches, such as reputation systems and standardized competency tests, develop weaknesses such as score inflation over time, thus degrading market quality. This paper presents HirePeer, a novel alternative approach to hiring at scale that leverages peer assessment to elicit honest assessments of fellow workers’ job application materials, which it then aggregates using an impartial ranking algorithm. This paper reports on three studies that investigate both the costs and the benefits to workers and employers of impartial peer-assessed hiring. We find, to solicit honest assessments, algorithms must be communicated in terms of their impartial effects. Second, in practice, peer assessment is highly accurate, and impartial rank aggregation algorithms incur a small accuracy cost for their impartiality guarantee. Third, workers report finding peer-assessed hiring useful for receiving targeted feedback on their job materials.

AAAI Conference 2020 Conference Paper

Multiagent Evaluation Mechanisms

• Tal Alon
• Magdalen Dobson
• Ariel Procaccia
• Inbal Talgam-Cohen
• Jamie Tucker-Foltz

We consider settings where agents are evaluated based on observed features, and assume they seek to achieve feature values that bring about good evaluations. Our goal is to craft evaluation mechanisms that incentivize the agents to invest effort in desirable actions; a notable application is the design of course grading schemes. Previous work has studied this problem in the case of a single agent. By contrast, we investigate the general, multi-agent model, and provide a complete characterization of its computational complexity.

NeurIPS Conference 2019 Conference Paper

Efficient and Thrifty Voting by Any Means Necessary

• Debmalya Mandal
• Ariel Procaccia
• Nisarg Shah
• David Woodruff

We take an unorthodox view of voting by expanding the design space to include both the elicitation rule, whereby voters map their (cardinal) preferences to votes, and the aggregation rule, which transforms the reported votes into collective decisions. Intuitively, there is a tradeoff between the communication requirements of the elicitation rule (i. e. , the number of bits of information that voters need to provide about their preferences) and the efficiency of the outcome of the aggregation rule, which we measure through distortion (i. e. , how well the utilitarian social welfare of the outcome approximates the maximum social welfare in the worst case). Our results chart the Pareto frontier of the communication-distortion tradeoff.

NeurIPS Conference 2019 Conference Paper

Envy-Free Classification

• Maria-Florina Balcan
• Travis Dick
• Ritesh Noothigattu
• Ariel Procaccia

In classic fair division problems such as cake cutting and rent division, envy-freeness requires that each individual (weakly) prefer his allocation to anyone else's. On a conceptual level, we argue that envy-freeness also provides a compelling notion of fairness for classification tasks, especially when individuals have heterogeneous preferences. Our technical focus is the generalizability of envy-free classification, i. e. , understanding whether a classifier that is envy free on a sample would be almost envy free with respect to the underlying distribution with high probability. Our main result establishes that a small sample is sufficient to achieve such guarantees, when the classifier in question is a mixture of deterministic classifiers that belong to a family of low Natarajan dimension.

NeurIPS Conference 2019 Conference Paper

Paradoxes in Fair Machine Learning

• Paul Goelz
• Anson Kahng
• Ariel Procaccia

Equalized odds is a statistical notion of fairness in machine learning that ensures that classification algorithms do not discriminate against protected groups. We extend equalized odds to the setting of cardinality-constrained fair classification, where we have a bounded amount of a resource to distribute. This setting coincides with classic fair division problems, which allows us to apply concepts from that literature in parallel to equalized odds. In particular, we consider the axioms of resource monotonicity, consistency, and population monotonicity, all three of which relate different allocation instances to prevent paradoxes. Using a geometric characterization of equalized odds, we examine the compatibility of equalized odds with these axioms. We empirically evaluate the cost of allocation rules that satisfy both equalized odds and axioms of fair division on a dataset of FICO credit scores.

AAAI Conference 2018 Conference Paper

A Voting-Based System for Ethical Decision Making

• Ritesh Noothigattu
• Snehalkumar Gaikwad
• Edmond Awad
• Sohan Dsouza
• Iyad Rahwan
• Pradeep Ravikumar
• Ariel Procaccia

We present a general approach to automating ethical decisions, drawing on machine learning and computational social choice. In a nutshell, we propose to learn a model of societal preferences, and, when faced with a specific ethical dilemma at runtime, efficiently aggregate those preferences to identify a desirable choice. We provide a concrete algorithm that instantiates our approach; some of its crucial steps are informed by a new theory of swap-dominance efficient voting rules. Finally, we implement and evaluate a system for ethical decision making in the autonomous vehicle domain, using preference data collected from 1. 3 million people through the Moral Machine website.

AAAI Conference 2018 Conference Paper

Approximation-Variance Tradeoffs in Facility Location Games

• Ariel Procaccia
• David Wajc
• Hanrui Zhang

We revisit the well-studied problem of constructing strategyproof approximation mechanisms for facility location games, but offer a fundamentally new perspective by considering risk averse designers. Specifically, we are interested in the tradeoff between a randomized strategyproof mechanism’s approximation ratio, and its variance (which has long served as a proxy for risk). When there is just one facility, we observe that the social cost objective is trivial, and derive the optimal tradeoff with respect to the maximum cost objective. When there are multiple facilities, the main challenge is the social cost objective, and we establish a surprising impossibility result: under mild assumptions, no smooth approximation-variance tradeoff exists. We also discuss the implications of our work for computational mechanism design at large.

AAAI Conference 2018 Conference Paper

Fair Rent Division on a Budget

• Ariel Procaccia
• Rodrigo Velez
• Dingli Yu

The standard approach to fair rent division assumes that agents have quasi-linear utilities, and seeks allocations that are envy free; it underlies an algorithm that is widely used in practice. However, this approach does not take budget constraints into account, and, therefore, may assign agents to rooms they cannot afford. By contrast, we design a polynomial-time algorithm that takes budget constraints as part of its input; it determines whether there exist envy-free allocations that satisfy the budget constraints, and, if so, computes one that optimizes an additional criterion of justice. In particular, this gives a polynomial-time implementation of the budget-constrained maximin solution, where the maximization objective is the minimum utility of any agent. We show that, like its non-budget-constrained counterpart, this solution is unique in terms of utilities (when it exists), and satisfies additional desirable properties.

AAAI Conference 2018 Conference Paper

Liquid Democracy: An Algorithmic Perspective

• Anson Kahng
• Simon Mackenzie
• Ariel Procaccia

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a nonlocal delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

AAAI Conference 2018 Conference Paper

Ranking Wily People Who Rank Each Other

• Anson Kahng
• Yasmine Kotturi
• Chinmay Kulkarni
• David Kurokawa
• Ariel Procaccia

We study rank aggregation algorithms that take as input the opinions of players over their peers, represented as rankings, and output a social ordering of the players (which reflects, e. g. , relative contribution to a project or fit for a job). To prevent strategic behavior, these algorithms must be impartial, i. e. , players should not be able to influence their own position in the output ranking. We design several randomized algorithms that are impartial and closely emulate given (nonimpartial) rank aggregation rules in a rigorous sense. Experimental results further support the efficacy and practicability of our algorithms.

AAAI Conference 2018 Conference Paper

Weighted Voting Via No-Regret Learning

• Nika Haghtalab
• Ritesh Noothigattu
• Ariel Procaccia

Voting systems typically treat all voters equally. We argue that perhaps they should not: Voters who have supported good choices in the past should be given higher weight than voters who have supported bad ones. To develop a formal framework for desirable weighting schemes, we draw on no-regret learning. Specifically, given a voting rule, we wish to design a weighting scheme such that applying the voting rule, with voters weighted by the scheme, leads to choices that are almost as good as those endorsed by the best voter in hindsight. We derive possibility and impossibility results for the existence of such weighting schemes, depending on whether the voting rule and the weighting scheme are deterministic or randomized, as well as on the social choice axioms satisfied by the voting rule.

NeurIPS Conference 2017 Conference Paper

Collaborative PAC Learning

• Avrim Blum
• Nika Haghtalab
• Ariel Procaccia
• Mingda Qiao

We introduce a collaborative PAC learning model, in which k players attempt to learn the same underlying concept. We ask how much more information is required to learn an accurate classifier for all players simultaneously. We refer to the ratio between the sample complexity of collaborative PAC learning and its non-collaborative (single-player) counterpart as the overhead. We design learning algorithms with O(ln(k)) and O(ln^2(k)) overhead in the personalized and centralized variants our model. This gives an exponential improvement upon the naive algorithm that does not share information among players. We complement our upper bounds with an Omega(ln(k)) overhead lower bound, showing that our results are tight up to a logarithmic factor.

AAAI Conference 2017 Conference Paper

Preference Elicitation For Participatory Budgeting

• Gerdus Benade
• Swaprava Nath
• Ariel Procaccia
• Nisarg Shah

Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable real-world impact. But making the most of this new paradigm requires a rethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We analytically compare four preference elicitation methods — knapsack votes, rankings by value or value for money, and threshold approval votes — through the lens of implicit utilitarian voting, and find that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections.

AAAI Conference 2017 Conference Paper

Small Representations of Big Kidney Exchange Graphs

• John Dickerson
• Aleksandr Kazachkov
• Ariel Procaccia
• Tuomas Sandholm

Kidney exchanges are organized markets where patients swap willing but incompatible donors. In the last decade, kidney exchanges grew from small and regional to large and national—and soon, international. This growth results in more lives saved, but exacerbates the empirical hardness of the NP-complete problem of optimally matching patients to donors. State-of-the-art matching engines use integer programming techniques to clear fielded kidney exchanges, but these methods must be tailored to specific models and objective functions, and may fail to scale to larger exchanges. In this paper, we observe that if the kidney exchange compatibility graph can be encoded by a constant number of patient and donor attributes, the clearing problem is solvable in polynomial time. We give necessary and sufficient conditions for losslessly shrinking the representation of an arbitrary compatibility graph. Then, using real compatibility graphs from the UNOS US-wide kidney exchange, we show how many attributes are needed to encode real graphs. The experiments show that, indeed, small numbers of attributes suffice.

AAAI Conference 2016 Conference Paper

An Algorithmic Framework for Strategic Fair Division

• Simina Brânzei
• Ioannis Caragiannis
• David Kurokawa
• Ariel Procaccia

We study the paradigmatic fair division problem of fairly allocating a divisible good among agents with heterogeneous preferences, commonly known as cake cutting. Classic cake cutting protocols are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, proposing a concrete computational model and reasoning about the gametheoretic properties of algorithms that operate in this model. Specifically, we show that each protocol in the class of generalized cut and choose (GCC) protocols — which includes the most important discrete cake cutting protocols — is guaranteed to have approximate subgame perfect Nash equilibria, or even exact equilibria if the protocol’s tie-breaking rule is flexible. We further observe that the (approximate) equilibria of proportional protocols — which guarantee each of the n agents a 1/n-fraction of the cake — must be (approximately) proportional, thereby answering the above question in the positive (at least for one common notion of fairness).

AAAI Conference 2016 Conference Paper

Optimal Aggregation of Uncertain Preferences

• Ariel Procaccia
• Nisarg Shah

A paradigmatic problem in social choice theory deals with the aggregation of subjective preferences of individuals — represented as rankings of alternatives — into a social ranking. We are interested in settings where individuals are uncertain about their own preferences, and represent their uncertainty as distributions over rankings. Under the classic objective of minimizing the (expected) sum of Kendall tau distances between the input rankings and the output ranking, we establish that preference elicitation is surprisingly straightforward and near-optimal solutions can be obtained in polynomial time. We show, both in theory and using real data, that ignoring uncertainty altogether can lead to suboptimal outcomes.

AAAI Conference 2016 Conference Paper

When Can the Maximin Share Guarantee Be Guaranteed?

• David Kurokawa
• Ariel Procaccia
• Junxing Wang

The fairness notion of maximin share (MMS) guarantee underlies a deployed algorithm for allocating indivisible goods under additive valuations. Our goal is to understand when we can expect to be able to give each player his MMS guarantee. Previous work has shown that such an MMS allocation may not exist, but the counterexample requires a number of goods that is exponential in the number of players; we give a new construction that uses only a linear number of goods. On the positive side, we formalize the intuition that these counterexamples are very delicate by designing an algorithm that provably finds an MMS allocation with high probability when valuations are drawn at random.

AAAI Conference 2015 Conference Paper

Audit Games with Multiple Defender Resources

• Jeremiah Blocki
• Nicolas Christin
• Anupam Datta
• Ariel Procaccia
• Arunesh Sinha

Modern organizations (e. g. , hospitals, social networks, government agencies) rely heavily on audit to detect and punish insiders who inappropriately access and disclose confidential information. Recent work on audit games models the strategic interaction between an auditor with a single audit resource and auditees as a Stackelberg game, augmenting associated well-studied security games with a configurable punishment parameter. We significantly generalize this audit game model to account for multiple audit resources where each resource is restricted to audit a subset of all potential violations, thus enabling application to practical auditing scenarios. We provide an FPTAS that computes an approximately optimal solution to the resulting non-convex optimization problem. The main technical novelty is in the design and correctness proof of an optimization transformation that enables the construction of this FPTAS. In addition, we experimentally demonstrate that this transformation significantly speeds up computation of solutions for a class of audit games and security games.

NeurIPS Conference 2015 Conference Paper

Is Approval Voting Optimal Given Approval Votes?

• Ariel Procaccia
• Nisarg Shah

Some crowdsourcing platforms ask workers to express their opinions by approving a set of k good alternatives. It seems that the only reasonable way to aggregate these k-approval votes is the approval voting rule, which simply counts the number of times each alternative was approved. We challenge this assertion by proposing a probabilistic framework of noisy voting, and asking whether approval voting yields an alternative that is most likely to be the best alternative, given k-approval votes. While the answer is generally positive, our theoretical and empirical results call attention to situations where approval voting is suboptimal.

AAAI Conference 2015 Conference Paper

Voting Rules As Error-Correcting Codes

• Ariel Procaccia
• Nisarg Shah
• Yair Zick

We present the first model of optimal voting under adversarial noise. From this viewpoint, voting rules are seen as errorcorrecting codes: their goal is to correct errors in the input rankings and recover a ranking that is close to the ground truth. We derive worst-case bounds on the relation between the average accuracy of the input votes, and the accuracy of the output ranking. Empirical results from real data show that our approach produces significantly more accurate rankings than alternative approaches.

AAAI Conference 2014 Conference Paper

Biased Games

• Ioannis Caragiannis
• David Kurokawa
• Ariel Procaccia

We present a novel extension of normal form games that we call biased games. In these games, a player’s utility is influenced by the distance between his mixed strategy and a given base strategy. We argue that biased games capture important aspects of the interaction between software agents. Our main result is that biased games satisfying certain mild conditions always admit an equilibrium. We also tackle the computation of equilibria in biased games.

NeurIPS Conference 2014 Conference Paper

Diverse Randomized Agents Vote to Win

• Albert Jiang
• Leandro Soriano Marcolino
• Ariel Procaccia
• Tuomas Sandholm
• Nisarg Shah
• Milind Tambe

We investigate the power of voting among diverse, randomized software agents. With teams of computer Go agents in mind, we develop a novel theoretical model of two-stage noisy voting that builds on recent work in machine learning. This model allows us to reason about a collection of agents with different biases (determined by the first-stage noise models), which, furthermore, apply randomized algorithms to evaluate alternatives and produce votes (captured by the second-stage noise models). We analytically demonstrate that a uniform team, consisting of multiple instances of any single agent, must make a significant number of mistakes, whereas a diverse team converges to perfection as the number of agents grows. Our experiments, which pit teams of computer Go agents against strong agents, provide evidence for the effectiveness of voting when agents are diverse.

AAAI Conference 2014 Conference Paper

Envy-Free Division of Sellable Goods

• Jeremy Karp
• Aleksandr Kazachkov
• Ariel Procaccia

We study the envy-free allocation of indivisible goods between two players. Our novel setting includes an option to sell each good for a fraction of the minimum value any player has for the good. To rigorously quantify the efficiency gain from selling, we reason about the price of envy-freeness of allocations of sellable goods — the ratio between the maximum social welfare and the social welfare of the best envy-free allocation. We show that envy-free allocations of sellable goods are significantly more efficient than their unsellable counterparts.

AAAI Conference 2014 Conference Paper

Lazy Defenders Are Almost Optimal against Diligent Attackers

• Avrim Blum
• Nika Haghtalab
• Ariel Procaccia

Most work building on the Stackelberg security games model assumes that the attacker can perfectly observe the defender’s randomized assignment of resources to targets. This assumption has been challenged by recent papers, which designed tailor-made algorithms that compute optimal defender strategies for security games with limited surveillance. We analytically demonstrate that in zero-sum security games, lazy defenders, who simply keep optimizing against perfectly informed attackers, are almost optimal against diligent attackers, who go to the effort of gathering a reasonable number of observations. This result implies that, in some realistic situations, limited surveillance may not need to be explicitly addressed.

NeurIPS Conference 2014 Conference Paper

Learning Optimal Commitment to Overcome Insecurity

• Avrim Blum
• Nika Haghtalab
• Ariel Procaccia

Game-theoretic algorithms for physical security have made an impressive real-world impact. These algorithms compute an optimal strategy for the defender to commit to in a Stackelberg game, where the attacker observes the defender's strategy and best-responds. In order to build the game model, though, the payoffs of potential attackers for various outcomes must be estimated; inaccurate estimates can lead to significant inefficiencies. We design an algorithm that optimizes the defender's strategy with no prior information, by observing the attacker's responses to randomized deployments of resources and learning his priorities. In contrast to previous work, our algorithm requires a number of queries that is polynomial in the representation of the game.

AAAI Conference 2014 Conference Paper

Modal Ranking: A Uniquely Robust Voting Rule

• Ioannis Caragiannis
• Ariel Procaccia
• Nisarg Shah

Motivated by applications to crowdsourcing, we study voting rules that output a correct ranking of alternatives by quality from a large collection of noisy input rankings. We seek voting rules that are supremely robust to noise, in the sense of being correct in the face of any “reasonable” type of noise. We show that there is such a voting rule, which we call the modal ranking rule. Moreover, we establish that the modal ranking rule is the unique rule with the preceding robustness property within a large family of voting rules, which includes a slew of well-studied rules.

AAAI Conference 2014 Conference Paper

On the Structure of Synergies in Cooperative Games

• Ariel Procaccia
• Nisarg Shah
• Max Tucker

We investigate synergy, or lack thereof, between agents in cooperative games, building on the popular notion of Shapley value. We think of a pair of agents as synergistic (resp. , antagonistic) if the Shapley value of one agent when the other agent participates in a joint effort is higher (resp. lower) than when the other agent does not participate. Our main theoretical result is that any graph specifying synergistic and antagonistic pairs can arise even from a restricted class of cooperative games. We also study the computational complexity of determining whether a given pair of agents is synergistic. Finally, we use the concepts developed in the paper to uncover the structure of synergies in two real-world organizations, the European Union and the International Monetary Fund.

AAAI Conference 2014 Conference Paper

Simultaneous Cake Cutting

• Eric Balkanski
• Simina Brânzei
• David Kurokawa
• Ariel Procaccia

We introduce the simultaneous model for cake cutting (the fair allocation of a divisible good), in which agents simultaneously send messages containing a sketch of their preferences over the cake. We show that this model enables the computation of divisions that satisfy proportionality — a popular fairness notion — using a protocol that circumvents a standard lower bound via parallel information elicitation. Cake divisions satisfying another prominent fairness notion, envy-freeness, are impossible to compute in the simultaneous model, but admit arbitrarily good approximations.

AAAI Conference 2014 Conference Paper

The Computational Rise and Fall of Fairness

• John Dickerson
• Jonathan Goldman
• Jeremy Karp
• Ariel Procaccia
• Tuomas Sandholm

The fair division of indivisible goods has long been an important topic in economics and, more recently, computer science. We investigate the existence of envyfree allocations of indivisible goods, that is, allocations where each player values her own allocated set of goods at least as highly as any other player’s allocated set of goods. Under additive valuations, we show that even when the number of goods is larger than the number of agents by a linear fraction, envy-free allocations are unlikely to exist. We then show that when the number of goods is larger by a logarithmic factor, such allocations exist with high probability. We support these results experimentally and show that the asymptotic behavior of the theory holds even when the number of goods and agents is quite small. We demonstrate that there is a sharp phase transition from nonexistence to existence of envy-free allocations, and that on average the computational problem is hardest at that transition.

AAAI Conference 2013 Conference Paper

Better Human Computation Through Principled Voting

• Andrew Mao
• Ariel Procaccia
• Yiling Chen

Designers of human computation systms often face the need to aggregate noisy information provided by multiple people. While voting is often used for this purpose, the choice of voting method is typically not principled. We conduct extensive experiments on Amazon Mechanical Turk to better understand how different voting rules perform in practice. Our empirical conclusions show that noisy human voting can differ from what popular theoretical models would predict. Our short-term goal is to motivate the design of better human computation systems; our long-term goal is to spark an interaction between researchers in (computational) social choice and human computation.

AAAI Conference 2013 Conference Paper

Dynamic Social Choice with Evolving Preferences

• David Parkes
• Ariel Procaccia

Social choice theory provides insights into a variety of collective decision making settings, but nowadays some of its tenets are challenged by internet environments, which call for dynamic decision making under constantly changing preferences. In this paper we model the problem via Markov decision processes (MDP), where the states of the MDP coincide with preference profiles and a (deterministic, stationary) policy corresponds to a social choice function. We can therefore employ the axioms studied in the social choice literature as guidelines in the design of socially desirable policies. We present tractable algorithms that compute optimal policies under different prominent social choice constraints. Our machinery relies on techniques for exploiting symmetries and isomorphisms between MDPs.

AAAI Conference 2013 Conference Paper

How Bad Is Selfish Voting?

• Simina Branzei
• Ioannis Caragiannis
• Jamie Morgenstern
• Ariel Procaccia

It is well known that strategic behavior in elections is essentially unavoidable; we therefore ask: how bad can the rational outcome be? We answer this question via the notion of the price of anarchy, using the scores of alternatives as a proxy for their quality and bounding the ratio between the score of the optimal alternative and the score of the winning alternative in Nash equilibrium. Specifically, we are interested in Nash equilibria that are obtained via sequences of rational strategic moves. Focusing on three common voting rules — plurality, veto, and Borda — we provide very positive results for plurality and very negative results for Borda, and place veto in the middle of this spectrum.

AAAI Conference 2013 Conference Paper

How to Cut a Cake Before the Party Ends

• David Kurokawa
• John Lai
• Ariel Procaccia

For decades researchers have struggled with the problem of envy-free cake cutting: how to divide a divisible good between multiple agents so that each agent likes his own allocation best. Although an envy-free cake cutting protocol was ultimately devised, it is unbounded, in the sense that the number of operations can be arbitrarily large, depending on the preferences of the agents. We ask whether bounded protocols exist when the agents’ preferences are restricted. Our main result is an envy-free cake cutting protocol for agents with piecewise linear valuations, which requires a number of operations that is polynomial in natural parameters of the given instance.

AAAI Conference 2012 Conference Paper

A Dynamic Rationalization of Distance Rationalizability

• Craig Boutilier
• Ariel Procaccia

Distance rationalizability is an intuitive paradigm for developing and studying voting rules: given a notion of consensus and a distance function on preference profiles, a rationalizable voting rule selects an alternative that is closest to being a consensus winner. Despite its appeal, distance rationalizability faces the challenge of connecting the chosen distance measure and consensus notion to an operational measure of social desirability. We tackle this issue via the decisiontheoretic framework of dynamic social choice, in which a social choice Markov decision process (MDP) models the dynamics of voter preferences in response to winner selection. We show that, for a prominent class of distance functions, one can construct a social choice MDP, with natural preference dynamics and rewards, such that a voting rule is (votewise) rationalizable with respect to the unanimity consensus for a given distance function iff it is a (deterministic) optimal policy in the MDP. This provides an alternative rationale for distance rationalizability, demonstrating the equivalence of rationalizable voting rules in a static sense and winner selection to maximize societal utility in a dynamic process.

AAAI Conference 2012 Conference Paper

Dynamic Matching via Weighted Myopia with Application to Kidney Exchange

• John Dickerson
• Ariel Procaccia
• Tuomas Sandholm

In many dynamic matching applications—especially high-stakes ones—the competitive ratios of prior-free online algorithms are unacceptably poor. The algorithm should take distributional information about possible futures into account in deciding what action to take now. This is typically done by drawing sample trajectories of possible futures at each time period, but may require a prohibitively large number of trajectories or prohibitive memory and/or computation to decide what action to take. Instead, we propose to learn potentials of elements (e. g. , vertices) of the current problem. Then, at run time, we simply run an offline matching algorithm at each time period, but subtracting out in the objective the potentials of the elements used up in the matching. We apply the approach to kidney exchange. Kidney exchanges enable willing but incompatible patient-donor pairs (vertices) to swap donors. These swaps typically include cycles longer than two pairs and chains triggered by altruistic donors. Fielded exchanges currently match myopically, maximizing the number of patients who get kidneys in an offline fashion at each time period. Myopic matching is sub-optimal; the clearing problem is dynamic since patients, donors, and altruists appear and expire over time. We theoretically compare the power of using potentials on increasingly large elements: vertices, edges, cycles, and the entire graph (optimum). Then, experiments show that by learning vertex potentials, our algorithm matches more patients than the current practice of clearing myopically. It scales to exchanges orders of magnitude beyond those handled by the prior dynamic algorithm.

AAAI Conference 2012 Conference Paper

On Maxsum Fair Cake Divisions

• Steven Brams
• Michal Feldman
• John Lai
• Jamie Morgenstern
• Ariel Procaccia

We consider the problem of selecting fair divisions of a heterogeneous divisible good among a set of agents. Recent work (Cohler et al. , AAAI 2011) focused on designing algorithms for computing maxsum—social welfare maximizing—allocations under the fairness notion of envyfreeness. Maxsum allocations can also be found under alternative notions such as equitability. In this paper, we examine the properties of these allocations. In particular, we provide conditions for when maxsum envy-free or equitable allocations are Pareto optimal and give examples where fairness with Pareto optimality is not possible. We also prove that maxsum envy-free allocations have weakly greater welfare than maxsum equitable allocations when agents have structured valuations, and we derive an approximate version of this inequality for general valuations.

AAMAS Conference 2012 Conference Paper

Optimizing Kidney Exchange with Transplant Chains: Theory and Reality

• John Dickerson
• Ariel Procaccia
• Tuomas Sandholm

Kidney exchange, where needy patients swap incompatible donors with each other, offers a lifesaving alternative to waiting for an organ from the deceased-donor waiting list. Recently, \emph{chains} -- sequences of transplants initiated by an altruistic kidney donor -- have shown marked success in practice, yet remain poorly understood. We provide a theoretical analysis of the efficacy of chains in the most widely used kidney exchange model, proving that long chains do not help beyond chains of length of 3 in the large. This completely contradicts our real-world results gathered from the budding nationwide kidney exchange in the United States; there, solution quality improves by increasing the chain length cap to 13 or beyond. We analyze reasons for this gulf between theory and practice, motivated by our experiences running the only nationwide kidney exchange. We augment the standard kidney exchange model to include a variety of real-world features. Experiments in the static setting support the theory and help determine how large is really "in the large". Experiments in the dynamic setting cannot be conducted in the large due to computational limitations, but with up to 460 candidates, a chain cap of 4 was best (in fact, better than 5).

AAAI Conference 2011 Conference Paper

Optimal Envy-Free Cake Cutting

• Yuga Cohler
• John Lai
• David Parkes
• Ariel Procaccia

We consider the problem of fairly dividing a heterogeneous divisible good among agents with different preferences. Previous work has shown that envy-free allocations, i.e., where each agent prefers its own allocation to any other, may not be efficient, in the sense of maximizing the total value of the agents. Our goal is to pinpoint the most efficient allocations among all envy-free allocations. We provide tractable algorithms for doing so under different assumptions regarding the preferences of the agents.

AAAI Conference 2010 Conference Paper

Can Approximation Circumvent Gibbard-Satterthwaite?

• Ariel Procaccia

The Gibbard-Satterthwaite Theorem asserts that any reasonable voting rule cannot be strategyproof. A large body of research in AI deals with circumventing this theorem via computational considerations; the goal is to design voting rules that are computationally hard, in the worst-case, to manipulate. However, recent work indicates that the prominent voting rules are usually easy to manipulate. In this paper, we suggest a new CS-oriented approach to circumventing Gibbard-Satterthwaite, using randomization and approximation. Specifically, we wish to design strategyproof randomized voting rules that are close, in a standard approximation sense, to prominent score-based (deterministic) voting rules. We give tight lower and upper bounds on the approximation ratio achievable via strategyproof randomized rules with respect to positional scoring rules, Copeland, and Maximin.

AAMAS Conference 2010 Conference Paper

On the Limits of Dictatorial Classification

• Reshef Meir
• Ariel Procaccia
• Jeffrey Rosenschein

In the strategyproof classification setting, a set of labeledexamples is partitioned among multiple agents. Given thereported labels, an optimal classification mechanism returnsa classifier that minimizes the number of mislabeled examples. However, each agent is interested in the accuracy ofthe returned classifier on its own examples, and may misreport its labels in order to achieve a better classifier, thuscontaminating the dataset. The goal is to design strategyproof mechanisms that correctly label as many examplesas possible. Previous work has investigated the foregoing setting under limiting assumptions, or with respect to very restrictedclasses of classifiers. In this paper, we study the strategyproof classification setting with respect to prominent classesof classifiers—boolean conjunctions and linear separators - and without any assumptions on the input. On the negativeside, we show that strategyproof mechanisms cannot achievea constant approximation ratio, by showing that such mechanisms must be dictatorial on a subdomain, in the sensethat the outcome is selected according to the preferences ofa single agent. On the positive side, we present a randomizedmechanism—Iterative Random Dictator—and demonstrateboth that it is strategyproof and that its approximation ratiodoes not increase with the number of agents. Interestingly, the notion of dictatorship is prominently featured in all ourresults, helping to establish both upper and lower bounds.

AAAI Conference 2010 Conference Paper

Truth, Justice, and Cake Cutting

• Yiling Chen
• John Lai
• David Parkes
• Ariel Procaccia

Cake cutting is a common metaphor for the division of a heterogeneous divisible good. There are numerous papers that study the problem of fairly dividing a cake; a small number of them also take into account self-interested agents and consequent strategic issues, but these papers focus on fairness and consider a strikingly weak notion of truthfulness. In this paper we investigate the problem of cutting a cake in a way that is truthful and fair, where for the first time our notion of dominant strategy truthfulness is the ubiquitous one in social choice and computer science. We design both deterministic and randomized cake cutting algorithms that are truthful and fair under different assumptions with respect to the valuation functions of the agents.

AAAI Conference 2010 Conference Paper

Voting Almost Maximizes Social Welfare Despite Limited Communication

• Ioannis Caragiannis
• Ariel Procaccia

In cooperative multiagent systems an alternative that maximizes the social welfare—the sum of utilities—can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006) have introduced the concept of distortion to quantify this gap. In this paper, we present the notion of embeddings into voting rules: functions that receive an agent’s utility function and return the agent’s vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.

AAMAS Conference 2008 Conference Paper

A Broader Picture of the Complexity of Strategic Behavior in Multi-Winner Elections

• Reshef Meir
• Ariel Procaccia
• Jeffrey Rosenschein

Recent work by Procaccia, Rosenschein and Zohar [14] established some results regarding the complexity of manipulation and control in elections with multiple winners, such as elections of an assembly or committee; that work provided an initial understanding of the topic. In this paper, we paint a more complete picture of the topic, investigating four prominent multi-winner voting rules. First, we characterize the complexity of manipulation and control in these voting rules under various kinds of formalizations of the manipulator’s goal. Second, we extend the results about complexity of control to various well-known types of control. This work enhances our comprehension of which multi-winner voting rules should be employed in various settings.

AAMAS Conference 2008 Conference Paper

Automated Design of Scoring Rules by Learning from Examples

• Ariel Procaccia
• Aviv Zohar
• Jeffrey Rosenschein

Scoring rules are a broad and concisely-representable class of voting rules which includes, for example, Plurality and Borda. Our main result asserts that the class of scoring rules, as functions from preferences into candidates, is efficiently learnable in the PAC model. We discuss the applications of this result to automated design of scoring rules. We also investigate possible extensions of our approach, and (along the way) we establish a lemma of independent interest regarding the number of distinct scoring rules.

AAMAS Conference 2006 Conference Paper

Junta Distributions and the Average-Case Complexity of Manipulating Elections

• Ariel Procaccia
• Jeffrey Rosenschein

AAMAS Conference 2006 Conference Paper

Learning to Identify Winning Coalitions in the PAC Model

• Ariel Procaccia
• Jeffrey Rosenschein

AAMAS Conference 2006 Conference Paper

The Communication Complexity of Coalition Formation Among Autonomous Agents

• Ariel Procaccia
• Jeffrey Rosenschein