Michael Zuckerman

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.

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 with Randomized Tie-Breaking under Maximin

• Michael Zuckerman
• Jeffrey Rosenschein

In recent papers, Obraztsova et al. initiated the study of the computational complexity of voting manipulation under randomized tie-breaking [3, 2]. The authors provided a polynomial-time algorithm for the problem of finding an optimal vote for the manipulator (a vote maximizing the manipulator’s expected utility) under the Maximin voting rule, for the case where the manipulator’s utilities of the candidates are given by the vector (1, 0, .. ., 0). On the other hand, they showed that this problem is NP-hard for the case where the utilities are (1, .. ., 1, 0). This paper continues that line of research. We prove that when the manipulator’s utilities of the candidates are given by the vector (1, .. ., 1, 0, .. ., 0), with k 1’s and (m − k) 0’s, then the problem of finding an optimal vote for the manipulator is fixed-parameter tractable when parameterized by k. Also, by exploring the properties of the graph built by the algorithm, we prove that when a certain sub-graph of this graph contains a 2-cycle, then the solution returned by the algorithm is optimal.

AAMAS Conference 2011 Conference Paper

An Algorithm for the Coalitional Manipulation Problem under Maximin

• Michael Zuckerman
• Omer Lev
• Jeffrey S. Rosenschein

We introduce a new algorithm for the Unweighted Coalitional Manipulation problem under the Maximin voting rule. We prove that the algorithm gives an approximation ratio of 12/3 to the corresponding optimization problem. This is an improvement over the previously known algorithm that gave a 2-approximation. We also prove that its approximation ratio is no better than 11/2, i. e. , there are instances on which a 11/2 -approximation is the best the algorithm can achieve. Finally, we prove that no algorithm can approximate the problem better than to the factor of 11/2, unless P = NP.

MFCS Conference 2010 Conference Paper

Proof Systems and Transformation Games

• Yoram Bachrach
• Michael Zuckerman
• Michael J. Wooldridge
• Jeffrey S. Rosenschein

Abstract We introduce Transformation Games (TGs), a form of coalitional game in which players are endowed with sets of initial resources, and have capabilities allowing them to derive certain output resources, given certain input resources. The aim of a TG is to generate a particular target resource; players achieve this by forming a coalition capable of performing a sequence of transformations from its combined set of initial resources to the target resource. After presenting the TG model, and discussing its interpretation, we consider possible restrictions on the transformation chain, resulting in different coalitional games. After presenting the basic model, we consider the computational complexity of several problems in TGs, such as testing whether a coalition wins, checking if a player is a dummy or a veto player, computing the core of the game, computing power indices, and checking the effects of possible restrictions on the coalition. Finally, we consider extensions to the model in which transformations have associated costs.

IJCAI Conference 2009 Conference Paper

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

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

AIJ Journal 2009 Journal Article

Algorithms for the coalitional manipulation problem

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

SODA Conference 2008 Conference Paper

Algorithms for the coalitional manipulation problem

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

AAAI Conference 2008 Conference Paper

Manipulating the Quota in Weighted Voting Games

• Michael Zuckerman
• Yoram Bachrach

Weighted voting games provide a popular model of decision making in multiagent systems. Such games are described by a set of players, a list of players’ weights, and a quota; a coalition of the players is said to be winning if the total weight of its members meets or exceeds the quota. The power of a player in such games is traditionally identified with her Shapley–Shubik index or her Banzhaf index, two classical power measures that reflect the player’s marginal contributions under different coalition formation scenarios. In this paper, we investigate by how much the central authority can change a player’s power, as measured by these indices, by modifying the quota. We provide tight upper and lower bounds on the changes in the individual player’s power that can result from a change in quota. We also study how the choice of quota can affect the relative power of the players. From the algorithmic perspective, we provide an efficient algorithm for determining whether there is a value of the quota that makes a given player a dummy, i. e. , reduces his power (as measured by both indices) to 0. On the other hand, we show that checking which of the two values of the quota makes this player more powerful is computationally hard, namely, complete for the complexity class PP, which is believed to be significantly more powerful than NP.