Reducing the number of linear programs needed for solving the nucleolus problem of n-person game theory

The algorithm for finding the nucleolus of a cooperative n-person-game introduced by Sankaran is compared to an earlier procedure by Behringer. It turns out that the latter is in every respect the superior one. In both concepts the computation of the nucleolus is reduced to the solution of a finite sequence of linear programs. Their number is O(2ⁿ). A method of reducing the number of linear programs to O(n) while not changing their size will be introduced.     

An algorithm for finding the nucleolus of assignment games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.     

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

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.     

A note on the nucleolus

It was shown byKohlberg [1972] that the nucleolus can be obtained by solving a linear program of extremely large size (2 ⁿ ! constraints). We show here how this program can be reduced to a more tractable size (4 ⁿ constraints).     

A note on the nucleolus for 2-convex TU games

For 2-convex n-person cooperative TU games, the nucleolus is determined as some type of constrained equal award rule. Its proof is based on Maschler, Peleg, and Shapley’s geometrical characterization for the intersection of the prekernel with the core. Pairwise bargaining ranges within the core are required to be in equilibrium. This system of non-linear equations is solved and its unique solution agrees with the nucleolus.     

On the nucleolus of NTU-games defined by multiple objective linear programs

In this article we derive a class of cooperative games with non-transferable utility from multiple objective linear programs. This is done in order to introduce the nucleolus, a solution concept from cooperative game theory, as a solution to multiple objective linear problems.We show that the nucleolus of such a game is a singleton, which is characterized by inclusion in the least core and the reduced game property. Furthermore the nucleolus satisfies efficiency, anonymity and strategic equivalence.We also present a polynomially bounded algorithm for computation of the nucleolus. Letn be the number of objective functions. The nucleolus is obtained by solving at most2n linear programs. Initially the ideal point is computed by solvingn linear programs. Then a sequence of at mostn linear programs is solved, and the nucleolus is obtained as the unique solution of the last program.Financial support from Nordic Academy for Advanced Study (NorFA) is gratefully acknowledged. Part of this work was done during autumn 1993 at Institute of Finance and Management Science, Norwegian School of Economics and Business Administration.     

The nucleolus and kernel for simple games or special valid inequalities for 0–1 linear integer programs

An equivalence between simplen-person cooperative games and linear integer programs in 0–1 variables is presented and in particular the nucleolus and kernel are shown to be special valid inequalities of the corresponding 0–1 program. In the special case of weighted majority games, corresponding to knapsack inequalities, we show a further class of games for which the nucleolus is a representation of the game, and develop a single test to show when payoff vectors giving identical amounts or zero to each player are in the kernel. Finally we give an algorithm for computing the nucleolus which has been used successfully on weighted majority games with over twenty players.     

The τ-value,The core and semiconvex games

Theτ-value for cooperativen-person games is central in this paper. Conditions are given which guarantee that theτ-value lies in the core of the game. A full-dimensional cone of semiconvex games is introduced. This cone contains the cones of convex and exact games and there is a simple formula for theτ-value for such games. The subclass of semiconvex games with constant gap function is characterized in several ways. It turns out to be an (n+1)-dimensional cone and for all games in this cone the Shapley value, the nucleolus and theτ-value coincide.     

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.     

Solution concepts ofk-convexn-person games

For any positive integersk andn, the subclass ofk-convexn-person games is considered. In casek=n, we are dealing with convexn-person games. Three characterizations ofk-convexn-person games, formulated in terms of the core and certain adapted marginal worth vectors, are given. Further it is shown that fork-convexn-person games the intersection of the (pre)kernel with the core consists of a unique point (namely the nucleolus), but that the (pre)kernel may contain points outside the core. For certain 1-convex and 2-convexn-person games the part of the bargaining set outside the core is even disconnected with the core. The Shapley value of ank-convexn-person game can be expressed in terms of the extreme points of the core and a correction-vector whenever the game satisfies a certain symmetric condition. Finally, theτ-value of ank-convexn-person game is given.     

On the comparative accuracy of lexicographical solutions in cooperative games

This study assesses the relative predictive accuracy of three lexicographical solution concepts within a context of eight 3-person, cooperative, superadditive, side-payment games with non-empty core. The solution concepts include the nucleolus [Schmeidler], the disruption nucleolus [Littlechild/Vaidya], and the 2-center solution [Spinetto, 1971]. The experiment involved 480 subjects (half male, half female) who participated in 160 randomly formed 3-person groups. Results indicate that the disruption nucleolus is significantly more accurate than the nucleolus (p<.01), which in turn is significantly more accurate than the 2-center solution (p<.01). These findings are discussed in terms of the lexicographical structure of the theories.     

On the core and nucleolus of minimum cost spanning tree games

We develop two efficient procedures for generating cost allocation vectors in the core of a minimum cost spanning tree (m.c.s.t.) game. The first procedure requires O(n ²) elementary operations to obtain each additional point in the core, wheren is the number of users. The efficiency of the second procedure, which is a natural strengthening of the first procedure, stems from the special structure of minimum excess coalitions in the core of an m.c.s.t. game. This special structure is later used (i) to ease the computational difficulty in computing the nucleolus of an m.c.s.t. game, and (ii) to provide a geometric characterization for the nucleolus of an m.c.s.t. game. This geometric characterization implies that in an m.c.s.t. game the nucleolus is the unique point in the intersection of the core and the kernel. We further develop an efficient procedure for generating fair cost allocations which, in some instances, coincide with the nucleolus. Finally, we show that by employing Sterns' transfer scheme we can generate a sequence of cost vectors which converges to the nucleolus. Part of this research was done while the author was visiting the Department of Operations Research at Stanford University. This research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A-4181.     

Strongly essential coalitions and the nucleolus of peer group games

Most of the known efficient algorithms designed to compute the nucleolus for special classes of balanced games are based on two facts: (i) in any balanced game, the coalitions which actually determine the nucleolus are essential; and (ii) all essential coalitions in any of the games in the class belong to a prespecified collection of size polynomial in the number of players. We consider a subclass of essential coalitions, called strongly essential coalitions, and show that in any game, the collection of strongly essential coalitions contains all the coalitions which actually determine the core, and in case the core is not empty, the nucleolus and the kernelcore. As an application, we consider peer group games, and show that they admit at most 2n−1 strongly essential coalitions, whereas the number of essential coalitions could be as much as 2ⁿ⁻¹. We propose an algorithm that computes the nucleolus of an n-player peer group game in time directly from the data of the underlying peer group situation.Research supported in part by OTKA grant T030945. The authors thank a referee and the editor for their suggestions on how to improve the presentation     

Allocating joint costs by means of the nucleolus

This paper presents a sufficient condition for the nucleolus to coincide with the SCRB method vector and for nonemptiness of the core. It also studies the reasonableness and the monotonicity of the nucleolus under this condition. Finally it analyses the class of games satisfying the condition and compares it with the classes of convex games, subconvex games and the classQ of Driessen and Tijs.     

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.     

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.

     

The nucleolus and the core-center of multi-sided Böhm-Bawerk assignment markets

We prove that both the nucleolus and the core-center, i.e., the mass center of the core, of an m-sided Böhm-Bawerk assignment market can be respectively computed from the nucleolus and the core-center of a convex game defined on the set of m sectors. What is more, in the calculus of the nucleolus of this latter game only singletons and coalitions containing all agents but one need to be taken into account. All these results simplify the computation of the nucleolus and the core-center of a multi-sided Böhm-Bawerk assignment market with a large number of agents. As a consequence we can show that, contrary to the bilateral case, for multi-sided Böhm-Bawerk assignment markets the nucleolus and the core-center do not coincide in general.     

Iterative processes with „nucleolar“ restrictions

Some aspects of the convergence of iterative processes are examined in a general context and a specific iterative process that generalizesStearns' K-transfer schemes is evolved. This yields a simplified proof ofStearns' convergence theorem and an iterative scheme that converges to the nucleolus. Stability and finite convergence properties are shown to hold and various known results on the nucleolus derive as by-products.