Characterization sets for the nucleolus
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.
- A characterization of the nucleolus for convex games
- On the computation of the nucleolus of a cooperative game
- On the 1-nucleolus
- Characterization sets for the nucleolus in balanced games
- The nucleolus of arborescence games in directed acyclic graphs
- Computing the nucleolus when the characteristic function is given implicitly: A constraint generation approach
- Nonsymmetric variants of the prekernel and the prenucleolus
- Finding the nucleolus of the vehicle routing game with time windows
- An algorithm to compute the nucleolus of shortest path games
- Finding and verifying the nucleolus of cooperative games
- A heuristic procedure for computing the nucleolus
- Strongly essential coalitions and the nucleolus of peer group games
- On the complexity of nucleolus computation for bipartite \(b\)-matching games
- The complexity of the nucleolus in compact games
- Analytic solution for the nucleolus of a three-player cooperative game
- scientific article; zbMATH DE number 3865013 (Why is no real title available?)
- scientific article; zbMATH DE number 4152185 (Why is no real title available?)
- Fast computation of the leastcore and prenucleolus of cooperative games
- scientific article; zbMATH DE number 149952 (Why is no real title available?)
- Characterization of the nucleolus for a class ofn-person games
- scientific article; zbMATH DE number 1999237 (Why is no real title available?)
- GEOMETRY AND COMPUTATION OF THE LORENZ SET
- Computing the Nucleolus by Solving a Prolonged Simplex Algorithm
- On the core and nucleolus of directed acyclic graph games
- A COMPUTATIONAL APPROACH TO THE COINCIDENCE OF EGALITARIAN SOLUTIONS FOR COST-SHARING GAMES
- Finding nucleolus of flow game
- Characterizations of the \(\mathbf{u}\)-prenucleolus by dually-\(\mathbf{u}\)-essential coalitions
- Cost allocation for set covering: the happy nucleolus
This page was built for publication: Characterization sets for the nucleolus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1972591)
