Complements,mollifiers and the propensity to disrupt

Gately [1974] andLittlechild/Vaidya [1976] defined and studied ratio measures of “disruption propensity” of coalitions in ann-person game. We define and study new incremental measures giving rise to a wide variety of “disruption solution” concepts free of various ratio defects and affording advantages of analysis and acceptability in terms of solution specifications. Various “mollifier” and “homomollifier” solution concepts are characterized which appear to be of promising utility.     

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

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.     

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     

Observations on the nucleolus and the central game

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

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.

     

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.     

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.     

Computing the nucleolus when the characteristic function is given implicitly: A constraint generation approach

We study a class of cooperative games that is such that the values of the characteristic function are given implicitly. A constraint generation procedure can be applied to compute the nucleolus (and related solutions) of such a game, even if the number of players is large.     

A note on the nucleolus and the kernel of the assignment game

There exist coalitional games with transferable utility which have the same core but different nucleoli. We show that this cannot happen in the case of assignment games. Whenever two assignment games have the same core, their nucleoli also coincide. To show this, we prove that the nucleolus of an assignment game coincides with that of its buyer–seller exact representative.I am grateful to C. Rafels and to the referees for their comments. Institutional support from research grants BEC 2002-00642 and SGR2001–0029 is also acknowledged.     

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.     

Finding the nucleolus of the vehicle routing game with time windows

Computing the nucleolus is recognized as an equitable solution to cooperative n person cost games, such as a vehicle routing game (VRG). Computing the nucleolus of a VRG, however, has been limited to small-sized benchmark instances with no more than 25 players, because of the computation time required to solve the NP-hard separation problem. To reduce computation time, we develop an enumerative algorithm that computes the nucleolus of the VRG with time windows (VRGTW) in the case of the non-empty core. Numerical simulations demonstrate the ability of the proposed algorithm to compute the nucleolus of benchmark instances with up to 100 players.     

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     

The canonical function game

The canonical function game is a game of length ω ₁ introduced by W. Hugh Woodin which falls inside a class of games known as Neeman games. Using large cardinals, we show that it is possible to force that the game is not determined. We also discuss the relationship between this result and Σ² ₂ absoluteness, cardinality spectra and Π₂ maximality for H(ω ₂) relative to the Continuum Hypothesis.     

The Sprague-Grundy function of the game Euclid

We show that the Sprague-Grundy function of the game Euclid is given by g(x,y)=⌊|y/x-x/y|⌋ for x,y≥1.