IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v105y2017icp122-147.html
   My bibliography  Save this article

The Inverse Shapley value problem

Author

Listed:
  • De, Anindya
  • Diakonikolas, Ilias
  • Servedio, Rocco A.

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

Suggested Citation

  • De, Anindya & Diakonikolas, Ilias & Servedio, Rocco A., 2017. "The Inverse Shapley value problem," Games and Economic Behavior, Elsevier, vol. 105(C), pages 122-147.
    • Handle: RePEc:eee:gamebe:v:105:y:2017:i:c:p:122-147
    DOI: 10.1016/j.geb.2017.06.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825617301021
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2017.06.004?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hans Peters, 2015. "The Shapley Value," Springer Texts in Business and Economics, in: Game Theory, edition 2, chapter 17, pages 305-325, Springer.
    2. Dennis Leech, 2003. "Computing Power Indices for Large Voting Games," Management Science, INFORMS, vol. 49(6), pages 831-837, June.
    3. Shapley, L. S. & Shubik, Martin, 1954. "A Method for Evaluating the Distribution of Power in a Committee System," American Political Science Review, Cambridge University Press, vol. 48(3), pages 787-792, September.
    4. Hans Peters, 2015. "Core, Shapley Value, and Weber Set," Springer Texts in Business and Economics, in: Game Theory, edition 2, chapter 18, pages 327-342, Springer.
    5. Guillermo Owen, 1972. "Multilinear Extensions of Games," Management Science, INFORMS, vol. 18(5-Part-2), pages 64-79, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sascha Kurz, 2020. "Are weighted games sufficiently good for binary voting?," Papers 2006.05330, arXiv.org, revised Jul 2021.
    2. Sascha Kurz, 2021. "Are Weighted Games Sufficiently Good for Binary Voting?," Homo Oeconomicus: Journal of Behavioral and Institutional Economics, Springer, vol. 38(1), pages 29-36, December.
    3. Kurz, Sascha, 2018. "The power of the largest player," Economics Letters, Elsevier, vol. 168(C), pages 123-126.
    4. Sascha Kurz, 2018. "Importance In Systems With Interval Decisions," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 21(06n07), pages 1-23, September.
    5. Xu, Hedong & Tian, Cunzhi & Xiao, Xinrong & Fan, Suohai, 2018. "Evolutionary investors’ power-based game on networks," Applied Mathematics and Computation, Elsevier, vol. 330(C), pages 125-133.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Taylan Mavruk & Conny Overland & Stefan Sjögren, 2020. "Keeping it real or keeping it simple? Ownership concentration measures compared," European Financial Management, European Financial Management Association, vol. 26(4), pages 958-1005, September.
    2. Hamers, Herbert & Husslage, Bart & Lindelauf, R. & Campen, Tjeerd, 2016. "A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack," Other publications TiSEM 8a67b416-1091-4efe-a1a6-7, Tilburg University, School of Economics and Management.
    3. Rahhal Lahrach & Jérôme Le Tensorer & Vincent Merlin, 2005. "Who benefits from the US withdrawal of the Kyoto Protocol? An application of the MMEA method to measure power," Post-Print halshs-00010171, HAL.
    4. Michela Chessa, 2014. "A generating functions approach for computing the Public Good index efficiently," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 658-673, July.
    5. Fabrice Barthélémy & Mathieu Martin, 2007. "Configurations study for the Banzhaf and the Shapley-Shubik indices of power," THEMA Working Papers 2007-07, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    6. Hamers, Herbert & Husslage, Bart & Lindelauf, R. & Campen, Tjeerd, 2016. "A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack," Discussion Paper 2016-042, Tilburg University, Center for Economic Research.
    7. Yuto Ushioda & Masato Tanaka & Tomomi Matsui, 2022. "Monte Carlo Methods for the Shapley–Shubik Power Index," Games, MDPI, vol. 13(3), pages 1-14, June.
    8. Fabrice Barthelemy & Mathieu Martin & Bertrand Tchantcho, 2011. "Some conjectures on the two main power indices," THEMA Working Papers 2011-14, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    9. Dennis Leech, 2013. "Power indices in large voting bodies," Public Choice, Springer, vol. 155(1), pages 61-79, April.
    10. José María Alonso-Meijide & Mikel Álvarez-Mozos & María Gloria Fiestras-Janeiro, 2015. "Power Indices and Minimal Winning Coalitions in Simple Games with Externalities Abstract: We propose a generalization of simple games to situations with coalitional externalities. The main novelty of ," UB School of Economics Working Papers 2015/328, University of Barcelona School of Economics.
    11. André Casajus & Frank Huettner, 2019. "The Coleman–Shapley index: being decisive within the coalition of the interested," Public Choice, Springer, vol. 181(3), pages 275-289, December.
    12. Adil Baykasoğlu & Burcu Kubur Özbel, 2021. "Explicit flow-risk allocation for cooperative maximum flow problems under interval uncertainty," Operational Research, Springer, vol. 21(3), pages 2149-2179, September.
    13. Casajus, André & Huettner, Frank, 2015. "Potential, value, and the multilinear extension," Economics Letters, Elsevier, vol. 135(C), pages 28-30.
    14. D. Kilgour & Terrence Levesque, 1984. "The Canadian constitutional amending formula: Bargaining in the past and the future," Public Choice, Springer, vol. 44(3), pages 457-480, January.
    15. Serguei Kaniovski, 2008. "The exact bias of the Banzhaf measure of power when votes are neither equiprobable nor independent," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(2), pages 281-300, August.
    16. Vito Fragnelli & Gianfranco Gambarelli, 2014. "Further open problems in cooperative games," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 24(4), pages 51-62.
    17. Benati, Stefano & Rizzi, Romeo & Tovey, Craig, 2015. "The complexity of power indexes with graph restricted coalitions," Mathematical Social Sciences, Elsevier, vol. 76(C), pages 53-63.
    18. Josep Freixas & Montserrat Pons, 2017. "Using the Multilinear Extension to Study Some Probabilistic Power Indices," Group Decision and Negotiation, Springer, vol. 26(3), pages 437-452, May.
    19. Widgrén, Mika, 2008. "The Impact of Council Voting Rules on EU Decision-Making," Discussion Papers 1162, The Research Institute of the Finnish Economy.
    20. Stefano Benati & Giuseppe Vittucci Marzetti, 2021. "Voting power on a graph connected political space with an application to decision-making in the Council of the European Union," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(4), pages 733-761, November.

    More about this item

    Keywords

    Shapley values; Weighted voting games; Algorithms; Fourier Analysis;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C79 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Other

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:105:y:2017:i:c:p:122-147. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.