The Shapley value as a function of the quota in weighted voting games

Yair Zick, Alexander Skopalik, Edith Elkind

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

18 Citations (Scopus)
7 Downloads (Pure)

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 coNPhard, 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.

Original languageEnglish
Title of host publicationIJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
Pages490-495
Number of pages6
DOIs
Publication statusPublished - 1 Dec 2011
Externally publishedYes
Event22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 - Barcelona, Spain
Duration: 16 Jul 201122 Jul 2011
Conference number: 22

Conference

Conference22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Abbreviated titleIJCAI
CountrySpain
CityBarcelona
Period16/07/1122/07/11

Cite this