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

Finding the nucleoli of large cooperative games

Author

Listed:
  • Nguyen, Tri-Dung
  • Thomas, Lyn

Abstract

The nucleolus is one of the most important solution concepts in cooperative game theory as a result of its attractive properties - it always exists (if the imputation is non-empty), is unique, and is always in the core (if the core is non-empty). However, computing the nucleolus is very challenging because it involves the lexicographical minimization of an exponentially large number of excess values. We present a method for computing the nucleoli of large games, including some structured games with more than 50 players, using nested linear programs (LP). Although different variations of the nested LP formulation have been documented in the literature, they have not been used for large games because of the large size and number of LPs involved. In addition, subtle issues such as how to deal with multiple optimal solutions and with tight constraint sets need to be resolved in each LP in order to formulate and solve the subsequent ones. Unfortunately, this technical issue has been largely overlooked in the literature. We treat these issues rigorously and provide a new nested LP formulation that is smaller in terms of the number of large LPs and their sizes. We provide numerical tests for several games, including the general flow games, the coalitional skill games and the weighted voting games, with up to 100 players.

Suggested Citation

  • Nguyen, Tri-Dung & Thomas, Lyn, 2016. "Finding the nucleoli of large cooperative games," European Journal of Operational Research, Elsevier, vol. 248(3), pages 1078-1092.
    • Handle: RePEc:eee:ejores:v:248:y:2016:i:3:p:1078-1092
    DOI: 10.1016/j.ejor.2015.08.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715007547
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.08.017?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. Ehud Kalai & Eitan Zemel, 1982. "Totally Balanced Games and Games of Flow," Mathematics of Operations Research, INFORMS, vol. 7(3), pages 476-478, August.
    2. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    3. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Hamers, Herbert & Klijn, Flip & Solymosi, Tamas & Tijs, Stef & Vermeulen, Dries, 2003. "On the nucleolus of neighbor games," European Journal of Operational Research, Elsevier, vol. 146(1), pages 1-18, April.
    5. Solymosi, Tamas & Raghavan, Tirukkannamangai E S, 1994. "An Algorithm for Finding the Nucleolus of Asignment Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(2), pages 119-143.
    6. Solymosi, Tamas & Raghavan, T. E. S. & Tijs, Stef, 2005. "Computing the nucleolus of cyclic permutation games," European Journal of Operational Research, Elsevier, vol. 162(1), pages 270-280, April.
    7. Potters, Jos & Reijnierse, Hans & Biswas, Amit, 2006. "The nucleolus of balanced simple flow networks," Games and Economic Behavior, Elsevier, vol. 54(1), pages 205-225, January.
    8. Xin Chen & Jiawei Zhang, 2009. "A Stochastic Programming Duality Approach to Inventory Centralization Games," Operations Research, INFORMS, vol. 57(4), pages 840-851, August.
    9. Dennis Leech, 2003. "Computing Power Indices for Large Voting Games," Management Science, INFORMS, vol. 49(6), pages 831-837, June.
    10. M. Maschler & B. Peleg & L. S. Shapley, 1979. "Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 303-338, November.
    11. Lemaire, Jean, 1991. "Cooperative Game Theory and its Insurance Applications," ASTIN Bulletin, Cambridge University Press, vol. 21(1), pages 17-40, April.
    12. Andreas S. Schulz & Nelson A. Uhan, 2010. "Sharing Supermodular Costs," Operations Research, INFORMS, vol. 58(4-part-2), pages 1051-1056, August.
    13. Sankaran, Jayaram K, 1991. "On Finding the Nucleolus of an N-Person Cooperative Game," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(4), pages 329-338.
    14. Jeroen Kuipers & Ulrich Faigle & Walter Kern, 2001. "On the computation of the nucleolus of a cooperative game," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(1), pages 79-98.
    15. Fromen, Bastian, 1997. "Reducing the number of linear programs needed for solving the nucleolus problem of n-person game theory," European Journal of Operational Research, Elsevier, vol. 98(3), pages 626-636, May.
    16. Daniel Granot & Michael Maschler, 1998. "Spanning network games," International Journal of Game Theory, Springer;Game Theory Society, vol. 27(4), pages 467-500.
    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. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(4), pages 1087-1109, December.
    2. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions (extended version)," CERS-IE WORKING PAPERS 1914, Institute of Economics, Centre for Economic and Regional Studies.
    3. 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).
    4. Meng, Fan-Yong & Gong, Zai-Wu & Pedrycz, Witold & Chu, Jun-Fei, 2023. "Selfish-dilemma consensus analysis for group decision making in the perspective of cooperative game theory," European Journal of Operational Research, Elsevier, vol. 308(1), pages 290-305.
    5. Reiner Wolff, 2017. "The Integer Nucleolus of Directed Simple Games: A Characterization and an Algorithm," Games, MDPI, vol. 8(1), pages 1-12, February.
    6. Márton Benedek & Jörg Fliege & Tri-Dung Nguyen, 2020. "Finding and verifying the nucleolus of cooperative games," CERS-IE WORKING PAPERS 2021, Institute of Economics, Centre for Economic and Regional Studies.
    7. Meinhardt, Holger Ingmar, 2017. "Simplifying the Kohlberg Criterion on the Nucleolus: A Disproof by Oneself," MPRA Paper 77143, University Library of Munich, Germany.
    8. Meinhardt, Holger Ingmar, 2016. "Finding the Nucleoli of Large Cooperative Games: A Disproof with Counter-Example," MPRA Paper 69789, University Library of Munich, Germany.
    9. Liebmann, Thomas & Kassberger, Stefan & Hellmich, Martin, 2017. "Sharing and growth in general random multiplicative environments," European Journal of Operational Research, Elsevier, vol. 258(1), pages 193-206.

    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. Márton Benedek & Jörg Fliege & Tri-Dung Nguyen, 2020. "Finding and verifying the nucleolus of cooperative games," CERS-IE WORKING PAPERS 2021, Institute of Economics, Centre for Economic and Regional Studies.
    2. Tamas Solymosi & Balazs Sziklai, 2015. "Universal Characterization Sets for the Nucleolus in Balanced Games," CERS-IE WORKING PAPERS 1512, Institute of Economics, Centre for Economic and Regional Studies.
    3. Peter Borm & Herbert Hamers & Ruud Hendrickx, 2001. "Operations research games: A survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 139-199, December.
    4. Qizhi Fang & Bo Li & Xiaohan Shan & Xiaoming Sun, 2018. "Path cooperative games," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 211-229, July.
    5. Guajardo, Mario & Jörnsten, Kurt, 2015. "Common mistakes in computing the nucleolus," European Journal of Operational Research, Elsevier, vol. 241(3), pages 931-935.
    6. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    7. Péter Biró & Walter Kern & Daniël Paulusma, 2012. "Computing solutions for matching games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 75-90, February.
    8. Walter Kern & Daniël Paulusma, 2009. "On the Core and f -Nucleolus of Flow Games," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 981-991, November.
    9. Vijay V. Vazirani, 2023. "LP-Duality Theory and the Cores of Games," Papers 2302.07627, arXiv.org, revised Mar 2023.
    10. Kuipers, Jeroen & Mosquera, Manuel A. & Zarzuelo, José M., 2013. "Sharing costs in highways: A game theoretic approach," European Journal of Operational Research, Elsevier, vol. 228(1), pages 158-168.
    11. Mingming Leng & Mahmut Parlar, 2010. "Analytic solution for the nucleolus of a three‐player cooperative game," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(7), pages 667-672, October.
    12. Vijay V. Vazirani, 2022. "New Characterizations of Core Imputations of Matching and $b$-Matching Games," Papers 2202.00619, arXiv.org, revised Dec 2022.
    13. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions (extended version)," CERS-IE WORKING PAPERS 1914, Institute of Economics, Centre for Economic and Regional Studies.
    14. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(4), pages 1087-1109, December.
    15. Rodica Brânzei & Tamás Solymosi & Stef Tijs, 2005. "Strongly essential coalitions and the nucleolus of peer group games," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(3), pages 447-460, September.
    16. Fromen, Bastian, 1997. "Reducing the number of linear programs needed for solving the nucleolus problem of n-person game theory," European Journal of Operational Research, Elsevier, vol. 98(3), pages 626-636, May.
    17. Elena Iñarra & Roberto Serrano & Ken-Ichi Shimomura, 2020. "The Nucleolus, the Kernel, and the Bargaining Set: An Update," Revue économique, Presses de Sciences-Po, vol. 71(2), pages 225-266.
    18. Uhan, Nelson A., 2015. "Stochastic linear programming games with concave preferences," European Journal of Operational Research, Elsevier, vol. 243(2), pages 637-646.
    19. Svetlana Tarashnina, 2011. "The simplified modified nucleolus of a cooperative TU-game," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(1), pages 150-166, July.
    20. Drechsel, J. & Kimms, A., 2010. "Computing core allocations in cooperative games with an application to cooperative procurement," International Journal of Production Economics, Elsevier, vol. 128(1), pages 310-321, November.

    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:248:y:2016:i:3:p:1078-1092. 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.