Determinacy of Infinite Games
J.M. Dijkstra (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Klaas Pieter Hart – Mentor (TU Delft - Analysis)
Cor Kraaikamp – Graduation committee member (TU Delft - Applied Probability)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This paper introduces the notion of infinite games, i.e., games in which two players take turns playing moves ad infinitum, so that player I wins if the sequence of moves is in a predetermined payoff set. Theorems are then provided about whether a player in such games can have a winning strategy. The first theorem, Gale-Stewart, shows that games with an open or closed payoff set are determined, i.e., one of the players has a winning strategy. The second theorem, Martin, shows moreover that any game with a Borel payoff set is determined. Finally, the paper presents some results that follow from these theorems, for instance that the Continuum Hypothesis holds for all Borel sets. This paper only requires knowledge of very basic set theory and will clearly define any new or otherwise unfamiliar concepts.