Games that never begin Games that never end play a major role in descriptive set theory.  See for example Kechris' GTM.  
Question: Does there exist a literature concerning games that never begin?
I have in mind two players, Alice and Bob, making alternate selections from ${\Bbb N}$,  their moves indexed by increasing non-positive integers, the game terminating when Bob plays his move 0.
As for payoff sets and strategies, define these as for games that never end, mutatis mutandis.  
One major difference: a pair of strategies, one for Alice, one for Bob no longer determines a unique run of the game, but rather now a set of runs, possibly empty.  Even so one may still say that Alice's strategy beats Bob's if every compatible run of one strategy against the other belongs to the payoff set.
Another major difference involves the set-theoretic size of strategies.  Now Alice and Bob play every move in the light of infinite history.  So size considerations mean that certain familiar arguments, for example non-determined games from the axiom of choice, don't work in any obvious way?
Question: What payoff sets give determined games that never begin?
Edits:  By the cold light of morning, I see that I abused the words "mutatis mutandis."  A la Kechris, Alice's strategy beats Bob's if the the unique run of the game falls in the payoff set.  What I had in mind here was that Alice's strategy beats Bob's
if the run set (consistent with both strategies) is a subset of the payoff set.  Joel David Hamkins' clever answer remains trenchant, only now with the import that Alice always wins by playing a strategy with empty run sets regardless of Bob's strategy.
Joel's Alice needs an infinite memory, but if her strategy at each move consists of increasing her previous move by 1, that also necessarily produces an empty run set regardless of Bob's choice.
Possible fix 1  Alice must play an engaged strategy, a strategy that produces a nonempty run set against at least one strategy of Bob's.
Possible fix 2  The residual game at any turn only has a finite future, so one player has a winning strategy from that point on.  Call a strategy rational if it requires the player to play a winning move in the residual game whenever one exists.  Call a strategy strongly rational if it requires the player to play the least possible winning move whenever one exists.  To avoid easy disengaged strategies that don't even reference the payoff set, insist on rational, or even strongly rational strategies.
Possible fix 3  Combine the previous fixes. 
 A: This is a very nice question.
Observation 1. Some strategies have no play that accords
with them. Consequently, such a strategy for Alice is winning in
any game, since every play in conformance with it is (vacuously)
in her payoff set. (Similar strategies exist for Bob.)
Proof: Here, I consider a strategy to be a function mapping a game
 position to the number to be played. A game position is an almost-infinite sequence, with only the final finitely many digits
 remaining unspecified. Consider the strategy for Alice: faced with a
game position of prior play, she inspects her own previous moves;
if infinitely many of them were $0$, she plays $1$, and otherwise
she plays $0$. There can be no play that accords with this
strategy, since if the play shows Alice to have played infinitely
many $0$s, then she should have been playing $1$ at any one of
them; and conversely, if she had played only finitely many $0$s,
then she should have started playing $0$ much earlier than she
did.
Another instance is the always-add-one strategy you mentioned in response to
this, and I find that to be quite elegant. If Alice plays so as to
 always add one to her previous move, then clearly she cannot have
 done this forever. This strategy makes sense in games with natural
 number plays, but actually one can use the same idea for binary
 games, where the players play $0$ or $1$, by having Alice play a (strictly longer) sequence of $n$ consecutive $1$s on her next $n$ moves (unless playing time runs out).
An earlier answer of mine (see edit history) contains another argument, using
diagonalization and the axiom of choice. QED
Thus, it seems that Alice wins every game, according to the
definition you have provided. But I prefer to say that both
players have winning strategies, because they both have strategies
such that any play that conforms with them is in their respective
payoff sets.
Observation 2. If one modifies the definition of strategy
so that one's moves depend only on the opponent's moves in a
position, then not every pair of strategies for Alice and Bob have
a conforming play.
Proof: Consider the strategy for Bob that simply copies Alice's
previous move, and the strategy for Alice that plays $1$ if and
only if all prior moves of Bob were $0$. There can be no
conforming play for this pair of strategies, since if Bob was
previously playing all zeros up to a point, then Alice should have
played $1$ much earlier, and if not, then Alice must have played
$1$ without cause. QED
Observation 3. There is a game for which both players have
rational engaged winning strategies.
Proof: Consider the game where Alice wins every play having only
finitely many $1$s. The always-play-$3$ strategy is a rational,
engaged winning strategy for Bob, since it has conforming plays,
every conforming play is a win for Bob, and from any position, it makes
a move that is winning in the finitely remaining game. Meanwhile,
Alice also has a winning strategy: to play $0$, if almost all
previous moves were $0$, and otherwise add one to her previous
move. This strategy is engaged, since Bob might have played $0$s,
and it is strongly rational for Alice, since she is playing $0$s
whenever she is in a winning position; and it is winning for
Alice, since the only conforming plays are almost all $0$ and
hence wins for Alice. QED
Theorem. (AC) There is a game for which neither player has
winning rational engaged strategy.
Proof: This theorem will work regardless of whether one allows the
strategies to depend on the full position or only on the
opponent's prior moves. Let's say that two sequences are almost
equal if they differ on only finitely many values. Using the
axiom of choice, we may select a representative from each
almost-equality class. Let $A$ be the game where Alice wins a
play, if the play deviates from the representative of its class
for the first time on her turn, and Bob wins if the play deviates
for the first time on his turn, or not at all. The thing to notice
is that if $s$ is a play of the game, then both Alice and Bob had
incentive to have played differently earlier, for by making a much
earlier different move, they would have caused a much earlier
deviation in the play, causing them to have won earlier. Indeed,
it was irrational of them not to have made the earlier move, since
their opponent might have won on the next move. Thus, there can be
no rational strategy for either player resulting in such a play.
So neither player has a rational engaged strategy. QED
Define that a set is a tail set if it is invariant under finite
modification. These are precisely the sets that are saturated with
respect to the almost-equality relation.
Observation 4. In every game whose payoff set is a tail
set, every strategy is rational.
Proof: The point is that when you are playing a game whose payoff
set is a tail set, then the game is already won or lost when any
particular move is made, since the tail equivalence class is
already determined. So in such a game, no particular individual move affects the outcome of the game.
QED
Finally, let me mention that your game concept reminds me of the
archeological model of infinite time computation, where the
infinite computation grows out of an infinite past rather than
stretching into an infinite future. The idea is that, having
opened up a chamber under the pyramid, you find a Turing machine,
still running, with an infinite tape all filled out and with all
indications that it has been running from time stretching
infinitely into the past. What kind of problems are decidable in
principle by such machines? For an interesting theory, assume we
may find pyramids corresponding to any given program.
A: As a supplement to Joel's answer, you may want to look at this nice paper of Bollobas, Leader, and Walters concerning continuous games.  As a starting point they discuss the classical Lion and Man game introduced by Rado.  In this game there is a lion chasing a man inside the unit disk.  Both have identical maximum speeds.  The lion wins if he catches the man, and the man wins if he is never caught by the lion.  If the lion chooses to always run directly toward the man, then he will get arbitrarily close to the man, but never catch him.  On the other hand, if the lion instead moves at top speed so that he is always on the radial vector from the centre to the man, it was 'clear' that this was a winning strategy.  Proof: without loss of generality, the man stays on the boundary of the disk.  However, in 1952, Besicovitch exhibited an ingenious winning strategy for man!  Thus, staying on the boundary is with loss of generality for man.  Nonetheless, one can ask the perplexing question if lion also has a winning strategy?  In this particular game, it turns out that the answer is no.  But by changing the metric space, Bollobas, Leader, and Walters prove that there are games in a similar vein where both lion and man have winning strategies!  
A: A slightly more tangential answer, but one which I hope is still useful: there is a well-known connection between infinite games and infintary logic. In the usual context of games with no ending, determinacy principles can be viewed as versions of De Morgan's Law for certain infinitary sentences: for $\Gamma$ a pointclass, $\Gamma$-Det is the statement that each of the disjunctions $$ \forall x_0\exists x_1\forall x_2\exists x_3 . . . . ((x_0, x_1, x_2, x_3, . . . )\not\in X) \vee \exists x_0\forall x_1\exists x_2\forall x_3 . . . ((x_0, x_1, x_2, x_3, . . . ) \in X)$$ for $X\in\Gamma$ is true. Similarly, games with no beginnings should be connected to the semantics of infinitary sentences with ill-founded strings of quantifiers. In the paper "On languages with non-homogeneous strings of quantifiers" (https://doi.org/10.1007/BF02771553), Saharon Shelah did some work on the behavior of such sentences (his semantics for these sentences is in terms of Skolem functions; it appears to avoid Joel's observation by requiring that a strategy for one player look only at moves made by the other player, but I'm not certain of this - please correct me if I'm wrong!). The main result is that "every linear string of quantifiers can be replaced by a well-ordered sequence of quantifiers," which goes some way towards reducing the study of beginningless games to the study of endless games.
However, it should be noted that non-linear "strings" (posets?) of quantifiers have also been studied (cf. "Dependence Logic"), and I have no idea what happens if we look at branching, ill-founded collections of quantifiers, or if this has been looked at in the past (although I vaguely recall a paper by either Hintikka or Vaananen on the subject, but I can't find it, so maybe it doesn't exist). I also don't know a good game-theoretic interpretation of such collections of quantifiers, but I imagine one would not be too hard to come by.
