On the computation of the nucleolus of a cooperative game

We consider classes of cooperative games. We show that we can efficiently compute an allocation in the intersection of the prekernel and the least core of the game if we can efficiently compute the minimum excess for any given allocation. In the case where the prekernel of the game contains exactly one core vector, our algorithm computes the nucleolus of the game. This generalizes both a recent result by Kuipers on the computation of the nucleolus for convex games and a classical result by Megiddo on the nucleolus of standard tree games to classes of more general minimum cost spanning tree games. Our algorithm is based on the ellipsoid method and Maschler's scheme for approximating the prekernel. Received February 2000/Final version April 2001     

The modified nucleolus: Properties and axiomatizations

A new solution concept for cooperative transferable utility games is introduced, which is strongly related to the nucleolus and therefore called modified nucleolus. It takes into account both the “power”, i.e. the worth, and the “blocking power” of a coalition, i.e. the amount which the coalition cannot be prevented from by the complement coalition. It can be shown that the modified nucleolus is reasonable, individually rational for weakly superadditive games, coincides with the prenucleolus for constant-sum games, and is contained in the core for convex games. Finally this paper proposes two axiomatizations of this solution concept on the set of games on an infinite universe of players which are similar to Sobolev's characterization of the prenucleolus.     

The nucleolus for cooperative games with arbitrary bounds of individual rationality

We consider cooperative games with a given bound for individual rationality. We introduce the nucleolus with respect to the set of preimputations satisfying the newly defined bounds of rationality. An axiomatization of this nucleolus is given.     

The least square nucleolus is a general nucleolus

This short note proves that the least square nucleolus (Ruiz et al. (1996)) and the lexicographical solution (Sakawa and Nishizaki (1994)) select the same imputation in each game with nonempty imputation set. As a consequence the least square nucleolus is a general nucleolus (Maschler et al. (1992)). Received: December 1998/Revised version: July 1999     

On finding the nucleolus of an n-person cooperative game

Kohlberg (1972) has shown how the nucleolus for ann-person game with side-payments may be found by solving a single minimization LP in case the imputation space is a polytope. However the coefficients in the LP have a very wide range even for problems with 3 or 4 players. Therefore the method is computationally viable only for small problems on machines with finite precision. Maschler et al. (1979) find the nucleolus by solving a sequence of minimization LPs with constraint coefficients of either –1, 0 or 1. However the number of LPs to be solved is o(4 ⁿ ). In this paper, we show how to find the nucleolus by solving a sequence of o(2 ⁿ ) LPs whose constraint coefficients are –1, 0 or 1.     

A cooperative game of information trading: The core,the nucleolus and the kernel

A certain trade of the information about a technological innovation between the initial owner of the information andn identical producers is studied by means of a cooperative game theoretic approach. The information trading situation is modelled as a cooperative (n+1)-person game with side payments. The symmetrical strong -cores (including the core), the nucleolus and the kernel of the cooperative game model are determined. Interpretations of these game theoretic solutions and their implications for the information trading problem are given.     

Core,least core and nucleolus for multiple scenario cooperative games

Multiple scenario cooperative games model situations where the worth of the coalitions is valued in different scenarios simultaneously or under different states of nature. In this paper we analyze solution concepts for this class of games keeping the multidimensional nature of the characteristic function. We obtain extensions of the notions of core, least core and nucleolus, and explore the relationship among these solution concepts.     

The nucleolus is well-posed

The lexicographic order is not representable by a real-valued function, contrary to many other orders or preorders. So, standard tools and results for well-posed minimum problems cannot be used. We prove that under suitable hypotheses it is however possible to guarantee the well-posedness of a lexicographic minimum over a compact or convex set. This result allows us to prove that some game theoretical solution concepts, based on lexicographic order are well-posed: in particular, this is true for the nucleolus.     

The kernel/nucleolus of a standard tree game

In this paper we characterize the nucleolus (which coincides with the kernel) of a tree enterprise. We also provide a new algorithm to compute it, which sheds light on its structure. We show that in particular cases, including a chain enterprise one can compute the nucleolus in O(n) operations, wheren is the number of vertices in the tree.     

The nucleolus of trees with revenues

Trees with revenues are a generalization of standard trees. In a tree with revenues, players have to pay for their connections to the root, but a player can also earn some revenue from being connected to the root. In this paper, we present an algorithm for calculating the nucleolus.     

The sigma-core of a cooperative game

This paper is concerned with the existence of (σ-additive) measures in the core of a cooperative game. The main theorem shows, for a capacityu on the Borel sets of a metric space, that to each additive set function, majorized byu and agreeing withu on a system of closed sets, there exists a measure having these same properties. This theorem is applied, in combination with known core theorems, to the case of a cooperative game defined on the Borel sets of a metric space and whose conjugate is a capacity.     

The kernel and the nucleolus of a product of simple games

The kernel and the nucleolus of a product of two simple games are given in terms of the kernels and the nucleoluses of the component games.     

The positive core of a cooperative game

The positive core is a nonempty extension of the core of transferable utility games. If the core is nonempty, then it coincides with the core. It shares many properties with the core. Six well-known axioms that are employed in some axiomatizations of the core, the prenucleolus, or the positive prekernel, and one new intuitive axiom, characterize the positive core for any infinite universe of players. This new axiom requires that the solution of a game, whenever it is nonempty, contains an element that is invariant under any symmetry of the game.     

The semireactive bargaining set of a cooperative game

The semireactive bargaining set, a solution for cooperative games, is introduced. This solution is in general a subsolution of the bargaining set and a supersolution of the reactive bargaining set. However, on various classes of transferable utility games the semireactive and the reactive bargaining set coincide. The semireactive prebargaining set on TU games can be axiomatized by one-person rationality, the reduced game property, a weak version of the converse reduced game property with respect to subgrand coalitions, and subgrand stability. Furthermore, it is shown that there is a suitable weakening of subgrand stability, which allows to characterize the prebargaining set. Replacing the reduced game by the imputation saving reduced game and employing individual rationality as an additional axiom yields characterizations of both, the bargaining set and the semireactive bargaining set. Received September 2000/Revised version June 2001     

The propensity to disrupt and the disruption nucleolus of a characteristic function game

Gately [1974] recently introduced the concept of an individual player's “propensity to disrupt” a payoff vector in a three-person characteristic function game. As a generalisation of this concept we propose the “disruption nucleolus” of ann-person game. The properties and computational possibilities of this concept are analogous to those of the nucleolus itself. Two numerical examples are given.     

The general nucleolus and the reduced game property

The nucleolus of a TU game is a solution concept whose main attraction is that it always resides in any nonempty -core. In this paper we generalize the nucleolus to an arbitrary pair (,F), where is a topological space andF is a finite set of real continuous functions whose domain is . For such pairs we also introduce the least core concept. We then characterize the nucleolus forclasses of such pairs by means of a set of axioms, one of which requires that it resides in the least core. It turns out that different classes require different axiomatic characterizations.One of the classes consists of TU-games in which several coalitions may be nonpermissible and, moreover, the space of imputations is required to be a certain generalized core. We call these gamestruncated games. For the class of truncated games, one of the axioms is a new kind ofreduced game property, in which consistency is achieved even if some coalitions leave the game, being promised the nucleolus payoffs. Finally, we extend Kohlberg's characterization of the nucleolus to the class of truncated games.     

The nucleolus and kernel of veto-rich transferable utility games

The process of computing the nucleolus of arbitrary transferable utility games is notoriously hard. A number of papers have appeared in which the nucleolus is computed by an algorithm in which either one or a huge number of huge linear programs have to be solved. We show that on the class of veto-rich games, the nucleolus is the unique kernel element. Veto-rich games are games in which one of the players is needed by coalitions in order to obtain a non-zero payoff. We then provide a fast algorithm which does not use linear programming techniques to compute the nucleolus of these games. Furthermore, we provide a few examples of economic situations which belong to the class of veto-rich games and which are treated in the literature.     

The core of a cooperative game without side payments

For cooperative games without side payments, there are several types of conditions which guarantee nonemptiness of the core, for example balancedness and convexity. In the present paper, a general condition for nonempty core is introduced which includes the known ones as special cases. Moreover, it is shown that every game with nonempty core satisfies this condition.     

The nucleolus of a standard tree game revisited: a study of its monotonicity and computational properties

This paper introduces yet another algorithm to compute the nucleolus of a standard tree game. One advantage of this algorithm is that it provides a very intuitive interpretation of the nucleolus, under which the players participate in a joint enterprize in which each group sends a member to help the community. Another advantage is that it demonstrates monotonicity properties of the nucleolus within this class of games. As a consequence the nucleolus of a tree game can be extended to a population monotonic allocation scheme.