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.     

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.     

Balancedness of infrastructure cost games

In this paper we study the class of infrastructure cost games. A game in this class models the infrastructure costs (both building and maintenance) produced when a set of users of different types makes use of a certain infrastructure, which may consist of several facilities. Special attention is paid to one facility infrastructure cost games. Such games are modeled as the sum of an airport game and a maintenance cost game. It turns out that the core and nucleolus of these games are very closely related to the core and nucleolus of an associated generalized airport game. Furthermore we provide necessary and sufficient conditions under which an infrastructure cost game is balanced.     

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

最短路博弈群体单调分配方案构造

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。     

最短路博弈群体单调分配方案构造

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。     

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     

Linear complementarity and discounted switching controller stochastic games

The class of discounted switching controller stochastic games can be solved in one step by a linear complementarity program (LCP). Following the proof of this technical result is a discussion of a special formulation and initialization of a standard LCP pivoting algorithm which has, in numerical experiments, always terminated in a complementary solution. That the LCP algorithm as formulated always finds a complementary solution has not yet been proven, but these theoretical and experimental results have the potential to provide an alternative proof of the ordered field property for these games. Numerical experimentation with the reformulated LCP is reviewed.     

凸对策核仁的非空性及合成凸对策核仁的单调性

本文给出了核仁与核及最小核心之间的关系 ,且证明了凸对策核仁的存在性和唯一性 ,证明了凸对策的合成对策仍是凸对策 .最后 ,我们讨论了合成凸对策的核仁不满足单调性 .     

A tractable multi-leader multi-follower peak-load-pricing model with strategic interaction

While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems.

     

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.     

On the core and nucleolus of directed acyclic graph games

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game—including monotonic minimum cost spanning tree games—can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-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.     

Credibility of Incentive Equilibrium Strategies in Linear-State Differential Games

We characterize in this paper the credibility of incentive equilibrium strategies for the class of linear-state differential games. We derive a general condition for credibility and illustrate its use on two differential games taken from the literature of environmental economics and knowledge accumulation. We show that the proposed linear incentive strategies are not always credible. Further, we provide alternative nonlinear credible strategies which suggest that we should not stick only to linear incentive strategies, even in a simple class of differential games such as the linear-state one.This research was completed when the first author was visiting professor at GERAD, HEC, Montréal. The first author’s research was partially supported by MCYT under project BEC2002-02361 and by JCYL under project VA051/03, confinanced by FEDER funds. The second author’s research was supported by NSERC, Canada.     

Weighted allocation rules for standard fixed tree games

In this paper we consider standard fixed tree games, for which each vertex unequal to the root is inhabited by exactly one player. We present two weighted allocation rules, the weighted down-home allocation and the weighted neighbour-home allocation, both inspired by the painting story in Maschler et al. (1995) . We show, in a constructive way, that the core equals both the set of weighted down-home allocations and the set of weighted neighbour allocations. Since every weighted down-home allocation specifies a weighted Shapley value (Kalai and Samet (1988)) in a natural way, and vice versa, our results provide an alternative proof of the fact that the core of a standard fixed tree game equals the set of weighted Shapley values. The class of weighted neighbour allocations is a generalization of the nucleolus, in the sense that the latter is in this class as the special member where players have all equal weights.     

Coalitional games: Monotonicity and core

We characterize a monotonic core solution defined on the class of veto balanced games. We also discuss what restricted versions of monotonicity are possible when selecting core allocations. We introduce a family of monotonic core solutions for veto balanced games and we show that, in general, the per capita nucleolus is not monotonic.     

Resource allocation games: a compromise stable extension of bankruptcy games

This paper presents an extension of the traditional bankruptcy problem. In a resource allocation problem there is a common-pool resource, which needs to be divided among agents. Each agent is characterized by a claim on this pool and an individual linear monetary reward function for assigned resources. Analyzing these problems a new class of transferable utility games is introduced, called resource allocation games. These games are based on the bankruptcy model, as introduced by O’Neill (Math Soc Sci 2:345–371, 1982). It is shown that the properties of totally balancedness and compromise stability can be extended to resource allocation games, although the property of convexity is not maintained in general. Moreover, an explicit expression for the nucleolus of these games is provided.     

A simple procedure to compute the nucleolus of Γ-component additive games

Summary This paper considers the Γ-component additive games which take into account the possibilities of communications among agents located in the nodes of a tree graph Γ. Gains from cooperation are derived from agents who are directly connected in the tree. We introduce a new procedure to compute the nucleolus for these games. This procedure is quick and it does not use linear programming techniques. We finally present a numerical example of a sequencing game to illustrate the procedure. This research has been supported partially by UPV-EHU research projects: 035.321-HA 130/93 and GV research proyects: 035.321-0046/93.