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

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 sig- nificantly by modifying the quota, and investigate some of the related algorithmic issues. In this pa- per, 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 is- sues related to quota manipulation.