Games with Infinitely Many Moves and Slightly Imperfect Information
David Blackwell · 1997
D. A. Martin in 1975 showed that all Borel Games with perfect information are determined. Question: are all Borel games with slightly imperfect information determined? Let A , B be finite nonempty sets, let C = A x B, and let W be the set of all infinite sequences w = ﹛c 1 , C 2 ,…﹜ from C. Any subset S of W defines a game G(S), whose n-th move, for n = 1, 2, …, is played as follows: Player I chooses A n ∈ A and, simultaneously, Player II chooses b n ∈ B. Each player is then told the other's choice, so that they both know c n — (a n ,b n ). Player I wins G(S) just if the play w — ﹛c 1 , C 2 ,…﹜ is in S. We say that G(S) is determined if there is a number υ such that, for every ϵ > 0, (a) Player I has a (random) strategy that wins for him with probability at least υ — ϵ against every strategy of Player II, and (b) Player II has a (random) strategy that restricts his probability of loss to at most υ + ϵ against every strategy of Player I. If S is finitary, i.e., depends on only finitely many coordinates of w, then G(S) is a finite game, and the von Neumann minimax theorem says that G(S) is determined. If S is open, i.e., the union of countably many finitary sets, then it is wellknown, and not hard to see, that G(S) is determined (and that Player II has a good strategy).