Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/222090
Authors: 
Benedek, Márton
Fliege, Jörg
Nguyen, Tri-Dung
Year of Publication: 
2020
Series/Report no.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/21
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.
Subjects: 
nucleolus
cooperative games
Kohlberg criterion
computation
JEL: 
C71
C61
Document Type: 
Working Paper

Files in This Item:
File
Size
815.59 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.