Wednesday, 15:15 - 15:40 h, Room: MA 043


Tri-Dung Nguyen
Finding solutions of large cooperative games


The nucleolus is one of the most important solution concepts in cooperative game theory as a result of its attractive properties - it always exists, is unique, and is always in the core (if the core is non-empty). However, computing the nucleolus is very challenging because this involves lexicographical minimization of an exponentially large number of excess values. We present a method for computing the nucleolus of large games. We formulate the problem as nested LPs and solve them using a constraint generation algorithm. Although the nested LPs formulation has been documented in the literature, it has not been used for large games because of the large LPs involved. In addition, subtle issues such as how to deal with multiple optimal solutions and with large tight constraint sets have not been discussed in the literature. These issues are crucial and need to be resolved in each LP in order to formulate and solve the subsequent ones. We treat them rigorously and show that the nucleolus can be found efficiently as long as the worst coalition can be identified for a given imputation. We demonstrate our methodology with the case of the weighted voting games with up to 100 players.


Talk 1 of the contributed session Wed.3.MA 043
"Solving cooperative games" [...]
Cluster 8
"Game theory" [...]


  . Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.