Hostname: page-component-8448b6f56d-tj2md Total loading time: 0 Render date: 2024-04-17T21:52:20.011Z Has data issue: false hasContentIssue false
  • English
  • Français

The determinacy of Blackwell games

Published online by Cambridge University Press:  12 March 2014

Donald A. Martin
Donald A. Martin*
Affiliation:
Department of Mathematics, University of California, Los Angeles, 405 Hilgard Avenue, Los Angeles, California 90095, USA. E-mail:dam@math.ucla.edu
Get access Rights & Permissions [Opens in a new window]

Extract

Games of infinite length and perfect information have been studied for many years. There are numerous determinacy results for these games, and there is a wide body of work on consequences of their determinacy.

Except for games with very special payoff functions, games of infinite length and imperfect information have been little studied. In 1969, David Blackwell [1] introduced a class of such games and proved a determinacy theorem for a subclass. During the intervening time, there has not been much progress in proving the determinacy of Blackwell's games. Orkin [17] extended Blackwell's result to a slightly wider class. Blackwell [2] found a new proof of his own result. Maitra and Sudderth [9, 10] improved Blackwell's result in a different direction from that of Orkin and also generalized to the case of stochastic games. Recently Vervoort [18] has obtained a substantial improvement. Nevertheless, almost all the basic questions have remained open.

In this paper we associate with each Blackwell game a family of perfect information games, and we show that the (mixed strategy) determinacy of the former follows from the (pure strategy) determinacy of the latter. The complexity of the payoff function for the Blackwell game is approximately the same as the complexity of the payoff sets for the perfect information games. In particular, this means that the determinacy of Blackwell games with Borel measurable payoff functions follows from the known determinacy of perfect information games with Borel payoff sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 4 , December 1998 , pp. 1565 - 1581
Copyright
Copyright © Association for Symbolic Logic 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Blackwell, David, Infinite Gδ games with imperfect information, Matematwyki Applications Mathematicae, vol. 10 (1969), pp. 99–101, Hugo Steinhaus Jubilee Volume.Google Scholar
[2] Blackwell, David, Operator solution of infinite Gδ games of imperfect information, Probability, statistics, and mathematics: Papers in honor of S. Karlin (Anderson, T. W., Athreya, K. B., and Iglehart, D. L., editors), Academic Press, New York, 1989, pp. 85–101.Google Scholar
[3] Davis, Morton, Infinite games of perfect information, Advances in game theory (Dresher, Melvin, Shapley, Lloyd S., and Tucker, Alan W., editors), Annals of Mathematics Studies #52, Princeton University Press, Princeton, 1964, pp. 85–101.Google Scholar
[4] Friedman, Harvey M., Higher set theory and mathematical practice, Annals of Mathematical Logic, vol. 2 (1971), pp. 325–357.CrossRefGoogle Scholar
[5] Gödel, Kurt F., The consistency of the axiom of choice and the generalized continuum-hypothesis, Proceedings of the National Academy of Science USA, vol. 24 (1938), pp. 556–557.CrossRefGoogle ScholarPubMed
[6] Kechris, Alexander S., Classical descriptive set theory, Springer-Verlag, New York, 1994.Google Scholar
[7] Maitra, A., Purves, R., and Sudderth, W, Approximation theorems for gambling problems and stochastic games, Game theory and economic applications (Dutta, B., Mookherjee, D., Parthasarathy, T., Raghavan, T. E. S., Ray, D., and Tijs, S., editors), Springer-Verlag, Berlin, 1991, Proceedings of conference in New Delhi, 12 1990, pp. 114–132.Google Scholar
[8] Maitra, A. and Sudderth, W., Finitely additive stochastic games with borel measurable payoffs, To appear.Google Scholar
[9] Maitra, A. and Sudderth, W., An operator solution of stochastic games, Israel Journal of Mathematics, vol. 78 (1992), pp. 33–49.CrossRefGoogle Scholar
[10] Maitra, A. and Sudderth, W., Borel stochastic games with lim sup payoff, Annals of Probability, vol. 21 (1993), pp. 861–885.CrossRefGoogle Scholar
[11] Martin, Donald A., Measurable cardinals and analytic games, Fundamenta Mathematical, vol. 66 (1970), pp. 287–291.Google Scholar
[12] Martin, Donald A., Borel determinacy, Annals of Mathematics, vol. 102 (1975), pp. 363–371.CrossRefGoogle Scholar
[13] Martin, Donald A., A purely inductive proof of Borel determinacy, Recursion theory (Providence) (Nerode, Anil and Shore, Richard A., editors), Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, 1985, pp. 303–308.CrossRefGoogle Scholar
[14] Martin, Donald A., An extension of Borel determinacy, Annals of Pure and Applied Logic, vol. 49 (1990), pp. 279–293.Google Scholar
[15] Martin, Donald A. and Steel, John R., A proof of projective determinacy, Journal of the American Mathematical Society, vol. 2 (1989), pp. 71–125.Google Scholar
[16] Neeman, Itay, Optimal proofs of determinacy, Bulletin of Symbolic Logic, vol. 1 (1995), pp. 327–339.Google Scholar
[17] Orkin, M., Infinite games with imperfect information, Transactions of the American Mathematical Society, vol. 171 (1972), pp. 501–507.Google Scholar
[18] Vervoort, Marco R., Blackwell games, Statistics, probability, and game theory: Papers in honor of David Blackwell (Ferguson, Thomas, Shapley, Lloyd, and MacQueen, James, editors), IMS Lecture Notes-Monograph Series, vol. 30, Institute of Mathematical Statistics, 1996, pp. 369–390.CrossRefGoogle Scholar
[19] von Neumann, John, Zur Theorie der Gesellschaftsspiele, Mathemathische Annalen, vol. 100 (1928), pp. 295–320.Google Scholar
[20] Woodin, W. Hugh, Supercompact cardinals, sets of reals and weakly homogeneous trees, Proceedings of the National Academy of Sciences USA, vol. 85 (1988), pp. 6587–6591.Google Scholar