The Inverse Shapley value problem

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 measure how much control each voter can exert over the overall outcome. The Inverse Shapley Value Problem is the problem of designing a weighted voting scheme which...

Full description

Saved in:
Bibliographic Details
Published in:Games and economic behavior 2017-09, Vol.105, p.122-147
Main Authors: De, Anindya, Diakonikolas, Ilias, Servedio, Rocco A.
Format: Article
Language:English
Subjects:
Algorithms
Fourier Analysis
Shapley values
Weighted voting games
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 measure how much control each voter can exert over the overall outcome. 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. We give the first efficient algorithm with provable guarantees for the Inverse Shapley Value Problem. For any constant ϵ>0 our algorithm runs in fixed poly(n) time and satisfies the following: 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, then our algorithm outputs a weighted voting scheme that achieves this vector of Shapley values to within error ϵ. •We study the problem of finding a weighted voting game from its Shapley values.•We propose an efficient approximation algorithm with provable performance guarantees.•Our analysis leverages ideas from learning theory and probability theory.
ISSN:0899-8256
1090-2473
DOI:10.1016/j.geb.2017.06.004