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.     

Equilibria in repeated games of incomplete information: The general symmetric case

Every two person repeated game of symmetric incomplete information, in which the signals sent at each stage to both players are identical and generated by a state and moves dependent probability distribution on a given finite alphabet, has an equilibrium payoff. Received March 1996/Revised version January 1997/Final version May 1997     

Optimal strategies in repeated games with incomplete information

The paper is concerned with zero-sum two-person repeated games with lack of information on one side. The main result in the construction of an optimal strategy for the uninformed player in the infinitely repeated game.     

On the relation between finitely and infinitely repeated games with incomplete information

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that \(\mathop {\lim }\limits_{n \to \infty } v_n\) exists,Ν _n being the value of the game withn repetitions. As for the speed of convergenceAumann andMaschler showed that the error termδ _n=¦Ν _n?limΝ _n¦ is bounded from above byc/√n for some positive constantc. Both results have been generalized byMertens andZamir. It is shown in this paper that the above mentioned theorem about the speed of convergence is sharp in the sense that there are games in whichδ _n≥c′/√n for some positive constantc′. However there are games for which δ_n is of a lower order of magnitude, for instancec′(logn)/n≤δ _n≤c (logn)/n orc′/n≤δ _n≤c/n. Sufficient conditions are given here for games to belong to one of these categories as well as examples of games from each category.     

Asymptotically optimal strategies in repeated games with incomplete information

It is known that for repeated zero-sum games with incomplete information the limit of the values of theN-stage game exists asN tends to infinity. In this paper strategies are constructed that guarantee in theN-stage game the limit of values up to an error term \(\frac{K}{{\sqrt N }}.\)      

Nash equilibria of n-player repeated games with semi-standard information

The folk theorem is extended here to the case where after each stage of the repeated game each player is informed only about the equivalence classes of the pure actions which were used by the other players. The sets of upper equilibrium payoffs and of lower equilibrium payoffs are characterized here, and they are found to be different.     

“Eventually revealing” repeated games with incomplete information

We consider two person zero-sum games with lack of information on one side given by two 2×2-matricesA ¹ andA ² for which val [pA ¹ +(1–p)A ²]=p valA ¹+(1–p) valA ². Using the approach developed by Heuer [1991] we give the explicit solution for all such finitely repeated games. It provides a supplement to the recent results on the limiting behavior of the value for these games (see Mertens, Sorin and Zamir [1990], De Meyer [1989], [1993]).We are grateful to the referees and the editor in charge for helpful and instructive comments and especially for the printed materials on the subject.     

Minmax and maxmin of repeated games with incomplete information

For a class of 2-Person 0-sum repeated games with incomplete information,Aumann/Masch1er [1967] andStearns [1967] have given a necessary and sufficient condition for the existence of v_∞ (the value of the infinitely repeated game).Mertens/Zamir [1971] andMertens [1971/72] have given the formula (and thus proved the existence) of \(\mathop {\lim }\limits_{n \to \infty } \) v _n , the limit of the values of the games withn repetitions, for a much larger class of games than that treated byAumann/Maschler andSteams. In this paper we extend the Aumann-Maschler-Stearns results to the larger family of games studied byMertens [1971/72].     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

On equilibria in repeated games with absorbing states

We prove the existence of ε-(Nash) equilibria in two-person non-zerosum limiting average repeated games with absorbing states. These are stochastic games in which all states but one are absorbing. A state is absorbing if the probability of ever leaving that state is zero for all available pairs of actions.     

On participation games with complete information

We analyze a class of two-candidate voter participation games under complete information that encompasses as special cases certain public good provision games. We characterize the Nash equilibria of these games as stationary points of a non-linear programming problem, the objective function of which is a Morse function (onethat does not admit degenerate critical points) for almost all costs of participation. We use this fact to establish that, outside a closed set of measure zero of participation costs, all equilibria of these games are regular (an alternative to the result of De Sinopoli and Iannantuoni in Econ Theory 25(2):477–486, 2005). One consequence of regularity is that the equilibria of these games are robust to the introduction of (mild) incomplete information. Finally, we establish the existence of monotone Nash equilibria, such that players with higher participation cost abstain with (weakly) higher probability.      

3-player repeated games with lack of information on one side

We study the existence of uniform equilibria for three-player repeated games with lack of information on one side and perfect observation. If there are only two states of nature, a completely revealing or a joint plan equilibrium always exists. This is not the case for larger spaces of states. Final version June 2001     

Correlated equilibria in a class of repeated games with incomplete information

This paper provides a characterization of correlated equilibria in two-person repeated games with lack of information on one side when the role of the informed player consists exclusively of transmitting information. The result is an analog to the “folk-theorem”.     

Note on nash equilibria in infinitely repeated games with incomplete information

We consider two-person repeated games with lack of information on one side where the role of the informed player consists exclusively of transmitting information. We show that, even in this case, there exist Nash equilibria that cannot be achieved with a single stage of signalling. We also provide an example where the number of revealing stages required by such an equilibrium is unbounded.     

Incentive compatible strategies for general stackelberg games with incomplete information

We study Stackelberg games with incomplete information in a general setting. In particular, we deduce the follower's reaction function, a set-valued function of the leader's action choice and a parameter specifying the follower's payoff type (a parameter about which the leader has only incomplete information), and using a generalized version of Komlos' Theorem due to Balder (1987), we show the existence of an expected payoff maximizing, incentive compatible strategy for the leader given the follower's reaction function.     

Infinitely repeated games of incomplete information: Symmetric case with random signals

We consider infinitely repeated two-person zero-sum games of incomplete information in which the signals are the same for both players and consist of probability distributions on a given alphabet. We show that such games have a value.     

Sequencing games with repeated players

Two classes of one machine sequencing situations are considered in which each job corresponds to exactly one player but a player may have more than one job to be processed, so called RP(repeated player) sequencing situations. In max-RP sequencing situations it is assumed that each player’s cost function is linear with respect to the maximum completion time of his jobs, whereas in min-RP sequencing situations the cost functions are linear with respect to the minimum completion times. For both classes, following explicit procedures to go from the initial processing order to an optimal order for the coalition of all players, equal gain splitting rules are defined. It is shown that these rules lead to core elements of the associated RP sequencing games. Moreover, it is seen that min-RP sequencing games are convex. We thank two referees for their valuable suggestions for improvement. Financial support for P. Calleja has been given by the Ministerio de Educación y Ciencia and FEDER under grant SEJ2005-02443/ECON, and by the Generalitat de Catalunya through a BE grant from AGAUR and grant 2005SGR00984.     

A note on the value of zero-sum sequential repeated games with incomplete information

We consider repeated two-person zero-sum games with lack of information on both sides. If the one shot game is played sequentially, it is proved that the sequencev _n is monotonic,v _n being the value of then shot game. Moreover the speed of convergence is bounded byK/n, and this is the best bound.