Finding and verifying the nucleolus of cooperative games

Márton Benedek, Jörg Fliege () and Tri-Dung Nguyen ()
Additional contact information
Jörg Fliege: Mathematical Sciences, University of Southampton, University Road, Southampton, SO17 1BJ, United Kingdom
Tri-Dung Nguyen: Mathematical Sciences, Business School and CORMSIS, University of Southampton, Southampton, SO17 1BJ, United Kingdom

No 2021, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

Abstract: The nucleolus offers a desirable payoff-sharing solution in cooperative games, thanks to its attractive properties. Although computing the nucleolus is very challenging, the Kohlberg criterion offers a method for verifying whether a solution is the nucleolus in relatively small games (number of players n at most 15). This approach becomes more challenging for larger games as the criterion involves possibly exponentially large collections of coalitions, with each collection being potentially exponentially large. The aim of this work is twofold. First, we develop an improved Kohlberg criterion that involves checking the `balancedness' of at most (n-1) sets of coalitions. Second, we exploit these results and introduce a novel descent-based constructive algorithm to find the nucleolus efficiently. We demonstrate the performance of the new algorithms by comparing them with existing methods over different types of games. Our contribution also includes the first open-source code for computing the nucleolus of moderately large games.

Keywords: nucleolus; cooperative games; Kohlberg criterion; computation (search for similar items in EconPapers)
JEL-codes: C61 C71 (search for similar items in EconPapers)
Pages: 54 pages
Date: 2020-05
New Economics Papers: this item is included in nep-cmp, nep-gth and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mtakti.hu/wp-content/uploads/2020/05/CERSIEWP202021.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:has:discpr:2021

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).