"Computing the per-capita nucleolus in balanced games: the case of assignment games" -- talk by Professor Tamás Solymosi (Budapest) Event
For more information regarding this event, please email Tri-Dung Nguyen at T.Nguyen@southampton.ac.uk .
Event details
The nucleolus, one of the major point-valued solutions for cooperative games, lexicographically maximizes the nondecreasingly ordered vector of the coalitional satisfactions (the difference between the payoff to and the value of the coalition) over the set of imputations. This satisfaction measure, however, does not take into account neither the size, nor the value (or any other characteristic that maybe important for an application) of the coalitions. In the first part of the talk, we show that if the core of the game is not empty, coalitions which are not anti-essential (which can be weakly minorized by a partition) in the dual game can be ignored in the computation of the per-capita nucleolus (Solymosi, 2019).
As an application of this general simplification result, in the second part of the talk, we present a strongly polynomial algorithm that computes the per-capita nucleolus in assignment games. It also rests on the following known features of assignment games (Núnez and Solymosi, 2017):
- in the dual game of an assignment game all dually anti-essential coalitions are either single-player or mixed-pair coalitions;
- these the dual game values can be computed by a polynomial time elementary method directly from the pairwise profit matrix that generates the assignment game.
Our algorithm shares the following features with the algorithm of Solymosi and Raghavan (1994) designed to compute the (standard) nucleolus in assignment games:
- starting from one of the two special vertices (here, the seller optimal corner) of the core, the algorithm generates the corresponding special vertices of the iterated per-capita least cores;
- the subsequent points in this (polynomial size) series are found by solving a longest path problem on an associated directed network having no cycle of positive length.
References:
Núnez, M. and Solymosi, T. (2017): Lexicographic allocations and extreme core payoffs: the case of assignment games. Annals of Operations Research 254(1):211-234.
Solymosi, T. (2019): Weighted nucleoli and dually essential coalitions. International Journal of Game Theory, https://doi.org/10.1007/s00182-019-00689-x .
Solymosi, T. and Raghavan, T.E.S. (1994): An algorithm for finding the nucleolus of assignment games. International Journal of Game Theory, 23 (2):119-143.
Speaker information
Professor Tamás Solymosi, Corvinus University of Budapest, Department of Operations Research and Actuarial Sciences, received his Ph.D. in mathematics (game theory) from the University of Illinois at Chicago in 1993. His research focuses on cooperative game theory and its application to various profit / cost allocation problems. He published papers in journals like International Journal of Game Theory, Games and Economic Behavior, European Journal of Operational Research, Annals of Operations Research, Mathematical Programming, and Mathematics of Operations Research.