Games of Incomplete Information, Ergodic Theory, and the Measurability of Equilibria

Robert Samuel Simon

This research was supported by the Center for Rationality and Interactive Decision Theory (Jerusalem), the Department of Mathematics of the Hebrew University (Jerusalem), the Edmund Landau Center for Research in Mathematical Analysis (Jerusalem) sponsored by the Minerva Foundation (Germany), the German Science Foundation (Deutsche Forschungsgemeinschaft), and the Institute of Mathematical Stochastics (Goettingen).

Abstract: We present an example of a one-stage three player game of incomplete information played on a sequence space {0, 1}^{Z} such that the players’ locally finite beliefs are conditional probabilities of the canonical Bernoulli distribution on {0, 1}^{Z}, each player has only two moves, the payoff matrix is determined by the 0-coordinate and all three players know that part of the payoff matrix pertaining to their own payoffs. For this example there are many equilibria (assuming the axiom of choice) but none that involve measurable selections of behavior by the players. By measurable we mean with respect to the completion of the canonical probability measure, e.g. all subsets of outer measure zero are measurable. This example demonstrates that the existence of equilibria is as much a philosophical issue as a mathematical one. We consider the double-shift Bernoulli probability space B^{Z^{2}}, where T_{1} is the shift in the first coordinate, T_{2} is the shift in the second coordinate, and x^{i,j} is the i, j-coordinate of x ∈ B^{Z^{2}}. Let C be a compact and convex set with compact subsets (A_{b} | b ∈ B) indexed by the set B such that ∩_{b∈B}A_{b} = ∅. We conjecture that measurable functions f : B^{Z^{2}} → C can not keep \frac{1}{4}(f(x) + f(T_{1}(x)) + f(T_{2}(x)) + f(T_{1} ∘ T_{2}(x))) in A_{x^{0,0}} for all x ∈ B^{Z^{2}} and that the inability of measurable functions to satisfy this property (in expectation) is bounded below by a positive constant dependent on the sets (A_{b} | b ∈ B). We give an example of a one-stage zero-sum game played on B^{Z^{2}} that would not have a value (but would have equilibria!) if this conjecture were valid.

Key words: Bayesian Equilibria, Belief Spaces, Sequence Spaces, Nonmeasurable Sets

1 Introduction

An equilibrium of a game is a set of strategies, one for each player, such that no player does better by choosing a different strategy, given that the other players do not change their strategies. In a game of incomplete information, what does it mean to do no better by choosing a different strategy? Should one evaluate a player’s actions according to the subjective and local beliefs of that player, or should one evaluate according to a probability distribution determined objectively by the game?

When the subjective beliefs of the players are conditionals of a common prior, a central question is whether there is a difference between the equilibria defined according to the subjective local beliefs and the equilibria defined according to a global functional evaluation. The former we call Bayesian equilibria and the latter we call Harsanyi equilibria. Harsanyi (1967-8) showed that these equilibria are equivalent when the set of all possible situations in the game is finite. Is there such an equivalence when the possible situations of the game are infinitely many?

In this paper we look at games that satisfy the following conditions:

1) there is one stage of play,

2) there are finitely many players,

3) each player has finitely many moves,

4) there are finitely many payoff matrices,

5) there is a compact space Ω with a Borel probability distribution μ and a finite partition into clopen subsets corresponding to the different payoff matrices; (the payoffs at x ∈ Ω are determined by the matrix associated with the partition member containing x),

6) at every point x ∈ Ω every player j has a discrete probability distribution on Ω with a finite support set S^{j}(x) containing x such that at all the other points in this finite support set S^{j}(x) the player j has the same discrete distribution,

7) these discrete beliefs of the players change continuously (with respect to the weak topology), and for any player j they are regular conditional probability distributions of μ with respect to the sigma algebra F^{j} := {B | B is Borel and x ∈ B ⇔ S^{j}(x) ⊆ B}. Such games we call ergodic games.

A strategy for a player in an ergodic game is a function from Ω to the probability simplex of his moves that is constant on every finite support set that he could believe to be possible. We call a function on Ω measurable when it is measurable with respect to the completion of μ, meaning that all sets of outer measure zero are measurable.

We give an example of a three player ergodic game that has no Bayesian equilibrium in measurable strategies (meaning also no Harsanyi equilibrium), yet it has many Bayesian equilibria that are not measurable. This example has the additional property that each player knows that part of the payoff matrix that pertains to his own payoff.

In the context of most multi-agent epistemic logics, a statement concerning the knowledge or belief of a player will correspond to a measurable subset of our sequence space. When applicable, the lack of a measurable equilibrium implies the impossibility for the behavior of the players in equilibrium to be determined by syntactic formulations of knowledge or belief.

Because the existence of non-measurable sets in our probability space can be denied by rejecting the axiom of choice, the existence of Bayesian equilibria for this game could be considered to be a philosophical question.

Do zero-sum ergodic games have values?

The question is difficult to answer because one must define the concept of value for ergodic games. A zero-sum game is a two-person game such that for all possible payoff matrices and all combinations of moves the payoff for one player is the negation of the payoff for the other player. Usually, a zero-sum game is defined to have a value r ∈ R (as a payoff for the first player) when for every positive ϵ the first player has a strategy such that no matter what the second player does it guarantees to him an expected payoff of at least r − ϵ, and vice-versa, the second player has a strategy such that no matter what the first player does the payoff to the first player is held down to r+ϵ or less. The problem with this definition of value is how to define the expected payoff of an ergodic game. If the strategies are measurable, then a payoff can be defined as an expectation over the probability space. But if strategies are not measurable, meaning that the evaluations of the players are strictly local in character, how should we define the expected payoff? Indeed, we will show an example of a Bayesian equilibrium of a zero-sum ergodic game that has an expected payoff for one player but not for the other player. We believe that the only reasonable definition of a value for a zero-sum ergodic game should be in relation to the set of measurable strategies.

We present an example of a zero-sum ergodic game and a conjecture of ergodic theory whose affirmation would show that this game would have no value in measurable strategies, and yet this game would have Bayesian equilibria.

The conjecture is the following. Let Ω = B^{Z^{2}} be the double-shift space over a finite set B, with the canonical Bernoulli probability distribution μ that gives equal probability to every b ∈ B in every coordinate position. Let T_{1} and T_{2} be the measure preserving transformations on Ω associated with shifting the first and second coordinates, respectively. Let C be a convex and compact subset of an Euclidean space with compact subsets (A_{b} | b ∈ B) such that ∩_{b∈B}A_{b} = ∅. For every measurable function f : Ω → C let d_{f} : Ω → R be the non-negative function defined by d_{f}(x) being the distance between \frac{1}{4}(f(x)+f(T_{1}(x))+f(T_{2}(x))+f(T_{1}∘T_{2}(x))) and the set A_{x^{0,0}}, where x^{0,0} ∈ B is the 0, 0 coordinate of x ∈ Ω. Conjecture: There a positive value w > 0 (dependent on the choice of the (A_{b} | b ∈ B)) such that for every choice of measurable function f : Ω → C the expected value of d_{f} over Ω must exceed w.

Due to Luzin’s theorem, one could replace in the conditions for the conjecture the measurability of f with the continuity of f.

Define the measure preserving involutions τ_{1}, τ_{2} : Ω → Ω by (τ_{1}(y))^{i,j} := y^{1−i,j} and (τ_{2}(y))^{i,j} := y^{i,1−j}. For our game theoretic purposes, it would suffice if the conjecture were true with the additional assumption that the function f is τ_{1} and τ_{2} invarient, meaning for all x ∈ Ω that f(τ_{1}(x)) = f(x) and f((τ_{2}(x)) = f(x).

As we shall see, the conjecture is false if formulated for the usual singleshift space {0, 1}^{Z} (with d_{f} defined with respect to the distance between \frac{1}{2}(f(x) + f(T (x)) and the appropriate compact subset).

The basic ideas in this paper belong to ergodic theory. One chooses a sequence space that allows for finitely many measure preserving involutions σ_{i} whose orbits are almost everywhere dense in the space. (σ_{i} ∘ σ_{i} is the identity, and for almost every x the subset of all the σ_{i_{1}}∘σ_{i_{2}}∘… σ_{i_{n}}(x) is dense in the space.) To each player is associated a finite subset of involutions that commute with eachtother, and for every point x, this player believes that only the points in the finite orbit of his commuting involutions are possible. The entries in the payoff matrix are determined by the topological position in the sequence space, in particular, by some coordinate position. The conditions defining Bayesian equilibria pertain to the orbits of the involutions σ_{i}, and these orbits do not contruct the space in a measurable way.

In the next section we define Bayesian and Harsanyi equilibria, prove that the countability of a belief structure implies the existence of Bayesian equilibria regardless of whether there exists a common prior, and we show that a Harsanyi equilibrium for an ergodic game generates a measurable Bayesian equilibrium for that game. In the third section we present the example of an ergodic game without measurable Bayesian equilibria. In the fourth section we discuss the conjecture and the present an example of a zero-sum ergodic game that would have no value in measurable strategies if the conjecture were true. In conclusion, we explore fundamental aspects of zero-sum games.

2 Bayesian and Harsanyi Equilibria

Δ(A) will stand for the set of regular Borel probability distributions of A, where A is a topological space (and if A is finite then we give A the discrete topology and Δ(A) is a simplex embedded in an Euclidean space). The distance in an Euclidean space, including in a simplex embedded in an Euclidean space, will be the Euclidean distance. Throughout this paper we will assume the axiom of choice. Sometimes a player will be refered to as he and sometimes as she.

2.1 Mertens-Zamir spaces

Ergodic games are a special case of games played on probability spaces that satisfy the Mertens-Zamir definition for a belief space.

A Mertens-Zamir belief space (Mertens and Zamir, 1985) is a tuple (S, X, ψ, N, (t^{j} | j ∈ N)), where X is a compact parameter set, S is a compact set, ψ is a continuous map from S to X, N is a finite set of players, for every j ∈ N t^{j} : S → Δ(S) is a continous function (with respect to the weak topology), and for every player j and every pair of points s, s′ ∈ S if s′ ∈ support (t^{j}(s)) then t^{j}(s) = t^{j}(s′).

Define a cell of a Mertens-Zamir belief space to be a minimal set C with the property that at every point y in C every player’s support set for the point y is contained in C (without the requirement that C must be compact).

Of special interest is the definition of mutual consistency for Mertens-Zamir belief spaces. For every player j ∈ N and define T^{j} to be the smallest Borel field of subsets of S such that the function t^{j} is measurable. A probability distribution μ on S is defined to be consistent if for every Borel subset A ⊆ S we have that μ(A) = ∫ t^{j}(y)(A)dμ(y). Mertens and Zamir (1985) showed that consistency is equivalent to the stronger statement that for every B ∈ T^{j} and Borel subset A ⊆ S we have μ(A ∩ B) = ∫_{B} t^{j}(y)(A)dμ(y). We prefer to use the Borel field F^{j} defined by F^{j} := {B | B is Borel and x ∈ B ⇔ support(t^{j}(x)) ⊆ B}, the largest Borel field on which a Borel measurable strategy for Player j can be defined. For the relation between the cells of a Mertens-Zamir belief space and the common prior, see Simon (2000).

For Mertens-Zamir belief spaces with a finite parameter space X it is easy to construct games that are played on the space S. Let ψ : S → X be the continuous function, N the finite player set, and for each j ∈ N t^{j} : S → Δ(S) the subjective beliefs of Player j. For each player j, there is a finite action set A^{j} with n^{j} := |A^{j}|. There are |X| different n^{1} × … × n^{|N|} matrices (Q_{x} | x ∈ X); every entry of every matrix is a vector payoff for the players in R^{N}. Nature chooses a point in S according to the common prior μ, which means also that a parameter in X is chosen through the function ψ. The players choose moves in their respective A^{j} independently, and after the choices are made the payoff to the players is the vector entry in Q_{x} corresponding to nature’s choice of the parameter in X and the moves of the players. A Bayesian equilibrium for a point z in the belief space is an |N|-set of functions (f^{j} | j ∈ N), each f^{j} from the cell that contains z to Δ(A^{j}), the simplex of mixed strategies, with the following properties for every player j ∈ N

1) f^{j} is constant within all support sets of Player j,

2) for all j′ ≠ j within the support set of t^{j′}(z) the function f^{j} is t^{j′}(z) measurable, and

3) within the support set of t^{j}(z) Player j can do no better than f^{j}(z) ∈ Δ(A^{j}) in response to the other functions f^{j′}, j′ ≠ j, as evaluated by t^{j}(z). When the |N|-set of functions is a Bayesian equilibrium for all points in a cell, then we call it a cellular equlibrium. A Bayesian equilibrium for the whole space is a collection of cellular equilibria, once for each cell.

If additionally the Mertens-Zamir belief space has a consistent common prior μ, we define a Harsanyi equilibrium to be a set of functions (f^{j} : S → Δ(A^{j}) | j ∈ N), each f^{j} measurable with respect to the Borel field F^{j}, such that no player can attain a higher expected payoff as evaluated by μ by choosing another such measurable function, (given that the strategies of the other players do not change).

Notice that ergodic games are special cases of games played on Mertens-Zamir spaces with consistent priors. From now one will be use the terminology of Mertens-Zamir spaces to describe an ergodic game, in particular the t^{j} to represent the belief of Player j; we will write support (t^{j}(x)) instead of S^{j}(x). We will adopt the term cell, though for all our examples a cell will be an orbit of a non-abelian group acting on the probability space. (A confusion with the orbits of a shift transformation T is avoided.) In an ergodic game, the local measurability condition 2) of a Bayesian equilibrium dissapears, leaving Bayesian equilibria with no measurability conditions at all.

2.2 Locally Finite Games

Now we define locally finite games, a class including the ergodic games, but without the assumption of a common prior or a compact space.

Let S be a finite or countably infinite set. There is a finite or countably infinite collection J and a map ν : J → 2^{S} such that for every J ∈ J ν(J) is a subset of S and for every s ∈ S the point s is contained in ν(J) for only finitely many members J of J. A member of J is a player of our game. For every J ∈ J there is a finite set A^{J} of moves and a sigma-additive probability distribution p^{J} on the set ν(J) such that the support of p^{J} is the set ν(J). For every s ∈ S define J (s) to be the finite subset of J whose projections by ν contain the point s. For every s ∈ S there is a payoff matrix Q_{s} of size ×_{J∈J (s)}|A^{J}| with entries in R^{J (s)}; for every choice of a ∈ ∏_{J∈J (s)} A^{J} there are corresponding payoffs for all the players in J (s).

A strategy of a player J ∈ J is a member of Δ(A^{J}). A Bayesian equilibrium for a locally finite game is a set of strategies (f^{J} ∈ Δ(A^{J}) | J ∈ J), such that for every J ∈ J the player J cannot get a higher expected payoff by choosing a move in A^{J} not in the support of f^{J}, given that the other players remain with (f^{K} ∈ Δ(A^{K}) | K ≠ J, K ∈ J)), with the expected payoff of a move calculated according to the distribution p^{J} and the expected payoffs from the matrices Q_{s} at each of the states s ∈ ν(J),

Proposition 1: If for every player J ∈ J in a locally finite game there is a uniform bound M^{J} on the absolute value of all payoffs to J in the set ν(J), then there exists a Bayesian equilibrium.

Proof: Let the set S be enumerated by S = {s_{1}, s_{2}, s_{3}, …}. For every i = 1, 2, … define the game Γ_{i} to be that played on the set S_{i} := {s_{1}, …, s_{i}} with the players J_{i} := {J ∈ J | ν(J) ∩ S_{i} ≠ ∅} and the probability distributions p_{i}^{J} on S_{i} (for the players in J_{i}) induced by p_{i}^{J}(B) := p^{J}(B)/p^{J}(S_{i}) for all B ⊆ S_{i}. Since each S_{i} and J_{i} are finite, there exists a Nash equilibrium f̃_{i} := (f_{i}^{J} ∈ Δ(A^{J}) | J ∈ J_{i}) to the game Γ_{i} for every i ≥ 1 (Nash, 1950). Assigning any distribution to f_{i}^{J} when ν(J) has an empty intersection with S_{i}, we have a sequence f_{i} in the set

Ã := ∏_{J∈J} Δ(A^{J}).

We give Ã the product topology. Due to Tychanov’s Theorem, Ã is compact, and we can assume that there exists a convergent subsequence f_{i_{n}} of the f_{i} converging to f ∈ Ã. Redefine the sequence (f_{i} | i = 1, 2, …) so that the new f_{n} is the old f_{i_{n}}.

We aim to show that f defines a Bayesian equilibrium of the original game. Fix an ϵ > 0. We will show that f is an ϵ-Bayesian equilibrium.

Let Player J ∈ J be given. Let i_{0} be so large that p^{J}(S_{i_{0}}) ≥ 1 − ϵ/4M^{J}. Let δ be the smallest positive probability by which Player J chooses some move with the strategy f^{J}. Let N_{i} be the finite cardinality of the set J_{i}. Now choose an i_{1} > i_{0} so large that l > i_{1} implies that f_{l}^{K} is within min(ϵ/4M^{J}N_{i_{0}}, δ/2) of f^{K} for all the K ∈ J_{i}, including J. Given that all other players K ≠ J stay with their strategies f^{K}, we need only show that the differences in expected payoffs for Player J by choosing different moves in support (f^{J}) do not exceed ϵ/2, and furthermore that Player J cannot obtain more than ϵ/2 by choosing a move outside of support (f^{J}). Because support (f^{J}) ⊆ support (f_{l}^{J}) for any l > i_{1}, both claims are easy to confirm. □

2.3 Measurable Equilibria

The following proof was explained to me by J.-F. Mertens.

Proposition 2: Any Harsanyi equilibrium of an ergodic game will generate a measurable Bayesian equilibrium of that game.

Proof: For all j ∈ N assume that f^{j} : Ω → Δ(A^{j}) are Harsanyi equilibria, meaning also that they are Borel measurable functions (measurable with respect to the Borel fields F^{j}, respectively). Let μ be the common prior probability distribution on Ω. For all j ∈ N, all moves a ∈ A^{j}, and all positive integers m define W_{0}^{j}(a, m) to be the subset of Ω such that Player j can obtain a payoff of at least 1/m more by choosing the move a instead of the distribution determined by f^{j}, as evaluated by the subjective probability distribution t^{j}. Since f^{k} for k ≠ j is Borel measurable and the t^{j} are continuous in the weak topology, the sets W_{0}^{j}(a, m) are also Borel. If μ(W_{0}^{j}(a, m)) were positive for some j, a, and m, then the (f^{j} | j ∈ N) would not have been a Harsanyi equilibrium. We define W_{0} to be ∪_{j,a,m}W_{0}^{j}(a, m). Because this union is countable, the set W_{0} is also Borel of measure zero. Now for all l ≥ 1 define inductively the sets W_{l}^{j} := {x ∈ Ω | t^{j}(x)(W_{l−1}) > 0} and W_{l} := ∪_{j∈N}W_{l}^{j}. We claim for all l and j that W_{l}^{j} is in F^{j}, W_{l} is Borel, and μ(W_{l}) = 0. We proceed by induction, assuming the claim for l − 1. That W_{l−1} is Borel implies that W_{l}^{j} is in F^{j}, and this implies that W_{l} = ∪_{j∈N}W_{l}^{j} is Borel. Due to the formula μ(W_{l−1} ∩ W_{l}^{j}) = ∫_{W_{l}^{j}} t^{j}(y)(W_{l−1})dμ(y) and the fact that t^{j}(y)(W_{l−1}) > 0 for all y ∈ W_{l}^{j}, μ(W_{l}^{j}) > 0 would imply that μ(W_{l−1}) ≥ μ(W_{l−1} ∩W_{l}^{j}) > 0, a contradiction. Therefore we can assume also that μ(W_{l}) = 0.

Define W := ∪_{l=0}^{∞}W_{l}. We have two important properties, that W is Borel with μ(W) = 0, and also from the structure of ergodic games that W is the union of cells. We can alter our Harsanyi equilibrium. We keep the original functions on Ω\W, and for all the cells in the set W we introduce any Bayesian equilibria obtained from Proposition 1. The result is a measurable Bayesian equilibrium that we seek.

3 Many Bayesian Equilibria, none Measurable

3.1 The Example

Let a and b be two distinct states of nature. Define Ω to be {a, b}^{Z}, where Z is the set of integers, including both the positive and the negative. The 0-coordinate of a point in Ω determines the state of nature, so that if y ∈ Ω and y^{0} = a then a is the state of nature at the point y. We define μ to be the canonical Bernoulli distribution on Ω, giving equal probability independently to a and b in all coordinate positions.

There will be three players, Players One, Two, and Three. Let σ : Ω → Ω be the measure preserving involution defined by (σ(y))^{i} := y^{−i}, where x^{i} is the ith coordinate of x ∈ Ω. σ is the reflection of the doubly infinite sequence about the position zero. Let τ : Ω → Ω be the measure preserving involution defined by (τ(y))^{i} := y^{1−i}. It follows that T := τ ∘ σ is the usual Bernoulli shift operator (T (y))^{i} = y^{i−1}. The beliefs of the players are determined as follows: at any point y ∈ Ω Player One considers only y and σ(y) to be possible, and with equal probability; (if σ(x) = x then Player One believes in x with full probability). At any x, both Player Two and Player Three believe that only x and τ(x) are possible, and with equal probability. Because the involutions σ and τ are continuous functions, our game is an ergodic game. The cells will be the orbits of the involutions σ and τ. Player Two and Three have the same beliefs. Player One always knows the state of nature, a or b, but not always what the other players might know. Such a game is called a game of incomplete information on one and a half sides (Sorin and Zamir 1985), though this term was invented with reference to infinitely repeated zero-sum games.

Each player has two moves, L and R, standing for left and right. The game is a variation of the well known game of matching pennies, with Player One playing against both Player Two and Player Three. Player Two and Three want to match the pennies, Player One wants to have a mismatch. The differences to the conventional game of matching pennies has two aspects. First, Player Two has a special relationship to the move L, her favorite move, and likewise Player Three has a special relationship to her favorite move R. Second, if both Players Two and Three choose their favorite moves, then the payoff to Player One is dependent on the state of nature.

By playing L, Player One at x ∈ Ω receives −1 if Player Two and Player Three both choose L, 1 if Player Two and Three both choose R, 0 if Player Two chooses R and Player Three chooses L, and δ_{a}(x^{0}) if Player Two chooses L and Player Three chooses R. δ stands for the Kroniker delta, which means that δ_{a} = 1 if the state of nature is a and δ_{a} = 0 if the state of nature is b.

By playing R, Player One at x ∈ Ω receives 1 if Player Two and Player Three both choose L, −1 if Player Two and Three both choose R, 0 if Player Two chooses R and Player Three chooses L, and δ_{b}(x^{0}) if Player Two chooses L and Player Three chooses R.

By playing L, Player Two receives (independently of the state of nature) 2 if Player One and Player Three choose L, 1 if Player One chooses L and Player Three chooses R, −1 if Player One chooses R.

By playing R, Player Two receives −1 if Player One chooses L, and 1 if Player One chooses R.

By playing L, Player Three receives 1 if Player One chooses L, and −1 if Player One chooses R.

By playing R, Player Three receives −1 if Player One chooses L, 1 if Player One chooses R and Player Two chooses L, and 2 if Player One and Player Two choose R.

For all Players i = 1, 2, 3 let f^{i} : Ω → [0, 1] be the behavior strategy for Player i, with f^{i}(x) representing the probability at x ∈ Ω that Player i chooses the move L. The only a-priori requirement placed on the behavior strategies (f^{i} | i = 1, 2, 3) is that for all x ∈ Ω f^{1}(x) = f^{1}(σ(x)) and f^{j}(x) = f^{j}(τ(x)) for either j = 2, 3.

Given any Player j ∈ {1, 2, 3} and two functions (f^{i} | i ≠ j) for the other two players, one can calculate the expected payoff to Player j at every x ∈ Ω for choosing L and for choosing R; for Player One one must average the expected payoffs of the moves with respect to (f^{i}(x) | i ≠ 1) and (f^{i}(σ(x)) | i ≠ 1), and for Players Two and Three one must do the same with respect to (f^{i}(x) | i ≠ j) and (f^{i}(τ(x)) | i ≠ j) for j = 2, 3. The three functions (f^{i} | i = 1, 2, 3) are a Bayesian equilibrium for the game if and only if at every appropriate pair of points for every j if Player j chooses the move D ∈ {L, R} with positive probability according to f^{j} then the other move E ∈ {L, R}, E ≠ D must deliver to Player j no higher an expected payoff than does the move D.

Define a pair of strategies (f^{2}, f^{3}) ∈ [0, 1]^{2} for Players Two and Three to be a ballanced pair if and only if f^{2} = 1 and f^{3} < 1 or f^{3} = 0 and f^{2} > 0. The ballanced pairs are those for which at least one of the two players chooses her favorite move with certainty and the other player is not choosing the same move with certainty.

The two pairs of strategies (f^{2}, f^{3}) ∈ [0, 1]^{2} such that f^{2} = f^{3} = 0 or f^{2} = f^{3} = 1 will be called the coordinated pairs. A strategy f^{1} ∈ [0, 1] of Player One that takes on the value of 0 or 1 will be called a pure strategy. A strategy of Player One in [0, 1] that is not pure will be called mixed.

Lemma 1: In any Bayesian equilibrium behavior Players Two and Three are using only pairs that are ballanced or coordinated.

Proof: Suppose for the sake of contradiction that f^{2}(x) < 1 and f^{3}(x) > 0. If f^{1}(x)+f^{1}(τ(x)) ≥ 1 then Player Two would prefer to choose L (f^{2} = 1) at the pair x and τ(x), and if f^{1}(x) + f^{1}(τ(x)) ≤ 1 then Player Three would prefer to choose R (f^{3} = 0) at the pair x and τ(x). □

Although the strategies available a-priori to Players Two and Three are two dimensional, in Bayesian equilibrium only a one-dimensional subset will be used. This will allow us to perceive the game much like a two-by-two game played between two players. Notice that if both Players Two and Three choose their favorite moves with certainty in a Bayesian equilibrium then it is impossible for either player to prefer her favorite move over the other move (since otherwise the other player would also prefer her non-favorite move). For this reason we perceive the pair (f^{2} = 1, f^{3} = 0) as ballanced, although strictly speaking both players are choosing pure strategies.

3.2 Strategy of the Proof

We suppose for the sake of contradiction that the three functions f^{i} : Ω → [0, 1] for i = 1, 2, 3 are measurable behavior strategies in Bayesian equilibrium. We will show that this leads to a contradiction. From Proposition 1 there would exist non-measurable Bayesian equilibria.

Our strategy is the following. We will divide Ω into two parts. The first part will be the set of x ∈ Ω where Player One is using a mixed strategy and Players Two and Three are using a ballanced strategy; the second part will be its compliment. The measurability assumption will imply that both parts of Ω are of measure zero.

From ergodic theory, we will need a few well known results.

First, we need the Birkhoff Ergodic Theorem. If a transformation T on a probability space Ω is measure preserving and f is an integrable function on Ω then the Birkhoff Ergodic Theorem states that lim_{n→∞} ∑_{i=0}^{n−1} f(T^{i}(x)) converges almost everywhere to an integrable function f^{∗} such that the integral of f^{∗} over Ω is equal to that of f (Theorem 1.14, Walters, 1982).

Second, we need the property called ergodic. A measure preserving transformation T of a probability space with a probability measure μ is ergodic if the only measurable sets B with the property T^{−1}(B) = B satisfy μ(B) = 0 or μ(B) = 1. A measure preserving transformation is ergodic if and only if the only measurable sets B with μ(T^{−1}(B)ΔB) = 0 are those with μ(B) = 0 or μ(B) = 1 (Theorem 1.5, Walters, 1982), where here Δ stands for the symmetric difference. It is well known that the Bernoulli shift operator of our example is ergodic.

The cells partition the space Ω. Because the σ and τ are measure preserving, the smallest union of cells containing any measure zero subset of Ω is also of measure zero. Notice that for almost all points x ∈ Ω that the points T^{k}(x) and T^{k} ∘ τ(x) for all k ∈ Z are distinct and comprise the cell containing x. Define such points and their cells to be doubly infinite.

For any finite k ≥ 1 any measurably defined behavior that occurs at most k times in any doubly infinite cell must occur only in a set of measure zero, since otherwise the distinctness of the points T^{k}(x) and T^{k} ∘ τ(x) for almost all x ∈ Ω would imply that the space Ω has infinite measure.

Define a point x ∈ Ω to be normal if and only if Player One uses a mixed strategy at x and Players Two and Three use a ballanced strategy at x. Define a cell to be normal if and only if it contains at least one normal point. The other cells will be called abnormal.

3.3 Normal cells

We define a homeomorphism between the ballanced pairs and the real numbers. Define k : (0, 1] → N_{0} = {0, 1, 2, …} and s : (0, 1] → [0, 1] by r = 3^{−k(r)}(1 − 2s(r)/3) for k(r) being the last number such that 3^{−k(r)} ≥ r. Define W to be the set of ballanced pairs, W := {(f^{2}, f^{3}) | f^{2} = 1 or f^{3} = 0}\{(0, 0), (1, 1)}. Define the homeomorphism ϕ : W → R by ϕ(1, 0) := 0, ϕ(1, t) := k(1 − t) + s(1 − t), and ϕ(t, 0) := −s(t) − k(t).

Lemma 2: If x is doubly infinite, f^{1}(x) is mixed and the strategy pair (f^{2}(x), f^{3}(x)) is ballanced, then there is one and only one value for f^{1}(τx) that preserves the Bayesian equilibrium property for Players Two and Three and there is one and only one ballanced pair (f^{2}(σ(x)), f^{3}(σ(x))) that preserves the Bayesian equilibrium property for Player One, namely f^{1}(τ(x)) = 1 − f^{1}(x) and

(f^{2}(σ(x)), f^{3}(σ(x))) = ϕ^{−1}( − 1^{δ_{b}(x^{0})} − ϕ(f^{2}(x), f^{3}(x))).

Proof: By symmetry we assume that f^{2}(x) = 1. The condition that f^{1}(τ(x)) = 1 − f^{1}(x) follows by the indifference of Player Three (and for both players in the case that f^{3}(x) = 0, as discussed above).

Again, assuming f^{2}(x) = 1, we must divide the argument into three cases. Case A is that of 0 ≤ f^{3}(x) ≤ 2/3 and x^{0} = a, Case B is that of x^{0} = b, and Case C is that of 2/3 ≤ f^{3}(x) < 1 and x^{0} = a. By Lemma 1 we need only consider the ballanced pairs and the coordinated pairs. Notice that increasing values for ϕ in both cases of x^{0} = a and x^{0} = b imply an increasing preference by Player One for the move R, so that if we find one ballanced pair that delivers indifference to Player One then we have found the only such ballanced pair, and furthermore neither coordinated pair could deliver such an indifference.

Case A: Consider the strategy pair g^{2} = 1 and g^{3} = 2/3 − f^{3}(x), which satisfy ϕ(f^{2}(x), f^{3}(x))+ϕ(g^{2}, g^{3}) = 1. If Player One chooses L, he can expect a payoff of \frac{1}{2}(−f^{3}(x) + 1 − f^{3}(x) − g^{3} + 1 − g^{3}) = 1/3. By playing R he can expect a payoff of \frac{1}{2}(f^{3}(x) + g^{3}) = 1/3.

Case B: Consider the strategy pair g^{3} = 0 and g^{2} = (1−f^{3}(x))/3, which satisfy ϕ(f^{2}(x), f^{3}(x)) + ϕ(g^{2}, g^{3}) = −1. If Player One chooses L, he can expect a payoff of \frac{1}{2}(−f^{3}(x) + 1 − g^{2}) = (1 − f^{3}(x))/3. If Player One chooses R, he can expect a payoff of \frac{1}{2}(f^{3}(x)+1−f^{3}(x)−(1−g^{2})+g^{2}) = (1−f^{3}(x))/3.

Case C: Consider the strategy pair g^{3} = 0 and g^{2} = 3(1 − f^{3}(x)), which satisfy ϕ(f^{2}(x), f^{3}(x))+ϕ(g^{2}, g^{3}) = 1. If Player One chooses L, he can expect a payoff of \frac{1}{2}(−f^{3}(x) + 1 − f^{3}(x) + g^{2} + 1 − g^{2}) = 1 − f^{3}(x). By playing R he can expect a payoff of \frac{1}{2}(f^{3}(x) − (1 − g^{2})) = 1 − f^{3}(x). □

Lemma 3: The measure of the union of all normal cells must be zero or one.

Proof: By Lemma 2 a doubly infinite cell is normal (contains a normal point) if and if all the points in the cell are normal. This means that the set of normal points is a T -invarient set, and therefore by the ergodicity of T they must be of measure zero or one. □

Lemma 4: Let f : Ω → R be a function with f(T x) + f(x) = −1^{δ_{b}(x^{0})} for almost all x ∈ Ω. Conclusion: The function f cannot be measurable.

Proof: Suppose for the sake of contradiction that the function f is measurable. This would imply that there exists an M > 0 such that the probability that f is in [−M + 2, M − 2] is at least 9/10.

Now consider the function g_{M} : Ω → [0, 1] defined by

g_{M}(x) := lim_{n→∞} inf \frac{|\{k | |k| ≤ n, |f(T^{k}x)| ≥ M\}|}{2n + 1}.

Now consider the transformation T^{2}. The action of T^{2} is that of a random walk, with f(T^{2}x) − f(x) = 2 if x^{0} = b and x^{−1} = a, f(T^{2}x) − f(x) = −2 if x^{0} = a and x^{−1} = b, and f(T^{2}x) = f(x) if both x^{0} and x^{−1} have the same value. Therefore for almost all x there is a k ∈ Z with f(T^{k}x) > M + 1, which means that g_{M}(x) ≥ 1/2 for almost all x ∈ Ω. But by the Birkhoff Ergodic Theorem, the expected value of g_{M} must equal the probability in Ω that the function f exceeds the value of M, a contradiction. □

Proposition 3: The union of all normal cells is of measure zero.

Proof: This result follows directly from Lemmatta 2, 3 and 4. □

3.4 Abnormal cells

Define x ∈ Ω to be a pure point if and only if f^{i}(x) ∈ {0, 1} for all i = 1, 2, 3 with f^{2}(x) = f^{3}(x) (meaning that Player One uses a pure strategy at x and Players Two and Three use a coordinated pair). Define the wind direction from a doubly infinite pure point x to be the direction on the cell of the y adjacent to x (equal to either σ(x) or τ(x)) such that y = σ(x) if all three of the f^{i}(x) have the same value in {0, 1}, and otherwise y = τ(x) if Player One chooses a different move from that chosen by Players Two and Three. Define the lee direction from a doubly infinite pure point to be the direction opposite to the wind direction. Define a pure point x to be a book end if additionally either Player One at x has a clear preference for his chosen move or the player among Players Two or Three who is not choosing her favorite move has a clear preference for her chosen and non-favorite move.

Lemma 5:

(1) The behavior of all players on the wind side of a doubly infinite pure point is determined; all of the points on the wind side of a doubly infinite pure point are also pure, alternating in values, and none are book ends.

(2) There can be at most two book ends in any doubly infinite abnormal cell.

(3) If there are no book ends in a doubly infinite abnormal cell, then either Player One or Players Two and Three are performing alternating behavior, meaning that choosing any point x in the cell we have that either the value f^{1}(T^{n}(x)) ∈ {0, 1} is determined by the parity of n or the value f^{2}(T^{n}(x)) = f^{3}(T^{n}(x)) ∈ {0, 1} is determined by the parity of n.

Proof:

(1) By symmetry, we can assume that Players Two and Three choose the move L at x. We consider two cases, (A) that Player One chooses L and (B) that Player One chooses R. In Case (A) the point σ(x) (and the transformation T) defines the wind direction. If Players Two and Three did not both choose R at σ(x), then it would have been in the interest of Player One to choose R at x. In Case (B) the point τ(x) (and T^{−1}) defines the wind direction. If Player One did not choose L at the point τ(x) then it would have been in the interest of Player Three to choose R at x. The rest follows by induction.

(2) For the sake of contradiction, let us assume that there is at least three book ends x in a doubly infinite cell. One of these three book ends must be between the other two. By Part 1, in one of the two directions from this middle book end there are no book ends, a contradiction.

(3) We consider three cases, (A) that there are no pure points in the cell and that Player One chooses a pure strategy at x, (B) that there are no pure points in the cell and Players Two and Three choose a coordinated pair at x, and (C) x is a pure point in the cell.

Case (A): If Player One is choosing L at x, then the lack of a pure point implies that Players Two and Three are choosing ballanced strategies at both x and σ(x). To maintain the indifference of these ballanced choices by at least one of either Players Two or Three, Player One must choose R at T x and T^{−1}x. The rest follows by induction.

Case (B): If Players Two and Three are both choosing L at x, then the lack of a pure point implies that Player One is choosing mixed strategies at both x and τ(x). To maintain the indifference of Player One, Players Two and Three are both choosing R at both T x and T^{−1}x. The rest follows by induction.

Case (C): Assume that x is a pure point, that Players Two and Three are choosing L at x, and Player One is choosing either L or R at x. If Player One is choosing L at x, then the lack of a book end implies that Player One is choosing R at T^{−1}(x), in the lee direction of x. If Player One is chossing R at x, then the lack of a book end implies that Players Two and Three are both choosing R at T (x), in the lee direction of x. By induction and Part 1 we conclude that the whole cell consists of alternating behavior by all three players. □

Proposition 4: The union of all the abnormal cells is a measure zero set.

Proof: Due to Part Two of Lemma 5, the measure of the set of all doubly infinite book ends is zero, and therefore also of all the cells containing a book end.

Let us define A to be the set of all points where Player One chooses the pure strategy L, and B the set where Player One chooses the pure strategy R. By assumption both A and B are measurable sets and by Lemma 5 T (A) = B and T (B) = A (modulo sets of measure zero). By the ergodicity of T we must have that μ(A) = 0 or μ(A) = 1. Since A and B are sets of the same measure, we must conclude that both are of measure zero. We proceed the same way with the sets where Players Two and Three both choose either L or R. By Lemma 5 we have exhausted the abnormal cells. □

Theorem 1: (f^{1}, f^{2}, f^{3}), an arbitrary Bayesian equilibrium, could not have consisted of measurable functions, (and therefore there could not have been a Harsanyi equilibrium by Proposition 2).

Proof: The result follows directly from Propositions 3 and 4. □

4 The Challenge of Approximate Equilibria

4.1 The Example

The following is an example of a zero-sum ergodic game for which there would be no value in measurable strategies if the conjecture (presented in the introduction) were true, though (from Proposition 1) there would exist Bayesian equilibria.

There are eleven states of nature, with B = {b_{0}, …, b_{10}}. The space is Ω := B^{Z^{2}}, with the canonical Bernoulli distribution μ. The 0, 0 -coordinate determines the state of nature, so that if y ∈ Ω and y^{0,0} = b_{i} then the payoffs are determined by the state b_{i}.

There are two players, Player One and Player Two, and at each state each player has eleven moves. It is a zero-sum game, so that the payoffs presented will be those of the first player. The following payoffs are for the state i, modulo 11, and the moves, also modulo 11.

If Player One chooses the move i, then the payoff is −100 if Player Two chooses i, 11 if Player Two chooses i − 1 (modulo 11), and 10 if Player Two chooses any other move k ∉ {i, i − 1}.

If Player One chooses the move k ≠ i, then the payoff is −100 if Player Two chooses k, and 10 if Player Two chooses l ≠ k, including l = i.

Next, consider the measure preserving involutions σ_{1}, σ_{2} : Ω → Ω defined by (σ_{1}(y))^{i,j} := y^{−i,j} and (σ_{2}(y))^{i,j} := y^{i,−j}. Notice that the σ_{1} and σ_{2} commute, so that for every x ∈ Ω we get at most four distinct points in the orbit of σ_{1} and σ_{2} applied to x. At every x ∈ Ω define t^{1}(x) so that Player One believes that x, σ_{1}(x), σ_{2}(x), σ_{2} ∘ σ_{1}(x) are given each 1/4 probability, (with i/4 probability given to a point that appears with multiplicity i). As before with the previous example, Player One always knows the state of nature, but not necessary what Player Two believes.

The measure preserving involutions τ_{1}, τ_{2} : Ω → Ω are defined by (τ_{1}(y))^{i,j} := y^{1−i,j} and (τ_{2}(y))^{i,j} := y^{i,1−j}. Likewise, the τ_{1} and τ_{2} commute, with at least four possibilities. At every x ∈ Ω define t^{2}(x) so that Player Two believes that x, τ_{1}(x), τ_{2}(x), τ_{2} ∘ τ_{1}(x) are given 1/4 probability each, (with i/4 probability given to a point that appears with multiplicity i). It follows that τ_{1} ∘ σ_{1} is the shift T_{1} : Ω → Ω defined by T (y)^{i,j} = y^{i−1,j} and τ_{2} ∘ σ_{2} is the shift T_{2} : Ω → Ω defined by T (y)^{i,j} = y^{i,j−1}. Define F^{1} := {B | B is Borel and x ∈ B ⇔ {x, σ_{1}(x), σ_{2}(x), σ_{1} ∘ σ_{2}(x)} ⊆ B}, and define F^{2} correspondingly with τ_{1} and τ_{2}. As before, for every Player j t^{j} is a regular conditional probability distribution of μ with respect to the Borel field F^{j}.

4.2 Application of the Conjecture

Lemma 6: In Bayesian equilibrium, at every quartet of points considered possible by Player One, she receives an expected payoff of at least 0.

Proof: It suffices to consider the strategy that puts an equal weight of 1/11 to all moves. Regardless of the state of nature and the strategies of Player Two, this strategy of Player One delivers to her a payoff of at least 0. □

Lemma 7: If Q is a member of F^{1} of positive measure and Player One uses a single move i with a probability of at least 1−δ at all points of Q then there will be a Q′ ∈ F^{2} containing Q where on the average Player Two holds Player One down to a payoff of no more than −67/4 + 111δ/4 and there is a Q^{∗} ∈ F^{1} containing Q′ where Player One is obtaining on the average no more than −4/3 + 37δ/3.

Proof: For almost all points x ∈ Ω, the structure of the cell containing x will be that of the two dimensional lattice Z^{2}. To see this, we define the actions of σ_{1}, σ_{2}, τ_{1}, τ_{2} on the set D := Z^{2} in the following way. If i is even, then σ_{1}(i, j) = (i + 1, j) and τ_{1}(i, j) = (i − 1, j), if i is odd, then σ_{1}(i, j) = (i − 1, j) and τ_{1}(i, j) = (i + 1, j), if j is even, then σ_{2}(i, j) = (i, j + 1) and τ_{2}(i, j) = (i, j − 1), if j is odd, then σ_{2}(i, j) = (i, j − 1) and τ_{2}(i, j) = (i, j + 1).

We have that T_{1}(i, j) := τ_{1} ∘ σ_{1}(i, j) = (i + 2, j) if i is even and equal to (i − 2, j) if i is odd, and that T_{2}(i, j) := τ_{2} ∘ σ_{2}(i, j) = (i, j + 2) if j is even and (i, j − 2) if j is odd. To confirm that this lattice structure represents correctly the generic cell and the actions of the involutions, we need to know two things, that points identified by D came from identical points in Ω, and that generically distinct points in D come from distinct points of Ω. For the former, if we start at any point in D and choose two pathways defined by our involutions that lead to the same point in D then we need to know that these involutions induce the same action on Ω. We must check that moving from (i, j) to (i+1, j +1) (and also the corresponding paths to (i + 1, j − 1), (i − 1, j + 1), or (i − 1, j − 1)) through either (i + 1, j) or (i, j + 1) correspond to the same action on Ω. This is confirmed by some pairs of involutions commuting, namely σ_{1} with σ_{2}, τ_{1} with τ_{2}, τ_{1} with σ_{2}, and σ_{1} with τ_{2}. For the latter, we notice for almost all x ∈ Ω that the points T_{1}^{m} ∘ T_{2}^{n}(x), T_{1}^{m} ∘ T_{2}^{n} ∘ τ_{1}(x), T_{1}^{m} ∘ T_{2}^{n} ∘ τ_{2}(x) and T_{1}^{m} ∘ T_{2}^{n} ∘ τ_{1} ∘ τ_{2}(x) for all m, n ∈ Z are distinct and comprise the orbit of x. (The probability that any given pair are equal is a set of measure zero, and the rest follows by sigma additivity.)

Now let us assume that at some point x ∈ Ω Player One puts a weight of at least 1 − δ on the move k ∈ {0, 1, …, 10}. Without loss of generality, let us assume that x is represented by the point (0, 0) in D. This means also that a weight of at least 1−δ is put on the move k at the points σ_{1}(x), σ_{2}(x), σ_{1} ∘σ_{2}(x), which are now mapped to (0, 1), (1, 0) and (1, 1) in D. Since at all four of these points Player Two could respond with the move k, the average payoff for Player One at the points mapped to {(i, j) | −1 ≤ i, j ≤ 2} cannot exceed \frac{1}{16}(12·11−4·100)(1−δ)+11δ = −67/4+111δ/4. Now consider the 36 different positions in D defined by {(i, j) | −2 ≤ i, j ≤ 3}. The average payoff for Player One on this set cannot exceed \frac{1}{36}(32 · 11 − 4 · 100)(1 − δ) + 11δ = −4/3 + 37δ/3. □

For every k ∈ {0, …, 10} and distinct pair m, n ∈ {0, …, 10} define E_{k}^{(m,n)} to be the subset of mixed strategies of Player Two in Δ({0, …, 10}) against which the moves m and n both maximize Player One’s payoff at the state b_{k} (meaning also that Player One is indifferent between the moves m and n). Define E_{k} := ∪_{m≠n}E_{k}^{(m,n)}.

Lemma 8: The intersection ∩_{k∈{0,...,10}}E_{k} is empty, and for every strategy g ∈ Δ({0, …, 10}) that is a positive distance of δ > 0 away from the set E_{k} there is a move of Player One that is prefered to all other moves at the state k by a value of at least δ/5.

Proof: Let q ≥ 0 be the least weight given by g to any move in {0, …, 10}. If q = 1/11 and g gives equal weight to all moves, then at any state b_{k} the move k will be prefered to all others by Player One. One the other hand, if q < 1/11, then choose any k ∈ {0, … 10} such that g gives strictly more than q to the move k − 1 (modulo 11) and gives exactly q to the move k (modulo 11). At the state b_{k} the move k will be prefered by Player One to all other moves.

The last claim follows directly from the fact that 1 is the smallest positive difference between any of the payoffs and the diameter of the simplex is strictly smaller than 5. □

Theorem 2: If the conjecture is valid, then there is a zero-sum ergodic game with no value in measurable functions.

Proof: Define the variable d_{g} in relation to the subsets E_{i} as stated by the conjecture. By the conjecture (and Lemma 8) the expected value of d_{g} is at least w > 0 for all measurable functions g. Without loss of generality we will assume that w ≤ 1. We will show that there cannot be a value v ∈ R and strategy functions (f, g) for Players One and Two, measurable in F^{1} and F^{2} respectively, such that the combination (f, g) delivers an expected payoff of v to Player One, f guarantees a payoff of at least v − w^{2}/10, 000 against all measurable strategies of Player Two and g holds Player One down to a payoff of no more than v + w^{2}/10, 000 against all measurable strategies of Player One.

Let Q be the measurable subset in F^{1} where according to f Player One uses a single move with probability of at least 1 − 1/90. By Lemma 7 there is an even larger set Q^{∗} ∈ F^{1} where Player One is getting an average payoff of no more than −4/3 + 37/270 < −1. Since by Lemma 6 Player One can guarantee a payoff of at least 0 in the set Q^{∗}, by the approximate optimality of g we must assume that the measure of Q^{∗} (and also Q) is no greater than w^{2}/10, 000.

Now let us look at a point x such that x^{0,0} = b_{k} and \frac{1}{4}(g(x) + g(T_{1}(x)) + g(T_{2}(x)) + g(T_{1} ∘ T_{2}(x)) is a distance of positive r > 0 from the set E_{k}. We notice that T_{1}(x) = τ_{1} ∘σ_{1}(x), T_{2}(x) = τ_{2} ∘σ_{2}(x), and T_{1} ∘T_{2}(x) = τ_{2} ∘τ_{1} ∘σ_{1} ∘ σ_{2}(x). Since the behavior of Player Two remains constant within the finite orbit of the τ_{1} and τ_{2}, we see that \frac{1}{4}(g(x)+g(σ_{1}(x))+g(σ_{2}(x))+g(σ_{1} ∘σ_{2}(x))) is a distance of positive r from the set E_{k}. By Lemma 8, Player One has a single move at x that delivers to her r/5 more than any other move. By the conjecture the distance r = w/2 is exceeded in a member of F^{1} of measure at least w/10 (since the diameter of the simplex is less than 5). Since the set Q where Player One chooses one move with frequency greater than 1−1/90 is so small, we conclude that there is a set P ∈ F^{1} of measure at least w/11 where the distance to the appropriate E_{k} (the k with b_{k} = x^{0,0}) is at least w/2 and Player One does not use any move with more than 1 − 1/90 probability. But now we can conclude by Lemma 8 that Player One can improve her expected payoff by at least \frac{1}{90} \frac{w}{10} in this subset of measure at least \frac{w}{11} by choosing some single move. Due to the measurability of g, a decision concerning which move is sufficient to obtain a payoff gain of \frac{1}{90} \frac{w}{10} can be done in a measurable way. □

4.3 Single-Shift Spaces

Now we look at how the conjecture fails for single-shift spaces.

Let us consider the following example. C = [0, 2], A_{1} = {1/3, 4/3}, A_{2} = \{2/3, 5/3\}, and Ω = \{1, 2\}^{Z}. We assume for all x ∈ Ω that \frac{1}{2}(f(x) + f(T (x))) ∈ A_{x^{0}}. Modulo one, the determination of f(x) for any x ∈ Ω will determine f(T^{k}x) for all k ∈ Z. From now on we will view everything in terms of modulo one. By the axiom of choice, we have a function f defined on all of Ω. First we show that f cannot be measurable, and second that measurable functions f can however approximate the requirement \frac{1}{2}(f(x) + f(T (x))) ∈ A_{x^{0}}.

If f were measurable, by Luzin’s Theorem, we should be able to approximate our function f in probability with continuous functions, meaning that for every ϵ > 0 there exists a continuous function g : {1, 2}^{Z} → [0, 1] (modulo 1) such that f and g differ only on a set of measure ϵ. Let ϵ be 1/100. Again by Luzin’s Theorem we know that there is a cylinder set E and a value r ∈ [0, 1] (modulo 1) such that within the set E the probability (conditioned on membership in E) that the value of f is further than ϵ from r is less than ϵ. Without loss of generality, we can assume that our cylinder set is defined by the choice of coordinates y^{−k}, …, y^{0}, …, y^{k−1} for some positive integer k. We define the value q (modulo 1) by it being the functional value of T^{−k}(x) (modulo 1) for any x with f(x) = r and define the value s to be the corresponding value of the T^{k}(x) (modulo 1). As long as x ∈ E is mapped to within ϵ of r, T^{−k}(x) and T^{k}(x) (modulo 1) will be mapped to within ϵ of q and s, respectively. The occurances of the cylinder set E in a typical orbit of T will be separated by many different sequences of intermediate values for the 0-coordinate. By our assumption, these seperating sequences must, with probability at least 1 − 2ϵ, connect values within ϵ of s to values within ϵ of q, an absurdity as long as ϵ is small compared to the distance between 1/3 and 2/3.

Looking at the same example, for any 0 < δ < 1/3 let us require instead that |\frac{1}{2}(f(x) + f(T (x))) − 1/3| ≤ δ (modulo 1) if x^{0} = 1 and |\frac{1}{2}(f(x) + f(T (x))) − 2/3| ≤ δ (modulo 1) if x^{0} = 2. Let N be larger than \frac{3}{δ}. Call an orbit typical if there are infinitely many points x with x^{0} = 2 and also infinitely many points x of the orbit such that (T^{n}(x))^{0} = 1 for all −N ≤ n ≤ N. The latter kind of point we call a center point. We will define a map f : Ω → [0, 1] (modulo 1) on the typical orbits in the following way. Every center point gets mapped to 1/3 (modulo 1). For every center point x let m(x) > N be the first number such that T^{m(x)+N}(x) is a center point and (T^{k}(x))^{0} = 2 for some k < m(x). (m(x) will be finite for all center points of typical orbits). For all points of the form y = T^{k}(x) for 0 ≤ k ≤ m(x), determine f(y) inductively according to the rule \frac{1}{2}(f(y) + f(T (y))) = 1/3 (modulo 1) if y^{0} = 1 and = 2/3 (modulo 1) if y^{0} = 2. For the row y = T^{m(x)}(x), T^{m(x)+1}(x), … T^{m(x)+N}(x) we define f so that |\frac{1}{2}(f(y)+f(T (y)))− 1/3| < δ (modulo 1) and f(T^{m(x)+N}(x)) = 1/3, (with T^{m(x)+N}(x) the next center point after T^{m(x)}(x)). We claim that these motions back to 1/3 can done in a deterministic and measurable way with respect to the starting point T^{m(x)}(x). Because the definition of f on the typical orbits can be broken down according to the distances to the next center points, the definition of f as restricted to the typical orbits would be measurable in character. But since almost all points belong to typical orbits, that would be sufficient for the measurability of f.

We believe that careful anaylsis of the example in Section 3 would reveal a similar mechanism to generate measurable ϵ-Bayesian equilibria for every positive ϵ, and we suspect that there exist measurable approximate Bayesian equilibria for all ergodic games played on Bernoulli single-shift spaces. On the other hand we see no such similar mechanism for getting measurable approximate Bayesian equilibria for games played on double-shift spaces or more exotic probability spaces with measure preserving transformations.

5 Conclusion: Zero-sum games

We are interested in zero-sum ergodic games because of the possibilities for violating conventional game theory. For the finite dimensional matrix games for which the original min-max theorem was proven (Von Neumann 1928), the value of the game is the expected payoff from all equilibrium strategies. Equilibrium strategies are also called optimal strategies, because if one exchanges the strategies in two pairs of equilibria, one obtains again an equilibrium.

Even if a zero-sum ergodic game does has measurable Bayesian equilibria, the non-measurable varieties can play havoc with the conventional understanding of value, expected payoff, equilibrium, and optimality. Let us look at a very simple example.

Let Ω be {a, b}^{Z} with the same belief structure as the example in Section 3, but with only two players, Player One and Player Two. We assume that there is only one payoff matrix, that corresponding to the game of matching pennies. Both players have only two moves, 0 and 1, and if the sum of their moves is even then Player One receives 1 and if this sum is odd than Player One receives −1. Let f^{j} : Ω → [0, 1] for j = 1, 2 represent the probability that Player j chooses the move 0.

We will consider two pairs of Bayesian equilibrium strategies for the players, (f_{1}^{1}, f_{1}^{2}) and (f_{2}^{1}, f_{2}^{2}). For both pairs the payoff will not be a measurable function on Ω, however for the first pair for each player there will be an expected payoff of 0 at all his pairs of states. For the second pair, however, Player Two will have an expected payoff of 0 at all his pairs of states, but the payoff to Player One will have no measurable interpretation. Exchanging these pairs of strategies will not create a new Bayesian equilibrium.

To define the pair (f_{1}^{1}, f_{1}^{2}) choose any doubly infinite x ∈ Ω and define f_{1}^{1}(x) = f_{1}^{2}(x) = 1, but also f_{1}^{1}(τ(x)) = f_{1}^{1}(σ ∘ τ(x)) = 0 and f_{1}^{2}(σ(x)) = f_{1}^{2}(τ ∘ σ(x)) = 0. Continue defining the strategies f_{1}^{1} and f_{1}^{2} on the cell containing x in an alternating way so that at all y in the cell we have f_{1}^{1}(y)+ f_{1}^{1}(τ(y)) = 1 and f_{1}^{2}(y) + f_{1}^{2}(σ(y)) = 1, with the values for f_{1}^{1} and f_{1}^{2} always either 0 or 1. This defines an equilibrium on the cell, and repeat this process for all the doubly infinite cells.

For x being any doubly infinite point with f_{1}^{1}(x) = f_{1}^{2}(x) = 1, for all points y = T^{k}x with k ≥ 1 define f_{2}^{2}(y) to be the same as f_{1}^{2}(y), but for all y = T^{−k}(x) with k ≥ 0 switch the values, meaning that f_{2}^{2}(y) + f_{1}^{2}(y) = 1.

For any y on this same cell, define f_{2}^{1} by f_{2}^{1}(y) + f_{1}^{1}(y) = 1. Notice that f_{2}^{1} and f_{2}^{2} are also in Bayesian equilibrium, but with the difference that for every doubly infinite cell there is one special pair of points considered possible by Player One, namely our chosen x and σ(x), where Player One expects a payoff of 1 instead of 0.

The pair (f_{1}^{1}, f_{2}^{2}) is not in Bayesian equilibrium, because Player One is very dissatisfied in his choice at the point x. One could object: Player One’s dissatifaction at only one point in the cell means that he is satisfied almost everywhere. This objection is flawed, for two reasons. First, since an adjacent point on a cell is evaluated to have a probability of one-half by some player, once the equlibrium property is destroyed at one point, it could be destroyed inductively for the entire containing cell. Second, since such behavior is repeated for almost all cells, the extreme dissatisfaction of Player One would not be limited to a set of measure zero. A set of points that intersect every cell in one and only one point is a non-measurable set, meaning that it has positive outer measure. It follows by the same argument that with the Bayesian equilibrium (f_{2}^{1}, f_{2}^{2}) there is no expected payoff for Player One.

One could try to define the value of a zero-sum ergodic game as some kind of limiting average payoff on the cells. Although the payoff function may not be measurable, perhaps this limiting average payoff is measurable and well behaved (e.g. the conclusion of the Birkhoff Ergodic Theorem without the conditions being satisfied). The problem with this approach is that it is uncertain what kind of interpretation should be given to such a limiting average. The measure preserving transformations in our situation do not represent the flow of time, the usual justification for ignoring finite subsets of a sequence. As argued above, we don’t understand why within a cell the players should consider arbitrary finite subsets to be insignificant.

Acknowledgements: The belief space of the first example, without the payoff matrices, is a variation of a belief space given in Simon (2000), but its precise formulation in this paper is due to Robert Aumann. The proof of Proposition 2 was based on a conversation with J.-F. Mertens. Discussions with Robert Aumann, Zbigniew Nitecki, and Benjamin Weiss were very helpful.

6 References

HARSANYI, J. C., (1967-8). “Games With Incomplete Information Played by Bayesian Players: Parts I, II, III”, Management Science 14 (3,5,7).

MERTENS, J.-F. and ZAMIR, S., (1985). “Formulation of Bayesian Analysis for Games with Incomplete Information”, International Journal of Game Theory, Vol. 14, Issue 1, pp. 1-29.

NASH, J., (1950). “Equilibrium Points in n-person Games”, Proceedings of the National Academy of Sciences, 36, pp. 48-49.

VON NEUMANN, J., (1928). “Zur Theorie der Gesellschaftsspiele”, Mathematische Annalen 100, pp. 295-320.

SIMON, R. (2000). “The Common Prior Assumption in Belief Spaces: An Example”, Discussion Paper 228, (December 2000), Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem.

SORIN, S. and ZAMIR, S. (1985). “A Two-Person Game with Lack of Information on One and One-Half Sides,” Mathematics of Operations Research 10, 17-23.

WALTERS, P., (1982). An Introduction to Ergodic Theory. Graduate Texts in Mathematics 79, Springer Verlag.