The determinacy of infinite games with eventual perfect monitoring

Shmaya, Eran

doi:10.1090/S0002-9939-2011-10987-0

The determinacy of infinite games with eventual perfect monitoring
HTML articles powered by AMS MathViewer

by Eran Shmaya PDF

Proc. Amer. Math. Soc. 139 (2011), 3665-3678 Request permission

Abstract:

An infinite two-player zero-sum game with a Borel winning set, in which the opponent’s actions are monitored eventually but not necessarily immediately after they are played, is determined. The proof relies on a representation of the game as a stochastic game with perfect information, in which Chance operates as a delegate for the players and performs the randomizations for them, and on Martin’s Theorem about the determinacy of such games.

References

D. Blackwell, Infinite $G_{\delta }$-games with imperfect information, Zastos. Mat. 10 (1969), 99–101. MR 243837
David Blackwell, Operator solution of infinite $G_\delta$ games of imperfect information, Probability, statistics, and mathematics, Academic Press, Boston, MA, 1989, pp. 83–87. MR 1031279
Ky Fan, Minimax theorems, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 42–47. MR 55678, DOI 10.1073/pnas.39.1.42
David Gale and F. M. Stewart, Infinite games with perfect information, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N.J., 1953, pp. 245–266. MR 0054922
Torgny Lindvall, Lectures on the coupling method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1992. A Wiley-Interscience Publication. MR 1180522
A. Maitra, R. Purves, and W. Sudderth, Approximation theorems for gambling problems and stochastic games, Game theory and economic applications (New Delhi, 1990) Lecture Notes in Econom. and Math. Systems, vol. 389, Springer, Berlin, 1992, pp. 114–132. MR 1228669
A. Maitra and W. Sudderth, Finitely additive stochastic games with Borel measurable payoffs, Internat. J. Game Theory 27 (1998), no. 2, 257–267. MR 1645524, DOI 10.1007/s001820050071
Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
Donald A. Martin, The determinacy of Blackwell games, J. Symbolic Logic 63 (1998), no. 4, 1565–1581. MR 1665779, DOI 10.2307/2586667
Wojciech Olszewski and Alvaro Sandroni, A nonmanipulable test, Ann. Statist. 37 (2009), no. 2, 1013–1039. MR 2502659, DOI 10.1214/08-AOS597
Dinah Rosenberg, Eilon Solan, and Nicolas Vieille, The MaxMin value of stochastic games with imperfect monitoring, Internat. J. Game Theory 32 (2003), no. 1, 133–150. Special anniversary issue. Part 2. MR 2046684, DOI 10.1007/s001820300150
H. E. Scarf and L. S. Shapley, Games with partial information, Contributions to the theory of games, vol. 3, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N.J., 1957, pp. 213–229. MR 0094260
Eran Shmaya. Many inspections are manipulable. Theoretical Economics, 3(3):376–382, 2008.
Sylvain Sorin, A first course on zero-sum repeated games, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 37, Springer-Verlag, Berlin, 2002. MR 1890574
Marco R. Vervoort, Blackwell games, Statistics, probability and game theory, IMS Lecture Notes Monogr. Ser., vol. 30, Inst. Math. Statist., Hayward, CA, 1996, pp. 369–390. MR 1481790, DOI 10.1214/lnms/1215453583
John von Neumann and Oskar Morgenstern, Theory of games and economic behavior, 3rd ed., Princeton University Press, Princeton, N.J., 1980. MR 565457