×

The determinacy of infinite games with eventual perfect monitoring. (English) Zbl 1229.91057

An infinite two-player zero-sum game is considered where the players take turns choosing actions. Before choosing at stage \(n\), the player whose turn it is to move receives some information about the actions at previous stages. The opponent’s actions are monitored eventually, but not necessarily after they are played. Player 1 wins the game if the infinite history of actions lies in a given Borel set. It is shown that the game 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.

MSC:

91A15 Stochastic games, stochastic differential games
03E75 Applications of set theory
03E15 Descriptive set theory
91A60 Probabilistic games; gambling
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Blackwell, Infinite \?_{\?}-games with imperfect information, Zastos. Mat. 10 (1969), 99 – 101. · Zbl 0232.90068
[2] David Blackwell, Operator solution of infinite \?_{\?} games of imperfect information, Probability, statistics, and mathematics, Academic Press, Boston, MA, 1989, pp. 83 – 87. · Zbl 0696.90094
[3] Ky Fan, Minimax theorems, Proc. Nat. Acad. Sci. U. S. A. 39 (1953), 42 – 47. · Zbl 0050.06501
[4] 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. · Zbl 0050.14305
[5] 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. · Zbl 0850.60019
[6] 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. · Zbl 0788.90093
[7] A. Maitra and W. Sudderth, Finitely additive stochastic games with Borel measurable payoffs, Internat. J. Game Theory 27 (1998), no. 2, 257 – 267. · Zbl 0947.91013 · doi:10.1007/s001820050071
[8] Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363 – 371. · Zbl 0336.02049 · doi:10.2307/1971035
[9] Donald A. Martin, The determinacy of Blackwell games, J. Symbolic Logic 63 (1998), no. 4, 1565 – 1581. · Zbl 0926.03071 · doi:10.2307/2586667
[10] Wojciech Olszewski and Alvaro Sandroni, A nonmanipulable test, Ann. Statist. 37 (2009), no. 2, 1013 – 1039. · Zbl 1162.62001 · doi:10.1214/08-AOS597
[11] 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. · Zbl 1101.91309 · doi:10.1007/s001820300150
[12] 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. · Zbl 0078.33101
[13] Eran Shmaya. Many inspections are manipulable. Theoretical Economics, 3(3):376-382, 2008.
[14] Sylvain Sorin, A first course on zero-sum repeated games, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 37, Springer-Verlag, Berlin, 2002. · Zbl 1005.91019
[15] 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. · doi:10.1214/lnms/1215453583
[16] John von Neumann and Oskar Morgenstern, Theory of games and economic behavior, 3rd ed., Princeton University Press, Princeton, N.J., 1980. · Zbl 0452.90092
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.