This article studies situations in which agents do not initially know the effect of their decisions, but learn from experience the payoffs induced by their choices and their opponents’. We chararacterize equilibrium payoffs in terms of simple strategies in which an exploration phase is followed by a payoff acquisition phase.

We exhibit a general class of interactive decision situations in which all the agents benefit from more information. This class includes as a special case the classical comparison of statistical experiments à la Blackwell. More specifically, we consider pairs consisting of a game with incomplete information G and an information structure S such that the extended game Gamma(G;S) has a unique Pareto payoff profile u. We prove that u is a Nash payoff profile of Gamma(G;S), and that for any information structure T that is coarser than S, all Nash payoff profiles of Gamma(G;T) are dominated by u.

We then prove that our condition is also necessary in the following sense: Given any convex compact polyhedron of payoff profiles, whose Pareto frontier is not a singleton, there exists an extended game Gamma(G;S) with that polyhedron as the convex hull of feasible payoffs, an information structure T coarser than S and a player i who strictly prefers a Nash equilibrium in Gamma(G;T) to any Nash equilibrium in Gamma(G;S).

Many results on repeated games played by finite automata rely on the complexity of the exact implementation of a coordinated play of length n. For a large proportion of sequences, this complexity appears to be no less than n. We study the complexity of a coordinated play when allowing for a few mismatches. We prove the existence of a constant C such that if (m ln(m))/n ≥ C, for almost any sequence of length n, there exists an automaton of size m that achieves a coordination ratio close to 1 with it. Moreover, we show that one can take any constant C such that C > e|X| ln(X), where |X| is the size of the alphabet from which the sequence is drawn. Our result contrasts with Neyman (1997) that shows that when (m ln(m))/n is close to 0, for almost no sequence of length n there exists an automaton of size m that achieves a coordination ratio significantly larger 1/|X| with it.

We characterize the max min of repeated zero-sum games in which player one plays in pure strategies conditional on the private observation of a fixed sequence of random variables. Meanwhile we introduce a definition of a strategic distance between probability measures, and relate it to the standard Kullback distance.

We consider the “and” communication device that receives input from two players and outputs the public signal yes if both inputs are yes and outputs no otherwise. We prove that no correlation can securely be implemented through this device, even if an infinite number of communication rounds are allowed.

We introduce the notion of an information structure I as being richer than another J when for every game G, all correlated equilibrium distributions of G induced by J are also induced by I. In particular, if I is richer than J then I can make all agents as well off as J in any game. We also define J to be faithfully reproducible from I when all the players can compute from their information in I “new information” that reproduces what they could have received from J. Our main result is that I is richer than J if and only if J is faithfully reproducible from I.

Correlated equilibria and communication equilibria are useful notions to understand the strategic effects of information and communication. Between these two models, a protocol generates information through communication. We define a secure protocol
as a protocol from which no individual may have strategic incentives to deviate and characterize these protocols.

Lorsque des possibilités de communication existent, un protocole désigne un ensemble de règles utilisées par les agents pour échanger de l’information. Nous définissons un protocole robuste comme un protocole duquel aucun agent n’a intérêt à dévier, et caractérisons ces protocoles.

This paper proves a Folk Theorem for overlapping generations games in the case where the mixed strategies used by a player are not observable by the others, but only their realizations are public.