IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v105y2017icp122-147.html

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

    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. Guillermo Owen, 1972. "Multilinear Extensions of Games," Management Science, INFORMS, vol. 18(5-Part-2), pages 64-79, January.
    3. Dennis Leech, 2003. "Computing Power Indices for Large Voting Games," Management Science, INFORMS, vol. 49(6), pages 831-837, June.
    4. repec:cup:apsrev:v:48:y:1954:i:03:p:787-792_00 is not listed on IDEAS
    5. 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.
    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. 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.
    3. 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.
    4. Kurz, Sascha, 2018. "The power of the largest player," Economics Letters, Elsevier, vol. 168(C), pages 123-126.
    5. 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.

    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. Casajus, André & Huettner, Frank, 2015. "Potential, value, and the multilinear extension," Economics Letters, Elsevier, vol. 135(C), pages 28-30.
    2. 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.
    3. 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), CY Cergy-Paris University, ESSEC and CNRS.
    4. A. Saavedra-Nieves, 2023. "On stratified sampling for estimating coalitional values," Annals of Operations Research, Springer, vol. 320(1), pages 325-353, January.
    5. 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.
    6. A. Saavedra-Nieves & M. G. Fiestras-Janeiro, 2021. "Sampling methods to estimate the Banzhaf–Owen value," Annals of Operations Research, Springer, vol. 301(1), pages 199-223, June.
    7. Dennis Leech, 2013. "Power indices in large voting bodies," Public Choice, Springer, vol. 155(1), pages 61-79, April.
    8. 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.
    9. Marc Feix & Dominique Lepelley & Vincent Merlin & Jean-Louis Rouet, 2007. "On the voting power of an alliance and the subsequent power of its members," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 28(2), pages 181-207, February.
    10. 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.
    11. 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 our generalization is a monotonicity property that," UB School of Economics Working Papers 2015/328, University of Barcelona School of Economics.
    12. 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.
    13. 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), CY Cergy-Paris University, ESSEC and CNRS.
    14. 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.
    15. 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.
    16. Leech, Dennis, 2010. "Power Indices in Large Voting Bodies," Economic Research Papers 270996, University of Warwick - Department of Economics.
    17. Casajus, André & Huettner, Frank, 2018. "Calculating direct and indirect contributions of players in cooperative games via the multi-linear extension," Economics Letters, Elsevier, vol. 164(C), pages 27-30.
    18. 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.
    19. Stéphane Gonzalez & Christophe Labreuche & Agnieszka Rusinowska, 2025. "Introduction to the Special Issue in Honor of Michel Grabisch," Theory and Decision, Springer, vol. 99(1), pages 1-12, September.
    20. Borgonovo, Emanuele & Plischke, Elmar & Rabitti, Giovanni, 2024. "The many Shapley values for explainable artificial intelligence: A sensitivity analysis perspective," European Journal of Operational Research, Elsevier, vol. 318(3), pages 911-926.

    More about this item

    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.