Finding and verifying the nucleolus of cooperative games

Arbeitspapier

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.

Object Details

• Language: Englisch

References and Relationships

• Bibliographic citation: Series: CERS-IE Working Papers ; No. CERS-IE WP - 2020/21

Classification and Topics

• Classification: Wirtschaft ; Cooperative Games ; Optimization Techniques; Programming Models; Dynamic Analysis
• Subject: nucleolus ; cooperative games ; Kohlberg criterion ; computation

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Benedek, Márton ; Fliege, Jörg ; Nguyen, Tri-Dung
• Event: Veröffentlichung
• (who): Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies
• (where): Budapest
• (when): 2020

Further information

• Handle: http://hdl.handle.net/10419/222090
• Last update: 10.03.2025, 11:41 AM CET