The Shapley Value as a Function of the Quota in Weighted Voting Games
Yair Zick, Alexander Skopalik and Edith Elkind
In weighted voting games, each agent has a weight; 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 of 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.: we show that, while deciding whether a quota maximizes or minimizes an agent's Shapley value is coNP-hard, finding a quota that maximizes a player's Shapley value is easy. Minimizing a player's power appears to be a harder problem; we propose and evaluate a heuristic algorithm for it which takes into account the voter's ranking and the overall weight distribution. Finally, we show that the dependence of the player's power on the quota may be highly non-monotone, which makes it more difficult to find the optimal quota from a given interval.