Filter by type:

2017 + Forthcoming

The Price of Diversity in Public Housing Allocation Problems

Nawal Benabbou, Mithun Chakraborty, Vinh Ho Xuan, Jakub Sliwinski and Yair Zick
To Appear

Abstract

The state of Singapore employs a unique large-scale public housing program, accounting for over 80 percent of its residential real-estate. In addition to providing a social benefit to its citizens and permanent residents in the form of subsidized housing, Singapore uses its housing allocation program to ensure ethnic diversity in its neighborhoods. It does so by imposing ethnic quotas: every new housing development may not house more than a certain predetermined percentage of households from each ethnic quota. Imposing such quotas ensures that every housing block contains members from each of Singapore's main ethnicities; however, limiting people's ability to freely choose apartments incurs some welfare loss. Our work studies this problem via the computational economics lens. The Singapore public housing allocation is an extension of the classic assignment problem, to which diversity constraints are added. We begin by showing that adding these constraints makes the problem computationally intractable; however, we identify a 2-approximation algorithm, as well as realistic agent utility models which admit a polynomial-time algorithm. In addition, we study the price of diversity: this is the loss in welfare incurred by imposing diversity constraints; we show that while the price of diversity can be unbounded if the number of ethnicities is unbounded, it is a constant if the number of ethnicities is small (as is the case for Singapore). Finally, by analyzing public data from Singapore's Housing Development Board, we create a simulated framework testing the welfare loss due to diversity constraints in realistic large-scale scenarios.

Learning What You Like by Knowing Who You Know

Ayumi Igarashi, Jakub Sliwinski and Yair Zick
To Appear

Abstract

We consider the PAC stabilizability of hedonic games with an underlying graph communication structure. In this setting, there exists some interaction network connecting players, and players would only consider joining groups that are connected components of the underlying graph. We show that when the interaction network is a tree, one can efficiently compute PAC stable coalition structures; that is, player partitions that are likely to be resistant against group deviation. This result is particularly interesting as computing stable coalition structure on tree-restricted hedonic games is computationally intractable. We further show that when the underlying interaction graph is not a tree, efficient PAC stabilizability is no longer achievable. Thus, our results completely characterize when one can leverage the underlying graph structure in order to compute PAC stable outcomes for hedonic games.

A Characterization of Monotone Influence Measures for Data Classification

Martin Strobel, Jakub Sliwinski and Yair Zick
To Appear

Abstract

In this work we focus on the following question: how important was the i-th feature in determining the outcome for a given datapoint? We identify a family of influence measures; functions that, given a datapoint x, assign a value to every feature i, which roughly corresponds to that i's importance in determining the outcome for x. This family is uniquely derived from a set of axioms: desirable properties that any reasonable influence measure should satisfy. Departing from prior work on influence measures, we assume no knowledge of - or access to - the underlying classifier labelling the dataset. In other words, our influence measures are based on the dataset alone, and do not make any queries to the classifier. While this requirement naturally limits the scope of explanations we provide, we show that it is effective on real datasets.

Learning Hedonic Games

Jakub Sliwinski and Yair Zick
Conference Paper The 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017

Abstract

Coalitional stability in hedonic games has usually been considered in the setting where agent preferences are fully known. We consider the setting where agent preferences are unknown; we lay the theoretical foundations for studying the interplay between coalitional stability and (PAC) learning in hedonic games. We introduce the notion of PAC stability — the equivalent of core stability under uncertainty — and examine the PAC stabilizability and learnability of several popular classes of hedonic games.

How to Form Winning Coalitions in Mixed Human-Computer Settings

Moshe Mash, Yair Zick, Yoram Bachrach, and Kobi Gal
Conference Paper The 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017

Abstract

This paper proposes a new negotiation game, based on the weighted voting paradigm in cooperative game theory, where agents need to form coalitions and agree on how to share the gains. Despite the prevalence of weighted voting in the real world, there has been little work studying people's behavior in such settings. We show that solution concepts from cooperative game theory (in particular, an extension of the Deegan-Packel Index) provide a good prediction of people's decisions to join coalitions in an online version of a weighted voting game. With this insight in mind, we design an agent that combines supervised learning with decision theory to make offers to people in this game. We show that the agent was able to obtain higher shares from coalitions than did people playing other people, without reducing the acceptance rate of its offers. We also find that people display certain biases in weighted voting settings, like creating unnecessarily large coalitions, and not rewarding strong players. These results demonstrate the benefit of incorporating concepts from cooperative game theory in the design of agents that interact with other people in weighted voting systems.

2016

Voting Rules as Error-Correcting Codes

Journal Paper Artificial Intelligence Volume 231, February 2016, Pages 1-16

Abstract

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

Which is the Fairest (Rent Division) of them All?

Kobi Gal, Moshe Mash, Ariel D. Procaccia and Yair Zick
Conference Paper The 17th ACM Conference on Economics and Computation (EC), 2016, Pages 67-84

Abstract

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

Analyzing Power in Weighted Voting Games with Super-Increasing Weights

Conference Paper The 9th International Symposium on Algorithmic Game Theory (SAGT), 2016, pages 169-181

Abstract

Weighted voting games (WVGs) are a class of cooperative games that capture settings of group decision making in various domains, such as parliaments or committees. Earlier work has revealed that the effective decision making power, or influence of agents in WVGs is not necessarily proportional to their weight. This gave rise to measures of influence for WVGs. However, recent work in the algorithmic game theory community have shown that computing agent voting power is computationally intractable. In an effort to characterize WVG instances for which polynomial-time computation of voting power is possible, several classes of WVGs have been proposed and analyzed in the literature. One of the most prominent of these are super increasing weight sequences. Recent papers show that when agent weights are super-increasing, it is possible to compute the agents’ voting power (as measured by the Shapley value) in polynomial-time. We provide the first set of explicit closed-form formulas for the Shapley value for super-increasing sequences. We bound the effects of changes to the quota, and relate the behavior of voting power to a novel function.

A Characterization of Voting Power for Discrete Weight Distributions

Conference Paper The 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016, pages 74-80

Abstract

Weighted voting games model decision-making bodies where decisions are made by a majority vote. In such games, each agent has a weight, and a coalition of agents wins the game if the sum of the weights of its members exceeds a certain quota. The Shapley value is used as an index for the true power held by the agents in such games. Earlier work has studied the implications of setting the value of the quota on the agents’ power under the assumption that the game is given with a fixed set of agent weights. We focus on a model where the agent weights originate from a stochastic pro- cess, resulting in weight uncertainty. We analyze the expected effect of the quota on voting power given the weight generating process. We examine two extreme cases of the balls and bins model: uniform and exponentially decaying probabilities. We show that the choice of a quota may have a large influence on the power disparity of the agents, even when the governing distribution is likely to result in highly similar weights for the agents. We characterize various interesting repetitive fluctuation patterns in agents’ power as a function of the quota.

Misrepresentation in District Voting

Conference Paper The 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016, pages 81-87

Abstract

Voting systems in which voters are partitioned to districts encourage accountability by providing voters an easily identifiable district representative, but can result in a selection of representatives not representative of the electorate's preferences. In some cases, a party may have a majority of the popular vote, but lose the elections due to districting effects. We define the Misrepresentation Ratio which quantifies the deviation from proportional representation in a district-based election, and provide bounds for this ratio under various voting rules. We also examine probabilistic models for election outcomes, and provide an algorithm for approximating the expected Misrepresentation Ratio under a given probabilistic election model. Finally, we provide simulation results for several such probabilistic election models, showing the effects of the number of voters and candidates on the misrepresentation ratio.

Optimal Interdiction of Illegal Network Flow

Qingyu Guo, Bo An, Yair Zick and Chunyan Miao
Conference Paper The 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016, pages 2507-2513

Abstract

Large scale smuggling of illegal goods is a long-standing problem, with $1.4b and thousands of agents assigned to protect the borders from such activity in the US-Mexico border alone. Illegal smuggling activities are usually blocked via inspection stations or ad-hoc checkpoints/roadblocks. Security resources are insufficient to man all stations at all times; furthermore, smugglers regularly conduct surveillance activities.This paper makes several contributions toward the challenging task of optimally interdicting an illegal network flow: i) A new Stackelberg game model for network flow interdiction; ii) A novel Column and Constraint Generation approach for computing the optimal defender strategy; iii) Complexity analysis of the column generation subproblem; iv) Compact convex nonlinear programs for solving the subproblems; v) Novel greedy and heuristic approaches for subproblems with good approximation guarantee. Experimental evaluation shows that our approach can obtain a robust enough solution outperforming the existing methods and heuristic baselines significantly and scale up to realistic-sized problems.

Algorithmic Transparency via Quantitative Input Influence: Theory and Experiments with Learning Systems

Anupam Datta, Shayak Sen and Yair Zick
Conference Paper The 37th IEEE Symposium on Security and Privacy (Oakland), 2016, pages 598-617

Abstract

Algorithmic systems that employ machine learning play an increasing role in making substantive decisions in modern society, ranging from online personalization to insurance and credit decisions to predictive policing. But their decision-making processes are often opaque -- it is difficult to explain why a certain decision was made. We develop a formal foundation to improve the transparency of such decision-making systems. Specifically, we introduce a family of Quantitative Input Influence (QII) measures that capture the degree of influence of inputs on outputs of systems. These measures provide a foundation for the design of transparency reports that accompany system decisions (e.g., explaining a specific credit decision) and for testing tools useful for internal and external oversight (e.g., to detect algorithmic discrimination). Distinctively, our causal QII measures carefully account for correlated inputs while measuring influence. They support a general class of transparency queries and can, in particular, explain decisions about individuals (e.g., a loan decision) and groups (e.g., disparate impact based on gender). Finally, since single inputs may not always have high influence, the QII measures also quantify the joint influence of a set of inputs (e.g., age and income) on outcomes (e.g. loan decisions) and the marginal influence of individual inputs within such a set (e.g., income). Since a single input may be part of multiple influential sets, the average marginal influence of the input is computed using principled aggregation measures, such as the Shapley value, previously applied to measure influence in voting. Further, since transparency reports could compromise privacy, we explore the transparency-privacy tradeoff and prove that a number of useful transparency reports can be made differentially private with very little addition of noise. Our empirical validation with standard machine learning algorithms demonstrates that QII measures are a useful transparency mechanism when black box access to the learning system is available. In particular, they provide better explanations than standard associative measures for a host of scenarios that we consider. Further, we show that in the situations we consider, QII is efficiently approximable and can be made differentially private while preserving accuracy.

Tracking Performance and Forming Study Groups for Prep Courses Using Probabilistic Graphical Models (Extended Abstract)

Short Paper The 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016, pages 1359-1361

Abstract

Efficient tracking of class performance across topics is an important aspect of classroom teaching; this is especially true for psychometric general intelligence exams, which test a varied range of abilities. We develop a framework that uncovers a hidden thematic structure underlying student responses to a large pool of questions, using a probabilistic graphical model.

2015

Incentivizing Peer Grading in MOOCS: an Audit Game Approach

Alejandro Carbonara, Anupam Datta, Arunesh Sinha and Yair Zick
Conference PaperThe 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 497-503

Abstract

In Massively Open Online Courses (MOOCs) TA resources are limited; most MOOCs use peer assessments to grade assignments. Students have to divide up their time between working on their own homework and grading others. If there is no risk of being caught and penalized, students have no reason to spend any time grading others. Course staff want to incentivize students to balance their time between course work and peer grading. They may do so by auditing students, ensuring that they perform grading correctly. One would not want students to invest too much time on peer grading, as this would result in poor course performance. We present the first model of strategic auditing in peer grading, modeling the student's choice of effort in response to a grader's audit levels as a Stackelberg game with multiple followers. We demonstrate that computing the equilibrium for this game is computationally hard. We then provide a PTAS in order to compute an approximate solution to the problem of allocating audit levels. However, we show that this allocation does not necessarily maximize social welfare; in fact, there exist settings where course auditor utility is arbitrarily far from optimal under an approximately optimal allocation. To circumvent this issue, we present a natural condition that guarantees that approximately optimal TA allocations guarantee approximately optimal welfare for the course auditors.

Learning Cooperative Games

Conference PaperThe 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 475-481

Abstract

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

Non-Myopic Negotiators See What's Best

Conference PaperThe 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 2047-2053

Abstract

We consider revenue negotiation problems in iterative settings. In our model, a group of agents has some initial resources, used in order to generate revenue. Agents must agree on some way of dividing resources, but there's a twist. At every time-step, the revenue shares received at time t are agent resources at time t + 1, and the game is repeated. The key issue here is that the way resources are shared has a dramatic effect on long-term social welfare, so in order to maximize individual long-term revenue one must consider the welfare of others, a behavior not captured by other models of cooperation and bargaining. Our work focuses on homogeneous production functions. We identify conditions that ensure that the socially optimal outcome is an ε-Nash equilibrium. We apply our results to some families of utility functions, and discuss their strategic implications.

Influence in Classification via Cooperative Game Theory

Conference PaperThe 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 511-517

Abstract

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

Voting Rules as Error-Correcting Codes

Conference PaperThe 29th AAAI Conference on Artificial Intelligence (AAAI), 2015, pages 1000-1006

Abstract

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

2014

Arbitration and Stability in Cooperative Games with Overlapping Coalitions

Journal PaperJournal of Artificial Intelligence Research Volume 50, 2014, Pages 847-884

Abstract

Overlapping Coalition Formation (OCF) games, introduced by Chalkiadakis, Elkind, Markakis, Polukarov and Jennings in 2010, are cooperative games where players can simultaneously participate in several coalitions. Capturing the notion of stability in OCF games is a difficult task: deviating players may continue to contribute resources to joint projects with non-deviators, and the crucial question is what payoffs the deviators expect to receive from such projects. Chalkiadakis et al. introduce three stability concepts for OCF games — the conservative core, the refined core, and the 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 stability concepts considered by Chalkiadakis et al. as well as a wide variety of alternative stability concepts. Our approach is based on the notion of arbitration functions, which determine the payoff obtained by the deviators, given their deviation and the current allocation of resources. We provide a characterization of stable outcomes under arbitration. We then conduct an in-depth study of four types of arbitration functions, which correspond to four notions of the core; these include the three notions of the core considered by Chalkiadakis et al. Our results complement those of Chalkiadakis et al. and answer questions left open by their work. In particular, we show that OCF games with the conservative arbitration function are essentially equivalent to non-OCF games, by relating the conservative core of an OCF game to the core of a non-overlapping cooperative game, and use this result to obtain a strictly weaker sufficient condition for conservative core non-emptiness than the one given by Chalkiadakis et al.

Arbitration and Stability in Cooperative Games

Yair Zick and Edith Elkind
Journal PaperSigEcom Exchanges 12.2, 2014, Pages 847-884

Abstract

We present a formal framework for handling deviation in settings where players divide resources among multiple projects, forming overlapping coalition structures. Having formed such a coalition structure, players share the revenue generated among themselves. Given a profit division, some players may decide that they are underpaid, and deviate from the outcome. The main insight of the work presented in this survey is that when players want to deviate, they must know how the non-deviators would react to their deviation: after the deviation, the deviators may still work with some of the non-deviators, which presents an opportunity for the non-deviators to exert leverage on deviators. We extend the overlapping coalition formation (OCF) model of Chalkiadakis et al. [2010] for cooperation with partial coalitions, by introducing arbitration functions, a general framework for handling deviation in OCF games. We review some interesting aspects of the model, characterizations of stability in this model, as well as methods for computing stable outcomes.

2013

On Random Quotas and Proportional Representation in Weighted Voting Games

Yair Zick
Conference PaperThe 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2013, pages 432-439

Abstract

Weighted voting games (WVGs) model decision making bodies such as parliaments and councils. In such settings, it is often important to provide a measure of the influence a player has on the vote. Two highly popular such measures are the Shapley-Shubik power index, and the Banzhaf power index. Given a power measure, proportional representation is the property of having players' voting power proportional to the number of parliament seats they receive. Approximate proportional representation (w.r.t. the Banzhaf power index) can be ensured by changing the number of parliament seats each party receives; this is known as Penrose's square root method. However, a discrepancy between player weights and parliament seats is often undesirable or unfeasible; a simpler way of achieving approximate proportional representation is by changing the quota, i.e. the number of votes required in order to pass a bill. It is known that a player's Shapley-Shubik power index is proportional to his weight when one chooses a quota at random; that is, when taking a random quota, proportional representation holds in expectation. In our work, we show that not only does proportional representation hold in expectation, it also holds for many quotas. We do so by providing bounds on the variance of the Shapley value when the quota is chosen at random, assuming certain weight distributions. We further explore the case where weights are sampled from i.i.d. binomial distributions; for this case, we show good bounds on an important parameter governing the behavior of the variance, as well as substantiating our claims with empirical analysis.

Bounding the Cost of Stability in Games Over Interaction Networks

Conference PaperThe 27th AAAI Conference on Artificial Intelligence (AAAI), 2013, pages 690-696

Abstract

We study the stability of cooperative games played over an interaction network, in a model that was introduced by Myerson ['77]. 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.

Dynamic Weighted Voting Games

Conference PaperThe 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013, pages 515-522

Abstract

We initiate the study of dynamic cooperative games—cooperative games where the characteristic function may change over time. We introduce two types of algorithmic problems for such games: computing a given solution concept at time t, and checking that a certain function of the game (e.g., the Shapley value of a given player or the value of the least core) remains within given bounds during time interval [t0, t1]. We then investigate the complexity of these problems for dynamic weighted voting games, where the weight of each player and the quota are functions of time that are given by low-degree polynomials with integer coefficients. We provide pseudopolynomial algorithms for problems of both types, for a variety of solution concepts. We then use our results to investigate the changes in power distribution in the Council of the European Union over the next 50 years.

Taxation and Stability in Cooperative Games

Conference PaperThe 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013, pages 523-530

Abstract

Cooperative games are a useful framework for modeling multiagent behavior in environments where agents must collaborate in order to complete tasks. Having jointly completed a task and generated revenue, agents need to agree on some reasonable method of sharing their profits. One particularly appealing family of payoff divisions is the core, which consists of all coalitionally rational (or, stable) payoff divisions. Unfortunately, it is often the case that the core of a game is empty, i.e. there is no payoff scheme guaranteeing each group of agents a total payoff higher than what they can get on their own. As stability is a highly attractive property, there have been various methods of achieving it proposed in the literature. One natural way of stabilizing a game is via taxation, i.e. reducing the value of some coalitions in order to decrease their bargaining power. Existing taxation methods include the ε-core, the least-core and several others. However, taxing coalitions is in general undesirable: one would not wish to overly tamper with a given coalitional game, or overly tax the agents. Thus, in this work we study minimal taxation policies, i.e. those minimizing the amount of tax required in order to stabilize a given game. We show that games that minimize the total tax are to some extent a linear approximation of the original games, and explore their properties. We demonstrate connections between the minimal tax and the cost of stability, and characterize the types of games for which it is possible to obtain a tax-minimizing policy using variants of notion of the ε-core, as well as those for which it is possible to do so using reliability extensions.

On Manipulation in Multi-Winner Elections Based on Scoring Rules

Conference PaperThe 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013, pages 359-366

Abstract

Multi-winner elections model scenarios where voters must select a fixed-size group of candidates based on their individual preferences. In such scenarios, it is often the case that voters are incentivized to manipulate, i.e. misreport their preferences in order to obtain a better outcome. In this paper, we study the complexity of manipulating multiwinner elections under scoring rules, with a particular focus on the role of tie-breaking rules. We consider both lexicographic tie-breaking rules, which break ties according to a fixed ordering of the candidates, and a natural randomized tie-breaking rule. We describe polynomial-time manipulation algorithms for several special cases of our problem. Specifically, we show that finding a successful manipulation is easy if the underlying voting rule is k-Approval or the number of candidates to be elected is bounded by a constant (for both types of tie-breaking rules), as well as if the manipulator’s utility function only takes values in {0, 1} and the ties are broken in the manipulator’s favor.

2012

Stability via Convexity and LP Duality in Games with Overlapping Coalitions

Conference PaperThe 26th AAAI Conference on Artificial Intelligence (AAAI), 2012, pages 1506-1512

Abstract

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 LP based argument.

Overlapping Coalition Formation Games: Charting the Tractability Frontier

Conference PaperThe 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012, pages 787-794

Abstract

Cooperative games with overlapping coalitions (OCF games) [3, 23] 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 ∈ N has a weight wi ∈ 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 provide efficient algorithms for games that belong to these subclasses. We supplement our tractability results by hardness proofs, which clarify the role of our constraints.

2011

The Shapley Value as a Function of the Quota in Weighted Voting Games

Conference PaperThe 22nd International Joint Conference on Artificial Intelligence (IJCAI), 2011, pages 490-496

Abstract

In weighted voting games, each agent has a weight, and a coalition of players is deemed to be winning if its weight meets or exceeds the given quota. An agent’s power in such games is usually measured by her Shapley value, which depends both on the agent’s weight and the quota. [Zuckerman et al., 2008] show that one can alter a player’s power significantly by modifying the quota, and investigate some of the related algorithmic issues. In this paper, we answer a number of questions that were left open by [Zuckerman et al., 2008]: we show that, even though deciding whether a quota maximizes or minimizes an agent’s Shapley value is coNP hard, finding a Shapley value-maximizing quota is easy. Minimizing a player’s power appears to be more difficult. However, we propose and evaluate a heuristic for this problem, which takes into account the voter’s rank and the overall weight distribution. We also explore a number of other algorithmic issues related to quota manipulation.

Arbitrators in Overlapping Coalition Formation Games

Yair Zick and Edith Elkind
Conference PaperThe 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2011, pages 55-62

Abstract

Overlapping Coalition Formation (OCF) games [3, 4] 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 [4] 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 in [4] 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 the results in [4] for the conservative core, and answering questions left open in [4]. 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 [12] to the OCF setting, and provide an axiomatic characterization for it.