Explicit formulas for repeated games with absorbing states

Explicit formulas are given for the asymptotic value lim_{λ → 0} v(λ) and the asymptotic minmax lim w(λ) of finite λ-discounted absorbing games together with new simple proofs for the existence of the limits as λ goes to zero. Similar characterizations for stationary Nash equilibrium payoffs are obtained. The results may be extended to absorbing games with compact metric action sets and jointly-continuous payoff functions.     

Pure equilibria of repeated games with public observation

The set of payoffs associated to pure uniform equilibria of a repeated game with public observation is characterized in terms of the one shot-game. The key of the result is first, a study of the effect of undetectable deviations and second, the definition of new types of punishments using approachability techniques.I wish to thank Prof. J. Abdou for his supervision.     

Repeated games with absorbing states and no signals

We recall the definition of stochastic games with signals. We show the existence of the MaxMin and MinMax if there is only one non absorbing state and if the players have no information about the other player's actions but only recall their own past moves.For having shared with me his experience in the domain, I would like to thank Sylvain Sorin.     

Nash equilibria of finitely repeated games

Under weak conditions, any feasible and individually rational payoff vector of a one-shot game can be approximated by the average payoff in a Nash equilibrium of a finitely repeated game with a long enough horizon.     

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.     

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.     

On equilibria in finite games

We are concerned with Nash equilibrium points forn-person games. It is proved that, given any real algebraic numberα, there exists a 3-person game with rational data which has a unique equilibrium point andα is the equilibrium payoff for some player. We also present a method which allows us to reduce an arbitraryn-person game to a 3-person one, so that a number of questions about generaln-person games can be reduced to consideration of the special 3-person case. Finally, a completely mixed game, where the equilibrium set is a manifold of dimension one, is constructed.     

On repeated games with general information function

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that limν _n exists,ν _n being the value of the game withn repetitions. If the players know at each stage the moves done by both players at all previous stages,Aumann andMaschler could prove that the error termδ _n=¦ν _n — limν _n ¦ satisfiesδ _n≤c/√n for somec>0. It was then shown byZamir that this bound is the lowest possible. In this paper it is shown that if previous moves are not always announced,δ _n may be of higher order of magnitude e.g.δ _n≥c/n ^1/3 for somec>0. New upper bounds forδ _n are given for two classes of games.     

On pure equilibria for bimatrix games

In Shapley (1964) several conditions are given for the existence of pure saddlepoints for a matrix game. In this paper we show that only a few of these conditions, when translated to the situation of a bimatrix game guarantee the existence of pure equilibria. Further, we associate with a bimatrix game a directed graph as well as a so-called binary game. If this graph has no cycles, then the bimatrix game in question has a pure equilibrium. It is shown that the binary game for a bimatrix game without a pure equilibrium possesses a fundamental subgame, which can be characterized by means of minimal cycles.     

On the existence of equilibria in generalized games

This paper deals with the existence of equilibrium in generalized games (the so-called abstract economies) and Nash equilibrium in games with general assumptions. Preference correspondences, unlike the existing theorems in the literature, need not have open graphs or open lower sections, strategy spaces need not be compact and finite dimensional, the number of agents need not be countable, and preference relations need not be ordered. Thus, our results generalize many of the existence theorems on equilibria in generalized games, including those of Debreu (1952), Shafer and Sonnenschein (1975), Toussaint (1984), Kim and Richter (1986), and Yannelis (1987).I wish to thank the editor and an anonymous referee for helpful comments and suggestions.     

On Pareto equilibria in vector-valued extensive form games

In this paper we investigate the existence of Pareto equilibria in vector-valued extensive form games. In particular we show that every vector-valued extensive form game with perfect information has at least one subgame perfect Pareto equilibrium in pure strategies. If one tries to prove this and develop a vector-valued backward induction procedure in analogy to the real-valued one, one sees that different effects may occur which thus have to be taken into account: First, suppose the deciding player at a nonterminal node makes a choice such that the equilibrium payoff vector of the subgame he would enter is undominated under the equilibrium payoff vectors of the other subgames he might enter. Then this choice need not to lead to a Pareto equilibrium. Second, suppose at a nonterminal node a chance move may arise. The combination of the Pareto equilibria of the subgames to give a strategy combination of the entire game need not be a Pareto equilibrium of the entire game.     

On the existence of Nash equilibria in large games

We study the existence of Nash equilibria in games with an infinite number of players. We show that there exists a Nash equilibrium in mixed strategies in all normal form games such that pure strategy sets are compact metric spaces and utility functions are continuous. The player set can be any nonempty set.     

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.     

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.     

Correlated equilibria in repeated games with lack of information on one side: A model with verifiable types

Games with lack of information on one side are considered where the uncertainty of the uniformed player concerns the (verifiable) identity of his opponent. Two solution concepts are compared: the correlated equilibrium and the noisy channel equilibrium. The analysis shows in particular that correlated equilibria behave differently in the model with verifiable types and in the one with unverifiable types.     

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.     

Perfect equilibria in stochastic games

We examine stochastic games with finite state and action spaces. For the -discounted case, as well as for the irreducible limiting average case, we show the existence of trembling-hand perfect equilibria and give characterizations of those equilibria. In the final section, we give an example which illustrates that the existence of stationary limiting average equilibria in a nonirreducible stochastic game does not imply the existence of a perfect limiting average equilibrium.Support was provided by the Netherlands Organization for Scientific Research NWO via the Netherlands Foundation for Mathematics SMC, Project 10-64-10.