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.     

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.     

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

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 asymptotic core,nucleolus and Shapley value of smooth market games with symmetric large players

We examine the asymptotic nucleolus of a smooth and symmetric oligopoly with an atomless sector in a transferable utility (TU) market game. We provide sufficient conditions for the asymptotic core and the nucleolus to coincide with the unique TU competitive payoff distribution. This equivalence results from nucleolus of a finite TU market game belonging to its core, the core equivalence in a symmetric oligopoly with identical atoms and single-valuedness of the core in the limiting smooth game. In some cases (but not always), the asymptotic Shapley value is more favourable for the large traders than the nucleolus, in contrast to the monopoly case (Einy et al. in J Econ Theory 89(2):186–206, 1999), where the nucleolus allocation is larger than the Shapley value for the atom.     

The kernel and bargaining set for convex games

It is shown that for convex games the bargaining set? ₁ ⁽ⁱ⁾ (for the grand coalition) coincides with the core. Moreover, it is proved that the kernel (for the grand coalition) of convex games consists of a unique point which coincides with the nucleolus of the game.     

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

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

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.     

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.     

Monotonic core solutions: beyond Young’s theorem

Young’s theorem implies that every core concept violates monotonicity. In this paper, we investigate when such a violation of monotonicity by a given core concept is justified. We introduce a new monotonicity property for core concepts. We pose several open questions for this new property. The open questions arise because the most important core concepts (the nucleolus and the per capita nucleolus) do not satisfy the property even in the class of convex games.     

Spanning network games

We study fundamental properties of monotone network enterprises which contain public vertices and have positive and negative costs on edges and vertices. Among the properties studied are the nonemptiness of the core, characterization of nonredundant core constraints, ease of computation of the core and the nucleolus, and cases of decomposition of the core and the nucleolus. Received December 1994/Final version March 1998     

简单网络流对策的相对N-核

主要研究简单网络流对策中相对N-核的算法.当网络中最大流值等于1时,证明相对N-核与对策的核心相同,不一定是单点集;而当网络中最大流值大于1时,利用Kopelowitz's序列线性规划方法和线性规划对偶理论,证明相对N-核与N-核相同(同为单点集),并且可在局中人个数的多项式时间内得到求解.     

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.     

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.     

Some recent results inn-person game theory

The discussion will center mainly on some work on two solution concepts: the core for gaines without side payments and the nucleolus for games with side payments (characteristic funtion games). The core has become an important equilibrium concept in mathematical economics. The nucleolus is related to the theory of bargaining sets.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.This work was supported by the National Science Foundation under grant GK-4795.