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.     

Directed graphical structure,Nash equilibrium,and potential games

This paper considers the directed graphical structure of a game, called influence structure, where a directed edge from player $i$ to player $j$ indicates that player $i$ may be able to affect $j$’s payoff via his unilateral change of strategies. We give a necessary and sufficient condition for the existence of pure-strategy Nash equilibrium of games having a directed graph in terms of the structure of that graph. We also discuss the relationship between the structure of graphs and potential games.     

Uncoupled automata and pure Nash equilibria

We study the problem of reaching a pure Nash equilibrium in multi-person games that are repeatedly played, under the assumption of uncoupledness: EVERY player knows only his own payoff function. We consider strategies that can be implemented by finite-state automata, and characterize the minimal number of states needed in order to guarantee that a pure Nash equilibrium is reached in every game where such an equilibrium exists.     

Zero-sum sequential games with incomplete information

Repeated zero-sum two-person games of incomplete information on one side are considered. If the one-shot game is played sequentially, the informed player moving first, it is proved that the value of then-shot game is constant inn and is equal to the concavification of the game in which the informed player disregards his extra information. This is a strengthening ofAumann andMaschler's results for simultaneous games. Optimal strategies for both players are constructed explicitly.     

Stationary equilibria in cyclic games: Search and structure

The existence of optimal stationary strategies for a cyclic game played on the vertices of a bipartite graph up to the first cycle with the payoff of one player to the other equaling the sum of the maximal and minimal local payoffs on this cycle is proved. This result implies that the problem belongs to the class NP ∩ co-NP; -a polynomial algorithm that yields optimal strategies for ergodic extensions of matrix games is given. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 913–921, June, 2000.     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

A duality theory for a class of non-zero sum economic games

In this paper we consider n-person games in which each player has a convex strategy set over which his closed strictly quasi-concave payoff function is defined. The interaction of the players' strategies is via linear constraints in the form of a convex cone. An appropriate duality theory is developed and applied to an example with economic significance. The resulting analysis leads naturally to a means for solving such a game that merely involves the solution of a set of linear equations.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

Average-discounted equilibria in stochastic games

In stochastic games with finite state and action spaces, we examine existence of equilibria where player 1 uses the limiting average reward and player 2 a discounted reward for the evaluations of the respective payoff sequences. By the nature of these rewards, the far future determines player 1's reward, while player 2 is rather interested in the near future. This gives rise to a natural cooperation between the players along the course of the play. First we show the existence of stationary ε-equilibria, for all ε>0, in these games. However, besides these stationary ε-equilibria, there also exist ε-equilibria, in terms of only slightly more complex ultimately stationary strategies, which are rather in the spirit of these games because, after a large stage when the discounted game is not interesting any longer, the players cooperate to guarantee the highest feasible reward to player 1. Moreover, we analyze an interesting example demonstrating that 0-equilibria do not necessarily exist in these games, not even in terms of history dependent strategies. Finally, we examine special classes of stochastic games with specific conditions on the transition and payoff structures. Several examples are given to clarify all these issues.     

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 a noisy-silent-versus-silent duel with equal accuracy functions

This paper deals with the noisy-silent-versus-silent duel with equal accuracy functions. Player I has a gun with two bullets and player II has a gun with one bullet. The first bullet of player I is noisy, the second bullet of player I is silent, and the bullet of player II is silent. Each player can fire their bullets at any time in [0, 1] aiming at his opponent. The accuracy function ist for both players. If player I hits player II, not being hit himself before, the payoff of the duel is +1; if player I is hit by player II, not hitting player II before, the payoff is –1. The optimal strategies and the value of the game are obtained. Although optimal strategies in past works concerning games of timing does not depend on the firing moments of the players, the optimal strategy obtained for player II depends explicitly on the firing moment of player I's noisy bullet.     

Two-noisy-versus-one-silent duel with equal accuracy functions

This paper deals with the two-noisy-versus-one-silent duel which is still open, as pointed out by Styszyński (Ref. 1). Player I has a noisy gun with two bullets, and player II has a silent gun with one bullet. Each player fires his bullets aiming at his opponent at any time in [0, 1]. The accuracy function (the probability that one player hits his opponent if he fires at timet) isp(t)=t for each player. If player I hits player II, without being hit himself before, the payoff of the duel is +1; if player I is hit by player II, without hitting player II before, the payoff is taken to be ?1. In this paper, we determine the optimal strategies and the value of the game. The strategy for player II depends explicitly on the firing moment of player I's first shot.     

Correlated equilibrium payoffs and public signalling in absorbing games

An absorbing game is a repeated game where some action combinations are absorbing, in the sense that whenever they are played, there is a positive probability that the game terminates, and the players receive some terminal payoff at every future stage.  We prove that every multi-player absorbing game admits a correlated equilibrium payoff. In other words, for every ε>0 there exists a probability distribution p _ε over the space of pure strategy profiles that satisfies the following. With probability at least 1−ε, if a pure strategy profile is chosen according to p _ε and each player is informed of his pure strategy, no player can profit more than ε in any sufficiently long game by deviating from the recommended strategy. Received: April 2001/Revised: June 4, 2002     

A model of a 2-player stopping game with priority and asynchronous observation

Various models of 2-player stopping games have been considered which assume that players simultaneously observe a sequence of objects. Nash equilibria for such games can be found by first solving the optimal stopping problems arising when one player remains and then defining by recursion the normal form of the game played at each stage when both players are still searching (a 2 × 2 matrix game). The model considered here assumes that Player 1 always observes an object before Player 2. If Player 1 accepts the object, then Player 2 does not see that object. If Player 1 rejects an object, then Player 2 observes it and may choose to accept or reject it. It is shown that such a game can be solved using recursion by solving appropriately defined subgames, which are played at each moment when both players are still searching. In these subgames Player 1 chooses a threshold, such that an object is accepted iff its value is above this threshold. The strategy of Player 2 in this subgame is a stopping rule to be used when Player 1 accepts this object, together with a threshold to be used when Player 1 rejects the object. Whenever the payoff of Player 1 does not depend on the value of the object taken by Player 2, such a game can be treated as two optimisation problems. Two examples are given to illustrate these approaches.     

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.     

On the existence of good stationary strategies for nonleavable stochastic games

This paper discusses the problem regarding the existence of optimal or nearly optimal stationary strategies for a player engaged in a nonleavable stochastic game. It is known that, for these games, player I need not have an -optimal stationary strategy even when the state space of the game is finite. On the contrary, we show that uniformly -optimal stationary strategies are available to player II for nonleavable stochastic games with finite state space. Our methods will also yield sufficient conditions for the existence of optimal and -optimal stationary strategies for player II for games with countably infinite state space. With the purpose of introducing and explaining the main results of the paper, special consideration is given to a particular class of nonleavable games whose utility is equal to the indicator of a subset of the state space of the game.     

Playing off-line games with bounded rationality

We study a two-person zero-sum game where players simultaneously choose sequences of actions, and the overall payoff is the average of a one-shot payoff over the joint sequence. We consider the maxmin value of the game played in pure strategies by boundedly rational players and model bounded rationality by introducing complexity limitations. First we define the complexity of a sequence by its smallest period (a nonperiodic sequence being of infinite complexity) and study the maxmin of the game where player 1 is restricted to strategies with complexity at most n and player 2 is restricted to strategies with complexity at most m. We study the asymptotics of this value and a complete characterization in the matching pennies case. We extend the analysis of matching pennies to strategies with bounded recall.     

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.     

Repeated two-player games with ruin

The class of repeated two-player games (with long-run average payoff criterion) is extended to accommodate initial holdings of wealth and the possibility of ruin. Equilibria of these games are studied under the assumption that each player regards his own ruin as the worst possible outcome of the game and his opponent's ruin as the best possible outcome.     

On weakly correlated and correlated equilibria in discontinuous games

This paper treats of non-zero-sum discontinuous games with compact Hausdorff strategy spaces. It is assumed that the payoff function of each player in the game is bounded, Borel measurable and is upper semicontinuous on his strategy space, for all fixed actions of the remaining players. It is shown that for each ε>0, such games possess weakly correlated ε-epuilibria introduced by Moulin and Vial as extension of correlated equilibria in the sense of Aumann. An upper semicontinuous came having weakly correlated equilibria and no correlated equilibria is discussed in details.