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. Daniel Granot, 1977. "Cooperative Games in Stochastic Characteristic Function Form," Management Science, INFORMS, vol. 23(6), pages 621-630, February.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Dennis Leech, 2003. "Computing Power Indices for Large Voting Games," Management Science, INFORMS, vol. 49(6), pages 831-837, June.
    10. 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.
    11. Barr, Jason & Passarelli, Francesco, 2009. "Who has the power in the EU?," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 339-366, May.
    12. Carreras, Francesc & Puente, María Albina, 2015. "Coalitional multinomial probabilistic values," European Journal of Operational Research, Elsevier, vol. 245(1), pages 236-246.
    13. Pradeep Dubey & Abraham Neyman & Robert James Weber, 1981. "Value Theory Without Efficiency," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 122-128, February.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. Francesc Carreras & María Albina Puente, 2015. "Multinomial Probabilistic Values," Group Decision and Negotiation, Springer, vol. 24(6), pages 981-991, November.
    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. 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.
    2. 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.
    3. 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.
    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. 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).
    6. 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.
    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Albizuri, M.J. & Goikoetxea, A., 2022. "Probabilistic Owen-Shapley spatial power indices," Games and Economic Behavior, Elsevier, vol. 136(C), pages 524-541.
    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. 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.
    11. 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.
    12. 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.
    13. 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.
    14. Stefano Moretti & Fioravante Patrone, 2008. "Transversality of the Shapley value," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 16(1), pages 1-41, July.
    15. L. Hernández-Lamoneda & Francisco Sánchez-Sánchez, 2015. "Cooperative games with homogeneous groups of participants," Theory and Decision, Springer, vol. 79(3), pages 451-461, November.
    16. Liu, Jia-Cai & Sheu, Jiuh-Biing & Li, Deng-Feng & Dai, Yong-Wu, 2021. "Collaborative profit allocation schemes for logistics enterprise coalitions with incomplete information," Omega, Elsevier, vol. 101(C).
    17. Hsien-Chung Wu, 2018. "Interval-Valued Cores and Interval-Valued Dominance Cores of Cooperative Games Endowed with Interval-Valued Payoffs," Mathematics, MDPI, vol. 6(11), pages 1-26, November.
    18. Habis, Helga & Herings, P. Jean-Jacques, 2011. "Transferable utility games with uncertainty," Journal of Economic Theory, Elsevier, vol. 146(5), pages 2126-2139, September.
    19. Voorneveld, Mark & Grahn, Sofia, 2001. "A Minimal Test for Convex Games and the Shapley Value," Working Paper Series 2001:2, Uppsala University, Department of Economics.
    20. 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.

    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.