AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
The Shapley Value as a Function of the Quota in Weighted Voting Games
Yair Zick, Alexander Skopalik, Edith Elkind

Last modified: 2011-06-28

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.

Full Text: PDF