Determinacy

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness". The games studied in set theory are usually Gale–Stewart games—two-player games of perfect information in which the players make an infinite sequence of moves and there are no draws. The field of game theory studies more general kinds of games, including games with draws such as tic-tac-toe, chess, or infinite chess, or games with imperfect information such as poker. The first sort of game we shall consider is the two-player game of perfect information of length ω, in which the players play natural numbers. These games are often called Gale–Stewart games. In this sort of game there are two players, often named I and II, who take turns playing natural numbers, with I going first. They play "forever"; that is, their plays are indexed by the natural numbers. When they're finished, a predetermined condition decides which player won. This condition need not be specified by any definable rule; it may simply be an arbitrary (infinitely long) lookup table saying who has won given a particular sequence of plays. More formally, consider a subset A of Baire space; recall that the latter consists of all ω-sequences of natural numbers. Then in the game GA, I plays a natural number a0, then II plays a1, then I plays a2, and so on. Then I wins the game if and only if and otherwise II wins. A is then called the payoff set of GA. It is assumed that each player can see all moves preceding each of his moves, and also knows the winning condition. Informally, a strategy for a player is a way of playing in which his plays are entirely determined by the foregoing plays.