×

The strength of Blackwell determinacy. (English) Zbl 1063.03033

Games of slightly imperfect information or Blackwell games are two-player games very close to Gale-Stewart games: the players play infinitely many rounds of simultaneous moves (in the Gale-Stewart case, Player I will have to reveal his or her move first in each round). These games have been investigated by D. Blackwell [Zastosow. Mat., Appl. Math. 10, 99–101 (1969; Zbl 0232.90068)], M. Orkin [Trans. Am. Math. Soc. 171, 501–507 (1972; Zbl 0296.90051)], A. Maitra and W. Sudderth [Isr. J. Math. 78, 33–49 (1992; Zbl 0785.90107)], and M. Vervoort [Doctoraalscriptie, Univ. Amsterdam (1995)] in the low levels of the Borel hierarchy. D. A. Martin [J. Symb. Log. 63, 1565–1581 (1998; Zbl 0926.03071)] proved that the determinacy of Blackwell games can be reduced to the determinacy of Gale-Stewart games (in particular, Borel Blackwell determinacy is a \(\text{ZFC}\) theorem), and conjectured that for boldface pointclasses \({\boldsymbol\Gamma}\) the determinacy of all \(\boldsymbol{\Gamma}\) games \(\text{Det}(\boldsymbol{\Gamma})\) and the Blackwell determinacy of all \(\boldsymbol{\Gamma}\) games \(\text{Bl}\text{-Det}(\boldsymbol{\Gamma})\) are equivalent. Martin’s conjecture on Blackwell games is still open and is currently the most important open problem in the set theory of imperfect information games. In this momentous paper, the authors prove many of the instances of Martin’s conjecture, in particular the case \(\boldsymbol{\Gamma} = \mathbf{L}(\mathbb{R})\cap\wp(\mathbb{R})\), i.e., they prove the equivalence of \(\text{Bl}\text{-AD}^{\mathbf{L}(\mathbb{R})}\) and \(\text{AD}^{\mathbf{L}(\mathbb{R})}\). This allows them to derive the equiconsistency of \(\text{Bl}\text{-AD}\) and \(\text{AD}\) as a corollary. Their proof has two important components. The first component is called the Zero-One Lemma for perfect information games played with mixed strategies. Both the Zero-One Lemma (Lemma 3.7) and the Strong Zero-One Lemma (Lemma 3.10) are useful tools in studying Blackwell games that have been used by the reviewer [Pac. J. Math. 214, 335–358 (2004; Zbl 1072.03032)] to derive combinatorial consequences from \(\text{Bl}\text{-AD}\). The Zero-One Lemma had been announced by Martin, but in 1999 a gap was found in its proof. This gap was fixed in early 2000 by Vervoort (who provided Lemma 3.4). The second component is a technique of constructing pure optimal strategies from mixed optimal strategies in the presence of scales (by adapting the ideas of the 3rd Periodicity Theorem). This result was announced by Neeman in 1999. Although the results of this paper form a substantial step forward in understanding the relationship between determinacy and Blackwell determinacy, fascinating open questions remain, the most vexing among them being the equivalence of \(\text{Bl}\text{-AD}\) and \(\text{AD}\). Another open question is the equivalence at the odd projective levels \(\boldsymbol{\Pi}^1_{2n+1}\) (except for \(n=0\) where the equivalence was proved by Tony Martin).

MSC:

03E15 Descriptive set theory
03E60 Determinacy principles
91A44 Games involving topology, set theory, or logic
PDF BibTeX XML Cite
Full Text: DOI Euclid

References:

[1] Alexander Kechris Classical descriptive set theory , Graduate Texts in Mathematics, vol. 156, Springer-Verlag,1995. · Zbl 0819.04002
[2] Alexander Kechris and Robert Solovay On the relative consistency strength of determinacy hypothesis , Transactions of the American Mathematical Society , vol. 290 (1985), pp. 179–211. · Zbl 0586.03045
[3] Alexander Kechris and Hugh Woodin Equivalence of partition properties and determinacy , Proceedings of the National Academy of Sciences USA , vol. 80 (1983), pp. 1783–1786. · Zbl 0523.03035
[4] Benedikt Loewe Blackwell Determinacy , Ph.D. thesis , Humboldt–Universität zu Berlin,2001.
[5] Donald A. Martin The Determinacy of Blackwell games , Journal of Symbolic Logic, vol. 63 (1998), pp. 1565–1582. JSTOR: · Zbl 0926.03071
[6] Yiannis N. Moschovakis Descriptive set theory , Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland, Amsterdam,1980. · Zbl 0433.03025
[7] John Steel Scales in \(\Ll[\R]\) , Cabal seminar 1979–81 , Lecture Notes in Mathematics, vol. 1019, Springer,1983, pp. 107–156.
[8] Marco Vervoort Blackwell games , Statistics, probability, and game theory: Papers in honor of David Blackwell (T.S. Ferguson, L.S. Shapley, and J.B. MacQueen, editors), Institute of Mathematical Statistics,1996, pp. 369–390.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.