IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v279y2019i1p93-106.html
   My bibliography  Save this article

A stochastic approach to approximate values in cooperative games

Author

Listed:
  • Benati, Stefano
  • López-Blázquez, Fernando
  • Puerto, Justo

Abstract

Computing additive values in cooperative games, like the Shapley value, is a hard task because, in general, it involves the summation of an exponential number of terms. We propose a new method, based on the stochastic approximation of deterministic games and sampling theory, to calculate a statistic estimate of these values and, at the same time, keeping under control estimation errors. We applied this technique to several well-known games and we show that in many cases we were able to improve previous results.

Suggested Citation

  • Benati, Stefano & López-Blázquez, Fernando & Puerto, Justo, 2019. "A stochastic approach to approximate values in cooperative games," European Journal of Operational Research, Elsevier, vol. 279(1), pages 93-106.
    • Handle: RePEc:eee:ejores:v:279:y:2019:i:1:p:93-106
    DOI: 10.1016/j.ejor.2019.05.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719304448
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.05.027?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. Judith Timmer & Peter Borm & Stef Tijs, 2005. "Convexity In Stochastic Cooperative Situations," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 7(01), pages 25-42.
    2. Badinger, Harald & Mühlböck, Monika & Nindl, Elisabeth & Reuter, Wolf Heinrich, 2014. "Theoretical vs. empirical power indices: Do preferences matter?," European Journal of Political Economy, Elsevier, vol. 36(C), pages 158-176.
    3. Irinel Dragan, 2006. "The least square values and the shapley value for cooperative TU games," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 14(1), pages 61-73, June.
    4. J. Puerto & F. Fernández & Y. Hinojosa, 2008. "Partially ordered cooperative games: extended core and Shapley value," Annals of Operations Research, Springer, vol. 158(1), pages 143-159, February.
    5. Dennis Leech, 2003. "Computing Power Indices for Large Voting Games," Management Science, INFORMS, vol. 49(6), pages 831-837, June.
    6. Barr, Jason & Passarelli, Francesco, 2009. "Who has the power in the EU?," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 339-366, May.
    7. Judith Timmer & Peter Borm & Stef Tijs, 2004. "On three Shapley-like solutions for cooperative games with random payoffs," International Journal of Game Theory, Springer;Game Theory Society, vol. 32(4), pages 595-613, August.
    8. Carreras, Francesc & Puente, María Albina, 2015. "Coalitional multinomial probabilistic values," European Journal of Operational Research, Elsevier, vol. 245(1), pages 236-246.
    9. Pradeep Dubey & Abraham Neyman & Robert James Weber, 1981. "Value Theory Without Efficiency," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 122-128, February.
    10. Francesc Carreras & María Albina Puente, 2018. "A note on multinomial probabilistic values," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(1), pages 164-186, April.
    11. Antti Pajala & Mika Widgrèn, 2004. "A Priori versus Empirical Voting Power in the EU Council of Ministers," European Union Politics, , vol. 5(1), pages 73-97, March.
    12. Francesc Carreras & María Albina Puente, 2015. "Multinomial Probabilistic Values," Group Decision and Negotiation, Springer, vol. 24(6), pages 981-991, November.
    13. Daniel Granot, 1977. "Cooperative Games in Stochastic Characteristic Function Form," Management Science, INFORMS, vol. 23(6), pages 621-630, February.
    14. J. Bilbao & J. Fernández & A. Losada & J. López, 2000. "Generating functions for computing power indices efficiently," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 8(2), pages 191-213, December.
    15. S. C. Littlechild & G. Owen, 1973. "A Simple Expression for the Shapley Value in a Special Case," Management Science, INFORMS, vol. 20(3), pages 370-372, November.
    16. Ruiz, Luis M. & Valenciano, Federico & Zarzuelo, Jose M., 1998. "The Family of Least Square Values for Transferable Utility Games," Games and Economic Behavior, Elsevier, vol. 24(1-2), pages 109-130, July.
    17. F. R. Fernández & J. Puerto & M. J. Zafra, 2002. "Cores Of Stochastic Cooperative Games With Stochastic Orders," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 4(03), pages 265-280.
    18. Judith Timmer, 2006. "The Compromise Value for Cooperative Games with Random Payoffs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 64(1), pages 95-106, August.
    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. 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.
    2. J. C. Gonçalves-Dosantos & I. García-Jurado & J. Costa & J. M. Alonso-Meijide, 2022. "Necessary players and values," Annals of Operations Research, Springer, vol. 318(2), pages 935-961, November.
    3. 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.
    4. Saavedra-Nieves, Alejandro & Saavedra-Nieves, Paula, 2020. "On systems of quotas from bankruptcy perspective: the sampling estimation of the random arrival rule," European Journal of Operational Research, Elsevier, vol. 285(2), pages 655-669.
    5. A. Saavedra-Nieves, 2023. "On stratified sampling for estimating coalitional values," Annals of Operations Research, Springer, vol. 320(1), pages 325-353, January.
    6. Luo, Chunlin & Zhou, Xiaoyang & Lev, Benjamin, 2022. "Core, shapley value, nucleolus and nash bargaining solution: A Survey of recent developments and applications in operations management," Omega, Elsevier, vol. 110(C).
    7. Margaretha Gansterer & Richard F. Hartl, 2020. "Shared resources in collaborative vehicle routing," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 1-20, April.

    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. Panfei Sun & Dongshuang Hou & Hao Sun, 2022. "Optimization implementation of solution concepts for cooperative games with stochastic payoffs," Theory and Decision, Springer, vol. 93(4), pages 691-724, November.
    2. Donald Nganmegni Njoya & Issofa Moyouwou & Nicolas Gabriel Andjiga, 2021. "The equal-surplus Shapley value for chance-constrained games on finite sample spaces," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(3), pages 463-499, June.
    3. 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.
    4. Hang Luo & Lize Yang & Kourosh Houshmand, 2021. "Power Structure Dynamics in Growing Multilateral Development Banks: The Case of the Asian Infrastructure Investment Bank," Global Policy, London School of Economics and Political Science, vol. 12(1), pages 24-39, February.
    5. R. Branzei & S. Gök & O. Branzei, 2011. "Cooperative games under interval uncertainty: on the convexity of the interval undominated cores," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 19(4), pages 523-532, December.
    6. Xu, Genjiu & Driessen, Theo S.H. & Sun, Hao & Su, Jun, 2013. "Consistency for the additive efficient normalization of semivalues," European Journal of Operational Research, Elsevier, vol. 224(3), pages 566-571.
    7. Albizuri, M.J. & Goikoetxea, A., 2022. "Probabilistic Owen-Shapley spatial power indices," Games and Economic Behavior, Elsevier, vol. 136(C), pages 524-541.
    8. J. C. Gonçalves-Dosantos & I. García-Jurado & J. Costa & J. M. Alonso-Meijide, 2022. "Necessary players and values," Annals of Operations Research, Springer, vol. 318(2), pages 935-961, November.
    9. Alparslan Gök, S.Z. & Branzei, O. & Branzei, R. & Tijs, S., 2011. "Set-valued solution concepts using interval-type payoffs for interval games," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 621-626.
    10. J. Puerto & F. Fernández & Y. Hinojosa, 2008. "Partially ordered cooperative games: extended core and Shapley value," Annals of Operations Research, Springer, vol. 158(1), pages 143-159, February.
    11. Giulia Cesari & Roberto Lucchetti & Stefano Moretti, 2017. "Generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 919-939, November.
    12. Meyer, Eric, 2013. "Die Macht der Mitgliedstaaten im Ministerrat der EU und im Ministerrat für Fragen der Währungsunion nach dem Vertrag von Lissabon," Beiträge zur angewandten Wirtschaftsforschung 36, University of Münster, Center of Applied Economic Research Münster (CAWM).
    13. 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.
    14. Judith Timmer, 2006. "The Compromise Value for Cooperative Games with Random Payoffs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 64(1), pages 95-106, August.
    15. A. Saavedra-Nieves, 2023. "On stratified sampling for estimating coalitional values," Annals of Operations Research, Springer, vol. 320(1), pages 325-353, January.
    16. Dan C. Popescu & Philip Kilby, 2020. "Approximation of the Shapley value for the Euclidean travelling salesman game," Annals of Operations Research, Springer, vol. 289(2), pages 341-362, June.
    17. Fritz Breuss, 2013. "Die Größe der Kleinen in der EU," WIFO Working Papers 452, WIFO.
    18. 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.
    19. René Brink & Yukihiko Funaki & Yuan Ju, 2013. "Reconciling marginalism with egalitarianism: consistency, monotonicity, and implementation of egalitarian Shapley values," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(3), pages 693-714, March.
    20. Monroy, L. & Hinojosa, M.A. & Mármol, A.M. & Fernández, F.R., 2013. "Set-valued cooperative games with fuzzy payoffs. The fuzzy assignment game," European Journal of Operational Research, Elsevier, vol. 225(1), pages 85-90.

    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:ejores:v:279:y:2019:i:1:p:93-106. 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/eor .

    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.