The inverse Shapley value problem

Anindya De, Ilias Diakonikolas, Rocco Servedio

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

For f a weighted voting scheme used by n voters to choose between two candidates, the n Shapley-Shubik Indices (or Shapley values) of f provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley and Martin Shubik in 1954 [SS54] and are widely studied in social choice theory as a measure of the "influence" of voters. The Inverse Shapley Value Problem is the problem of designing a weighted voting scheme which (approximately) achieves a desired input vector of values for the Shapley-Shubik indices. Despite much interest in this problem no provably correct and efficient algorithm was known prior to our work. We give the first efficient algorithm with provable performance guarantees for the Inverse Shapley Value Problem. For any constant ε > 0 our algorithm runs in fixed poly(n) time (the degree of the polynomial is independent of ε) and has the following performance guarantee: given as input a vector of desired Shapley values, if any "reasonable" weighted voting scheme (roughly, one in which the threshold is not too skewed) approximately matches the desired vector of values to within some small error, then our algorithm explicitly outputs a weighted voting scheme that achieves this vector of Shapley values to within error ε. If there is a "reasonable" voting scheme in which all voting weights are integers at most poly(n) that approximately achieves the desired Shapley values, then our algorithm runs in time poly(n) and outputs a weighted voting scheme that achieves the target vector of Shapley values to within error ε = n-1/8.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages266-277
Number of pages12
EditionPART 1
DOIs
StatePublished - 2012
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: Jul 9 2012Jul 13 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom
CityWarwick
Period7/9/127/13/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'The inverse Shapley value problem'. Together they form a unique fingerprint.

Cite this