# The Inverse Shapley value problem

*Anindya De*,
*Ilias Diakonikolas* and
*Rocco A. Servedio*

*Games and Economic Behavior*, 2017, vol. 105, issue C, 122-147

**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 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 ϵ.

**Keywords:** Shapley values; Weighted voting games; Algorithms; Fourier Analysis (search for similar items in EconPapers)

**JEL-codes:** C71 C79 (search for similar items in EconPapers)

**Date:** 2017

**References:** View references in EconPapers View complete reference list from CitEc

**Citations** View citations in EconPapers (1) Track citations by RSS feed

**Downloads:** (external link)

http://www.sciencedirect.com/science/article/pii/S0899825617301021

Full text for ScienceDirect subscribers only

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** https://EconPapers.repec.org/RePEc:eee:gamebe:v:105:y:2017:i:c:p:122-147

Access Statistics for this article

Games and Economic Behavior is currently edited by *E. Kalai*

More articles in Games and Economic Behavior from Elsevier

Bibliographic data for series maintained by Dana Niculescu ().