Information patterns and Nash equilibria in extensive games — II

In Part I of this paper we introduced extensive games with a non-atomic continuum of players. It was shown that the Nash plays (outcomes) are invariant of the information patterns on the game, provided that no player's unilateral change in moves can be observed by others. This led to an enormous reduction in the Nash plays of the these games, as exemplified in the anti-folk theorem. Our concern in this sequel is to develop a finite version of these results.     

Values of mixed games

Aumann andShapley [1973] have investigated values of games in which all players are individually insignificant, i.e. form a non-atomic continuum, or “ocean”. In this paper we treat games in which, in addition to such an ocean, there are also some “atoms”, i.e. players who are individually significant. We define spaces of such games that are analogous to those investigated byAumann andShapley, and prove the existence of values on some of them. Unlike in the non-atomic case, we find that in general there are infinitely many values, corresponding to various ways in which the atoms can be imbedded in the ocean. The results generalize those ofMilnor andShapley [1961]. Precise statements will be found in Section 2.     

Weighted values for non-atomic games: an axiomatic approach

Weighted values of non-atomic games were introduced by Hart and Monderer. These values have been studied by using three approaches: the potential, the asymptotic and the random order approach. In this study we analyze the axiomatic approach for one class of weight functions: the set of players is partitioned into a finite number of types, with each type having different weight.     

On symmetric stochastic games of resource extraction with weakly continuous transitions

We study stochastic games of resource extraction, in which the players have identical preferences. The transition probability is either non-atomic or a convex combination of transition probabilities depending on the investment with coefficients also dependent on the investment. Our approach covers the unbounded utility case, which was not examined in this class of games beforehand. We prove the existence of a stationary Markov perfect equilibrium in a non-randomised class of strategies.     

Independent mistakes in large games

Economic models usually assume that agents play precise best responses to others' actions. It is sometimes argued that this is a good approximation when there are many agents in the game, because if their mistakes are independent, aggregate uncertainty is small. We study a class of games in which players' payoffs depend solely on their individual actions and on the aggregate of all players' actions. We investigate whether their equilibria are affected by mistakes when the number of players becomes large. Indeed, in generic games with continuous payoff functions, independent mistakes wash out in the limit. This may not be the case if payoffs are discontinuous. As a counter-example we present the n players Nash bargaining game, as well as a large class of “free-rider games.” Received: November 1997/Final version: December 1999     

Structure of equilibria inN-person non-cooperative games

Here we study the structure of Nash equilibrium points forN-person games. For two-person games we observe that exchangeability and convexity of the set of equilibrium points are synonymous. This is shown to be false even for three-person games. For completely mixed games we get the necessary inequality constraints on the number of pure strategies for the players. Whereas the equilibrium point is unique for completely mixed two-person games, we show that it is not true for three-person completely mixed game without some side conditions such as convexity on the equilibrium set. It is a curious fact that for the special three-person completely mixed game with two pure strategies for each player, the equilibrium point is unique; the proof of this involves some combinatorial arguments.     

Cores of non-atomic market games

We study the cores of non-atomic market games, a class of transferable utility cooperative games introduced by Aumann and Shapley (Values of non-atomic games, 1974), and, more in general, of those games that admit a na-continuous and concave extension to the set of ideal coalitions, studied by Einy et al. (Int J Game Theory 28:1–14, 1999). We show that the core of such games is norm compact and some related results. We also give a Multiple Priors interpretation of some of our findings.     

Computing solutions of the multiclass network equilibrium problem with affine cost functions

Annals of Operations Research - We consider a non-atomic congestion game on a graph, with several classes of players. Each player wants to go from his origin vertex to his destination vertex at the...     

Rankings and values for team games

In this article we attack several problems that arise when a group of individuals is organized in several teams with equal number of players in each one (e.g., for company work, in sports leagues, etc). We define a team game as a cooperative game v that can have non-zero values only on coalitions of a given cardinality; it is further shown that, for such games, there is essentially a unique ranking among the players. We also study the way the ranking changes after one or more players retire. Also, we characterize axiomatically different ways of ranking the players that intervene in a cooperative game.     

Totally balanced combinatorial optimization games

Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000     

Nash and Stackelberg Differential Games

A large class of stochastic differential games for several players is considered in this paper.The class includes Nash differential games as well as Stackelberg differential games.A mix is possible.The...     

Stabilizing network bargaining games by blocking players

Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, we focus on stabilizing instances of the above games by blocking as few players as possible. Formally, given a graph G we want to find a minimum cardinality set of vertices such that its removal from G yields a stable graph. We give a combinatorial polynomial-time algorithm for this problem, and develop approximation algorithms for some NP-hard weighted variants, where each vertex has an associated non-negative weight. Our approximation algorithms are LP-based, and we show that our analysis are almost tight by giving suitable lower bounds on the integrality gap of the used LP relaxations.     

On the minimal representation of homogeneous games

It is known that the lattice-minimal representation (by natural numbers) of a weighted majority game may be not unique and may lack of equal treatment (Isbell 1959). The same is true for the total-weight minimal representation. Both concepts coincide on the class of homogeneous games. The main theorem of this article is that for homogeneous games there is a unique minimal representation. This result is given by means of a construction that depends on the natural order on the set of player types. This order coincides with one induced by the “desirability relation”. In order to compute the minimal representation inductively, while proceeding from smaller players to the greater one, we are led to distinguish two different kinds of players: some players are “replacable” by smaller ones, some not.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

Solution concepts in two-person multicriteria games

In this paper, we propose new solution concepts for multicriteria games and compare them with existing ones. The general setting is that of two-person finite games in normal form (matrix games) with pure and mixed strategy sets for the players. The notions of efficiency (Pareto optimality), security levels, and response strategies have all been used in defining solutions ranging from equilibrium points to Pareto saddle points. Methods for obtaining strategies that yield Pareto security levels to the players or Pareto saddle points to the game, when they exist, are presented. Finally, we study games with more than two qualitative outcomes such as combat games. Using the notion of guaranteed outcomes, we obtain saddle-point solutions in mixed strategies for a number of cases. Examples illustrating the concepts, methods, and solutions are included.     

The maximum and the addition of assignment games

In the framework of two-sided assignment markets, we first consider that, with several markets available, the players may choose where to trade. It is shown that the corresponding game, represented by the maximum of a finite set of assignment games, may not be balanced. Some conditions for balancedness are provided and, in that case, properties of the core are analyzed. Secondly, we consider that players may trade simultaneously in more than one market and then add up the profits. The corresponding game, represented by the sum of a finite set of assignment games, is balanced. Moreover, under some conditions, the sum of the cores of two assignment games coincides with the core of the sum game.     

The multichoice consistent value

We consider multichoice NTU games, i.e., cooperative NTU games in which players can participate in the game with several levels of activity. For these games, we define and characterize axiomatically the multichoice consistent value, which is a generalization of the consistent NTU value for NTU games and of the multichoice value for multichoice TU games. Moreover, we show that this value coincides with the consistent NTU value of a replicated NTU game and we provide a probabilistic interpretation. Received: May 1998/Final version: January 2000     

Matroidal games

The theory ofmatriods consists of generalization of basic notions oflinear algebra likedependence, basis andspan. In this paper we point out that every non-trivial matroid represents a simple game though the converse need not be true. The class of simple games which possess the matroidal structure is designated asmatroidal games. In matroidal games, we have a generalization of the concept of complete exchangeability of players observed in purely size dependent games. Invoking the well developed theory of matroids, we study the combinatorial structure of matroidal games.