Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

Loss of skills in coordination games

This paper deals with 2-player coordination games with vanishing actions, which are repeated games where all diagonal payoffs are strictly positive and all non-diagonal payoffs are zero with the following additional property: At any stage beyond r, if a player has not played a certain action for the last r stages, then he unlearns this action and it disappears from his action set. Such a game is called an r-restricted game. To evaluate the stream of payoffs we use the average reward. For r = 1 the game strategically reduces to a one-shot game and for r ≥ 3 in Schoenmakers (Int Game Theory Rev 4:119–126, 2002) it is shown that all payoffs in the convex hull of the diagonal payoffs are equilibrium rewards. In this paper for the case r = 2 we provide a characterization of the set of equilibrium rewards for 2 × 2 games of this type and a technique to find the equilibrium rewards in m × m games. We also discuss subgame perfection.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Games with finite resources

Games with Finite Resources as defined by Gale (1957) are two-person zero-sum N-stage games in which each player has N resources and may use each resource once and only once in the N stages. Gale's theorem on these games is generalized in several directions. First the payoff is allowed to be any symmetric function of the stage payoffs. Second, the players are allowed some latitude in choosing which game is being played. Applications are given to some open questions in the area of Inspection Games. Finally the payoff is allowed to be random, thus incorporating a result of Ross (1972) on Goofspiel. Application is made to a game-theoretic version of the Generalized House Selling Problem. Received August 1999/revised version March 2000     

Characterization of correlated equilibria in stochastic games

A general communication device is a device that at every stage of the game receives a private message from each player, and in return sends a private signal to each player; the signals the device sends depend on past play, past signals it sent, and past messages it received.  An autonomous correlation device is a general communication device where signals depend only on past signals the device sent, but not on past play or past messages it received.  We show that the set of all equilibrium payoffs in extended games that include a general communication device coincides with the set of all equilibrium payoffs in extended games that include an autonomous correlation device. A stronger result is obtained when the punishment level is independent of the history. Final version July 2001     

Single-payoff farsighted stable sets in strategic games with dominant punishment strategies

We investigate farsighted stable sets in a class of strategic games with dominant punishment strategies. In this class of games, each player has a strategy that uniformly minimizes the other players’ payoffs for any given strategies chosen by these other players. We particularly investigate a special class of farsighted stable sets, each of which consists of strategy profiles yielding a single payoff vector. We call such a farsighted stable set as a single-payoff farsighted stable set. We propose a concept called an inclusive set that completely characterizes single-payoff farsighted stable sets in strategic games with dominant punishment strategies. We also show that the set of payoff vectors yielded by single-payoff farsighted stable sets is closely related to the strict \(\alpha \)-core in a strategic game. Furthermore, we apply the results to strategic games where each player has two strategies and strategic games associated with some market models.     

A set optimization approach to zero-sum matrix games with multi-dimensional payoffs

A new solution concept for two-player zero-sum matrix games with multi-dimensional payoffs is introduced. It is based on extensions of the vector order in \(\mathbb {R}^d\) to order relations in the power set of \(\mathbb {R}^d\), so-called set relations, and strictly motivated by the interpretation of the payoff as multi-dimensional loss for one and gain for the other player. The new concept provides coherent worst case estimates for games with multi-dimensional payoffs. It is shown that–in contrast to games with one-dimensional payoffs–the corresponding strategies are different from equilibrium strategies for games with multi-dimensional payoffs. The two concepts are combined into new equilibrium notions for which existence theorems are given. Relationships of the new concepts to existing ones such as Shapley and vector equilibria, vector minimax and maximin solutions as well as Pareto optimal security strategies are clarified.     

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.     

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     

Aggregate monotonic stable single-valued solutions for cooperative games

This article considers single-valued solutions of transferable utility cooperative games that satisfy core selection and aggregate monotonicity, defined either on the set of all games, G ^N , or on the set of essential games, E ^N (those with a non-empty imputation set). The main result is that for an arbitrary set of players, core selection and aggregate monotonicity are compatible with individual rationality, the dummy player property and symmetry for single-valued solutions defined on both G ^N and E ^N . This result solves an open question in the literature (see for example Young et?al. Water Resour Res 18:463?C475, 1982).     

Internal correlation in repeated games

This paper characterizes the set of all the Nash equilibrium payoffs in two player repeated games where the signal that the players get after each stage is either trivial (does not reveal any information) or standard (the signal is the pair of actions played). It turns out that if the information is not always trivial then the set of all the Nash equilibrium payoffs coincides with the set of the correlated equilibrium payoffs. In particular, any correlated equilibrium payoff of the one shot game is also a Nash equilibrium payoff of the repeated game.For the proof we develop a scheme by which two players can generate any correlation device, using the signaling structure of the game. We present strategies with which the players internally correlate their actions without the need of an exogenous mediator.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

On coalition formation: a game-theoretical approach

This paper deals with the question of coalition formation inn-person cooperative games. Two abstract game models of coalition formation are proposed. We then study the core and the dynamic solution of these abstract games. These models assume that there is a rule governing the allocation of payoffs to each player in each coalition structure called a payoff solution concept. The predictions of these models are characterized for the special case of games with side payments using various payoff solution concepts such as the individually rational payoffs, the core, the Shapley value and the bargaining set M₁ ⁽ⁱ⁾. Some modifications of these models are also discussed.     

On the Probability of Existence of Pure Equilibria in Matrix Games

In a recent paper (Ref. 1), Papavassilopoulos obtained results on the probability of the existence of pure equilibrium solutions in stochastic matrix games. We report a similar result, but where the payoffs are drawn from a finite set of numbers N. In the limiting case, as N tends to infinity, our result and that of Papavassilopoulos are identical. We also cite similar results obtained independently by others, some of which were already independently brought to the notice of Papavassilopoulos by Li Calzi as reported in Papavassilopoulos (Ref. 2). We cite a much earlier result obtained by Goldman (Ref. 3). We also cite our related work (Ref. 4), in which we derive the conditions for the existence of mixed strategy equilibria in two-person zero-sum games.     

Games with frequency-dependent stage payoffs

Games with frequency-dependent stage payoffs (FD-games), are infinitely repeated non-cooperative games played at discrete moments in time called stages. The stage payoffs depend on the action pair actually chosen, and on the relative frequencies with which all actions were chosen before. We assume that players wish to maximize their expected (limiting) average rewards over the entire time-horizon. We prove an analogy to, as well as an extension of the (perfect) Folk Theorem. Each pair of rewards in the convex hull of all individually-rational jointly-convergent pure-strategy rewards can be supported by an equilibrium. Moreover, each pair of rewards in same set giving each player strictly more than the threat-point-reward, can be supported by a subgame-perfect equilibrium. Under a pair of jointly-convergent strategies, the relative frequency of each action pair converges in the long run. Received: March 2002/Revised: January 2003     

Reduced games,consistency, and the core

This paper establishes an axiomatization of the core by means of an internal consistency property with respect to a new reduced game introduced by Moulin (1985). Given a payoff vector chosen by a solution for some game, and given a subgroup of agents, we define thereduced game as that in which each coalition in the subgroup could attain payoffs to its members only if they are compatible with the initial payoffs toall the members outside of the subgroup. The solution isconsistent if it selects the same payoff distribution for the reduced game as initially. We show that consistency together with individual rationality characterizes the core of both transferable and non-transferable utility games.     

On stochastic games with additive reward and transition structure

In this paper, we introduce a new class of two-person stochastic games with nice properties. For games in this class, the payoffs as well as the transitions in each state consist of a part which depends only on the action of the first player and a part dependent only on the action of the second player.For the zero-sum games in this class, we prove that the orderfield property holds in the infinite-horizon case and that there exist optimal pure stationary strategies for the discounted as well as the undiscounted payoff criterion. For both criteria also, finite algorithms are given to solve the game. An example shows that, for nonzero sum games in this class, there are not necessarily pure stationary equilibria. But, if such a game possesses a stationary equilibrium point, then there also exists a stationary equilibrium point which uses in each state at most two pure actions for each player.     

Axiomatizations of Banzhaf permission values for games with a permission structure

In games with a permission structure it is assumed that players in a cooperative transferable utility game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. We provide axiomatic characterizations of Banzhaf permission values being solutions that are obtained by applying the Banzhaf value to modified TU-games. In these characterizations we use power- and player split neutrality properties. These properties state that splitting a player’s authority and/or contribution over two players does not change the sum of their payoffs.     

Two-person repeated games with finite automata

We study two-person repeated games in which a player with a restricted set of strategies plays against an unrestricted player. An exogenously given bound on the complexity of strategies, which is measured by the size of the smallest automata that implement them, gives rise to a restriction on strategies available to a player.  We examine the asymptotic behavior of the set of equilibrium payoffs as the bound on the strategic complexity of the restricted player tends to infinity, but sufficiently slowly. Results from the study of zero sum case provide the individually rational payoff levels. Received February 1997/revised version March 2000     

Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t−1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 consists of playing the same mixed action at every stage, irrespective of past play. Furthermore, for games in which player 1 has a simple optimal strategy, we characterize the set of stationary optimal strategies for player 2.