Control-space properties of cooperative games

If two or more players agree to cooperate while playing a game, they help one another to minimize their respective costs as long as it is not to their individual disadvantages. This leads at once to the concept of undominated solutions to a game. Anundominated orPareto-optimal solution has the property that, compared to any other solution, at least one playerdoes worse or alldo the same if they use a solution other than the Pareto-optimal one.Closely related to the concept of a Pareto-optimal solution is theabsolutely cooperative solution. Such a solution has the property that, compared to any other permissible solution,every playerdoes no better if a solution other than the absolutely cooperative one is employed.This paper deals with control-space properties of Pareto-optimal and absolutely cooperative solutions for both static, continuous games and differential games. Conditions are given for cases in which solutions to the Pareto-optimal and absolutely cooperative games lie in the interior or on the boundary of the control set.The solution of a Pareto-optimal or absolutely cooperative game is related to the solution of a minimization problem with avector cost criterion. The question of whether or not a problem with a vector cost criterion can be reduced to a family of minimization problems with ascalar cost criterion is also discussed.An example is given to illustrate the theory.This research was supported in part by NASA Grant No. NGR-03-002-011 and ONR Contract No. N00014-69-A-0200-1020.     

Player splitting in extensive form games

By a player splitting we mean a mechanism that distributes the information sets of a player among so-called agents. A player splitting is called independent if each path in the game tree contains at most one agent of every player. Following Mertens (1989), a solution is said to have the player splitting property if, roughly speaking, the solution of an extensive form game does not change by applying independent player splittings. We show that Nash equilibria, perfect equilibria, Kohlberg-Mertens stable sets and Mertens stable sets have the player splitting property. An example is given to show that the proper equilibrium concept does not satisfy the player splitting property. Next, we give a definition of invariance under (general) player splittings which is an extension of the player splitting property to the situation where we also allow for dependent player splittings. We come to the conclusion that, for any given dependent player splitting, each of the above solutions is not invariant under this player splitting. The results are used to give several characterizations of the class of independent player splittings and the class of single appearance structures by means of invariance of solution concepts under player splittings. Received: December 1996/Revised Version: January 2000     

Sequentially compatible payoffs and the core in TU-games

In the context of cooperative TU-games, we introduce a recursive procedure to distribute the surplus of cooperation when there is an exogenous ordering among the set of players N. In each step of the process, using a given notion of reduced games, an upper and a lower bound for the payoff to the player at issue are required. Sequentially compatible payoffs are defined as those allocation vectors that meet these recursive bounds. For a family of reduction operations, the behavior of this new solution concept is analyzed. For any ordering of N, the core of the game turns out to be the set of sequentially compatible payoffs when the Davis–Maschler reduced games are used. Finally, we study which reduction operations give an advantage to the first player in the ordering.     

A sufficiency condition for coalitive pareto-optimal solutions

In ak-player, nonzero-sum differential game, there exists the possibility that a group of players will form a coalition and work together. If allk players form the coalition, the criterion usually chosen is Pareto optimality whereas, if the coalition consists of only one player, a minmax or Nash equilibrium solution is sought.In this paper, games with coalitions of more than one but less thank players are considered. Coalitive Pareto optimality is chosen as the criterion. Sufficient conditions are presented for coalitive Pareto-optimal solutions, and the results are illustrated with an example.     

The bounded core for games with precedence constraints

An element of the possibly unbounded core of a cooperative game with precedence constraints belongs to its bounded core if any transfer to a player from any of her subordinates results in payoffs outside the core. The bounded core is the union of all bounded faces of the core, it is nonempty if the core is nonempty, and it is a continuous correspondence on games with coinciding precedence constraints. If the precedence constraints generate a connected hierarchy, then the core is always nonempty. It is shown that the bounded core is axiomatized similarly to the core for classical cooperative games, namely by boundedness (BOUND), nonemptiness for zero-inessential two-person games (ZIG), anonymity, covariance under strategic equivalence (COV), and certain variants of the reduced game property (RGP), the converse reduced game property (CRGP), and the reconfirmation property. The core is the maximum solution that satisfies a suitably weakened version of BOUND together with the remaining axioms. For games with connected hierarchies, the bounded core is axiomatized by BOUND, ZIG, COV, and some variants of RGP and CRGP, whereas the core is the maximum solution that satisfies the weakened version of BOUND, COV, and the variants of RGP and CRGP.     

Semi-marginalistic Values for Set Games

Concerning the solution theory for set games, the paper focuses on a family of values, each of which allocates to any player some type of marginalistic contribution with respect to any coalition containing the player. For any value of the relevant family, an axiomatization is given by means of three properties, namely one type of an efficiency property, the equal treatment property and one type of a monotonicity property. We present one proof technique which is based on the decomposition of any arbitrary set game into a union of simple set games, the value of which are much easier to determine. A simple set game is associated with an arbitrary, but fixed item of the universe.     

On repeated games with incomplete information played by non-Bayesian players

Unlike in the traditional theory of games of incomplete information, the players here arenot Bayesian, i.e. a player does not necessarily have any prior probability distribution as to what game is being played. The game is infinitely repeated. A player may be absolutely uninformed, i.e. he may know only how many strategies he has. However, after each play the player is informed about his payoff and, moreover, he has perfect recall. A strategy is described, that with probability unity guarantees (in the sense of the liminf of the average payoff) in any game, whatever the player could guarantee if he had complete knowledge of the game.     

A conflict between sequential rationality and consistency principles

It is shown that no solution concept that selects sequentially rational (perfect, proper, persistent, or members of some stable set of) equilibria satisfies the following consistency property. Suppose that in every solution of the game G, player i's action is a, and denote by G ^a the game in which player i is restricted to choose a. Then some player j≠i has an action c that is used with positive probability in both some solution of G and some solution of G ^a. This result illustrates a conflict between a mild consistency condition and sequential rationality. Received: January 2001/Final version: April 2002     

Information market games

In this paper information markets with perfect patent protection and only one initial owner of the information are studied by means of cooperative game theory. To each information market of this type a cooperative game with sidepayments is constructed. These cooperative games are called information (market) games. The set of all information games with fixed player set is a cone in the set of all cooperative games with the same player set. Necessary and sufficient conditions are given in order that a cooperative game is an information game. The core of this kind of games is not empty and is also the minimal subsolution of the game. The core is the image of an (n-1)-dimensional hypercube under an affine transformation, (= hyperparallellopiped), the nucleolus and -value coincide with the center of the core. The Shapley value is computed and may lie inside or outside the core. The Shapley value coincides with the nucleolus and the -value if and only if the information game is convex. In this case the core is also a stable set.     

A Pareto-optimal solution of a maintenance-production differential game

This paper deals with a maintenance-production problem, modelled as a two-player nonzero-sum differential game. In a firm, the maintenance department is responsible for the maintenance of the machines used by the production department. Maintenance expenditures improve the quality of the machines but are costly. Production, on the other hand, yields revenue to the firm, but reduces the quality of the machines.Assuming that the two departments will make a decision on maintenance expenditures and production rate in a cooperative mood, we are looking for a Pareto-optimal solution. Using phase diagram analysis it turns out that the equilibrium in state-costate plane is a saddle point, implying (in the most realistic cases) decresing maintenance expenditures and increasing production rate.It is interesting to note that the basic features of the Pareto solution are the same as in the one player solution (i.e. the optimal control problem). Also, some similarities with the non-cooperative Nash solution are pointed out.     

Egalitarian allocation and players of certain type

In cooperative game theory the Shapley value is different from the egalitarian value, the latter of which allocates payoffs equally. The null player property and the nullifying player property assign zero payoff to each null player and each nullifying player, respectively. It is known that if the null player property for characterizing the Shapley value is replaced by the nullifying player property, then the egalitarian value is determined uniquely. We propose several properties to replace the nullifying player property to characterize the egalitarian value. Roughly speaking, the results in this note hint that equal division for players of certain types may lead to the egalitarian allocation.     

Allocation processes in cooperative games

This paper deals with a temporal aspect of cooperative games. A solution of the game is reached through an allocation process. At each stage of the allocation process of a cooperative game a budget of fixed size is distributed among the players. In the first part of this paper we study a type of process that, at any stage, endows the budget to a player whose contribution to the total welfare, according to some measurements, is maximal. It is shown that the empirical distribution of the budget induced by each process of the family converges to a least square value of the game, one such value being the Shapley value. Other allocation processes presented here converge to the core or to the least core. Received: January 2001/Revised: July 2002 I am grateful to the Associate Editor and to the two anonymous referees of International Journal of Game Theory. This research was partially supported by the Israel Science Foundation, grant no. 178/99     

Time inconsistency and learning in bargaining games

This paper studies an alternating-offers bargaining game between possibly time-inconsistent players. The time inconsistency is modeled by quasi-hyperbolic discounting and the “naive backwards induction” solution concept is used in order to obtain the results. Both naive agents who remain naive and those who learn about their own preferences are considered. Offers of the players who are naive or partially naive are never accepted by any type of player in either no learning or gradual learning cases. The game between a naive or partially naive player who never learns and a time-consistent agent ends in an immediate agreement if the time-consistent agent is the proposer. A one period delay occurs if the time-consistent agent is the responder. The more naive the player is, the higher the share received. In addition, two naive agents who never learn disagree perpetually. When naive and partially naive agents play against exponential or sophisticated agents and they are able to learn their types over time, there exists a critical date before which there is no agreement. Therefore, the existence of time-inconsistent players who can learn their types as they play the game can be a new explanation for delays in bargaining. The relationship among the degree of naivete, impatience level and bargaining delay is also characterized. Specifically, for sufficiently high discount factors, agreement is always delayed. On the other hand, if the naive agent has sufficiently firm initial beliefs (slow learning or high degree of naivete), agents agree immediately.     

On a duel with time lag and equal accuracy functions

This paper deals with a duel with time lag that has the following structure: Each of two players I and II has a gun with one bullet and he can fire his bullet at any time in [0, 1], aiming at this opponent. The gun of player I is silent and the gun of player II is noisy with time lagt (i.e., if player II fires at timex, then player I knows it at timex+t). They both have equal accuracy functions. Furthermore, if player I hits player II without being hit himself before, the payoff is +1; if player I is hit by player II without hitting player II before, the payoff is –1; if they hit each other at the same time or both survive, the payoff is 0.This paper gives the optimal strategy for each player, the game value, and some examples.     

A ranking for the nodes of directed graphs based on game theory (Poster Presentation)

We introduce a value that allows us to emphasize the importance of each player in a cooperative game when the cooperation possibilities are limited according to the links of an oriented network. The proposed concept of accessibility tries to conjugate the marginal contributions of each node as a game player with the cooperation geometry imposed by the directed graph that models the network. As a consequence, it is possible to offer a ranking for the nodes of directed graphs. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Accessibility in oriented networks

The aim of this work consists of allocating a value that allows us to emphasize the importance of each player in a cooperative game when the cooperation possibilities are limited according to the links of an oriented network. The proposed concept of accessibility tries to conjugate the marginal contributions of each node as a game player with the cooperation geometry imposed by the digraph that models the network. We study general properties of this concept and particularly with respect to oriented paths. Concrete applications are proposed.     

Node-Consistent Shapley Value for Games Played over Event Trees with Random Terminal Time

We consider a class of dynamic games played over an event tree, with random terminal time. We assume that the players wish to jointly optimize their payoffs throughout the whole planning horizon and adopt the Shapley value to share the joint cooperative outcome. We devise a node-consistent decomposition of the Shapley value, which means that in any node of the event tree, the players prefer to stick to cooperation and to continue implementing the Shapley value rather than switching to noncooperation. For each node and each player, we provide two payment values, one that applies if the game terminates at that node and the other if the game continues. We illustrate our results with an example of pollution control.     

Stability property of matchings is a natural solution concept in coalitional market games

Stability of matchings was proved to be a new cooperative equilibrium concept in Sotomayor (Dynamics and equilibrium: essays in honor to D. Gale, 1992). That paper introduces the innovation of treating as multi-dimensional the payoff of a player with a quota greater than one. This is done for the many-to-many matching model with additively separable utilities, for which the stability concept is defined. It is then proved, via linear programming, that the set of stable outcomes is nonempty and it may be strictly bigger than the set of dual solutions and strictly smaller than the core. The present paper defines a general concept of stability and shows that this concept is a natural solution concept, stronger than the core concept, for a much more general coalitional game than a matching game. Instead of mutual agreements inside partnerships, the players are allowed to make collective agreements inside coalitions of any size and to distribute his labor among them. A collective agreement determines the level of labor at which the coalition operates and the division, among its members, of the income generated by the coalition. An allocation specifies a set of collective agreements for each player.     

An axiomatization of the Shapley value using a fairness property

In this paper we provide an axiomatization of the Shapley value for TU-games using a fairness property. This property states that if to a game we add another game in which two players are symmetric then their payoffs change by the same amount. We show that the Shapley value is characterized by this fairness property, efficiency and the null player property. These three axioms also characterize the Shapley value on the class of simple games. Revised August 2001     

Structural satisfaction in simple games

A fundamental maxim for any theory of social behavior is that knowledge of the theory should not cause behavior that contradicts the theory's assertions. Although this maxim consistently has been heeded in the theory of noncooperative games, it largely has been ignored in solution theory for cooperative games. Solution theory, the central concern of this paper, seeks to identify a subset of the feasible outcomes of a cooperative game that are ‘stable’ results of competition among participants, each of whom attempts to bring about an outcome he favors, rather than to prescribe ‘fair’ outcomes that accord with a standard of equity. We show that learning by participants about the solution theory can cause the outcomes identified as stable by certain solution concepts to become unstable, and discover that an important distinction in this regard is whether the solution concept requires each element of the solution set to defend itself against alternatives rather than relying on other elements for its defense. Finally, we develop a concept of ‘solid’ solutions which have a special claim for stability.The unifying theme of this paper concerns the sense in which certain outcomes of a cooperative game may be regarded as stable, and the extent to which this stability requires that the players are ignorant of the theory. Although the issues raised here have implications for the theory of cooperative games in general, Section 1 establishes the focus of the analysis on collective decision games. Section 2 develops some general perspectives on solution theory which are used in Sections 3 and 4 to evaluate the Condorcet solution, the core, the robust proposals set, von Neumann- Morgenstern solutions and competitive solutions. Section 5 presents the concept of a solid solution and relates this idea to the solution concepts reviewed earlier. We demonstrate that in general a solution concept has a strong claim to stability only if it is solid. Finally, Section 6 concludes by indicating that the basic argument also can be applied to Aumann and Maschler's bargaining sets and, more generally, to solution theory for any cooperative game.