We know that, under AC, there exists a game in which two players play finite numbers and neither one has winning strategy. There are also such undetermined games when we consider players playing countable ordinals, and AC is not needed this time. However, both of these types if games are proven to exist nonconstructively.
I've been wondering - can we exhibit a simple example of an infinite game without ties where neither player has a winning strategy? I'd want a specific definition not involving choice, and, if possible, a game in which players alternate discrete steps, not continuous games.
Thanks in advance!
Edit: Clarifying what I mean with no ties: I consider the finished game a tie if rules don't specify which player is a winner. In game suggested by Ross in comments, if I understand it correctly, every string of bits which doesn't stabilize eventually is a tie, because then there is no tail of eventually the same bits and no player is a winner.
There is no such example (but see below). Assuming consistency of a Woodin cardinal, it is consistent with ZFC that there is no undetermined (two-player perfect information length ω) game on integers with ordinal definable payoff. Also, assuming infinitely many Woodin cardinals and a measurable above them, every (length ω) game on integers with the payoff set in L(R) is determined.
On the other hand,
* In the constructible universe L, there is an undetermined $Σ^1_1$ game (i.e. the payoff is $Σ^1_1$).
* There is a generic extension of V with an undetermined $Σ^2_1$ game, and a generic extension of V satisfying GCH with an undetermined $Σ^2_2$ game.
* If we do not impose restrictions on the type of moves, an undetermined game can be defined as follows: The first player wins iff the first move of the first player is a set of real numbers coding an undetermined game G on integers, and the remaining moves form a winning play according to G.
* Consistency of determinacy for length ω games on ordinals (i.e. moves are ordinals) and ordinal definable payoff is an open question.