The prenucleolus and the prekernel for games with communication structures

It is well-known that the prekernel on the class of TU games is uniquely determined by non-emptiness, Pareto efficiency (EFF), covariance under strategic equivalence (COV), the equal treatment property, the reduced game property (RGP), and its converse. We show that the prekernel on the class of TU games restricted to the connected coalitions with respect to communication structures may be axiomatized by suitably generalized axioms. Moreover, it is shown that the prenucleolus, the unique solution concept on the class of TU games that satisfies singlevaluedness, COV, anonymity, and RGP, may be characterized by suitably generalized versions of these axioms together with a property that is called “independence of irrelevant connections”. This property requires that any element of the solution to a game with communication structure is an element of the solution to the game that allows unrestricted cooperation in all connected components, provided that each newly connected coalition is sufficiently charged, i.e., receives a sufficiently small worth. Both characterization results may be extended to games with conference structures.     

凸随机合作对策的核心

本文将凸性扩展到随机合作对策中,从而得到凸随机合作对策具有超可加性与非空的核心,且凸随机合作对策的核心满足Minkowski和与Minkowski差.     

The core of a cooperative game without side payments

For cooperative games without side payments, there are several types of conditions which guarantee nonemptiness of the core, for example balancedness and convexity. In the present paper, a general condition for nonempty core is introduced which includes the known ones as special cases. Moreover, it is shown that every game with nonempty core satisfies this condition.     

On the restricted cores and the bounded core of games on distributive lattices

A game with precedence constraints is a TU game with restricted cooperation, where the set of feasible coalitions is a distributive lattice, hence generated by a partial order on the set of players. Its core may be unbounded, and the bounded core, which is the union of all bounded faces of the core, proves to be a useful solution concept in the framework of games with precedence constraints. Replacing the inequalities that define the core by equations for a collection of coalitions results in a face of the core. A collection of coalitions is called normal if its resulting face is bounded. The bounded core is the union of all faces corresponding to minimal normal collections. We show that two faces corresponding to distinct normal collections may be distinct. Moreover, we prove that for superadditive games and convex games only intersecting and nested minimal collection, respectively, are necessary. Finally, it is shown that the faces corresponding to pairwise distinct nested normal collections may be pairwise distinct, and we provide a means to generate all such collections.     

The Compromise Value for Cooperative Games with Random Payoffs

This paper introduces and studies the compromise value for cooperative games with random payoffs, that is, for cooperative games where the payoff to a coalition of players is a random variable. This value is a compromise between utopia payoffs and minimal rights and its definition is based on the compromise value for NTU games and the τ-value for TU games. It is shown that the nonempty core of a cooperative game with random payoffs is bounded by the utopia payoffs and the minimal rights. Consequently, for such games the compromise value exists. Further, we show that the compromise value of a cooperative game with random payoffs coincides with the τ-value of a related TU game if the players have a certain type of preferences. Finally, the compromise value and the marginal value, which is defined as the average of the marginal vectors, coincide on the class of two-person games. This results in a characterization of the compromise value for two-person games.I thank Peter Borm, Ruud Hendrickx and two anonymous referees for their valuable comments.     

Axiomatizations of the core on the universal domain and other natural domains

We prove that the core on the set of all transferable utility games with players contained in a universe of at least five members can be axiomatized by the zero inessential game property, covariance under strategic equivalence, anonymity, boundedness, the weak reduced game property, the converse reduced game property, and the reconfirmation property. These properties also characterize the core on certain subsets of games, e.g., on the set of totally balanced games, on the set of balanced games, and on the set of superadditive games. Suitable extensions of these properties yield an axiomatization of the core on sets of nontransferable utility games. Received September 1999/Final version December 2000     

The prenucleolus and the reduced game property: Equal treatment replaces anonymity

In his paper, Sobolev [1975] characterized the prenucleolus as the unique solution concept, defined over the class of cooperative games that satisfies single valuedness, anonymity, covariance under strategic equivalence and reduced game property (consistency).In this paper we show that anonymity can be weakened and replaced by a requirement of equal treatment (symmetry).     

Shortest path games

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.     

The semireactive bargaining set of a cooperative game

The semireactive bargaining set, a solution for cooperative games, is introduced. This solution is in general a subsolution of the bargaining set and a supersolution of the reactive bargaining set. However, on various classes of transferable utility games the semireactive and the reactive bargaining set coincide. The semireactive prebargaining set on TU games can be axiomatized by one-person rationality, the reduced game property, a weak version of the converse reduced game property with respect to subgrand coalitions, and subgrand stability. Furthermore, it is shown that there is a suitable weakening of subgrand stability, which allows to characterize the prebargaining set. Replacing the reduced game by the imputation saving reduced game and employing individual rationality as an additional axiom yields characterizations of both, the bargaining set and the semireactive bargaining set. Received September 2000/Revised version June 2001     

Associated consistency and values for TU games

In the framework of the solution theory for cooperative transferable utility games, Hamiache axiomatized the well-known Shapley value as the unique one-point solution verifying the inessential game property, continuity, and associated consistency. The purpose of this paper is to extend Hamiache’s axiomatization to the class of efficient, symmetric, and linear values, of which the Shapley value is the most important representative. For this enlarged class of values, explicit relationships to the Shapley value are exploited in order to axiomatize such values with reference to a slightly adapted inessential game property, continuity, and a similar associated consistency. The latter axiom requires that the solutions of the initial game and its associated game (with the same player set, but a different characteristic function) coincide.     

On the core of cost-revenue games: Minimum cost spanning tree games with revenues

In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).     

Constrained core solutions for totally positive games with ordered players

In many applications of cooperative game theory to economic allocation problems, such as river-, polluted river- and sequencing games, the game is totally positive (i.e., all dividends are nonnegative), and there is some ordering on the set of the players. A totally positive game has a nonempty core. In this paper we introduce constrained core solutions for totally positive games with ordered players which assign to every such a game a subset of the core. These solutions are based on the distribution of dividends taking into account the hierarchical ordering of the players. The Harsanyi constrained core of a totally positive game with ordered players is a subset of the core of the game and contains the Shapley value. For special orderings it coincides with the core or the Shapley value. The selectope constrained core is defined for acyclic orderings and yields a subset of the Harsanyi constrained core. We provide a characterization for both solutions.     

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.     

Power Measures and Solutions for Games Under Precedence Constraints

Games under precedence constraints model situations, where players in a cooperative transferable utility game belong to some hierarchical structure, which is represented by an acyclic digraph (partial order). In this paper, we introduce the class of precedence power solutions for games under precedence constraints. These solutions are obtained by allocating the dividends in the game proportional to some power measure for acyclic digraphs. We show that all these solutions satisfy the desirable axiom of irrelevant player independence, which establishes that the payoffs assigned to relevant players are not affected by the presence of irrelevant players. We axiomatize these precedence power solutions using irrelevant player independence and an axiom that uses a digraph power measure. We give special attention to the hierarchical solution, which applies the hierarchical measure. We argue how this solution is related to the known precedence Shapley value, which does not satisfy irrelevant player independence, and thus is not a precedence power solution. We also axiomatize the hierarchical measure as a digraph power measure.     

Three-person spanning tree games

There are many situations where allocation of costs among the users of a minimum spanning tree network is a problem of concern. In [1], formulation of this problem as a game theoretic model, spanning tree games, has been considered. It is well known that st games have nonempty cores. Many researchers have studied other solutions related to st games. In this paper, we study three-person st games. Various properties connected to the convexity or no-convexity, and τ-value is studied. A characterization of the core and geometric interpretation is given. In special cases, the nucleolus of the game is given.     

On balanced games with infinitely many players: Revisiting Schmeidler's result

We consider transferable utility cooperative games with infinitely many players and the core understood in the space of bounded additive set functions. We show that, if a game is bounded below, then its core is non-empty if and only if the game is balanced. This finding generalizes Schmeidler (1967) “On Balanced Games with Infinitely Many Players”, where the game is assumed to be non-negative. We also generalize Schmeidler's (1967) result to the case of restricted cooperation too.     

Characterizations of perfect recall

This paper considers the condition of perfect recall for the class of arbitrarily large discrete extensive form games. The known definitions of perfect recall are shown to be equivalent even beyond finite games. Further, a qualitatively new characterization in terms of choices is obtained. In particular, an extensive form game satisfies perfect recall if and only if the set of choices, viewed as sets of ultimate outcomes, fulfill the “Trivial Intersection” property, that is, any two choices with nonempty intersection are ordered by set inclusion.     

Totally balanced games arising from controlled programming problems

A cooperative game in characteristic-function form is obtained by allowing a number of individuals to esercise partial control over the constraints of a (generally nonlinear) mathematical programming problem, either directly or through committee voting. Conditions are imposed on the functions defining the programming problem and the control system which suffice to make the game totally balanced. This assures a nonempty core and hence a stable allocation of the full value of the programming problem among the controlling palyers. In the linear case the core is closely related to the solutions of the dual problem. Applications are made to a variety of economic models, including the transferable utility trading economies of Shapley and Shubik and a multishipper one-commodity transshipment model with convex cost functions and concave revenue functions. Dropping the assumption of transferable utility leads to a class of controlled multiobjective or ‘Pareto programming’ problems, which again yield totally balanced games.     

Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner

We investigate privacy-preserving ways of allocating payoffs among players participating in a joint venture, using tools from cooperative game theory and differential privacy. In particular, we examine linear programming games, an important class of cooperative games that model a myriad of payoff sharing problems, including those from logistics and network design. We show that we can compute a payoff allocation in the approximate core of these games in a way that satisfies joint differential privacy.     

Cooperative games of choosing partners and forming coalitions in the marketplace

Two games of interacting between a coalition of players in a marketplace and the residual players acting there are discussed, along with two approaches to fair imputation of gains of coalitions in cooperative games that are based on the concepts of the Shapley vector and core of a cooperative game. In the first game, which is an antagonistic one, the residual players try to minimize the coalition's gain, whereas in the second game, which is a noncooperative one, they try to maximize their own gain as a coalition. A meaningful interpretation of possible relations between gains and Nash equilibrium strategies in both games considered as those played between a coalition of firms and its surrounding in a particular marketplace in the framework of two classes of n-person games is presented. A particular class of games of choosing partners and forming coalitions in which models of firms operating in the marketplace are those with linear constraints and utility functions being sums of linear and bilinear functions of two corresponding vector arguments is analyzed, and a set of maximin problems on polyhedral sets of connected strategies which the problem of choosing a coalition for a particular firm is reducible to are formulated based on the firm models of the considered kind.