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.     

On the regions of linearity for the nucleolus and their computation

This paper describes a method for computing the linearity regions for the nucleolus for ann-person cooperative game. It also provides a way to compute the nucleolus for games with smalln.     

On the rate of taxation in a cooperative bin packing game

We investigate a cooperative game with two types of players envolved: Every player of the first type owns a unit size bin, and every player of the second type owns an item of size at most one. The value of a coalition of players is defined to be the maximum overall size of packed items over all packings of the items owned by the coalition into the bins owned by the coalition.We prove that for=1/3 this cooperative bin packing game is-balanced in the taxation model of Faigle and Kern (1993).This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.     

The simplified modified nucleolus of a cooperative TU-game

In the present paper, we introduce a new solution concept for TU-games, the simplified modified nucleolus or the SM-nucleolus. It is based on the idea of the modified nucleolus (the modiclus) and takes into account both the constructive power and the blocking power of a coalition. The SM-nucleolus inherits this convenient property from the modified nucleolus, but it avoids its high computational complexity. We prove that the SM-nucleolus of an arbitrary n-person TU-game coincides with the prenucleolus of a certain n-person constant-sum game, which is constructed as the average of the game and its dual. Some properties of the new solution are discussed. We show that the SM-nucleolus coincides with the Shapley value for three-person games. However, this does not hold for general n-person cooperative TU-games. To confirm this fact, a counter example is presented in the paper. On top of this, we give several examples that illustrate similarities and differences between the SM-nucleolus and well-known solution concepts for TU-games. Finally, the SM-nucleolus is applied to the weighted voting games.     

On the existence of a cooperative solution for a coalitional game with externalities

This paper analyzes a game in coalitional form that is derived from a simple economy with multilateral externalities. Following Chander and Tulkens (1997) we assume that agents react to a blocking coalition by choosing individual best reply strategies. A non-empty core of this game is established by showing that the game is balanced. The proof relies only on standard convexity assumptions and, therefore, substantially generalizes the results in Chander and Tulkens (1997). Received June 2000/Revised version March 2001     

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 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.     

A procedure for finding the nucleolus of a cooperativen person game

The nucleolus is a central concept of solution in the theory of cooperativen person games with side payments; it has been introduced and studied by Schmeidler [1969] and several methods for finding the nucleolus have been proposed byKopelowitz [1967],Bruyneel [1979],Stearns [1968] andJustman [1977], respectively. The aim of the present paper is that of giving a new algorithm for finding the nucleolus and to discuss the relationship of this algorithm with those given by Kopelowitz and Bruyneel.The algorithm is based upon the concept of minimal balanced set of a finite set; this last concept has been introduced for other purposes byShapley [1967]. The relationship between the nucleolus and the balanced sets has been studied byKohlberg [1971], where it has been shown that the so-called coalition array of an imputation is the coalition array of the nucleolus iff some parts of it are balanced sets. Our algorithm computes such a coalition array by finding a sequence of minimal balanced sets. Any element of the sequence can be found be solving a LP problem, then the nucleolus is easily found from the coalition array.The algorithm is in some sense a dual of the Kopelowitz algorithm. It clarifies completely the relationship between the nucleolus and the minimal balanced sets, that allowed the statement of the Bruyneel's algorithm; moreover, our algorithm doesn't assume the knowledge of the list of weight vectors associated to the set of minimal balanced sets, but constructs only the part of the list needed for finding the nucleolus.

---

Zusammenfassung Ein kooperativesn-Personen-Spiel wird durch eine endliche MengeN (die Spielermenge) und eine nicht additive Mengenfunktionv, definiert auf der Potenzmenge vonN (d.h. auf den Koalitionen), charakterisiert. Auf Schmeidler geht der Begriff des Nukleolus als eines für ein kooperatives Spiel geeigneten Lösungskonzeptes zurück. Bruyneel und Kopelowitz haben jeweils Algorithmen zur Berechnung des Nukleolus eines vorgegebenen kooperativen Spieles angegeben. Das vorliegende Papier gibt einen weiteren Algorithmus an. Dieser ist — ähnlich wie der von Bruyneel entwickelte — begrifflich gestützt auf das Konzept der minimal balancierten Koalitionssysteme (eingeführt von Shapley). In seiner direkten Form benötigt der Algorithmus die Liste aller zu minimal balancierten Mengensystemen gehörenden Gewichtsvektoren, jedoch wird in Abschnitt 2 eine Methode angegeben, diese Liste mit Hilfe einer Folge linearer Programme zu vermeiden. Es stellt sich heraus, daß der vorgelegte Algorithmus in gewisser Weise dual zu dem von Kopelowitz entwickelten ist. Ein Vergleich aller drei nunmehr vorliegenden Algorithmen findet sich in Abschnitt 2.

     

Observations on the nucleolus and the central game

Some theorems containing new results on the nucleolus and the central game are proven.     

Price oligopoly as a cooperative game

We consider an oligopolistic market as follows. In the market, one good is traded for money. Each oligopolist is a price setter and has the same linear cost function. Each buyer is a price taker and buys the good from oligopolists setting the lowest price. We formulate this market as a cooperative game, and consider two kinds of solution concepts, the core and a bargaining set of the game. First we show that in the monopolistic market, the core gives the monopoly price, but in the oligopolistic market, the core is empty. Second, we obtain the bargaining set of the oligopolistic market.     

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 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.     

Maximizing selections from the core of a cooperative game

A core selection is a function which for each cooperative game with non-empty core selects a subset, possibly a single element, of the core. In this paper, we study selections which maximize some function or binary relation on the core. We present an axiomatic characterization of such core selections, as well as a local characterization using duality which can be applied to investigate properties of core selections. We give an application of the local characterization to a question of coalitional monotonicity of core selections.     

A procedure to compute the nucleolus of the assignment game

The assignment game introduced by Shapley and Shubik (1972)  [6] is a model for a two-sided market where there is an exchange of indivisible goods for money and buyers or sellers demand or supply exactly one unit of the goods. We give a procedure to compute the nucleolus of any assignment game, based on the distribution of equal amounts to the agents, until the game is reduced to fewer agents.     

Comparative cooperative game theory

Given two side-payment gamesv andw, both defined for the same finite player-setN, the following three welfare criteria are characterized in terms of the datav andw: (A) For everyy C(w) there existsx C(v) such thatyx; (A) For everyxC(v) there existsyC(w) such thatyx; and (B) There existyC(w) andxC(v) such thatyx. (HereC(v) denotes the core ofv.) Given two non-side-payment gamesv andw, sufficient conditions for the criteria (A) and (B) are established, by observing that an ordinal convex game has a large core.In memory of my teacher in Japan, Professor Ryuichi Watanabe, 1928–1986.     

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.