Edith Elkind

AIJ Journal 2026 Journal Article

Proportional justified representation

• Luis Sánchez-Fernández
• Edith Elkind
• Martin Lackner
• Norberto Fernández García
• Jesús A. Fisteus
• Pablo Basanta Val
• Piotr Skowron

AIJ Journal 2026 Journal Article

Settling the score: Portioning with cardinal preferences

• Edith Elkind
• Matthias Greger
• Patrick Lederer
• Warut Suksompong
• Nicholas Teh

IJCAI Conference 2025 Conference Paper

Not in My Backyard! Temporal Voting Over Public Chores

• Edith Elkind
• Tzeh Yuan Neoh
• Nicholas Teh

We study a temporal voting model where voters have dynamic preferences over a set of public chores---projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.

AAMAS Conference 2025 Conference Paper

Selecting Interlacing Committees

• Chris Dong
• Martin Bullinger
• Tomasz Was
• Larry Birnbaum
• Edith Elkind

Polarization is a major concern for a well-functioning society. Often, mass polarization of a society is driven by polarizing political representation, even when the latter is easily preventable. The existing computational social choice methods for the task of committee selection are not designed to address this issue. We enrich the standard approach to committee selection by defining two quantitative measures that evaluate how well a given committee interconnects the voters. Maximizing these measures aims at avoiding polarizing committees. While the corresponding maximization problems are NP-complete in general, we obtain efficient algorithms for profiles in the voter-candidate interval domain. Moreover, we analyze the compatibility of our goals with other representation objectives, such as excellence, diversity, and proportionality. We identify tradeoffs between approximation guarantees, and describe algorithms that achieve simultaneous constant-factor approximations.

AAMAS Conference 2025 Conference Paper

Temporal Fair Division of Indivisible Items

• Edith Elkind
• Alexander Lam
• Mohamad Latifian
• Tzeh Yuan Neoh
• Nicholas Teh

We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results for achieving approximate envy-freeness under the assumption that agents have no information about future items. In contrast, we assume that the algorithm has complete knowledge of the future, and aim to ensure that the cumulative allocation at each round satis�es approximate envy-freeness, which we de�ne as temporal envy-freeness up to one item (TEF1). We focus on settings where items are exclusively goods or exclusively chores. For goods, while TEF1 allocations may fail to exist, we identify several special cases where they do—two agents, two item types, generalized binary valuations, unimodal preferences—and provide polynomial-time algorithms for these cases. We also prove that determining the existence of a TEF1 allocation is NP-hard. For chores, we obtain analogous results for the special cases, but present a slightly weaker intractability result. We also show that TEF1 is incompatible with Pareto optimality, with the implication that it is intractable to�nd a TEF1 allocation that maximizes any? -mean welfare, even for two agents.

AAMAS Conference 2025 Conference Paper

Towards Fair and Efficient Public Transportation: A Bus Stop Model

• Martin Bullinger
• Edith Elkind
• Mohamad Latifian

We consider a stylized formal model of public transportation, where a set of agents need to travel along a given road, and there is a bus that runs the length of this road. Each agent has a left terminal and a right terminal between which they wish to travel; they can walk all the way, or walk to/from the nearest stop and use the bus for the rest of their journey. The bus can make a fixed number of stops, and the planner needs to select locations for these stops. We study notions of efficiency and fairness for this setting. First, we give a polynomial-time algorithm for computing a solution that minimizes the total travel time; our approach can capture further extensions of the base model, such as more general cost functions or existing infrastructure. Second, we develop a polynomial-time algorithm that outputs solutions with provable fairness guarantees (such as a variant of the justified representation axiom or 2-approximate core). Our simulations indicate that our algorithm almost always outputs fair solutions, even for parameter regimes that do not admit theoretical guarantees.

AAAI Conference 2025 Conference Paper

Verifying Proportionality in Temporal Voting

• Edith Elkind
• Svetlana Obraztsova
• Jannik Peters
• Nicholas Teh

We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms.

ECAI Conference 2024 Conference Paper

Multiwinner Temporal Voting with Aversion to Change

• Valentin Zech
• Niclas Boehmer
• Edith Elkind
• Nicholas Teh

We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin–Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e. g. , we investigate the average number of changes in the committee as a function of changes in voters’ preferences and the role of ties.

ICLR Conference 2024 Conference Paper

Select to Perfect: Imitating desired behavior from large multi-agent data

• Tim Franzmeyer
• Edith Elkind
• Philip H. S. Torr
• Jakob N. Foerster
• João F. Henriques

AI agents are commonly trained with large datasets of demonstrations of human behavior. However, not all behaviors are equally safe or desirable. Desired characteristics for an AI agent can be expressed by assigning desirability scores, which we assume are not assigned to individual behaviors but to collective trajectories. For example, in a dataset of vehicle interactions, these scores might relate to the number of incidents that occurred. We first assess the effect of each individual agent's behavior on the collective desirability score, e.g., assessing how likely an agent is to cause incidents. This allows us to selectively imitate agents with a positive effect, e.g., only imitating agents that are unlikely to cause incidents. To enable this, we propose the concept of an agent's \textit{Exchange Value}, which quantifies an individual agent's contribution to the collective desirability score. The Exchange Value is the expected change in desirability score when substituting the agent for a randomly selected agent. We propose additional methods for estimating Exchange Values from real-world datasets, enabling us to learn desired imitation policies that outperform relevant baselines. The project website can be found at https://tinyurl.com/select-to-perfect.

AAMAS Conference 2024 Conference Paper

Selecting Representative Bodies: An Axiomatic View

• Manon Revel
• Niclas Boehmer
• Rachael Colley
• Markus Brill
• Piotr Faliszewski
• Edith Elkind

As the world’s democratic institutions are challenged by dissatisfied citizens, political scientists and computer scientists have proposed and analyzed various (innovative) methods to select representative bodies, a crucial task in every democracy. However, a unified framework to analyze and compare different selection mechanisms is largely missing. To address this gap, we advocate employing concepts and tools from computational social choice to devise a model in which different selection mechanisms can be formalized. Such a model would allow for conceptualizing and evaluating desirable representation axioms. We make the first step in this direction by proposing a unifying mathematical formulation of different selection mechanisms as well as various social-choice-inspired axioms such as proportionality and monotonicity.

ECAI Conference 2024 Conference Paper

Temporal Elections: Welfare, Strategyproofness, and Proportionality

• Edith Elkind
• Tzeh Yuan Neoh
• Nicholas Teh

We investigate a model of sequential decision-making where a single alternative is chosen at each round. We focus on two objectives—utilitarian welfare (UTIL) and egalitarian welfare (EGAL)—and consider the computational complexity of the associated maximization problems, as well as their compatibility with strategyproofness and proportionality. We observe that maximizing UTIL is easy, but the corresponding decision problem for EGAL is NP-complete even in restricted cases. We complement this hardness result for EGAL with parameterized complexity analysis and an approximation algorithm. Additionally, we show that, while a mechanism that outputs a UTIL outcome is strategyproof, all deterministic mechanisms for computing EGAL outcomes fail a very weak variant of strategyproofness, called non-obvious manipulability (NOM). However, we show that when agents have non-empty approval sets at each timestep, choosing an EGAL-maximizing outcome while breaking ties lexicographically satisfies NOM. Regarding proportionality, we prove that a proportional (PROP) outcome can be computed efficiently, but finding an outcome that maximizes UTIL while guaranteeing PROP is NP-hard. We also derive upper and lower bounds on the price of proportionality with respect to UTIL and EGAL.

AAAI Conference 2024 Conference Paper

Temporal Fairness in Multiwinner Voting

• Edith Elkind
• Svetlana Obraztsova
• Nicholas Teh

Multiwinner voting captures a wide variety of settings, from parliamentary elections in democratic systems to product placement in online shopping platforms. There is a large body of work dealing with axiomatic characterizations, computational complexity, and algorithmic analysis of multiwinner voting rules. Although many challenges remain, significant progress has been made in showing existence of fair and representative outcomes as well as efficient algorithmic solutions for many commonly studied settings. However, much of this work focuses on single-shot elections, even though in numerous real-world settings elections are held periodically and repeatedly. Hence, it is imperative to extend the study of multiwinner voting to temporal settings. Recently, there have been several efforts to address this challenge. However, these works are difficult to compare, as they model multi-period voting in very different ways. We propose a unified framework for studying temporal fairness in this domain, drawing connections with various existing bodies of work, and consolidating them within a general framework. We also identify gaps in existing literature, outline multiple opportunities for future work, and put forward a vision for the future of multiwinner voting in temporal settings.

AAAI Conference 2024 Conference Paper

Unravelling Expressive Delegations: Complexity and Normative Analysis

• Giannis Tyrovolas
• Andrei Constantinescu
• Edith Elkind

We consider binary group decision-making under a rich model of liquid democracy: agents submit ranked delegation options, where each option may be a function of multiple agents' votes; e.g., "I vote yes if a majority of my friends vote yes." Such ballots are unravelled into a profile of direct votes by selecting one entry from each ballot so as not to introduce cyclic dependencies. We study delegation via monotonic Boolean functions, and two unravelling procedures: MinSum, which minimises the sum of the ranks of the chosen entries, and its egalitarian counterpart, MinMax. We provide complete computational dichotomies: MinSum is hard to compute (and approximate) as soon as any non-trivial functions are permitted, and polynomial otherwise; for MinMax the easiness results extend to arbitrary-arity logical ORs and ANDs taken in isolation, but not beyond. For the classic model of delegating to individual agents, we give asymptotically near-tight algorithms for carrying out the two procedures and efficient algorithms for finding optimal unravellings with the highest vote count for a given alternative. These algorithms inspire novel tie-breaking rules for the setup of voting to change a status quo. We then introduce a new axiom, which can be viewed as a variant of the participation axiom, and use algorithmic techniques developed earlier in the paper to show that it is satisfied by MinSum and a lexicographic refinement of MinMax (but not MinMax itself).

AAMAS Conference 2024 Conference Paper

Verifying Proportionality in Temporal Voting

• Edith Elkind
• Svetlana Obraztsova
• Nicholas Teh

We study a model of multiwinner voting where candidates are selected sequentially in rounds over a time horizon. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the standard single-round multiwinner election case to the temporal setting. In our work, we focus on the complexity of verifying whether a given outcome is proportional. We show that the temporal setting is strictly harder than the standard single-round model of multiwinner voting, but identify natural special cases that enable efficient verification.

TCS Journal 2023 Journal Article

Justifying groups in multiwinner approval voting

• Edith Elkind
• Piotr Faliszewski
• Ayumi Igarashi
• Pasin Manurangsi
• Ulrike Schmidt-Kraepelin
• Warut Suksompong

AAMAS Conference 2023 Conference Paper

k -Prize Weighted Voting Game

• Wei-Chen Lee
• David Hyland
• Alessandro Abate
• Edith Elkind
• Jiarui Gan
• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

We introduce a natural variant of weighted voting games, which we refer to as 𝑘-Prize Weighted Voting Games. Such games consist of 𝑛 players with weights, and 𝑘 prizes, of possibly differing values. The players form coalitions, and the 𝑖-th largest coalition (by the sum of weights of its members) wins the 𝑖-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.

AAMAS Conference 2023 Conference Paper

Proportionality in Multiwinner Voting: The Power of Local Search

• Edith Elkind

In multiwinner voting, voters report their preferences over the available alternatives, and the goal is to select a fixed-size subset of alternatives, usually referred to as a committee; this model captures a variety of real-life scenarios, from selecting a representative governing body to deciding which search results should appear on the first page of a search engine’s output or selecting validators for a proof-of-stake blockchain protocol. A particularly well-studied special case of this general setting is multiwinner voting with approval ballots, where each voter reports which alternatives they approve. A key desideratum in multiwinner voting is proportionality, i. e. , assuring that large groups of voters with similar preferences receive appropriate representation in the selected committee. In the context of approval ballots, a series of papers proposed a family of axioms that aim to capture this intuition, including (from weakest to strongest) justified representation, proportional/extended/full justified representation, and the core. A major research challenge, then, is to identify voting rules that are efficiently computable and whose outputs satisfy these axioms; another important goal is to design efficient verification methods that can decide whether a given committee satisfies an axiom. In this talk, we will survey recent progress on these challenges, compare the properties of several multiwinner voting rules with strong axiomatic properties, discuss tradeoffs between proportionality and other objectives (such as, e. g. , social welfare), and highlight the power of local search to produce high-quality, easily verifiable solutions in a robust and flexible manner.

ECAI Conference 2023 Conference Paper

Settling the Score: Portioning with Cardinal Preferences

• Edith Elkind
• Warut Suksompong
• Nicholas Teh

We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a division of the resource. We consider two families of aggregation rules for this setting—those based on coordinate-wise aggregation and those that optimize some notion of welfare—as well as the recently proposed Independent Markets mechanism. We provide a detailed analysis of these rules from an axiomatic perspective, both for classic axioms, such as strategyproofness and Pareto optimality, and for novel axioms, which aim to capture proportionality in this setting. Our results indicate that a simple rule that computes the average of all proposals satisfies many of our axioms, including some that are violated by more sophisticated rules.

IJCAI Conference 2022 Conference Paper

Better Collective Decisions via Uncertainty Reduction

• Shiri Alouf-Heffetz
• Laurent Bulteau
• Edith Elkind
• Nimrod Talmon
• Nicholas Teh

We consider an agent community wishing to decide on several binary issues by means of issue-by-issue majority voting. For each issue and each agent, one of the two options is better than the other. However, some of the agents may be confused about some of the issues, in which case they may vote for the option that is objectively worse for them. A benevolent external party wants to help the agents to make better decisions, i. e. , select the majority-preferred option for as many issues as possible. This party may have one of the following tools at its disposal: (1) educating some of the agents, so as to enable them to vote correctly on all issues, (2) appointing a subset of highly competent agents to make decisions on behalf of the entire group, or (3) guiding the agents on how to delegate their votes to other agents, in a way that is consistent with the agents' opinions. For each of these tools, we study the complexity of the decision problem faced by this external party, obtaining both NP-hardness results and fixed-parameter tractability results.

AAAI Conference 2022 Conference Paper

Complexity of Deliberative Coalition Formation

• Edith Elkind
• Abheek Ghosh
• Paul Goldberg

Elkind et al. (2021) introduced a model for deliberative coalition formation, where a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. In their model, agents and proposals are points in a metric space, agents’ preferences are determined by distances, and agents deliberate by dynamically forming coalitions around proposals that they prefer over the status quo. The deliberation process operates via kcompromise transitions, where agents from k (current) coalitions come together to form a larger coalition in order to support a (perhaps new) proposal, possibly leaving behind some of the dissenting agents from their old coalitions. A deliberation succeeds if it terminates by identifying a proposal with the largest possible support. For deliberation in d dimensions, Elkind et al. consider two variants of their model: in the Euclidean model, proposals and agent locations are points in Rd and the distance is measured according to || · ||2; and in the hypercube model, proposals and agent locations are vertices of the d-dimensional hypercube and the metric is the Hamming distance. They show that in the Euclidean model 2compromises are guaranteed to succeed, but in the hypercube model for deliberation to succeed it may be necessary to use k-compromises with k ≥ d. We complement their analysis by (1) proving that in both models it is hard to find a proposal with a high degree of support, and even a 2-compromise transition may be hard to compute; (2) showing that a sequence of 2-compromise transitions may be exponentially long; (3) strengthening the lower bound on the size of the compromise for the d-hypercube model from d to 2Ω(d).

IJCAI Conference 2022 Conference Paper

Contests to Incentivize a Target Group

• Edith Elkind
• Abheek Ghosh
• Paul W. Goldberg

We study how to incentivize agents in a target subpopulation to produce a higher output by means of rank-order allocation contests, in the context of incomplete information. We describe a symmetric Bayes--Nash equilibrium for contests that have two types of rank-based prizes: (1) prizes that are accessible only to the agents in the target group; (2) prizes that are accessible to everyone. We also specialize this equilibrium characterization to two important sub-cases: (i) contests that do not discriminate while awarding the prizes, i. e. , only have prizes that are accessible to everyone; (ii) contests that have prize quotas for the groups, and each group can compete only for prizes in their share. For these models, we also study the properties of the contest that maximizes the expected total output by the agents in the target group.

AIJ Journal 2022 Journal Article

Defense coordination in security games: Equilibrium analysis and mechanism design

• Jiarui Gan
• Edith Elkind
• Sarit Kraus
• Michael Wooldridge

ICML Conference 2022 Conference Paper

Exact Learning of Preference Structure: Single-peaked Preferences and Beyond

• Sonja Kraiczy
• Edith Elkind

We consider the setting where the members of a society (voters) have preferences over candidates, and the candidates can be ordered on an axis so that the voters’ preferences are single-peaked on this axis. We ask whether this axis can be identified by sampling the voters’ preferences. For several natural distributions, we obtain tight bounds on the number of samples required and show that, surprisingly, the bounds are independent of the number of candidates. We extend our results to the case where voters’ preferences are sampled from two different axes over the same candidate set (one of which may be known). We also consider two alternative models of learning: (1) sampling pairwise comparisons rather than entire votes, and (2) learning from equivalence queries.

NeurIPS Conference 2022 Conference Paper

Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning

• Niclas Boehmer
• Robert Bredereck
• Edith Elkind
• Piotr Faliszewski
• Stanisław Szufa

We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. For each of them, we give an explicit formula or an efficient algorithm for computing its frequency matrix, which captures the probability that a given candidate appears in a given position in a sampled vote. We use these matrices to draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties. We further develop a general and unified framework for learning the distribution of real-world preferences using the frequency matrices of established vote distributions.

IJCAI Conference 2022 Conference Paper

Explaining Preferences by Multiple Patterns in Voters’ Behavior

• Sonja Kraiczy
• Edith Elkind

In some preference aggregation scenarios, voters' preferences are highly structured: e. g. , the set of candidates may have one-dimensional structure (so that voters' preferences are single-peaked) or be described by a binary decision tree (so that voters' preferences are group-separable). However, sometimes a single axis or a decision tree is insufficient to capture the voters' preferences; rather, there is a small number K of axes or decision trees such that each vote in the profile is consistent with one of these axes (resp. , trees). In this work, we study the complexity of deciding whether voters' preferences can be explained in this manner. For K=2, we use the technique developed by Yang [2020, https: //doi. org/10. 3233/FAIA200099] in the context of single-peaked preferences to obtain a polynomial-time algorithm for several domains: value-restricted preferences, group-separable preferences, and a natural subdomain of group-separable preferences, namely, caterpillar group-separable preferences. For K > 2, the problem is known to be hard for single-peaked preferences; we establish that it is also hard for value-restricted and group-separable preferences. Our positive results for K=2 make use of forbidden minor characterizations of the respective domains; in particular, we establish that the domain of caterpillar group-separable preferences admits a forbidden minor characterization.

AAMAS Conference 2022 Conference Paper

Facility Location With Approval Preferences: Strategyproofness and Fairness

• Edith Elkind
• Minming Li
• Houyu Zhou

We develop a formal model of multiwinner facility location with approval preferences in one dimension: there is a set of facilities, a set of potential locations, and the goal is to build k facilities at these locations. Agents have approval preferences over ‘facility, location’ pairs, and may misreport their preferences if they can benefit from doing so. We consider both unit-demand agents and agents with additive demands, and the social objectives of coverage and utilitarian welfare. We ask whether these social objectives can be satisfied in a computationally efficient and strategyproof way. We also initiate the study of proportional representation in the context of facility location. We show that the axiom of justified representation, which is used to capture proportionality in multiwinner voting with approval preferences, is not well-suited for the facility location setting, and provide a relaxation of this axiom that can handle incompatibilities and may be of broader interest.

JAAMAS Journal 2022 Journal Article

Guest editorial: special issue on fair division

• Edith Elkind
• Nicolas Maudet
• Warut Suksompong

AIJ Journal 2022 Journal Article

Mind the gap: Cake cutting with separation

• Edith Elkind
• Erel Segal-Halevi
• Warut Suksompong

JAIR Journal 2022 Journal Article

Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results

• Dominik Peters
• Lan Yu
• Hau Chan
• Edith Elkind

A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989b) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin–Courant rule for preferences single-peaked on trees. We show that in this setting the egalitarian version of this rule admits a polynomial-time winner determination algorithm. For the utilitarian version, we prove that winner determination remains NP-hard for the Borda scoring function; indeed, this hardness results extends to a large family of scoring functions. However, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We then explore the power and limitations of this framework: we develop polynomial-time algorithms to find trees with the smallest maximum degree, diameter, or pathwidth, but show that it is NP-hard to check whether a given profile is single-peaked on a tree that is isomorphic to a given tree, or on a regular tree.

AAAI Conference 2022 Conference Paper

The Price of Justified Representation

• Edith Elkind
• Piotr Faliszewski
• Ayumi Igarashi
• Pasin Manurangsi
• Ulrike Schmidt-Kraepelin
• Warut Suksompong

In multiwinner approval voting, the goal is to select kmember committees based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of imposing the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding ‘good’ committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets.

IJCAI Conference 2021 Conference Paper

Graphical Cake Cutting via Maximin Share

• Edith Elkind
• Erel Segal-Halevi
• Warut Suksompong

We study the recently introduced cake-cutting setting in which the cake is represented by an undirected graph. This generalizes the canonical interval cake and allows for modeling the division of road networks. We show that when the graph is a forest, an allocation satisfying the well-known criterion of maximin share fairness always exists. Our result holds even when separation constraints are imposed; however, in the latter case no multiplicative approximation of proportionality can be guaranteed. Furthermore, while maximin share fairness is not always achievable for general graphs, we prove that ordinal relaxations can be attained.

IJCAI Conference 2021 Conference Paper

Keep Your Distance: Land Division With Separation

• Edith Elkind
• Erel Segal-Halevi
• Warut Suksompong

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of proportionality is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the ordinal maximin share approximation, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axes-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting.

AAAI Conference 2021 Conference Paper

Mind the Gap: Cake Cutting With Separation

• Edith Elkind
• Erel Segal-Halevi
• Warut Suksompong

We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then establish several computational properties of maximin share fairness—for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i. e. , a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved.

AAAI Conference 2021 Conference Paper

Proportional Representation under Single-Crossing Preferences Revisited

• Andrei Costin Constantinescu
• Edith Elkind

We study the complexity of determining a winning committee under the Chamberlin–Courant voting rule when voters’ preferences are single-crossing on a line, or, more generally, on a tree. For the line, Skowron et al. (2015) describe an O(n2 mk) algorithm (where n, m, k are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to O(nmk). We then improve this bound for k = Ω(log n) by reducing our problem to the k-link path problem for DAGs with concave Monge weights, obtaining a nm2O( √ log k log log n) algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe, and Slinko (2015), and develop a O(nmk) algorithm for this case as well.

AIJ Journal 2021 Journal Article

Protecting elections by recounting ballots

• Edith Elkind
• Jiarui Gan
• Svetlana Obraztsova
• Zinovi Rabinovich
• Alexandros A. Voudouris

AIJ Journal 2021 Journal Article

Schelling games on graphs

• Aishwarya Agarwal
• Edith Elkind
• Jiarui Gan
• Ayumi Igarashi
• Warut Suksompong
• Alexandros A. Voudouris

AAAI Conference 2021 Conference Paper

United for Change: Deliberative Coalition Formation to Change the Status Quo

• Edith Elkind
• Davide Grossi
• Ehud Shapiro
• Nimrod Talmon

We study a setting in which a community wishes to identify a strongly supported proposal from a large space of alternatives, in order to change the status quo. We describe a deliberation process in which agents dynamically form coalitions around proposals that they prefer over the status quo. We formulate conditions on the space of proposals and on the ways in which coalitions are formed that guarantee deliberation to succeed, that is, to terminate by identifying a proposal with the largest possible support. Our results provide theoretical foundations for the analysis of deliberative processes in systems for democratic deliberation support, such as, e. g. , LiquidFeedback or Polis.

UAI Conference 2020 Conference Paper

Election Control by Manipulating Issue Significance

• Andrew Estornell
• Sanmay Das
• Edith Elkind
• Yevgeniy Vorobeychik

Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors. The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control Rothe [2016]. One means of election control that has been proposed, pertinent to the spatial voting model, is to select a subset of issues that determine voter preferences over candidates. We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments. We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues. However, we demonstrate that the problem becomes tractable with a constant number of voters or issues. Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting behavior enables tractable manipulation.

AAAI Conference 2020 Conference Paper

Individual-Based Stability in Hedonic Diversity Games

• Niclas Boehmer
• Edith Elkind

In hedonic diversity games (HDGs), recently introduced by Bredereck, Elkind, and Igarashi (2019), each agent belongs to one of two classes (men and women, vegetarians and meateaters, junior and senior researchers), and agents’ preferences over coalitions are determined by the fraction of agents from their class in each coalition. Bredereck et al. show that while an HDG may fail to have a Nash stable (NS) or a core stable (CS) outcome, every HDG in which all agents have singlepeaked preferences admits an individually stable (IS) outcome, which can be computed in polynomial time. In this work, we extend and strengthen these results in several ways. First, we establish that the problem of deciding if an HDG has an NS outcome is NP-complete, but admits an XP algorithm with respect to the size of the smaller class. Second, we show that, in fact, all HDGs admit IS outcomes that can be computed in polynomial time; our algorithm for finding such outcomes is considerably simpler than that of Bredereck et al. We also consider two ways of generalizing the model of Bredereck et al. to k ≥ 2 classes. We complement our theoretical results by empirical analysis, comparing the IS outcomes found by our algorithm, the algorithm of Bredereck et al. and a natural better-response dynamics.

IJCAI Conference 2020 Conference Paper

Keeping Your Friends Close: Land Allocation with Friends

• Edith Elkind
• Neel Patel
• Alan Tsang
• Yair Zick

We examine the problem of assigning plots of land to prospective buyers who prefer living next to their friends. In this setting, each agent's utility depends on the plot she receives and the identities of the agents who receive the adjacent plots. We are interested in mechanisms without money that guarantee truthful reporting of both land values and friendships, as well as Pareto optimality and computational efficiency. We explore several modifications of the Random Serial Dictatorship (RSD) mechanism, and identify one that performs well according to these criteria, We also study the expected social welfare of the assignments produced by our mechanisms when agents' values for the land plots are binary; it turns out that we can achieve good approximations to the optimal social welfare, but only if the agents value the friendships highly.

AAAI Conference 2020 Conference Paper

On Swap Convexity of Voting Rules

• Svetlana Obraztsova
• Edith Elkind
• Piotr Faliszewski

Obraztsova et al. (2013) have recently proposed an intriguing convexity axiom for voting rules. This axiom imposes conditions on the shape of the sets of elections with a given candidate as a winner. However, this new axiom is both too weak and too strong: it is too weak because it defines a set to be convex if for any two elements of the set some shortest path between them lies within the set, whereas the standard definition of convexity requires all shortest paths between two elements to lie within the set, and it is too strong because common voting rules do not satisfy this axiom. In this paper, we (1) propose several families of voting rules that are convex in the sense of Obraztsova et al. ; (2) put forward a weaker notion of convexity that is satisfied by most common voting rules; (3) prove impossibility results for a variant of this definition that considers all, rather than some shortest paths.

AIJ Journal 2020 Journal Article

Price of Pareto Optimality in hedonic games

• Edith Elkind
• Angelo Fanelli
• Michele Flammini

IJCAI Conference 2020 Conference Paper

Stable Roommate Problem with Diversity Preferences

• Niclas Boehmer
• Edith Elkind

In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences (Bredereck, Elkind, Igarashi, AAMAS'19): each agent belongs to one of the two types (e. g. , juniors and seniors, artists and engineers), and agents’ preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem.

AAAI Conference 2020 Conference Paper

Swap Stability in Schelling Games on Graphs

• Aishwarya Agarwal
• Edith Elkind
• Jiarui Gan
• Alexandros Voudouris

We study a recently introduced class of strategic games that is motivated by and generalizes Schelling’s well-known residential segregation model. These games are played on undirected graphs, with the set of agents partitioned into multiple types; each agent either occupies a node of the graph and never moves away or aims to maximize the fraction of her neighbors who are of her own type. We consider a variant of this model that we call swap Schelling games, where the number of agents is equal to the number of nodes of the graph, and agents may swap positions with other agents to increase their utility. We study the existence, computational complexity and quality of equilibrium assignments in these games, both from a social welfare perspective and from a diversity perspective.

AIJ Journal 2019 Journal Article

Cooperative games with overlapping coalitions: Charting the tractability frontier

• Yair Zick
• Georgios Chalkiadakis
• Edith Elkind
• Evangelos Markakis

IJCAI Conference 2019 Conference Paper

Correlating Preferences and Attributes: Nearly Single-Crossing Profiles

• Foram Lakhani
• Dominik Peters
• Edith Elkind

We use social choice theory to develop correlation coefficients between ranked preferences and an ordinal attribute such as educational attainment or income level. For example, such correlations could be used to formalise statements such as "voters' preferences over parties are better explained by age than by income level". In the literature, preferences that are perfectly explained by a single-dimensional agent attribute are commonly taken to be single-crossing preferences. Thus, to quantify how well an attribute explains preferences, we can order the voters by the value of the attribute and compute how far the resulting ordered profile is from being single-crossing, for various commonly studied distance measures (Kendall tau distance, voter/alternative deletion, etc. ). The goal of this paper is to evaluate the computational feasibility of this approach. To this end, we investigate the complexity of computing these distances, obtaining an essentially complete picture for the distances we consider.

IJCAI Conference 2019 Conference Paper

Fairness Towards Groups of Agents in the Allocation of Indivisible Items

• Nawal Benabbou
• Mithun Chakraborty
• Edith Elkind
• Yair Zick

In this paper, we study the problem of matching a set of items to a set of agents partitioned into types so as to balance fairness towards the types against overall utility/efficiency. We extend multiple desirable properties of indivisible goods allocation to our model and investigate the possibility and hardness of achieving combinations of these properties, e. g. we prove that maximizing utilitarian social welfare under constraints of typewise envy-freeness up to one item (TEF1) is computationally intractable. We also define a new concept of waste for this setting, show experimentally that augmenting an existing algorithm with a marginal utility maximization heuristic can produce a TEF1 solution with reduced waste, and also provide a polynomial-time algorithm for computing a non-wasteful TEF1 allocation for binary agent-item utilities.

AAMAS Conference 2019 Conference Paper

Hedonic Diversity Games

• Robert Bredereck
• Edith Elkind
• Ayumi Igarashi

We consider a coalition formation setting where each agent belongs to one of the two types, and agents’ preferences over coalitions are determined by the fraction of the agents of their own type in each coalition. This setting differs from the well-studied Schelling’s model in that some agents may prefer homogeneous coalitions, while others may prefer to be members of a diverse group, or a group that mostly consists of agents of the other type. We model this setting as a hedonic game and investigate the existence of stable outcomes using hedonic games solution concepts. We show that a core stable outcome may fail to exist and checking the existence of core stable outcomes is computationally hard. On the other hand, we propose an efficient algorithm to find an individually stable outcome under the natural assumption that agents’ preferences over fractions of the agents of their own type are single-peaked.

IJCAI Conference 2019 Conference Paper

Multigoal Committee Selection

• Maciej Kocot
• Anna Kolonko
• Edith Elkind
• Piotr Faliszewski
• Nimrod Talmon

We study the problem of computing committees that perform well according to several different criteria, which are expressed as committee scoring rules. We analyze the computational complexity of computing such committees and provide an experimental evaluation of the compromise levels that can be achieved between several well-known rules, including k-Borda, SNTV, Bloc, and the Chamberlin--Courant rule.

IJCAI Conference 2019 Conference Paper

Preferences Single-Peaked on a Tree: Sampling and Tree Recognition

• Jakub Sliwinski
• Edith Elkind

In voting theory, impossibility results and computational hardness results are often circumvented by recognising that voters' preferences are not arbitrary, but lie within a restricted domain. Uncovering the structure of the underlying domain often provides useful insights about the nature of the alternative space, and may be helpful in identifying a collective choice. Preferences single-peaked on a tree are an example of a relatively broad domain that nonetheless exhibits several desirable properties. We consider the setting where voters' preferences are independently sampled from rankings that are single-peaked on a given tree, and study the problem of reliably identifying the tree that generated the observed votes. We test our algorithm empirically; to this end, we develop an algorithm to uniformly sample preferences that are single-peaked on a given tree.

IJCAI Conference 2019 Conference Paper

Protecting Elections by Recounting Ballots

• Edith Elkind
• Jiarui Gan
• Svetlana Obraztsova
• Zinovi Rabinovich
• Alexandros A. Voudouris

Complexity of voting manipulation is a prominent topic in computational social choice. In this work, we consider a two-stage voting manipulation scenario. First, a malicious party (an attacker) attempts to manipulate the election outcome in favor of a preferred candidate by changing the vote counts in some of the voting districts. Afterwards, another party (a defender), which cares about the voters' wishes, demands a recount in a subset of the manipulated districts, restoring their vote counts to their original values. We investigate the resulting Stackelberg game for the case where votes are aggregated using two variants of the Plurality rule, and obtain an almost complete picture of the complexity landscape, both from the attacker's and from the defender's perspective.

IJCAI Conference 2019 Conference Paper

Schelling Games on Graphs

• Edith Elkind
• Jiarui Gan
• Ayumi Igarashi
• Warut Suksompong
• Alexandros A. Voudouris

We consider strategic games that are inspired by Schelling's model of residential segregation. In our model, the agents are partitioned into k types and need to select locations on an undirected graph. Agents can be either stubborn, in which case they will always choose their preferred location, or strategic, in which case they aim to maximize the fraction of agents of their own type in their neighborhood. We investigate the existence of equilibria in these games, study the complexity of finding an equilibrium outcome or an outcome with high social welfare, and also provide upper and lower bounds on the price of anarchy and stability. Some of our results extend to the setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.

AIJ Journal 2018 Journal Article

Approximating optimal social choice under metric preferences

• Elliot Anshelevich
• Onkar Bhardwaj
• Edith Elkind
• John Postl
• Piotr Skowron

JAIR Journal 2018 Journal Article

Bounds on the Cost of Stabilizing a Cooperative Game

• Yoram Bachrach
• Edith Elkind
• Enrico Malizia
• Reshef Meir
• Dmitrii Pasechnik
• Jeffrey S. Rosenschein
• Jörg Rothe
• Michael Zuckerman

A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core---the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.

AAAI Conference 2018 Conference Paper

Cooperative Games With Bounded Dependency Degree

• Ayumi Igarashi
• Rani Izsak
• Edith Elkind

Cooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts tend to be intractable—NP-hard or worse. In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of cooperative games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we observe that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games.

AAAI Conference 2018 Conference Paper

On Recognising Nearly Single-Crossing Preferences

• Florian Jaeckle
• Dominik Peters
• Edith Elkind

If voters’ preferences are one-dimensional, many hard problems in computational social choice become tractable. A preference profile can be classified as one-dimensional if it has the singlecrossing property, which requires that the voters can be ordered from left to right so that their preferences are consistent with this order. In practice, preferences may exhibit some onedimensional structure, despite not being single-crossing in the formal sense. Hence, we ask whether one can identify preference profiles that are close to being single-crossing. We consider three distance measures, which are based on partitioning voters or candidates or performing a small number of swaps in each vote. We prove that it can be efficiently decided if voters can be split into two single-crossing groups. Also, for every fixed k ⩾ 1 we can decide in polynomial time if a profile can be made single-crossing by performing at most k candidate swaps per vote. In contrast, for each k ⩾ 3 it is NP-complete to decide whether candidates can be partitioned into k sets so that the restriction of the input profile to each set is single-crossing.

AAAI Conference 2018 Conference Paper

On the Complexity of Extended and Proportional Justified Representation

• Haris Aziz
• Edith Elkind
• Shenwei Huang
• Martin Lackner
• Luis Sanchez-Fernandez
• Piotr Skowron

We consider the problem of selecting a fixed-size committee based on approval ballots. It is desirable to have a committee in which all voters are fairly represented. Aziz et al. (2015a; 2017) proposed an axiom called extended justified representation (EJR), which aims to capture this intuition; subsequently, Sánchez-Fernández et al. (2017) proposed a weaker variant of this axiom called proportional justified representation (PJR). It was shown that it is coNP-complete to check whether a given committee provides EJR, and it was conjectured that it is hard to find a committee that provides EJR. In contrast, there are polynomial-time computable voting rules that output committees providing PJR, but the complexity of checking whether a given committee provides PJR was an open problem. In this paper, we answer open questions from prior work by showing that EJR and PJR have the same worst-case complexity: we provide two polynomial-time algorithms that output committees providing EJR, yet we show that it is coNP-complete to decide whether a given committee provides PJR. We complement the latter result by fixedparameter tractability results.

AAMAS Conference 2018 Conference Paper

Stackelberg Security Games with Multiple Uncoordinated Defenders

• Jiarui Gan
• Edith Elkind
• Michael Wooldridge

Stackelberg security games have received much attention in recent years. While most existing work focuses on single-defender settings, there are many real-world scenarios that involve multiple defenders (e. g. , multi-national anti-crime actions in international waters, different security agencies patrolling the same area). In this paper, we consider security games with uncoordinated defenders who jointly protect a set of targets, but may have different valuations for these targets; each defender schedules their own resources and selfishly optimizes their own utility. We generalize the standard (single-defender) model of Stackelberg security games to this setting and formulate an equilibrium concept that captures the nature of strategic interaction among the players. We argue that an exact equilibrium may fail to exist, and, in fact, deciding whether it exists is NP-hard. However, under mild assumptions, every multi-defender security game admits an ϵ-equilibrium for every ϵ > 0, and the limit points corresponding to ϵ → 0 can be efficiently approximated.

AAMAS Conference 2017 Conference Paper

Doodle Poll Games

• Svetlana Obraztsova
• Maria Polukarov
• Zinovi Rabinovich
• Edith Elkind

In Doodle polls, each voter approves a subset of the available alternatives according to his preferences. While such polls can be captured by the standard models of Approval voting, Zou et al. [18] analyse real-life Doodle poll data and conclude that poll participants’ behaviour seems to be affected by considerations other than their intrinsic preferences over the alternatives. To capture this phenomenon, they propose a model of social voting, where voters approve their top alternatives as well as additional ‘safe’ choices so as to appear cooperative. The predictions of this model turn out to be consistent with the real-life data. However, Zou et al. do not attempt to rationalise the voters’ behaviour in the context of social voting: they explicitly describe the voters’ strategies rather than explain how these strategies arise from voters’ preferences. In this paper, we complement the work of Zou et al. by putting forward a model in which the behaviour described by Zou et al. arises as an equilibrium strategy. In our model, a voter derives a bonus from approving each additional alternative, up to a certain cap. We show that trembling hand perfect Nash equilibria of our model behave consistently with the model of Zou et al. Importantly, placing a cap on the total bonus is an essential component of our model: in the absence of the cap, all Nash equilibria are very far from the behaviour observed in Doodle polls.

IJCAI Conference 2017 Conference Paper

Fair Division of a Graph

• Sylvain Bouveret
• Katarína Cechlárová
• Edith Elkind
• Ayumi Igarashi
• Dominik Peters

We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e. g. , fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases wherethe underlying graph has simple structure, and/or the number of agents---or, less restrictively, the number of agent types---is small. In particular, despite non-existence results in the general case, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently.

AAAI Conference 2017 Conference Paper

Group Activity Selection on Social Networks

• Ayumi Igarashi
• Dominik Peters
• Edith Elkind

We propose a new variant of the group activity selection problem (GASP), where the agents are placed on a social network and activities can only be assigned to connected subgroups. We show that if multiple groups can simultaneously engage in the same activity, finding a stable outcome is easy as long as the network is acyclic. In contrast, if each activity can be assigned to a single group only, finding stable outcomes becomes intractable, even if the underlying network is very simple: the problem of determining whether a given instance of a GASP admits a Nash stable outcome turns out to be NPhard when the social network is a path, a star, or if the size of each connected component is bounded by a constant. On the other hand, we obtain fixed-parameter tractability results for this problem with respect to the number of activities.

IJCAI Conference 2017 Conference Paper

Manipulating Opinion Diffusion in Social Networks

• Robert Bredereck
• Edith Elkind

We consider opinion diffusion in binary influence networks, where at each step one or more agents update their opinions so as to be in agreement with the majority of their neighbors. We consider several ways of manipulating the majority opinion in a stable outcome, such as bribing agents, adding/deleting links, and changing the order of updates, and investigate the computational complexity of the associated problems, identifying tractable and intractable cases.

AAMAS Conference 2017 Conference Paper

On Parameterized Complexity of Group Activity Selection Problems on Social Networks

• Ayumi Igarashi
• Robert Bredereck
• Edith Elkind

In Group Activity Selection Problem with graph structure (gGASP), players form coalitions to participate in activities and have preferences over pairs of the form (activity, group size); moreover, a group of players can only engage in the same activity if the members of the group form a connected subset of the underlying communication structure. We study the parameterized complexity of finding outcomes of gGASP that are Nash stable, individually stable or core stable. For the parameter ‘number of activities’, we propose an FPT algorithm for Nash stability for the case where the social network is acyclic and obtain a W[1]-hardness result for cliques (i. e. , for classic GASP); similar results hold for individual stability. In contrast, finding a core stable outcome is hard even if the number of activities is bounded by a small constant, both for classic GASP and when the social network is a star. For the parameter ‘number of players’, all problems we consider are in XP for arbitrary social networks; on the other hand, we prove W[1]-hardness results with respect to the parameter ‘number of players’ for the case where the social network is a clique (i. e. , for classic GASP).

AAAI Conference 2017 Conference Paper

Proportional Justified Representation

• Luis S‡nchez-Fern‡ndez
• Edith Elkind
• Martin Lackner
• Norberto Fern‡ndez
• Jesœs Fisteus
• Pablo Basanta Val
• Piotr Skowron

The goal of multi-winner elections is to choose a fixed-size committee based on voters’ preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. Recently, Aziz et al. (2015a; 2017) proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). In this paper, we extend the work of Aziz et al. in several directions. First, we answer an open question of Aziz et al. , by showing that Reweighted Approval Voting satisfies JR for k = 3, 4, 5, but fails it for k ≥ 6. Second, we observe that EJR is incompatible with the Perfect Representation criterion, which is important for many applications of multi-winner voting, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with perfect representation, and a committee that provides PJR can be computed in polynomial time if the committee size divides the number of voters. Moreover, just like EJR, PJR can be used to characterize the classic PAV rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.

IJCAI Conference 2017 Conference Paper

Proportional Rankings

• Piotr Skowron
• Martin Lackner
• Markus Brill
• Dominik Peters
• Edith Elkind

We extend the principle of proportional representation to rankings: given approval preferences, we aim to generate aggregate rankings so that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Such rankings are desirable in situations where initial segments of different lengths may be relevant, e. g. , in recommender systems, for hiring decisions, or for the presentation of competing proposals on a liquid democracy platform. We define what it means for rankings to be proportional, provide bounds for well-known aggregation rules, and experimentally evaluate the performance of these rules.

AAAI Conference 2017 Conference Paper

Social Choice Under Metric Preferences: Scoring Rules and STV

• Piotr Skowron
• Edith Elkind

We consider voting under metric preferences: both voters and candidates are associated with points in a metric space, and each voter prefers candidates that are closer to her to ones that are further away. In this setting, it is often desirable to select a candidate that minimizes the sum of distances to the voters. However, common voting rules operate on voters’ preference rankings and therefore may be unable to identify the best candidate. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of a candidate selected by the rule and that of an optimal candidate. Anshelevich, Bhardwaj and Postl (2015) show that some popular rules such as Borda and Plurality do badly in this regard: their distortion scales linearly with the number of candidates. On the positive side, Anshelevich et al. identify a few voting rules whose distortion is bounded by a constant; however, these rules are rarely used in practice. In this paper, we analyze the distortion of two widely used (classes of) voting rules, namely, scoring rules and Single Transferable Vote (STV). We show that all scoring rules have super-constant distortion, answering a question that was left open by Anshelevich et al. ; however, we identify a scoring rule whose distortion is asymptotically better than that of Plurality and Borda. For STV, we obtain an upper bound of O(ln m), where m is the number of candidates, as well as a super-constant lower bound; thus, STV is a reasonable, though not a perfect rule from this perspective.

IJCAI Conference 2017 Conference Paper

The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality

• Haris Aziz
• Edith Elkind
• Piotr Faliszewski
• Martin Lackner
• Piotr Skowron

We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.

AAAI Conference 2017 Conference Paper

What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain

• Edith Elkind
• Piotr Faliszewski
• Jean-Francois Laslier
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

We visualize aggregate outputs of popular multiwinner voting rules—SNTV, STV, Bloc, k-Borda, Monroe, Chamberlin– Courant, and PAV—for elections generated according to the two-dimensional Euclidean model. We consider three applications of multiwinner voting, namely, parliamentary elections, portfolio/movie selection, and shortlisting, and use our results to understand which of our rules seem to be best suited for each application. In particular, we show that STV (one of the few nontrivial rules used in real high-stake elections) exhibits excellent performance, whereas the Bloc rule (also often used in practice) performs poorly.

AIJ Journal 2016 Journal Article

A hybrid exact algorithm for complete set partitioning

• Tomasz Michalak
• Talal Rahwan
• Edith Elkind
• Michael Wooldridge
• Nicholas R. Jennings

AAMAS Conference 2016 Conference Paper

Complexity of Finding Equilibria of Plurality Voting Under Structured Preferences

• Edith Elkind
• Evangelos Markakis
• Svetlana Obraztsova
• Piotr Skowron

We study the complexity of finding pure Nash equilibria in voting games over well-known restricted preference domains, such as the domains of single-peaked and single-crossing preferences. We focus on the Plurality rule, and, following the recent work of Elkind et al. [15], consider three popular tie-breaking rules (lexicographic, random-candidate, and random-voter) and two types of voters’ attitude: lazy voters, who prefer to abstain when their vote cannot affect the election outcome, and truth-biased voters, who prefer to vote truthfully in such cases. Elkind et al. [15] have shown that for most of these combinations of tie-breaking rules and voters’ attitudes finding a Nash equilibrium is NP-hard; in contrast, we demonstrate that in almost all cases this problem is tractable for preferences that are single-peaked or singlecrossing, under mild technical assumptions. General Terms Algorithms, Economics, Theory

AAMAS Conference 2016 Conference Paper

Hedonic Games with Graph-restricted Communication

• Ayumi Igarashi
• Edith Elkind

We study hedonic coalition formation games in which cooperation among the players is restricted by a graph structure: a subset of players can form a coalition if and only if they are connected in the given graph. We investigate the complexity of finding stable outcomes in such games, for several notions of stability. In particular, we provide an efficient algorithm that finds an individually stable partition for an arbitrary hedonic game on an acyclic graph. We also introduce a new stability concept—in-neighbor stability—which is tailored for our setting. We show that the problem of finding an inneighbor stable outcome admits a polynomial-time algorithm if the underlying graph is a path, but is NP-hard for arbitrary trees even for additively separable hedonic games; for symmetric additively separable games we obtain a PLS-hardness result. General Terms Algorithms, Economics, Theory

AAMAS Conference 2016 Conference Paper

Manipulating Citation Indices in a Social Context

• Chrystalla Pavlou
• Edith Elkind

The h-index [6] is a popular measure of a researcher’s publication activity: a researcher’s h-index is the largest number x such that she has at least x papers that have received at least x citations each. It has been observed that one can manipulate her h-index by strategically merging one or more articles, and the complexity of finding a successful/optimal manipulation has been investigated for a variety of models [3, 11]. In this paper, we extend this line of research to two other popular citation indices, namely, the g-index [4] and the i10-index, and show that these indices are somewhat easier to manipulate than the h-index. We then consider settings where the manipulator would like to take into account the impact of her actions on other researchers (she may want to make sure that her manipulation does not harm her friends or that it hurts her competitors) or a group of researchers manipulate their indices simultaneously. We analyze the complexity of these problems, both in the worst-case and in the parameterized framework.

IJCAI Conference 2016 Conference Paper

Pairwise Diffusion of Preference Rankings in Social Networks

• Markus Brill
• Edith Elkind
• Ulle Endriss
• Umberto Grandi

We introduce a model of preference diffusion in which agents in a social network update their preferences based on those of their influencers in the network, and we study the dynamics of this model. Preferences are modelled as ordinal rankings over a finite set of alternatives. At each time step, some of the agents update the relative ordering of two alternatives adjacent in their current ranking with the majority view of their influencers. We consider both a synchronous and an asynchronous variant of this model. Our results show how the graph-theoretic structure of the social network and the structure of the agents' preferences affect the termination of the diffusion process and the properties of the preference profile at the time of termination.

IJCAI Conference 2016 Conference Paper

Preference Restrictions in Computational Social Choice: Recent Progress

• Edith Elkind
• Martin Lackner
• Dominik Peters

The goal of this short paper is to provide an overview of recent progress in understanding and exploiting useful properties of restricted preference domains, such as, e. g. , the domains of single-peaked, single-crossing and 1-Euclidean preferences.

AAAI Conference 2016 Conference Paper

Preferences Single-Peaked on Nice Trees

• Dominik Peters
• Edith Elkind

Preference profiles that are single-peaked on trees enjoy desirable properties: they admit a Condorcet winner (Demange 1982), and there are hard voting problems that become tractable on this domain (Yu, Chan, and Elkind 2013). Trick (1989) proposed a polynomial-time algorithm that finds some tree with respect to which a given preference profile is singlepeaked. However, some voting problems are only known to be easy for profiles that are single-peaked on “nice” trees, and Trick’s algorithm provides no guarantees on the properties of the tree that it outputs. To overcome this issue, we build on the work of Trick and Yu et al. to develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the “best” tree for a given profile, according to a number of criteria; for other criteria, we obtain NP-hardness results. In particular, we show that it is NP-hard to decide whether an input profile is single-peaked with respect to a given tree. To demonstrate the applicability of our framework, we use it to identify a new class of profiles that admit an efficient algorithm for a popular variant of the Chamberlin–Courant (1983) rule.

AAAI Conference 2016 Conference Paper

Price of Pareto Optimality in Hedonic Games

• Edith Elkind
• Angelo Fanelli
• Michele Flammini

Price of Anarchy measures the welfare loss caused by selfish behavior: it is defined as the ratio of the social welfare in a socially optimal outcome and in a worst Nash equilibrium. A similar measure can be derived for other classes of stable outcomes. In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i. e. , outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight.

IJCAI Conference 2016 Conference Paper

Trembling Hand Equilibria of Plurality Voting

• Svetlana Obraztsova
• Zinovi Rabinovich
• Edith Elkind
• Maria Polukarov
• Nicholas R. Jennings

Trembling hand (TH) equilibria were introduced by Selten in 1975. Intuitively, these are Nash equilibria that remain stable when players assume that there is a small probability that other players will choose off-equilibrium strategies. This concept is useful for equilibrium refinement, i. e. , selecting the most plausible Nash equilibria when the set of all Nash equilibria can be very large, as is the case, for instance, for Plurality voting with strategic voters. In this paper, we analyze TH equilibria of Plurality voting. We provide an efficient algorithm for computing a TH best response and establish many useful properties of TH equilibria in Plurality voting games. On the negative side, we provide an example of a Plurality voting game with no TH equilibria, and show that it is NP-hard to check whether a given Plurality voting game admits a TH equilibrium where a specific candidate is among the election winners.

IJCAI Conference 2015 Conference Paper

Gibbard-Satterthwaite Games

• Edith Elkind
• Umberto Grandi
• Francesca Rossi
• Arkadii Slinko

The Gibbard-Satterthwaite theorem implies the ubiquity of manipulators–voters who could change the election outcome in their favor by unilaterally modifying their vote. In this paper, we ask what happens if a given profile admits several such voters. We model strategic interactions among Gibbard–Satterthwaite manipulators as a normal-form game. We classify the 2-by-2 games that can arise in this setting for two simple voting rules, namely Plurality and Borda, and study the complexity of determining whether a given manipulative vote weakly dominates truth-telling, as well as existence of Nash equilibria.

AAAI Conference 2015 Conference Paper

Justified Representation in Approval-Based Committee Voting

• Haris Aziz
• Markus Brill
• Vincent Conitzer
• Edith Elkind
• Rupert Freeman
• Toby Walsh

We consider approval-based committee voting, i. e. , the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.

IJCAI Conference 2015 Conference Paper

Simple Causes of Complexity in Hedonic Games

• Dominik Peters
• Edith Elkind

Hedonic games provide a natural model of coalition formation among self-interested agents. The associated problem of finding stable outcomes in such games has been extensively studied. In this paper, we identify simple conditions on expressivity of hedonic games that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard. Somewhat surprisingly, these conditions are very mild and intuitive. Our results apply to a wide range of stability concepts (core stability, individual stability, Nash stability, etc.) and to many known formalisms for hedonic games (additively separable games, games with W-preferences, fractional hedonic games, etc.), and unify and extend known results for these formalisms. They also have broader applicability: for several classes of hedonic games whose computational complexity has not been explored in prior work, we show that our framework immediately implies a number of hardness results for them.

IJCAI Conference 2015 Conference Paper

Strategic Candidacy Games with Lazy Candidates

• Svetlana Obraztsova
• Edith Elkind
• Maria Polukarov
• Zinovi Rabinovich

In strategic candidacy games, both voters and candidates have preferences over the set of candidates, and candidates may strategically withdraw from the election in order to manipulate the outcome according to their preferences. In this work, we extend the standard model of strategic candidacy games by observing that candidates may find it costly to run an electoral campaign and may therefore prefer to withdraw if their presence has no effect on the election outcome. We study the Nash equilibria and outcomes of natural best-response dynamics in the resulting class of games, both from a normative and from a computational perspective, and compare them with the Nash equilibria of the standard model.

IJCAI Conference 2015 Conference Paper

Structure in Dichotomous Preferences

• Edith Elkind
• Martin Lackner

Many hard computational social choice problems are known to become tractable when voters’ preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, all algorithmic results of this type have been obtained for the setting where each voter’s preference list is a total order of candidates. The goal of this paper is to extend this line of research to the setting where voters’ preferences are dichotomous, i. e. , each voter approves a subset of candidates and disapproves the remaining candidates. We propose several analogues of the notions of single-peaked and single-crossing preferences for dichotomous profiles and investigate the relationships among them. We then demonstrate that for some of these notions the respective restricted domains admit efficient algorithms for computationally hard approval-based multi-winner rules.

TCS Journal 2015 Journal Article

The complexity of fully proportional representation for single-crossing electorates

• Piotr Skowron
• Lan Yu
• Piotr Faliszewski
• Edith Elkind

AAAI Conference 2015 Conference Paper

The Complexity of Recognizing Incomplete Single-Crossing Preferences

• Edith Elkind
• Piotr Faliszewski
• Martin Lackner
• Svetlana Obraztsova

We study the complexity of deciding if a given profile of incomplete votes (i. e. , a profile of partial orders over a given set of alternatives) can be extended to a singlecrossing profile of complete votes (total orders). This problem models settings where we have partial knowledge regarding voters’ preferences and we would like to understand whether the given preference profile may be single-crossing. We show that this problem admits a polynomial-time algorithm when the order of votes is fixed and the input profile consists of top orders, but becomes NP-complete if we are allowed to permute the votes and the input profile consists of weak orders or independent-pairs orders. Also, we identify a number of practical special cases of both problems that admit polynomial-time algorithms.

AAAI Conference 2014 Conference Paper

A Characterization of the Single-Peaked Single-Crossing Domain

• Edith Elkind
• Piotr Faliszewski
• Piotr Skowron

We investigate elections that are simultaneously singlepeaked and single-crossing (SPSC). We show that the domain of 1-dimensional Euclidean elections (where voters and candidates are points on the real line, and each voter prefers the candidates that are close to her to the ones that are further away) is a proper subdomain of the SPSC domain, by constructing an election that is single-peaked and singlecrossing, but not 1-Euclidean. We then establish a connection between narcissistic elections (where each candidate is ranked first by at least one voter), single-peaked elections and single-crossing elections, by showing that an election is SPSC if and only if it can be obtained from a narcissistic singlecrossing election by deleting voters. We show two applications of our characterization.

UAI Conference 2014 Conference Paper

Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains

• Edith Elkind
• Nisarg Shah 0001

Picking the best alternative in a given set is a well-studied problem at the core of social choice theory. In some applications, one can assume that there is an objectively correct way to compare the alternatives, which, however, cannot be observed directly, and individuals’ preferences over the alternatives (votes) are noisy estimates of this ground truth. The goal of voting in this case is to estimate the ground truth from the votes. In this paradigm, it is usually assumed that the ground truth is a ranking of the alternatives by their true quality. However, sometimes alternatives are compared using not one but multiple quality parameters, which may result in cycles in the ground truth as well as in the preferences of the individuals. Motivated by this, we provide a formal model of voting with possibly intransitive ground truth and preferences, and investigate the maximum likelihood approach for picking the best alternative in this case. We show that the resulting framework leads to polynomial-time algorithms, and also approximates the corresponding NP-hard problems in the classic framework.

AAAI Conference 2014 Conference Paper

On Detecting Nearly Structured Preference Profiles

• Edith Elkind
• Martin Lackner

Structured preference domains, such as, for example, the domains of single-peaked and single-crossing preferences, are known to admit efficient algorithms for many problems in computational social choice. Some of these algorithms extend to preferences that are close to having the respective structural property, i. e. , can be made to enjoy this property by performing minor changes to voters’ preferences, such as deleting a small number of voters or candidates. However, it has recently been shown that finding the optimal number of voters or candidates to delete in order to achieve the desired structural property is NP-hard for many such domains. In this paper, we show that these problems admit efficient approximation algorithms. Our results apply to all domains that can be characterized in terms of forbidden configurations; this includes, in particular, single-peaked and single-crossing elections. For a large range of scenarios, our approximation results are optimal under a plausible complexity-theoretic assumption. We also provide parameterized complexity results for this class of problems.

AAAI Conference 2013 Conference Paper

Bounding the Cost of Stability in Games over Interaction Networks

• Reshef Meir
• Yair Zick
• Edith Elkind
• Jeffrey Rosenschein

We study the stability of cooperative games played over an interaction network, in a model that was introduced by Myerson (1977). We show that the cost of stability of such games (i. e. , the subsidy required to stabilize the game) can be bounded in terms of natural parameters of their underlying interaction networks. Specifically, we prove that if the treewidth of the interaction network H is k, then the relative cost of stability of any game played over H is at most k + 1, and if the pathwidth of H is k, then the relative cost of stability is at most k. We show that these bounds are tight for all k ≥ 2 and all k ≥ 1, respectively.

IJCAI Conference 2013 Conference Paper

Multiwinner Elections under Preferences that Are Single-Peaked on a Tree

• Lan Yu
• Hau Chan
• Edith Elkind

We study the complexity of electing a committee under several variants of the Chamberlin–Courant rule when the voters’ preferences are single-peaked on a tree. We first show that this problem is easy for the egalitarian, or “minimax” version of this problem, for arbitrary trees and misrepresentation functions. For the standard (utilitarian) version of this problem we provide an algorithm for an arbitrary misrepresentation function whose running time is polynomial in the input size as long as the number of leaves of the underlying tree is bounded by a constant. On the other hand, we prove that our problem remains computationally hard on trees that have bounded degree, diameter, or pathwidth. Finally, we show how to modify Trick’s [1989] algorithm to check whether an election is single-peaked on a tree whose number of leaves does not exceed a given parameter λ.

IS Journal 2012 Journal Article

Cooperative Game Theory: Basic Concepts and Computational Challenges

• Georgios Chalkiadakis
• Edith Elkind
• Michael Wooldridge

Cooperative game theory studies situations in which agents can benefit by working together. This article outlines the key concepts of cooperative game theory, and discusess the challenges that arise in applying these in AI applications.

AIJ Journal 2012 Journal Article

Manipulating the quota in weighted voting games

• Michael Zuckerman
• Piotr Faliszewski
• Yoram Bachrach
• Edith Elkind

AAMAS Conference 2012 Conference Paper

Manipulation Under Voting Rule Uncertainty

• Edith Elkind
• G
• aacute; bor Erd
• eacute; lyi

An important research topic in the field of computational social choice is the complexity of various forms of dishonest behavior, such as manipulation, control, and bribery. While much of the work on this topic assumes that the cheating party has full information about the election, recently there have been a number of attempts to gauge the complexity of non-truthful behavior under uncertainty about the voters' preferences. In this paper, we analyze the complexity of (coalitional) manipulation for the setting where there is uncertainty about the voting rule: the manipulator(s) know that the election will be conducted using a voting rule from a given list, and need to select their votes so as to succeed no matter which voting rule will eventually be chosen. We identify a large class of voting rules such that arbitrary combinations of rules from this class are easy to manipulate; in particular, we show that this is the case for single-voter manipulation and essentially all easy-to-manipulate voting rules, and for coalitional manipulation and $k$-approval. While a combination of a hard-to-manipulate rule with an easy-to-manipulate one is usually hard to manipulate -- we prove this in the context of coalitional manipulation for several combinations of prominent voting rules -- we also provide counterexamples showing that this is not always the case.

AAAI Conference 2012 Conference Paper

Optimal Manipulation of Voting Rules

• Svetlana Obraztsova
• Edith Elkind

Complexity of voting manipulation is a prominent research topic in computational social choice. The voting manipulation literature usually assumes that the manipulator is only concerned with improving the outcome of the election from her perspective. However, in practice, the manipulator may also be reluctant to lie, i. e. , she may have a preference for submitting a vote that does not deviate too much from her true ranking of the candidates. In this paper, we study the complexity of finding a manipulative vote that achieves the manipulator’s goal yet is as close as possible to her true preference order. We analyze this problem for three natural notions of closeness, namely, swap distance, footrule distance, and maximum displacement distance, and a variety of voting rules, such as scoring rules, Bucklin, Copeland, and Maximin. For all three distances, we obtain polynomial-time algorithms for all scoring rules and Bucklin and hardness results for Copeland and Maximin.

AAMAS Conference 2012 Conference Paper

Optimal Manipulation of Voting Rules

• Svetlana Obraztsova
• Edith Elkind

Complexity of voting manipulation is a prominent research topic in computational social choice. In this paper, we study the complexity of {\em optimal} manipulation, i. e. , finding a manipulative vote that achieves the manipulator's goal yet deviates as little as possible from her true ranking. We study this problem for three natural notions of closeness, namely, swap distance, footrule distance, and maximum displacement distance, and a variety of voting rules, such as scoring rules, Bucklin, Copeland, and Maximin. For all three distances, we obtain poly-time algorithms for all scoring rules and Bucklin and hardness results for Copeland and Maximin.

AAMAS Conference 2012 Conference Paper

Overlapping Coalition Formation Games: Charting the Tractability Frontier

• Yair Zick
• Georgios Chalkiadakis
• Edith Elkind

Cooperative games with overlapping coalitions (OCF games) model scenarios where agents can distribute their resources among several tasks; each task generates a profit which may be freely divided among the agents participating in the task. The goal of this work is to initiate a systematic investigation of algorithmic aspects of OCF games. We propose a discretized model of overlapping coalition formation, where each agent $i \in N$ has a weight $w_i \in \mathbb{N}$ and may allocate an integer amount of weight to any task. Within this framework, we focus on the computation of outcomes that are socially optimal and/or stable. We discover that the algorithmic complexity of the associated problems crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of interaction among the agents. We identify several constraints that lead to tractable subclasses of OCF games, and provideefficient algorithms for games that belong to these subclasses. We supplement our tractability results by hardness proofs, which clarify the role of our constraints.

AAAI Conference 2012 Conference Paper

Stability Via Convexity and LP Duality in OCF Games

• Yair Zick
• Evangelos Markakis
• Edith Elkind

The core is a central solution concept in cooperative game theory, and therefore it is important to know under what conditions the core of a game is guaranteed to be non-empty. Two notions that prove to be very useful in this context are Linear Programming (LP) duality and convexity. In this work, we apply these tools to identify games with overlapping coalitions (OCF games) that admit stable outcomes. We focus on three notions of the core defined in (Chalkiadakis et al. 2010) for such games, namely, the conservative core, the refined core and the optimistic core. First, we show that the conservative core of an OCF game is non-empty if and only if the core of a related classic coalitional game is non-empty. This enables us to improve the result of (Chalkiadakis et al. 2010) by giving a strictly weaker sufficient condition for the non-emptiness of the conservative core. We then use LP duality to characterize OCF games with non-empty refined core; as a corollary, we show that the refined core of a game is non-empty as long as the superadditive cover of its characteristic function is convex. Finally, we identify a large class of OCF games that can be shown to have a non-empty optimistic core using an LPbased argument.

AAMAS Conference 2011 Conference Paper

Arbitrators in Overlapping Coalition Formation Games

• Yair Zick
• Edith Elkind

Overlapping Coalition Formation (OCF) games are cooperative games where the players can simultaneously participate in several coalitions. Capturing the notion of stability in OCF games is a difficult task: a player may deviate by abandoning some, but not all of the coalitions he is involved in, and the crucial question is whether he then gets to keep his payoff from the unaffected coalitions. In related work the authors introduce three stability concepts for OCF games - the conservative, refined, and optimistic core - that are based on different answers to this question. In this paper, we propose a unified framework for the study of stability in the OCF setting, which encompasses the concepts considered previously as well as a wide variety of alternative stability concepts. Our approach is based on the notion of an arbitrator, which can be thought of as an external party that determines payoff to deviators. We give a complete characterization of outcomes that are stable under arbitration. In particular, our results provide a criterion for the outcome to be in the refined or optimistic core, thus complementing previously results for the conservative core, and answering questions left open previously. We also introduce a notion of the nucleolus for arbitrated OCF games, and argue that it is non-empty. Finally, we extend the definition of the Shapley value to the OCF setting, and provide an axiomatic characterization for it.

AAAI Conference 2011 Conference Paper

Campaign Management under Approval-Driven Voting Rules

• Ildiko Schlotter
• Piotr Faliszewski
• Edith Elkind

Approval-like voting rules, such as Sincere-Strategy Preference-Based Approval voting (SP-AV), the Bucklin rule (an adaptive variant of k-Approval voting), and the Fallback rule (an adaptive variant of SP-AV) have many desirable properties: for example, they are easy to understand and encourage the candidates to choose electoral platforms that have a broad appeal. In this paper, we investigate both classic and parameterized computational complexity of electoral campaign management under such rules. We focus on two methods that can be used to promote a given candidate: asking voters to move this candidate upwards in their preference order or asking them to change the number of candidates they approve of. We show that finding an optimal campaign management strategy of the first type is easy for both Bucklin and Fallback. In contrast, the second method is computationally hard even if the degree to which we need to affect the votes is small. Nevertheless, we identify a large class of scenarios that admit a fixed-parameter tractable algorithm.

IJCAI Conference 2011 Conference Paper

Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion

• Edith Elkind
• J
• eacute; r
• ocirc; me Lang
• Abdallah Saffidine

In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a setvalued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as theta-winning set. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

IJCAI Conference 2011 Conference Paper

Coalitional Voting Manipulation: A Game-Theoretic Perspective

• Yoram Bachrach
• Edith Elkind
• Piotr Faliszewski

Computational social choice literature has successfully studied the complexity of manipulation in variousvoting systems. However, the existing modelsof coalitional manipulation view the manipulatingcoalition as an exogenous input, ignoring thequestion of the coalition formation process. While such analysis is useful as a first approximation, a richer framework is required to model voting manipulationin the real world more accurately, and, inparticular, to explain how a manipulating coalitionarises and chooses its action. In this paper, we apply tools from cooperative game theory to developa model that considers the coalition formation processand determines which coalitions are likely toform and what actions they are likely to take. We explore the computational complexity of several standard coalitional game theory solution concepts in our setting, and study the relationship betweenour model and the classic coalitional manipulation problem as well as the now-standard bribery model.

AAAI Conference 2011 Conference Paper

Constrained Coalition Formation

• Talal Rahwan
• Tomasz Michalak
• Edith Elkind
• Piotr Faliszewski
• Jacek Sroka
• Michael Wooldridge
• Nicholas Jennings

The conventional model of coalition formation considers every possible subset of agents as a potential coalition. However, in many real-world applications, there are inherent constraints on feasible coalitions: for instance, certain agents may be prohibited from being in the same coalition, or the coalition structure may be required to consist of coalitions of the same size. In this paper, we present the first systematic study of constrained coalition formation (CCF). We propose a general framework for this problem, and identify an important class of CCF settings, where the constraints specify which groups of agents should/should not work together. We describe a procedure that transforms such constraints into a structured input that allows coalition formation algorithms to identify, without any redundant computations, all the feasible coalitions. We then use this procedure to develop an algorithm for generating an optimal (welfare-maximizing) constrained coalition structure, and show that it outperforms existing state-of-the-art approaches by several orders of magnitude.

IJCAI Conference 2011 Conference Paper

Dynamics of Profit-Sharing Games

• John Augustine
• Ning Chen
• Edith Elkind
• Angelo Fanelli
• Nikolay Gravin
• Dmitry Shiryaev

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i. e. , work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a concave function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i. e. , they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

AAMAS Conference 2011 Conference Paper

Homogeneity and Monotonicity of Distance-Rationalizable Voting Rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

Distance rationalizability is a framework for classifying voting rules by interpreting them in terms of distances and consensus classes. It can also be used to design new voting rules with desired properties. A particularly natural and versatile class of distances that can be used for this purpose is that of votewise distances, which "lift" distances over individual votes to distances over entire elections using a suitable norm. In this paper, we continue the investigation of the properties of votewise distance-rationalizable rules initiated in Elkind et al. We describe a number of general conditions on distances and consensus classes that ensure that the resulting voting rule is homogeneous or monotone. This complements the results of Elkind et al. , where the authors focus on anonymity, neutrality and consistency. We also introduce a new class of voting rules, that can be viewed as "majority variants" of classic scoring rules, and have a natural interpretation in the context of distance rationalizability.

IJCAI Conference 2011 Conference Paper

On the Complexity of Voting Manipulation under Randomized Tie-Breaking

• Svetlana Obraztsova
• Edith Elkind

Computational complexity of voting manipulation is one of the most actively studied topics in the area of computational social choice, starting with the groundbreaking work of [Bartholdi et al. , 1989]. Most of the existing work in this area, including that of [Bartholdi et al. , 1989], implicitly assumes that whenever several candidates receive the top score with respect to the given voting rule, the resulting tie is broken according to a lexicographic ordering over the candidates. However, till recently, an equally appealing method of tiebreaking, namely, selecting the winner uniformly at random among all tied candidates, has not been considered in the computational social choice literature. The first paper to analyze the complexity of voting manipulation under randomized tiebreaking is [Obraztsova et al. , 2011], where the authors provide polynomial-time algorithms for this problem under scoring rules and-under an additional assumption on the manipulator's utilities-for Maximin. In this paper, we extend the results of [Obraztsova et al. , 2011] by showing that finding an optimal vote under randomized tie-breaking is computationally hard for Copeland and Maximin (with general utilities), as well as for STV and Ranked Pairs, but easy for the Bucklin rule and Plurality with Runoff.

IJCAI Conference 2011 Conference Paper

The Complexity of Safe Manipulation under Scoring Rules

• Egor Ianovski
• Lan Yu
• Edith Elkind
• Mark C. Wilson

Slinko and White, (2008) have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call safe strategic voting. The computational aspects of this model were first studied by Hazon and Elkind, (2010), who provide polynomial-time algorithms for finding a safe strategic vote under k-approval and the Bucklin rule. In this paper, we answer an open question of Hazon and Elkind, (2010) by presenting a polynomial-time algorithm for finding a safe strategic vote under the Borda rule. Our results for Borda generalize to several interesting classes of scoring rules.

AAMAS Conference 2011 Conference Paper

Ties Matter: Complexity of Voting Manipulation Revisited

• Svetlana Obraztsova
• Edith Elkind
• Noam Hazon

In their groundbreaking paper, Bartholdi, Tovey and Trick argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important assumption made in that paper is that the manipulator's goal is to ensure that his preferred candidate is among the candidates with the maximum score, or, equivalently, that ties are broken in favor of the manipulator's preferred candidate. In this paper, we examine the role of this assumption in the easiness results of Bartholdi et al. We observe that the algorithm presented in Bartholdi et al extends to all rules that break ties according to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator's utility function that is inspired by the original model of Bartholdi et al. In contrast, we show that manipulation becomes hard when arbitrary polynomial-time tie-breaking rules are allowed, both for the rules considered in Bartholdi et al, and for a large class of scoring rules.

IJCAI Conference 2011 Conference Paper

Ties Matter: Complexity of Voting Manipulation Revisited

• Svetlana Obraztsova
• Edith Elkind
• Noam Hazon

In their groundbreaking paper, Bartholdi, Tovey and Trick [1989] argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important assumption made in that paper is that the manipulator's goal is to ensure that his preferred candidate is among the candidates with the maximum score, or, equivalently, that ties are broken in favor of the manipulator's preferred candidate. In this paper, we examine the role of this assumption in the easiness results of [Bartholdi et al. , 1989]. We observe that the algorithm presented in [Bartholdi et al. , 1989] extends to all rules that break ties according to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator's utility function that is inspired by the original model of [Bartholdi et al. , 1989]. In contrast, we show that manipulation becomes hard when arbitrary polynomial-time tie-breaking rules are allowed, both for the rules considered in [Bartholdi et al. , 1989], and for a large class of scoring rules.

AAAI Conference 2010 Conference Paper

Cloning in Elections

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

We consider the problem of manipulating elections via cloning candidates. In our model, a manipulator can replace each candidate c by one or more clones, i. e. , new candidates that are so similar to c that each voter simply replaces c in his vote with the block of c’s clones. The outcome of the resulting election may then depend on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of prominent voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with the related problem of control via adding candidates.

FOCS Conference 2010 Conference Paper

Frugal Mechanism Design via Spectral Techniques

• Ning Chen 0005
• Edith Elkind
• Nikolai Gravin
• Fedor Petrov 0001

We study the design of truthful mechanisms for set systems, i. e. , scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [2] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the √-mechanism for buying a path in a graph [18] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, our mechanism is within a factor of k + 1 from optimal; moreover, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [10]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [18] and answers several open questions proposed in [18].

AAAI Conference 2010 Conference Paper

Good Rationalizations of Voting Rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

We explore the relationship between two approaches to rationalizing voting rules: the maximum likelihood estimation (MLE) framework originally suggested by Condorcet and recently studied in (Conitzer and Sandholm 2005; Conitzer, Rognlie, and Xia 2009) and the distance rationalizability (DR) framework (Meskanen and Nurmi 2008; Elkind, Faliszewski, and Slinko 2009). The former views voting as an attempt to reconstruct the correct ordering of the candidates given noisy estimates (i. e. , votes), while the latter explains voting as search for the nearest consensus outcome. We provide conditions under which an MLE interpretation of a voting rule coincides with its DR interpretation, and classify a number of classic voting rules, such as Kemeny, Plurality, Borda and Single Transferable Vote (STV), according to how well they fit each of these frameworks. The classification we obtain is more precise than the ones that result from using MLE or DR alone: indeed, we show that the MLE approach can be used to guide our search for a more refined notion of distance rationalizability and vice versa.

JAAMAS Journal 2010 Journal Article

Guest editorial: special issue on computational social choice

• Edith Elkind
• Jérôme Lang

AAMAS Conference 2010 Conference Paper

On the Role of Distances in Defining Voting Rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

A voting rule is an algorithm for determining the winner in an election, and there are several approaches that have been used to justify the proposed rules. One justification is to show that a rule satisfies a set of desirable axioms that uniquely identify it. Another is to show that the calculation that it performs is actually maximum likelihood estimation relative to a certain model of noise that affects voters (MLE approach). The third approach, which has been recently actively investigated, is the so-called {\em distance rationalizability} framework. In it, a voting rule is defined via a class of consensus elections (i. e. , a class of elections that have a clear winner) and a distance function. A candidate $c$ is a winner of an election $E$ if $c$ wins in one of the consensus elections that are closest to $E$ relative to the given distance. In this paper, we show that essentially any voting rule is distance-rationalizable if we do not restrict the two ingredients of the rule: the consensus class and the distance. Thus distance rationalizability of a rule does not by itself guarantee that the voting rule has any desirable properties. However, we demonstrate that the distance used to rationalize a given rule may provide useful information about this rule's behavior. Specifically, we identify a large class of distances, which we call {\em votewise} distances, and show that if a rule is rationalized via a distance from this class, many important properties of this rule can be easily expressed in terms of the underlying distance. This enables us to provide a new characterization of scoring rules and to establish a connection with the MLE framework. We alsogive bounds on the complexity of the winner determination problem for distance-rationalizable rules.

IJCAI Conference 2009 Conference Paper

• Georgios Chalkiadakis
• Edith Elkind
• Nicholas R. Jennings

We introduce coalitional games with beliefs (CGBs), a natural generalization of coalitional games to environments where agents possess private beliefs regarding the capabilities (or types) of others. We put forward a model to capture such agent-type uncertainty, and study coalitional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coalition structures. For simple games without coalition structures, we then provide a characterization of the core that matches the one for the full information case, and use it to derive a polynomial-time algorithm to check core nonemptiness. In contrast, we demonstrate that in games with coalition structures allowing beliefs increases the computational complexity of stability-related problems. In doing so, we introduce and analyze weighted voting games with beliefs, which may be of independent interest. Finally, we discuss connections between our model and other classes of coalitional games.

AAMAS Conference 2009 Conference Paper

Boolean Combinations of Weighted Voting Games

• Piotr Faliszewski
• Edith Elkind
• Michael Wooldridge

Weighted voting games are a natural and practically important class of simple coalitional games, in which each agent is assigned a numeric weight, and a coalition is deemed to be winning if the sum of weights of agents in that coalition meets some stated threshold. We study a natural generalisation of weighted voting games called Boolean Weighted Voting Games (BWVGs). BWVGs are intended to model decision-making processes in which components of an overall decision are delegated to committees, with each committee being an individual weighted voting game. We consider the perspective of an individual who has some overall goal that they desire to achieve, represented as a propositional logic formula over the decisions controlled by the various committees. We begin by formulating the framework of BWVGs, and show that BWVGs can provide a succinct representation scheme for simple coalitional games, compared to other representations based on weighted voting games. We then consider the computational complexity of problems such as determining the power of a particular player with respect to some goal, and investigate how the power of a player with respect to the overall goal is related to the power of that player in individual games. We show trade-offs between the complexity of these problems, the nature of underlying Boolean formulas used, and representations of weights (binary versus unary) in our games.

SODA Conference 2009 Conference Paper

Computing the nucleolus of weighted voting games

• Edith Elkind
• Dmitrii V. Pasechnik

Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his weight, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al. (2007) studied the complexity of stability-related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result. In this paper, we solve an open problem posed by Elkind et al. by showing that the nucleolus of WVGs, and, more generally, k -vector weighted voting games with fixed k, can be computed in pseudopolynomial time, i. e. , there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players n and the maximum weight W. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.

AAMAS Conference 2009 Conference Paper

Hedonic Coalition Nets

• Edith Elkind
• Michael Wooldridge

In hedonic games, players have the opportunity to form coalitions, and have preferences over the coalitions they might join. Such games can be used to model a variety of settings ranging from multi-agent coordination to group formation in social networks. However, the practical application of hedonic games is hindered by the fact that the naive representation for such games is exponential in the number of players. In this paper, we study hedonic coalition nets—a succinct, rule-based representation for hedonic games. This formalism is based on marginal contribution nets, which were developed by Ieong and Shoham for representing coalitional games with transferable utility. We show that hedonic coalition nets are universally expressive, yet are at least as succinct as other existing representation schemes for hedonic games. We then investigate the complexity of many natural decision problems for hedonic coalition nets. In particular, we provide a complete characterisation of the computational difficulty of problems related to coalitional stability for hedonic games represented with hedonic nets.

TARK Conference 2009 Conference Paper

On distance rationalizability of some voting rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii M. Slinko

The concept of distance rationalizability has several applications within social choice. In the context of voting, it allows one to define (“rationalize”) voting rules via a consensus class (roughly, a set of elections in which it is obvious who should win) and a distance function: namely, a candidate is said to be an election winner if it is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be represented in this manner. In this paper, we provide new results on distance rationalizability of several well-known voting rules such as all scoring rules, Approval, Young’s rule and Maximin. We also show that a previously published proof of distance rationalizability of Young’s rule is incorrect: the consensus notion and the distance function used in that proof give rise to a voting rule that is similar to—but distinct from—the Young’s rule. Finally, we demonstrate that some voting rules cannot be rationalized via certain notions of consensus. To the best of our knowledge, these are the first non-distance-rationalizability results for voting rules.

AAMAS Conference 2009 Conference Paper

The Price of Democracy in Coalition Formation

• Georgios Chalkiadakis
• Edith Elkind
• Maria Polukarov
• Nicholas R. Jennings

Whenever rational agents form coalitions to execute tasks, doing so via a decentralized negotiation process—while more robust and democratic—may lead to a loss of efficiency compared to a centralized solution. To quantify this loss, we introduce the notion of the Price of Democracy (PoD), which measures the amount of resources needlessly committed to the task(s) at hand. After defining this concept for general coalitional games, we instantiate it in the setting of weighted voting games, a simple but expressive class of coalitional games that can be used to model resource allocation in multiagent scenarios. We approach the problem of forming winning coalitions in this setting from a non-cooperative perspective, and put forward an intuitive deterministic bargaining process, which exhibits no delay of agreement (i. e. , the agents are guaranteed to form a winning coalition in round one) and allows for efficient computation of bargaining strategies. We show a tight bound of 3/2 on the PoD of our process if two rounds of bargaining are allowed, and demonstrate that this bound cannot improve with more rounds. We then generalize our bargaining process to settings where multiple coalitions are allowed to be formed, show that this generalization also exhibits no delay of agreement, and discuss the PoD in such settings.

AAMAS Conference 2008 Conference Paper

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

• Edith Elkind
• Leslie Ann Goldberg
• Paul Goldberg
• Michael Wooldridge

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC-nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MCnets are a rule-based formalism, in which rules take the form pattern −→ value, where “pattern” is a Boolean condition over agents, and “value” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional game that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MCnets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks.

AAMAS Conference 2008 Conference Paper

Approximating Mixed Nash Equilibria using Smooth Fictitious Play in Simultaneous Auctions

• Enrico Gerding
• Andrew Byde
• Edith Elkind
• Zinovi Rabinovich
• NICK JENNINGS

ECAI Conference 2008 Conference Paper

Coalition Structures in Weighted Voting Games

• Edith Elkind
• Georgios Chalkiadakis
• Nicholas R. Jennings

Weighted voting games are a popular model of collaboration in multiagent systems. In such games, each agent has a weight (intuitively corresponding to resources he can contribute), and a coalition of agents wins if its total weight meets or exceeds a given threshold. Even though coalitional stability in such games is important, existing research has nonetheless only considered the stability of the grand coalition. In this paper, we introduce a model for weighted voting games with coalition structures. This is a natural extension in the context of multiagent systems, as several groups of agents may be simultaneously at work, each serving a different task. We then proceed to study stability in this context. First, we define the CS-core, a notion of the core for such settings, discuss its non-emptiness, and relate it to the traditional notion of the core in weighted voting games. We then investigate its computational properties. We show that, in contrast with the traditional setting, it is computationally hard to decide whether a game has a non-empty CS-core, or whether a given outcome is in the CS-core. However, we then provide an efficient algorithm that verifies whether an outcome is in the CS-core if all weights are small (polynomially bounded). Finally, we also suggest heuristic algorithms for checking the non-emptiness of the CS-core.

AAMAS Conference 2008 Conference Paper

Divide and Conquer: False-Name Manipulations in Weighted Voting Games

• Yoram Bachrach
• Edith Elkind

In this paper, we study false-name manipulations in weighted voting games. Weighted voting is a well-known model of cooperation among agents in decision-making domains. In such games, each of the players has a weight, and a coalition of players wins the game if its total weight exceeds a certain quota. While a player’s ability to influence the outcome of the game is related to its weight, it is not always directly proportional to it. This observation has led to the concept of a power index, which is a measure of an agent’s “real power” in this domain. One prominent power index is the Shapley–Shubik index, which has been widely used to analyze political power. This index is equal to the Shapley value of the player in the game. If an agent can alter the game so that his Shapley–Shubik index increases, this will mean that he has gained power in the game. Moreover, the Shapley value is often used to distribute the gains of the grand coalition. In this case, this alteration will also increase the agent’s payoffs. One way in which an agent can change the game (and hence his payoffs) is by distributing his weight among several false identities. We call this behavior a false-name manipulation. We show that such manipulations can indeed increase an agent’s power, as determined by the Shapley– Shubik power index, or his payoffs, as given by the Shapley value. We provide upper and lower bounds on the effects of such manipulations. We then study this issue from the computational perspective, and show that checking whether a beneficial split exists is NP-hard. We also discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case.

AAAI Conference 2008 Conference Paper

On the Dimensionality of Voting Games

• Edith Elkind
• Paul Goldberg

In a yes/no voting game, a set of voters must determine whether to accept or reject a given alternative. Weighted voting games are a well-studied subclass of yes/no voting games, in which each voter has a weight, and an alternative is accepted if the total weight of its supporters exceeds a certain threshold. Weighted voting games are naturally extended to k-vector weighted voting games, which are intersections of k different weighted voting games: a coalition wins if it wins in every component game. The dimensionality, k, of a kvector weighted voting game can be understood as a measure of the complexity of the game. In this paper, we analyse the dimensionality of such games from the point of view of complexity theory. We consider the problems of equivalence, (checking whether two given voting games have the same set of winning coalitions), and minimality, (checking whether a given k-vector voting game can be simplified by deleting one of the component games, or, more generally, is equivalent to a k0 -weighted voting game with k0 < k). We show that these problems are computationally hard, even if k = 1 or all weights are 0 or 1. However, we provide efficient algorithms for cases where both k is small and the weights are polynomially bounded. We also study the notion of monotonicity in voting games, and show that monotone yes/no voting games are essentially as hard to represent and work with as general games.

AAAI Conference 2007 Conference Paper

Computational Complexity of Weighted Threshold Games

• Edith Elkind
• Paul Goldberg

Weighted threshold games are coalitional games in which each player has a weight (intuitively corresponding to its voting power), and a coalition is successful if the sum of its weights exceeds a given threshold. Key questions in coalitional games include finding coalitions that are stable (in the sense that no member of the coalition has any rational incentive to leave it), and finding a division of payoffs to coalition members (an imputation) that is fair. We investigate the computational complexity of such questions for weighted threshold games. We study the core, the least core, and the nucleolus, distinguishing those problems that are polynomial-time computable from those that are NP-hard, and providing pseudopolynomial and approximation algorithms for the NP-hard problems.

SODA Conference 2007 Conference Paper

Designing and learning optimal finite support auctions

• Edith Elkind

SODA Conference 2004 Conference Paper

Frugality in path auctions

• Edith Elkind
• Amit Sahai
• Kenneth Steiglitz