Characterization sets for the nucleolus (Q1972591)

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.