Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The determinacy of infinite games with eventual perfect monitoring

Author: Eran Shmaya
Journal: Proc. Amer. Math. Soc. 139 (2011), 3665-3678
MSC (2010): Primary 91A15, 03E75; Secondary 03E15, 91A60
Published electronically: May 24, 2011
MathSciNet review: 2813396
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. David Blackwell.
    Infinite $ G_\delta$ games with imperfect information.
    Zastosowania Matematyki (Applicationes Mathematicae), 10:99-101, 1969. MR 0243837 (39:5158)
  • 2. David Blackwell.
    Operator solution of infinite $ G_\delta$ games of imperfect information.
    In Theodore W. Anderson, Krishna B. Athreya, and Donald L. Igelhart, editors, Probability, Statistics, and Mathematics, pages 83-87. Academic Press, Boston, MA, 1989. MR 1031279 (91d:90107)
  • 3. Ky Fan.
    Minimax theorems.
    Proceedings of the National Academy of Sciences U.S.A., 39:42-47, 1953. MR 0055678 (14:1109f)
  • 4. David Gale and F.M. Stewart.
    Infinite Games with Perfect Information.
    Annals of Mathematics Studies, 28, Princeton Univ. Press, Princeton, NJ, 1953. MR 0054922 (14:999b)
  • 5. Torgny Lindvall.
    Lectures on the Coupling Method.
    Wiley, New York, 1992. MR 1180522 (94c:60002)
  • 6. Ashok P. Maitra, Roger A. Purves, and William D. Sudderth.
    Approximation theorems for gambling problems and stochastic games.
    Lecture Notes in Economics and Mathematical Systems, 389:114-132, Springer, Berlin, 1992. MR 1228669 (94g:90189)
  • 7. Ashok P. Maitra and William D. Sudderth.
    Finitely additive stochastic games with Borel measurable payoffs.
    International Journal of Game Theory, 27(2):257-267, July 1998. MR 1645524 (2000d:91020)
  • 8. Donald A. Martin.
    Borel determinacy.
    Annals of Mathematics (2), 102(2):363-371, 1975. MR 0403976 (53:7785)
  • 9. Donald A. Martin.
    The determinacy of Blackwell games.
    Journal of Symbolic Logic, 63(4):1565-1581, December 1998. MR 1665779 (2000d:03118)
  • 10. Wojciech Olszewski and Alvaro Sandroni.
    A nonmanipulable test.
    Ann. Statist., 37(2):1013-1039, 2009. MR 2502659 (2010c:62011)
  • 11. Dinah Rosenberg, Eilon Solan, and Nicolas Vieille.
    The MaxMin value of stochastic games with imperfect monitoring.
    Internat. J. Game Theory, 32(1):133-150, 2003.
    Special anniversary issue. Part 2. MR 2046684 (2005f:91026)
  • 12. Herbert Scarf and L.S. Shapley.
    Games with Partial Information.
    Annals of Mathematics Studies, 39:213-229, Princeton, Univ. Press, Princeton, NJ, 1957. MR 0094260 (20:779)
  • 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.
    Springer, Berlin-Heidelberg, 2002. MR 1890574 (2002m:91001)
  • 15. Marco R. Vervoort.
    Blackwell games.
    In Thomas S. Ferguson, Lloyd S. Shapley, and James B. MacQueen, editors, Statistics, Probability, and Game Theory, pages 369-390. Institute of Mathematical Statistics, Hayward, California, 1996. MR 1481790 (98j:90100)
  • 16. John von Neumann and Oskar Morgenstern.
    Theory of Games and Economic Behavior.
    Princeton Univ. Press, Princeton, NJ, 2004.
    Reprint of the 1980 edition, Princeton Univ. Press, Princeton, NJ. MR 0565457.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 91A15, 03E75, 03E15, 91A60

Retrieve articles in all journals with MSC (2010): 91A15, 03E75, 03E15, 91A60

Additional Information

Eran Shmaya
Affiliation: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208

Keywords: Infinite games, determinacy, stochastic games, imperfect monitoring
Received by editor(s): July 5, 2010
Published electronically: May 24, 2011
Additional Notes: I thank the anonymous referee for helpful suggestions and comments, and also thank Chris Chambers, Tzachi Gilboa, John Levy, Ehud Lehrer, Wojciech Olszewski, Phil Reny, Eilon Solan, Bill Sudderth and Rakesh Vohra.
Communicated by: Ken Ono
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society