The Axiom of Choice implies that there exist infinite games in which neither player has a winning strategy.  Thus, the Axiom of Choice is incompatible with the [Axiom of Determinacy](http://en.wikipedia.org/wiki/Axiom_of_determinacy).  An example of a game where neither player has a winning strategy is the following (caveat: I'm not a set-theorist).

The *game* is a subset $G \subset [0,1]$ of real numbers.  At stage 1, player 1 chooses a bit which is either 0 or 1.  At stage 2, player 2 (knowing player 1's choices so far) chooses another bit.  The players then repeat.  After $\omega$ steps, they have constructed a real number $g \in [0,1]$ where the odd bits of $g$ (in binary) are given by player 1's choices and the even bits of $g$ are given by player 2's choices.  Player 1 wins if $g \in G$, and player 2 wins if $g \notin G$.  

Regarding the question that inspired the question, I've had a look at the paper (it's available on Springerlink).  I'm convinced that $L$ does have a winning strategy.  So, that particular game *is* determined.