Characterization sets for the nucleolus
type: Item
instance of: scholarly article
title: Characterization sets for the nucleolus
zbMATH Open document ID: 0960.91009
author: Frieda Granot
author: Daniel Granot
author: Weiping R. Zhu
published in: International Journal of Game Theory
publication date: 2000-04-11T00:00:00Z
review text: The authors note that, although the problem of computing the nucleolus of a cooperative game in characteristic function form entails comparisons between vectors whose length grows exponentially as the number of players, in many special cases algorithms are known whose computational effort, in the worst case, grows only as a polynomial function of the number of players. The authors note that in these special cases, such as the assignment games, fixed cost spanning forest games and certain routing games, efficient algorithms are based on the observation that the information needed to characterize the nucleolus is much less than what the general definition would indicate. The authors generalize this approach of efficient computing in these special cases to more general cooperative games. They introduce the concept of a characterization set which embodies the notion of minimum relevant information needed to characterize the nucleolus of a class of games. Sufficient conditions are derived for a family of coalitions to form a characterization set. Finally it is shown that if the nucleolus of a game has a characterization set whose size grows only as a polynomial function of the number of players, then the nucleolus of this game can be computed by a strongly polynomial algorithm.
Mathematics Subject Classification ID: 91A12
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 1429817
zbMATH Keywords: oooperative game
zbMATH Keywords: nucleolus
zbMATH Keywords: strongly polynomial algorithm
zbMATH Keywords: minimum cost spanning tree games
reviewed by: Srinivas Raghava Mohan
MaRDI profile type: Publication
full work available at URL: s001820050078
OpenAlex ID: W2066311617
DOI: 10.1007/S001820050078
description: scientific article; zbMATH DE number 1429817