Ariel D. Procaccia

ICML Conference 2025 Conference Paper

Clone-Robust AI Alignment

• Ariel D. Procaccia
• Benjamin Schiffer
• Shirley Zhang 0001

A key challenge in training Large Language Models (LLMs) is properly aligning them with human preferences. Reinforcement Learning with Human Feedback (RLHF) uses pairwise comparisons from human annotators to train reward functions and has emerged as a popular alignment method. However, input datasets in RLHF can be unbalanced due to adversarial manipulation or inadvertent repetition. Therefore, we want RLHF algorithms to perform well even when the set of alternatives is not uniformly distributed. Drawing on insights from social choice theory, we introduce robustness to approximate clones, a desirable property of RLHF algorithms which requires that adding near-duplicate alternatives does not significantly change the learned reward function. We first demonstrate that the standard RLHF algorithm based on regularized maximum likelihood estimation (MLE) fails to satisfy this property. We then propose the weighted MLE, a new RLHF algorithm that modifies the standard regularized MLE by weighting alternatives based on their similarity to other alternatives. This new algorithm guarantees robustness to approximate clones while preserving desirable theoretical properties.

AAAI Conference 2025 Conference Paper

Federated Assemblies

• Daniel Halpern
• Ariel D. Procaccia
• Ehud Shapiro
• Nimrod Talmon

A *citizens' assembly* is a group of people who are randomly selected to represent a larger population in a deliberation. While this approach has successfully strengthened democracy, it has certain limitations that suggest the need for assemblies to form and associate more organically. In response, we propose *federated assemblies*, where assemblies are interconnected, and each parent assembly is selected from members of its child assemblies. The main technical challenge is to develop random selection algorithms that meet new representation constraints inherent in this hierarchical structure. We design and analyze several algorithms that provide different representation guarantees under various assumptions on the structure of the underlying graph.

ICML Conference 2025 Conference Paper

Generative Social Choice: The Next Generation

• Niclas Boehmer
• Sara Fish
• Ariel D. Procaccia

A key task in certain democratic processes is to produce a concise slate of statements that proportionally represents the full spectrum of user opinions. This task is similar to committee elections, but unlike traditional settings, the candidate set comprises all possible statements of varying lengths, and so it can only be accessed through specific queries. Combining social choice and large language models, prior work has approached this challenge through a framework of generative social choice. We extend the framework in two fundamental ways, providing theoretical guarantees even in the face of approximately optimal queries and a budget limit on the overall length of the slate. Using GPT-4o to implement queries, we showcase our approach on datasets related to city improvement measures and drug reviews, demonstrating its effectiveness in generating representative slates from unstructured user opinions.

AAAI Conference 2025 Conference Paper

Multi-Apartment Rent Division

• Ariel D. Procaccia
• Benjamin Schiffer
• Shirley Zhang

Rent division is the well-studied problem of fairly assigning rooms and dividing rent among a set of roommates within a single apartment. A shortcoming of existing solutions is that renters are assumed to be considering apartments in isolation, whereas in reality, renters can choose among multiple apartments. In this paper, we generalize the rent division problem to the multi-apartment setting, where the goal is to both fairly choose an apartment among a set of alternatives and fairly assign rooms and rents within the chosen apartment. Our main contribution is a generalization of envy-freeness called *negotiated envy-freeness*. We show that a solution satisfying negotiated envy-freeness is guaranteed to exist and that it is possible to optimize over all negotiated envy-free solutions in polynomial time. We also define an even stronger fairness notion called *universal envy-freeness* and study its existence when values are drawn randomly.

ICLR Conference 2025 Conference Paper

Strategic Classification With Externalities

• Safwan Hossain
• Evi Micha
• Yiling Chen 0001
• Ariel D. Procaccia

We propose a new variant of the strategic classification problem: a principal reveals a classifier, and $n$ agents report their (possibly manipulated) features to be classified. Motivated by real-world applications, our model crucially allows the manipulation of one agent to affect another; that is, it explicitly captures inter-agent externalities. The principal-agent interactions are formally modeled as a Stackelberg game, with the resulting agent manipulation dynamics captured as a simultaneous game. We show that under certain assumptions, the pure Nash Equilibrium of this agent manipulation game is unique and can be efficiently computed. Leveraging this result, PAC learning guarantees are established for the learner: informally, we show that it is possible to learn classifiers that minimize loss on the distribution, even when a random number of agents are manipulating their way to a pure Nash Equilibrium. We also comment on the optimization of such classifiers through gradient-based approaches. This work sets the theoretical foundations for a more realistic analysis of classifiers that are robust against multiple strategic actors interacting in a common environment.

ICLR Conference 2025 Conference Paper

The Hidden Cost of Waiting for Accurate Predictions

• Ali Shirali
• Ariel D. Procaccia
• Rediet Abebe

Algorithmic predictions are increasingly informing societal resource allocations by identifying individuals for targeting. Policymakers often build these systems with the assumption that by gathering more observations on individuals, they can improve predictive accuracy and, consequently, allocation efficiency. An overlooked yet consequential aspect of prediction-driven allocations is that of timing. The planner has to trade off relying on earlier and potentially noisier predictions to intervene before individuals experience undesirable outcomes, or they may wait to gather more observations to make more precise allocations. We examine this tension using a simple mathematical model, where the planner collects observations on individuals to improve predictions over time. We analyze both the ranking induced by these predictions and optimal resource allocation. We show that though individual prediction accuracy improves over time, counter-intuitively, the average ranking loss can worsen. As a result, the planner's ability to improve social welfare can decline. We identify inequality as a driving factor behind this phenomenon. Our findings provide a nuanced perspective and challenge the conventional wisdom that it is preferable to wait for more accurate predictions to ensure the most efficient allocations.

IJCAI Conference 2025 Conference Paper

The Proportional Veto Principle for Approval Ballots

• Daniel Halpern
• Ariel D. Procaccia
• Warut Suksompong

The proportional veto principle, which captures the idea that a candidate vetoed by a large group of voters should not be chosen, has been studied for ranked ballots in single-winner voting. We introduce a version of this principle for approval ballots, which we call flexible-voter representation (FVR). We show that while the approval voting rule and other natural scoring rules provide the optimal FVR guarantee only for some flexibility threshold, there exists a scoring rule that is FVR-optimal for all thresholds simultaneously. We also extend our results to multi-winner voting.

NeurIPS Conference 2024 Conference Paper

Axioms for AI Alignment from Human Feedback

• Luise Ge
• Daniel Halpern
• Evi Micha
• Ariel D. Procaccia
• Itai Shapira
• Yevgeniy Vorobeychik
• Junlin Wu

In the context of reinforcement learning from human feedback (RLHF), the reward function is generally derived from maximum likelihood estimation of a random utility model based on pairwise comparisons made by humans. The problem of learning a reward function is one of preference aggregation that, we argue, largely falls within the scope of social choice theory. From this perspective, we can evaluate different aggregation methods via established axioms, examining whether these methods meet or fail well-known standards. We demonstrate that both the Bradley-Terry-Luce Model and its broad generalizations fail to meet basic axioms. In response, we develop novel rules for learning reward functions with strong axiomatic guarantees. A key innovation from the standpoint of social choice is that our problem has a linear structure, which greatly restricts the space of feasible rules and leads to a new paradigm that we call linear social choice.

NeurIPS Conference 2024 Conference Paper

Bias Detection via Signaling

• Yiling Chen
• Tao Lin
• Ariel D. Procaccia
• Aaditya Ramdas
• Itai Shapira

We introduce and study the problem of detecting whether an agent is updating their prior beliefs given new evidence in an optimal way that is Bayesian, or whether they are biased towards their own prior. In our model, biased agents form posterior beliefs that are a convex combination of their prior and the Bayesian posterior, where the more biased an agent is, the closer their posterior is to the prior. Since we often cannot observe the agent's beliefs directly, we take an approach inspired by information design. Specifically, we measure an agent's bias by designing a signaling scheme and observing the actions they take in response to different signals, assuming that they are maximizing their own expected utility; our goal is to detect bias with a minimum number of signals. Our main results include a characterization of scenarios where a single signal suffices and a computationally efficient algorithm to compute optimal signaling schemes.

ICML Conference 2024 Conference Paper

Fair Federated Learning via the Proportional Veto Core

• Bhaskar Ray Chaudhury
• Aniket Murhekar
• Zhuowen Yuan
• Bo Li 0026
• Ruta Mehta
• Ariel D. Procaccia

Previous work on fairness in federated learning introduced the notion of core stability, which provides utility-based fairness guarantees to any subset of participating agents. However, these guarantees require strong assumptions on agent utilities that render them impractical. To address this shortcoming, we measure the quality of output models in terms of their ordinal rank instead of their cardinal utility, and use this insight to adapt the classical notion of proportional veto core (PVC) from social choice theory to the federated learning setting. We prove that models that are PVC-stable exist in very general learning paradigms, even allowing non-convex model sets, as well as non-convex and non-concave loss functions. We also design Rank-Core-Fed, a distributed federated learning algorithm, to train a PVC-stable model. Finally, we demonstrate that Rank-Core-Fed outperforms baselines in terms of fairness on different datasets.

NeurIPS Conference 2024 Conference Paper

Honor Among Bandits: No-Regret Learning for Online Fair Division

• Ariel D. Procaccia
• Benjamin Schiffer
• Shirley Zhang

We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player's value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves $\tilde{O}(T^{2/3})$ regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space.

NeurIPS Conference 2024 Conference Paper

Learning Social Welfare Functions

• Kanad S. Pardeshi
• Itai Shapira
• Ariel D. Procaccia
• Aarti Singh

Is it possible to understand or imitate a policy maker's rationale by looking at past decisions they made? We formalize this question as the problem of learning social welfare functions belonging to the well-studied family of power mean functions. We focus on two learning tasks; in the first, the input is vectors of utilities of an action (decision or policy) for individuals in a group and their associated social welfare as judged by a policy maker, whereas in the second, the input is pairwise comparisons between the welfares associated with a given pair of utility vectors. We show that power mean functions are learnable with polynomial sample complexity in both cases, even if the social welfare information is noisy. Finally, we design practical algorithms for these tasks and evaluate their performance.

AAAI Conference 2024 Conference Paper

Manipulation-Robust Selection of Citizens’ Assemblies

• Bailey Flanigan
• Jennifer Liang
• Ariel D. Procaccia
• Sven Wang

Among the recent work on designing algorithms for selecting citizens' assembly participants, one key property of these algorithms has not yet been studied: their manipulability. Strategic manipulation is a concern because these algorithms must satisfy representation constraints according to volunteers' self-reported features; misreporting these features could thereby increase a volunteer's chance of being selected, decrease someone else's chance, and/or increase the expected number of seats given to their group. Strikingly, we show that Leximin — an algorithm that is widely used for its fairness — is highly manipulable in this way. We then introduce a new class of selection algorithms that use Lp norms as objective functions. We show that the manipulability of the Lp-based algorithm decreases in O(1/n^(1-1/p)) as the number of volunteers n grows, approaching the optimal rate of O(1/n) as p approaches infinity. These theoretical results are confirmed via experiments in eight real-world datasets.

NeurIPS Conference 2024 Conference Paper

Policy Aggregation

• Parand A. Alamdari
• Soroush Ebadian
• Ariel D. Procaccia

We consider the challenge of AI value alignment with multiple individuals that have different reward functions and optimal policies in an underlying Markov decision process. We formalize this problem as one of policy aggregation, where the goal is to identify a desirable collective policy. We argue that an approach informed by social choice theory is especially suitable. Our key insight is that social choice methods can be reinterpreted by identifying ordinal preferences with volumes of subsets of the state-action occupancy polytope. Building on this insight, we demonstrate that a variety of methods — including approval voting, Borda count, the proportional veto core, and quantile fairness — can be practically applied to policy aggregation.

SODA Conference 2024 Conference Paper

School Redistricting: Wiping Unfairness Off the Map

• Ariel D. Procaccia
• Isaac Robinson
• Jamie Tucker-Foltz

AAAI Conference 2023 Conference Paper

Now We’re Talking: Better Deliberation Groups through Submodular Optimization

• Jake Barrett
• Kobi Gal
• Paul Gölz
• Rose M. Hong
• Ariel D. Procaccia

Citizens’ assemblies are groups of randomly selected constituents who are tasked with providing recommendations on policy questions. Assembly members form their recommendations through a sequence of discussions in small groups (deliberation), in which group members exchange arguments and experiences. We seek to support this process through optimization, by studying how to assign participants to discussion groups over multiple sessions, in a way that maximizes interaction between participants and satisfies diversity constraints within each group. Since repeated meetings between a given pair of participants have diminishing marginal returns, we capture interaction through a submodular function, which is approximately optimized by a greedy algorithm making calls to an ILP solver. This framework supports different submodular objective functions, and we identify sensible options, but we also show it is not necessary to commit to a particular choice: Our main theoretical result is a (practically efficient) algorithm that simultaneously approximates every possible objective function of the form we are interested in. Experiments with data from real citizens' assemblies demonstrate that our approach substantially outperforms the heuristic algorithm currently used by practitioners.

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

Strategyproof Voting under Correlated Beliefs

• Daniel Halpern
• Rachel Li
• Ariel D. Procaccia

In voting theory, when voters have ranked preferences over candidates, the celebrated Gibbard-Satterthwaite Theorem essentially rules out the existence of reasonable strategyproof methods for picking a winner. What if we weaken strategyproofness to only hold for Bayesian voters with beliefs over others' preferences? When voters believe other participants' rankings are drawn independently from a fixed distribution, the impossibility persists. However, it is quite reasonable for a voter to believe that other votes are correlated, either to each other or to their own ranking. We consider such beliefs induced by classic probabilistic models in social choice such as the Mallows, Placket-Luce, and Thurstone-Mosteller models. We single out the plurality rule (choosing the candidate ranked first most often) as a particularly promising choice as it is strategyproof for a large class of beliefs containing the specific ones we introduce. Further, we show that plurality is unique among positional scoring rules in having this property: no other scoring rule is strategyproof for beliefs induced by the Mallows model when there are a sufficient number of voters. Finally, we give examples of prominent non-scoring voting rules failing to be strategyproof on beliefs in this class, further bolstering the case for plurality.

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.

SODA Conference 2022 Conference Paper

Compact Redistricting Plans Have Many Spanning Trees

• Ariel D. Procaccia
• Jamie Tucker-Foltz

In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. There are influential Markov chain Monte Carlo methods for doing so that are based on sampling and splitting random spanning trees. Empirical evidence suggests that the distributions such algorithms sample from place higher weight on more “compact” redistricting plans, which is a practically useful and desirable property. In this paper, we confirm these observations analytically, establishing an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled. This result provides theoretical underpinnings for algorithms that are already making a significant real-world impact.

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.

NeurIPS Conference 2022 Conference Paper

Robust Rent Division

• Dominik Peters
• Ariel D. Procaccia
• David Zhu

In fair rent division, the problem is to assign rooms to roommates and fairly split the rent based on roommates' reported valuations for the rooms. Envy-free rent division is the most popular application on the fair division website Spliddit. The standard model assumes that agents can correctly report their valuations for each room. In practice, agents may be unsure about their valuations, for example because they have had only limited time to inspect the rooms. Our goal is to find a robust rent division that remains fair even if agent valuations are slightly different from the reported ones. We introduce the lexislack solution, which selects a rent division that remains envy-free for valuations within as large a radius as possible of the reported valuations. We also consider robustness notions for valuations that come from a probability distribution, and use results from learning theory to show how we can find rent divisions that (almost) maximize the probability of being envy-free, or that minimize the expected envy. We show that an almost optimal allocation can be identified based on polynomially many samples from the valuation distribution. Finding the best allocation given these samples is NP-hard, but in practice such an allocation can be found using integer linear programming.

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.

AAAI Conference 2021 Conference Paper

District-Fair Participatory Budgeting

• D Ellis Hershkowitz
• Anson Kahng
• Dominik Peters
• Ariel D. Procaccia

Participatory budgeting is a method used by city governments to select public projects to fund based on residents’ votes. Many cities use participatory budgeting at a district level. Typically, a budget is divided among districts proportionally to their population, and each district holds an election over local projects and then uses its budget to fund the projects most preferred by its voters. However, district-level participatory budgeting can yield poor social welfare because it does not necessarily fund projects supported across multiple districts. On the other hand, decision making that only takes global social welfare into account can be unfair to districts: A social-welfare-maximizing solution might not fund any of the projects preferred by a district, despite the fact that its constituents pay taxes to the city. Thus, we study how to fairly maximize social welfare in a participatory budgeting setting with a single city-wide election. We propose a notion of fairness that guarantees each district at least as much welfare as it would have received in a district-level election. We show that, although optimizing social welfare subject to this notion of fairness is NP-hard, we can efficiently construct a lottery over welfare-optimal outcomes that is fair in expectation. Moreover, we show that, when we are allowed to slightly relax fairness, we can efficiently compute a fair solution that is welfare-maximizing, but which may overspend the budget.

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.

AAAI Conference 2021 Conference Paper

If You Like Shapley Then You’ll Love the Core

• Tom Yan
• Ariel D. Procaccia

The prevalent approach to problems of credit assignment in machine learning — such as feature and data valuation — is to model the problem at hand as a cooperative game and apply the Shapley value. But cooperative game theory offers a rich menu of alternative solution concepts, which famously includes the core and its variants. Our goal is to challenge the machine learning community’s current consensus around the Shapley value, and make a case for the core as a viable alternative. To that end, we prove that arbitrarily good approximations to the least core — a core relaxation that is always feasible — can be computed efficiently (but prove an impossibility for a more refined solution concept, the nucleolus). We also perform experiments that corroborate these theoretical results and shed light on settings where the least core may be preferable to the Shapley value.

AAAI Conference 2021 Conference Paper

Inverse Reinforcement Learning From Like-Minded Teachers

• Ritesh Noothigattu
• Tom Yan
• Ariel D. Procaccia

We study the problem of learning a policy in a Markov decision process (MDP) based on observations of the actions taken by multiple teachers. We assume that the teachers are like-minded in that their (linear) reward functions — while different from each other — are random perturbations of an underlying reward function. Under this assumption, we demonstrate that inverse reinforcement learning algorithms that satisfy a certain property — that of matching feature expectations — yield policies that are approximately optimal with respect to the underlying reward function, and that no algorithm can do better in the worst case. We also show how to efficiently recover the optimal policy when the MDP has one state — a setting that is akin to multi-armed bandits.

JAIR Journal 2021 Journal Article

Liquid Democracy: An Algorithmic Perspective

• Anson Kahng
• Simon Mackenzie
• Ariel D. 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 non-local delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

AAAI Conference 2021 Conference Paper

Preference Elicitation as Average-Case Sorting

• Dominik Peters
• Ariel D. Procaccia

Many decision making systems require users to indicate their preferences via a ranking. It is common to elicit such rankings through pairwise comparison queries. By using sorting algorithms, this can be achieved by asking at most O(m log m) adaptive comparison queries. However, in many cases we have some advance (probabilistic) information about the user’s preferences, for instance if we have a learnt model of the user’s preferences or if we expect the user’s preferences to be correlated with those of previous users. For these cases, we design elicitation algorithms that ask fewer questions in expectation, by building on results for average-case sorting. If the user’s preferences are drawn from a Mallows φ model, O(m) queries are enough; for a mixture of k Mallows models, log k + O(m) queries are enough; for Plackett–Luce models, the answer varies with the alternative weights. Our results match information-theoretic lower bounds. We also provide empirical evidence for the benefits of our approach.

NeurIPS Conference 2020 Conference Paper

Axioms for Learning from Pairwise Comparisons

• Ritesh Noothigattu
• Dominik Peters
• Ariel D. Procaccia

To be well-behaved, systems that process preference data must satisfy certain conditions identified by economic decision theory and by social choice theory. In ML, preferences and rankings are commonly learned by fitting a probabilistic model to noisy preference data. The behavior of this learning process from the view of economic theory has previously been studied for the case where the data consists of rankings. In practice, it is more common to have only pairwise comparison data, and the formal properties of the associated learning problem are more challenging to analyze. We show that a large class of random utility models (including the Thurstone–Mosteller Model), when estimated using the MLE, satisfy a Pareto efficiency condition. These models also satisfy a strong monotonicity property, which implies that the learning process is responsive to input data. On the other hand, we show that these models fail certain other consistency conditions from social choice theory, and in particular do not always follow the majority opinion. Our results inform existing and future applications of random utility models for societal decision making.

NeurIPS Conference 2020 Conference Paper

Explainable Voting

• Dominik Peters
• Ariel D. Procaccia
• Alexandros Psomas
• Zixin Zhou

The design of voting rules is traditionally guided by desirable axioms. Recent work shows that, surprisingly, the axiomatic approach can also support the generation of explanations for voting outcomes. However, no bounds on the size of these explanations is given; for all we know, they may be unbearably tedious. We prove, however, that outcomes of the important Borda rule can be explained using $O(m^2)$ steps, where $m$ is the number of alternatives. Our main technical result is a general lower bound that, in particular, implies that the foregoing bound is asymptotically tight. We discuss the significance of our results for AI and machine learning, including their potential to bolster an emerging paradigm of automated decision making called virtual democracy.

NeurIPS Conference 2020 Conference Paper

Neutralizing Self-Selection Bias in Sampling for Sortition

• Bailey Flanigan
• Paul Gölz
• Anupam Gupta
• Ariel D. Procaccia

Sortition is a political system in which decisions are made by panels of randomly selected citizens. The process for selecting a sortition panel is traditionally thought of as uniform sampling without replacement, which has strong fairness properties. In practice, however, sampling without replacement is not possible since only a fraction of agents is willing to participate in a panel when invited, and different demographic groups participate at different rates. In order to still produce panels whose composition resembles that of the population, we develop a sampling algorithm that restores close-to-equal representation probabilities for all agents while satisfying meaningful demographic quotas. As part of its input, our algorithm requires probabilities indicating how likely each volunteer in the pool was to participate. Since these participation probabilities are not directly observable, we show how to learn them, and demonstrate our approach using data on a real sortition panel combined with information on the general population in the form of publicly available survey data.

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.

IJCAI Conference 2019 Conference Paper

Achieving a Fairer Future by Changing the Past

• Jiafan He
• Ariel D. Procaccia
• Alexandros Psomas
• David Zeng

We study the problem of allocating T indivisible items that arrive online to agents with additive valuations. The allocation must satisfy a prominent fairness notion, envy-freeness up to one item (EF1), at each round. To make this possible, we allow the reallocation of previously allocated items, but aim to minimize these so-called adjustments. For the case of two agents, we show that algorithms that are informed about the values of future items can get by without any adjustments, whereas uninformed algorithms require Theta(T) adjustments. For the general case of three or more agents, we prove that even informed algorithms must use Omega(T) adjustments, and design an uninformed algorithm that requires only O(T^(3/2)).

AAAI Conference 2019 Conference Paper

Fairly Allocating Many Goods with Few Queries

• Hoon Oh
• Ariel D. Procaccia
• Warut Suksompong

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

AAAI Conference 2019 Conference Paper

Low-Distortion Social Welfare Functions

• Gerdus Benadè
• Ariel D. Procaccia
• Mingda Qiao

Work on implicit utilitarian voting advocates the design of preference aggregation methods that maximize utilitarian social welfare with respect to latent utility functions, based only on observed rankings of the alternatives. This approach has been successfully deployed in order to help people choose a single alternative or a subset of alternatives, but it has previously been unclear how to apply the same approach to the design of social welfare functions, where the desired output is a ranking. We propose to address this problem by assuming that voters’ utilities for rankings are induced by unknown weights and unknown utility functions, which, moreover, have a combinatorial (subadditive) structure. Despite the extreme lack of information about voters’ preferences, we show that it is possible to choose rankings such that the worst-case gap between their social welfare and that of the optimal ranking, called distortion, is no larger (up to polylogarithmic factors) than the distortion associated with much simpler problems. Through experiments, we identify practical methods that achieve nearoptimal social welfare on average.

AAAI Conference 2019 Conference Paper

Migration as Submodular Optimization

• Paul Gölz
• Ariel D. Procaccia

Migration presents sweeping societal challenges that have recently attracted significant attention from the scientific community. One of the prominent approaches that have been suggested employs optimization and machine learning to match migrants to localities in a way that maximizes the expected number of migrants who find employment. However, it relies on a strong additivity assumption that, we argue, does not hold in practice, due to competition effects; we propose to enhance the data-driven approach by explicitly optimizing for these effects. Specifically, we cast our problem as the maximization of an approximately submodular function subject to matroid constraints, and prove that the worst-case guarantees given by the classic greedy algorithm extend to this setting. We then present three different models for competition effects, and show that they all give rise to submodular objectives. Finally, we demonstrate via simulations that our approach leads to significant gains across the board.

ICML Conference 2019 Conference Paper

Statistical Foundations of Virtual Democracy

• Anson Kahng
• Min Kyung Lee
• Ritesh Noothigattu
• Ariel D. Procaccia
• Christos-Alexandros Psomas

Virtual democracy is an approach to automating decisions, by learning models of the preferences of individual people, and, at runtime, aggregating the predicted preferences of those people on the dilemma at hand. One of the key questions is which aggregation method – or voting rule – to use; we offer a novel statistical viewpoint that provides guidance. Specifically, we seek voting rules that are robust to prediction errors, in that their output on people’s true preferences is likely to coincide with their output on noisy estimates thereof. We prove that the classic Borda count rule is robust in this sense, whereas any voting rule belonging to the wide family of pairwise-majority consistent rules is not. Our empirical results further support, and more precisely measure, the robustness of Borda count.

IJCAI Conference 2019 Conference Paper

The Provable Virtue of Laziness in Motion Planning

• Nika Haghtalab
• Simon Mackenzie
• Ariel D. Procaccia
• Oren Salzman
• Siddhartha Srinivasa

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm such as manipulation in cluttered environments and planning for robots in surgical settings; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

ICAPS Conference 2018 Conference Paper

The Provable Virtue of Laziness in Motion Planning

• Nika Haghtalab
• Simon Mackenzie
• Ariel D. Procaccia
• Oren Salzman
• Siddhartha S. Srinivasa

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

AAMAS Conference 2017 Conference Paper

Multi-Channel Marketing with Budget Complementarities

• Haifeng Zhang
• Yevgeniy Vorobeychik
• Ariel D. Procaccia

Utility maximization under a budget constraint is a classical problem in economics and management science. It is commonly assumed that the utility is a “nice” known analytic function, for example, continuous and concave. In many domains, such as marketing, increased availability of computational resources and data has enabled the development of sophisticated simulations to evaluate the impact of allocating a fixed budget among alternatives (e. g. , marketing channels) on outcomes, such as demand. While simulations enable high resolution evaluation of alternative budget allocation strategies, they significantly complicate the associated budget optimization problem. In particular, simulation runs are time consuming, significantly limiting the space of options that can be explored. An important second challenge is the common presence of budget complementarities, where non-negligible budget increments are required for an appreciable marginal impact from a channel. This introduces a combinatorial structure on the decision space. We propose to address these challenges by first converting the problem into a multi-choice knapsack optimization problem with unknown weights. We show that if weights (corresponding to marginal impact thresholds for each channel) are well approximated, we can achieve a solution within a factor of 2 of optimal, and this bound is tight. We then develop several parsimonious query algorithms for achieving this approximation in an online fashion. Experimental evaluation demonstrates the effectiveness of our approach.

SODA Conference 2017 Conference Paper

Opting Into Optimal Matchings

• Avrim Blum
• Ioannis Caragiannis
• Nika Haghtalab
• Ariel D. Procaccia
• Eviatar B. Procaccia
• Rohit Vaish

We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player—who is associated with a subset of vertices—matches as many of his own vertices when he opts into the matching mechanism as when he opts out. We offer a new perspective on this problem by considering an arbitrary graph, but assuming that vertices are associated with players at random. Our main result asserts that, under certain conditions, any fixed optimal matching is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms. We discuss the implications of our results for market design in general, and kidney exchange in particular.

JAIR Journal 2017 Journal Article

Subset Selection Via Implicit Utilitarian Voting

• Ioannis Caragiannis
• Swaprava Nath
• Ariel D. Procaccia
• Nisarg Shah

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach -- which we refer to as implicit utilitarian voting -- assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of RoboVote.org, a not-for-profit website that helps users make group decisions via AI-driven voting methods.

IJCAI Conference 2017 Conference Paper

Which is the Fairest (Rent Division) of Them All? [Extended Abstract]

• Ya'akov (Kobi) Gal
• Moshe Mash
• Ariel D. Procaccia
• Yair Zick

What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.

IJCAI Conference 2017 Conference Paper

Why You Should Charge Your Friends for Borrowing Your Stuff

• Kijung Shin
• Euiwoong Lee
• Dhivya Eswaran
• Ariel D. Procaccia

We consider goods that can be shared with k-hop neighbors (i. e. , the set of nodes within k hops from an owner) on a social network. We examine incentives to buy such a good by devising game-theoretic models where each node decides whether to buy the good or free ride. First, we find that social inefficiency, specifically excessive purchase of the good, occurs in Nash equilibria. Second, the social inefficiency decreases as k increases and thus a good can be shared with more nodes. Third, and most importantly, the social inefficiency can also be significantly reduced by charging free riders an access cost and paying it to owners, leading to the conclusion that organizations and system designers should impose such a cost. These findings are supported by our theoretical analysis in terms of the price of anarchy and the price of stability; and by simulations based on synthetic and real social networks.

IJCAI Conference 2016 Conference Paper

Subset Selection via Implicit Utilitarian Voting

• Ioannis Caragiannis
• Swaprava Nath
• Ariel D. Procaccia
• Nisarg Shah

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach - which we refer to as implicit utilitarian voting - assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of an upcoming social choice website.

IJCAI Conference 2016 Conference Paper

Three Strategies to Success: Learning Adversary Models in Security Games

• Nika Haghtalab
• Fei Fang
• Thanh H. Nguyen
• Arunesh Sinha
• Ariel D. Procaccia
• Milind Tambe

State-of-the-art applications of Stackelberg security games - including wildlife protection - offer a wealth of data, which can be used to learn the behavior of the adversary. But existing approaches either make strong assumptions about the structure of the data, or gather new data through online algorithms that are likely to play severely suboptimal strategies. We develop a new approach to learning the parameters of the behavioral model of a bounded rational attacker (thereby pinpointing a near optimal strategy), by observing how the attacker responds to only three defender strategies. We also validate our approach using experiments on real and synthetic data.

ICML Conference 2016 Conference Paper

Truthful Univariate Estimators

• Ioannis Caragiannis
• Ariel D. Procaccia
• Nisarg Shah 0001

We revisit the classic problem of estimating the population mean of an unknown single-dimensional distribution from samples, taking a game-theoretic viewpoint. In our setting, samples are supplied by strategic agents, who wish to pull the estimate as close as possible to their own value. In this setting, the sample mean gives rise to manipulation opportunities, whereas the sample median does not. Our key question is whether the sample median is the best (in terms of mean squared error) truthful estimator of the population mean. We show that when the underlying distribution is symmetric, there are truthful estimators that dominate the median. Our main result is a characterization of worst-case optimal truthful estimators, which provably outperform the median, for possibly asymmetric distributions with bounded support.

AIJ Journal 2016 Journal Article

Voting rules as error-correcting codes

• Ariel D. Procaccia
• Nisarg Shah
• Yair Zick

TCS Journal 2015 Journal Article

An improved 2-agent kidney exchange mechanism

• Ioannis Caragiannis
• Aris Filos-Ratsikas
• Ariel D. Procaccia

IJCAI Conference 2015 Conference Paper

Impartial Peer Review

• David Kurokawa
• Omer Lev
• Jamie Morgenstern
• Ariel D. Procaccia

Motivated by a radically new peer review system that the National Science Foundation recently experimented with, we study peer review systems in which proposals are reviewed by PIs who have submitted proposals themselves. An (m, k)-selection mechanism asks each PI to review m proposals, and uses these reviews to select (at most) k proposals. We are interested in impartial mechanisms, which guarantee that the ratings given by a PI to others’ proposals do not affect the likelihood of the PI’s own proposal being selected. We design an impartial mechanism that selects a k-subset of proposals that is nearly as highly rated as the one selected by the non-impartial (abstract version of) the NSF pilot mechanism, even when the latter mechanism has the “unfair” advantage of eliciting honest reviews.

IJCAI Conference 2015 Conference Paper

Influence in Classification via Cooperative Game Theory

• Amit Datta
• Anupam Datta
• Ariel D. Procaccia
• Yair Zick

A dataset has been classified by some unknown classifier into two types of points. What were the most important factors in determining the classification outcome? In this work, we employ an axiomatic approach in order to uniquely characterize an influence measure: a function that, given a set of classified points, outputs a value for each feature corresponding to its influence in determining the classification outcome. We show that our influence measure takes on an intuitive form when the unknown classifier is linear. Finally, we employ our influence measure in order to analyze the effects of user profiling on Google’s online display advertising.

IJCAI Conference 2015 Conference Paper

Learning Cooperative Games

• Maria Florina Balcan
• Ariel D. Procaccia
• Yair Zick

This paper explores a PAC (probably approximately correct) learning model in cooperative games. Specifically, we are given m random samples of coalitions and their values, taken from some unknown cooperative game; can we predict the values of unseen coalitions? We study the PAC learnability of several well-known classes of cooperative games, such as network flow games, threshold task games, and induced subgraph games. We also establish a novel connection between PAC learnability and core stability: for games that are efficiently learnable, it is possible to find payoff divisions that are likely to be stable using a polynomial number of samples.

AIJ Journal 2015 Journal Article

Optimal social choice functions: A utilitarian view

• Craig Boutilier
• Ioannis Caragiannis
• Simi Haber
• Tyler Lu
• Ariel D. Procaccia
• Or Sheffet

IJCAI Conference 2015 Conference Paper

Ranked Voting on Social Networks

• Ariel D. Procaccia
• Nisarg Shah
• Eric Sodomka

Classic social choice theory assumes that votes are independent (but possibly conditioned on an underlying objective ground truth). This assumption is unrealistic in settings where the voters are connected via an underlying social network structure, as social interactions lead to correlated votes. We establish a general framework — based on random utility theory — for ranked voting on a social network with arbitrarily many alternatives (in contrast to previous work, which is restricted to two alternatives). We identify a family of voting rules which, without knowledge of the social network structure, are guaranteed to recover the ground truth with high probability in large networks, with respect to a wide range of models of correlation among input votes.

IJCAI Conference 2013 Conference Paper

Audit Games

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

Effective enforcement of laws and policies requires expending resources to prevent and detect offenders, as well as appropriate punishment schemes to deter violators. In particular, enforcement of privacy laws and policies in modern organizations that hold large volumes of personal information (e. g. , hospitals, banks) relies heavily on internal audit mechanisms. We study economic considerations in the design of these mechanisms, focusing in particular on effective resource allocation and appropriate punishment schemes. We present an audit game model that is a natural generalization of a standard security game model for resource allocation with an additional punishment parameter. Computing the Stackelberg equilibrium for this game is challenging because it involves solving an optimization problem with non-convex quadratic constraints. We present an additive FPTAS that efficiently computes the solution.

IJCAI Conference 2013 Conference Paper

Defender (Mis)Coordination in Security Games

• Albert Xin Jiang
• Ariel D. Procaccia
• Yundi Qian
• Nisarg Shah
• Milind Tambe

We study security games with multiple defenders. To achieve maximum security, defenders must perfectly synchronize their randomized allocations of resources. However, in real-life scenarios (such as protection of the port of Boston) this is not the case. Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically and empirically. We introduce two notions that capture this loss under different assumptions: the price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely high in the worst case, while our simulations establish a smaller yet significant loss in practice.

IJCAI Conference 2013 Conference Paper

Externalities in Cake Cutting

• Simina Branzei
• Ariel D. Procaccia
• Jie Zhang

The cake cutting problem models the fair division of a heterogeneous good between multiple agents. Previous work assumes that each agent derives value only from its own piece. However, agents may also care about the pieces assigned to other agents; such externalities naturally arise in fair division settings. We extend the classical model to capture externalities, and generalize the classical fairness notions of proportionality and envyfreeness. Our technical results characterize the relationship between these generalized properties, establish the existence or nonexistence of fair allocations, and explore the computational feasibility of fairness in the face of externalities.

UAI Conference 2012 Conference Paper

A Maximum Likelihood Approach For Selecting Sets of Alternatives

• Ariel D. Procaccia
• Sashank J. Reddi
• Nisarg Shah 0001

We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.

AIJ Journal 2012 Journal Article

Algorithms for strategyproof classification

• Reshef Meir
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

UAI Conference 2012 Conference Paper

Bayesian Vote Manipulation: Optimal Strategies and Impact on Welfare

• Tyler Lu
• Pingzhong Tang
• Ariel D. Procaccia
• Craig Boutilier

Most analyses of manipulation of voting schemes have adopted two assumptions that greatly diminish their practical import. First, it is usually assumed that the manipulators have full knowledge of the votes of the nonmanipulating agents. Second, analysis tends to focus on the probability of manipulation rather than its impact on the social choice objective (e.g., social welfare). We relax both of these assumptions by analyzing optimal Bayesian manipulation strategies when the manipulators have only partial probabilistic information about nonmanipulator votes, and assessing the expected loss in social welfare (in the broad sense of the term). We present a general optimization framework for the derivation of optimal manipulation strategies given arbitrary voting rules and distributions over preferences. We theoretically and empirically analyze the optimal manipulability of some popular voting rules using distributions and real data sets that go well beyond the common, but unrealistic, impartial culture assumption. We also shed light on the stark difference between the loss in social welfare and the probability of manipulation by showing that even when manipulation is likely, impact to social welfare is slight (and often negligible).

AIJ Journal 2012 Journal Article

On the approximability of Dodgson and Young elections

• Ioannis Caragiannis
• Jason A. Covey
• Michal Feldman
• Christopher M. Homan
• Christos Kaklamanis
• Nikos Karanikolas
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

AAMAS Conference 2011 Conference Paper

Incentive Design for Adaptive Agents

• Yiling Chen
• Jerry Kung
• David C. Parkes
• Ariel D. Procaccia
• Haoqi Zhang

We consider a setting in which a principal seeks to induce an adaptive agent to select a target action by providing incentives on one or more actions. The agent maintains a belief about the value for each action-which may update based on experience-and selects at each time step the action with the maximal sum of value and associated incentive. The principal observes the agent's selection, but has no information about the agent's current beliefs or belief update process. For inducing the target action as soon as possible, or as often as possible over a fixed time period, it is optimal for a principal with a per-period budget to assign the budget to the target action and wait for the agent to want to make that choice. But with an across-period budget, no algorithm can provide good performance on all instances without knowledge of the agent's update process, except in the particular case in which the goal is to induce the agent to select the target action once. We demonstrate ways to overcome this strong negative result with knowledge about the agent's beliefs, by providing a tractable algorithm for solving the offline problem when the principal has perfect knowledge, and an analytical solution for an instance of the problem in which partial knowledge is available.

TARK Conference 2011 Conference Paper

Sum of us: strategyproof selection from the selectors

• Noga Alon
• Felix A. Fischer
• Ariel D. Procaccia
• Moshe Tennenholtz

We consider the special case of approval voting when the set of agents and the set of alternatives coincide. This captures situations in which the members of an organization want to elect a president or a committee from their ranks, as well as a variety of problems in networked environments, for example in internet search, social networks like Twitter, or reputation systems like Epinions. More precisely, we look at a setting where each member of a set of n agents approves or disapproves of any other member of the set and we want to select a subset of k agents, for a given value of k, in a strategyproof and approximately efficient way. Here, strategyproofness means that no agent can improve its own chances of being selected by changing the set of other agents it approves. A mechanism is said to provide an approximation ratio of α for some α ≥ 1 if the ratio between the sum of approval scores of any set of size k and that of the set selected by the mechanism is always at most α. We show that for k ∈ {1, 2, .. ., n − 1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. We then present a randomized strategyproof mechanism that provides an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.

IJCAI Conference 2011 Conference Paper

Towards More Expressive Cake Cutting

• Ioannis Caragiannis
• John K. Lai
• Ariel D. Procaccia

Cake cutting is a playful name for the problem of fairly dividing a heterogeneous divisible good among a set of agents. The agent valuations for different pieces of cake are typically assumed to be additive. However, in certain practical settings this assumption is invalid because agents may not have positive value for arbitrarily small "crumbs" of cake. In this paper, we propose a new, more expressive model of agent valuations that captures this feature. We present an approximately proportional algorithm for any number of agents that have such expressive valuations. The algorithm is optimal in the sense that no other algorithm can guarantee a greater worst-case degree of proportionality. We also design an optimal approximately proportional and fully envy-free algorithm for two agents.

AIJ Journal 2011 Journal Article

Voting almost maximizes social welfare despite limited communication

• Ioannis Caragiannis
• Ariel D. Procaccia

IJCAI Conference 2009 Conference Paper

• Reshef Meir
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

Strategyproof classification deals with a setting where a decision-maker must classify a set of input points with binary labels, while minimizing the expected error. The labels of the input points are reported by self-interested agents, who might lie in order to obtain a classifier that more closely matches their own labels, thus creating a bias in the data; this motivates the design of truthful mechanisms that discourage false reports. Previous work [Meir et al. , 2008] investigated both decisiontheoretic and learning-theoretic variations of the setting, but only considered classifiers that belong to a degenerate class. In this paper we assume that the agents are interested in a shared set of input points. We show that this plausible assumption leads to powerful results. In particular, we demonstrate that variations of a truthful random dictator mechanism can guarantee approximately optimal outcomes with respect to any class of classifiers.

IJCAI Conference 2009 Conference Paper

• Alon Altman
• Ariel D. Procaccia
• Moshe Tennenholtz

A tournament is a binary dominance relation on a set of alternatives. Tournaments arise in many contexts that are relevant to AI, most notably in voting (as a method to aggregate the preferences of agents). There are many works that deal with choice rules that select a desirable alternative from a tournament, but very few of them deal directly with incentive issues, despite the fact that gametheoretic considerations are crucial with respect to systems populated by selfish agents. We deal with the problem of the manipulation of choice rules by considering two types of manipulation. We say that a choice rule is monotonic if an alternative cannot get itself selected by losing on purpose, and pairwise nonmanipulable if a pair of alternatives cannot make one of them the winner by reversing the outcome of the match between them. Our main result is a combinatorial construction of a choice rule that is monotonic, pairwise nonmanipulable, and onto the set of alternatives, for any number of alternatives besides three.

IJCAI Conference 2009 Conference Paper

• Ariel D. Procaccia

The problem of fairly dividing a cake (as a metaphor for a heterogeneous divisible good) has been the subject of much interest since the 1940’s, and is of importance in multiagent resource allocation. Two fairness criteria are usually considered: proportionality, in the sense that each of the n agents receives at least 1/n of the cake; and the stronger property of envy-freeness, namely that each agent prefers its own piece of cake to the others’ pieces. For proportional division, there are algorithms that require O(n log n) steps, and recent lower bounds imply that one cannot do better. In stark contrast, known (discrete) algorithms for envy-free division require an unbounded number of steps, even when there are only four agents. In this paper, we give an Ω(n2 ) lower bound for the number of steps required by envy-free cake-cutting algorithms. This result provides, for the first time, a true separation between envy-free and proportional division, thus giving a partial explanation for the notorious difficulty of the former problem.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Michael Zuckerman
• Ariel D. Procaccia
• Vincent Conitzer
• Jeffrey S. Rosenschein

Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.

AIJ Journal 2009 Journal Article

Algorithms for the coalitional manipulation problem

• Michael Zuckerman
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

SODA Conference 2009 Conference Paper

On the approximability of Dodgson and Young elections

• Ioannis Caragiannis
• Jason A. Covey
• Michal Feldman
• Christopher M. Homan
• Christos Kaklamanis
• Nikos Karanikolas
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

AIJ Journal 2009 Journal Article

The learnability of voting rules

• Ariel D. Procaccia
• Aviv Zohar
• Yoni Peleg
• Jeffrey S. Rosenschein

SODA Conference 2008 Conference Paper

Algorithms for the coalitional manipulation problem

• Michael Zuckerman
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

SODA Conference 2008 Conference Paper

Incentive compatible regression learning

• Ofer Dekel
• Felix A. Fischer
• Ariel D. Procaccia

IJCAI Conference 2007 Conference Paper

• Ariel D. Procaccia
• Yoram Bachrach
• Jeffrey S. Rosenschein

Decentralized Reputation Systems have recently emerged as a prominent method of establishing trust among self-interested agents in online environments. A key issue is the efficient aggregation of data in the system; several approaches have been proposed, but they are plagued by major shortcomings. We put forward a novel, decentralized data management scheme grounded in gossip-based algorithms. Rumor mongering is known to possess algorithmic advantages, and indeed, our framework inherits many of their salient features: scalability, robustness, globality, and simplicity. We also demonstrate that our scheme motivates agents to maintain a sparkling clean reputation, and is inherently impervious to certain kinds of attacks.

IJCAI Conference 2007 Conference Paper

• Ariel D. Procaccia
• Jeffrey S. Rosenschein
• Aviv Zohar

Although recent years have seen a surge of interest in the computational aspects of social choice, no attention has previously been devoted to elections with multiple winners, e. g. , elections of an assembly or committee. In this paper, we fully characterize the worst-case complexity of manipulation and control in the context of four prominent multi-winner voting systems. Additionally, we show that several tailor-made multi-winner voting schemes are impractical, as it is NP-hard to select the winners in these schemes.

AAMAS Conference 2007 Conference Paper

A Computational Characterization of Multiagent Games with Fallacious Rewards

• Ariel D. Procaccia
• Jeffrey S. Rosenschein

Agents engaged in noncooperative interaction may seek to achieve a Nash equilibrium; this requires that agents be aware of others' rewards. Misinformation about rewards leads to a gap between the real interaction model–the explicit game–and the game that the agents perceive–the implicit game.

AAMAS Conference 2007 Conference Paper

Average-Case Tractability of Manipulation in Voting via the Fraction of Manipulators

• Ariel D. Procaccia
• Jeffrey S. Rosenschein

Recent results have established that a variety of voting rules are computationally hard to manipulate in the worst-case; this arguably provides some guarantee of resistance to ma- nipulation when the voters have bounded computational power. Nevertheless, it has become apparent that a truly dependable obstacle to manipulation can only be provided by voting rules that are average-case hard to manipulate.

AAAI Conference 2007 Conference Paper

Learning Voting Trees

• Ariel D. Procaccia
• Yoni Peleg

Binary voting trees provide a succinct representation for a large and prominent class of voting rules. In this paper, we investigate the PAC-learnability of this class of rules. We show that, while in general a learning algorithm would require an exponential number of samples, if the number of leaves is polynomial in the size of the set of alternatives then a polynomial training set suffices. We apply these results in an emerging theory: automated design of voting rules by learning.

AAMAS Conference 2007 Conference Paper

On the Robustness of Preference Aggregation in Noisy Environments

• Ariel D. Procaccia
• Jeffrey S. Rosenschein
• Gal A. Kaminka

In an election held in a noisy environment, agents may unintentionally perturb the outcome by communicating faulty preferences. We investigate this setting by introducing a theoretical model of noisy preference aggregation and formally defining the (worst-case) robustness of a voting rule. We use our model to analytically bound the robustness of various prominent rules. The results show that the robustness of voting rules is diverse, with different rules positioned at either end of the spectrum. These results allow selection of voting rules that support preference aggregation in the face of noise.

EUMAS Conference 2005 Conference Paper

Extensive-Form Argumentation Games

• Ariel D. Procaccia
• Jeffrey S. Rosenschein

EUMAS Conference 2005 Conference Paper

Junta Distributions and the Average-Case Complexity of Manipulating Elections

• Ariel D. Procaccia
• Jeffrey S. Rosenschein

EUMAS Conference 2005 Conference Paper

Learning to Identify Winning Coalitions in the PAC model

• Ariel D. Procaccia
• Jeffrey S. Rosenschein

EUMAS Conference 2005 Conference Paper

The Communication Complexity of Coalition Formation Among Autonomous Agents

• Ariel D. Procaccia
• Jeffrey S. Rosenschein