Anne and Bill play the following sequential game: at odd stages Anne chooses either 0 or 1, and at even stages Bill chooses either 0 or 1. This way they generate an infinite sequence of bits, which is the binary expansion of a real number x in the interval [0,1]. Who wins the game? Well, there is a subset W of [0,1], the winning set of Anne, which is known to the players in advance. If the real number x that they generated is in W, Anne wins. If it is outside W, Bill wins.
Suppose for example that W=[0,1/2]. Then, by choosing 0 at the first stage of the game, Anne guarantees a win. If, on the other hand, W is the union of the two intervals [0,1/4) and (1/2,3/4), then by choosing 0 at the second stage, Bill guarantees a win.
Zermelo’s Theorem guarantees that every finite two-player game with two outcomes: “player I wins” or “player II wins”, is determined: one of the players has a winning strategy. The game between Anne and Bill is not a finite game, and therefore Zermelo’s Theorem does not apply.
Gale and Stewart (1953) proved that if the set W is closed, then the game is determined. This result was significantly extended by Martin (1975), who proved that if W is Borel measurable then the game is determined.
Borel games are similar to the game described above between Anne and Bill, but instead of choosing a bit at every stage, Anne and Bill have some set of actions A available to them; at odd stages Anne chooses an action from A, and at even stages Bill chooses an action from A. The set A may be finite or infinite. When the set of actions A is not {0,1}, Anne’s winning set is a subset of A^∞.
In fact, it does not matter whether Anne and Bill have the same set of actions, or different sets of actions. Actually, the set of actions available to each of them may be history dependent. Also, the players need not alternate in choosing actions: the identity of the player who currently chooses the action may be history dependent as well. The result of Martin (1975) was proved to this general setup.
Up to now, the outcome of the game was either 1 (Anne wins) or -1 (Bill wins). However, we could think of general two-player zero-sum Borel games. Here the data of the game includes a payoff function u that assigns a real number u(p) to each play p (=infinite sequence of actions).
One game that falls into this class of games is the following: we are given a directed graph. The vertices of the graph are divided into four types: some vertices are “win vertices of Anne”, others are “win vertices of Bill”, yet others are “vertices controlled by Anne”, and the rest are “vertices controlled by Bill”. The game starts at one of the vertices, and moves between the vertices as follows: if the current vertex s is controlled by Anne, Anne chooses an outgoing edge from s, and the vertex at the end of the edge is the new vertex. If s is controlled by Bill, it is he who chooses an outgoing edge. If s is a winning vertex of one of the players, then that player is the winner, and the game ends. If the play never reaches a winning vertex, the game ends with a draw.
Martin’s (1975) result implies that if the payoff function u is measurable and bounded, then the game has a value. The argument is as follows: for every real number x denote by W(x) the set of all plays p where u(p) ≥ x. Because u is Borel measurable, the set W(x) is a Borel set. By Martin, the game G(x) with winning set W(x) is determined for every x. If Anne can guarantee a win in G(x), it means that she can guarantee a payoff of at least x in the original game; if Bill can guarantee a win in G(x), it means that he can guarantee a payoff smaller than x in the original game. Because u is bounded, for x=∞ Bill can guarantee a win in the game G(x), and for x=-∞ Anne can guarantee a win in the game G(x). Let then x* be the maximal x for which the game G(x) is determined for Anne. Then x* is the value of the original game.
So, every two-player zero-sum Borel game has a value? What about equilibria in multi-player Borel games? This will be discussed in a subsequent post.