The Inverse Shapley value problem

• 成果类型: Article
• 署名作者: De, Anindya; Diakonikolas, Ilias; Servedio, Rocco A.
• 署名单位: Northwestern University; University of Southern California; Columbia University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2017.06.004
• 发表日期: 2017
• 页码: 122-147
• 关键词: Shapley values; Weighted voting games; algorithms; Fourier Analysis

摘要

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 is an element of > 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 is an element of. (C) 2017 Elsevier Inc. All rights reserved.