`At every day a player takes an action’. This is the starting point of many models of repeated interaction. We let time run to infinity to reflect the fact that players don’t have in mind a fixed termination point for the game. We do, however, fix the starting point , which I think in many cases is unnatural: By the time I realize I know the bartender in my local Starbucks and maybe I should start tipping, I already lost count of the number of times I have been there. This is why I would like to model it as a game with infinite past. Also, it will be cool to have a paper that starts with `At every day ‘ for a change. But, as I am sure many game theorists have independently discovered, it is not clear how to proceed.

Suppose we have two players; you already know their names. Alice plays at even days and Bob plays at odd days. Each chooses an action from . It is tempting to define a pure strategy for Alice as a collection of functions : For every even , the argument for is the sequence of previous actions of Bob and the output is Alice’s action at day . Strategies of Bob can be defined analogously. But consider:

Example 1Assume that Alice`s strategy is `At every day play if Bob has already played infinitely many times and play otherwise’ and Bob’s strategy is `At every day play if Alice has already played infinitely many times and play otherwise’.

In Example 1 there is no play path that is consistent with both strategies. We described each player’s plan, but for some reason it can’t be that both players play according to their plan.

Example 2Assume that both Bob and Alice play `tit for tat’, which means play the same action that your opponent played yesterday.

In Example 2 there are two games paths that are consistent with the strategy profile. We described exactly each player’s plan but for some reason, these plans don’t pin down completely what will actually happen in the game.

Following von-Neumann and Morgenstern, for me to call something a game, you need to have a normal-form representation, which means that any strategy profile should uniquely determine the outcome of the game. This is why I used to view these examples as a dead end. And, since there is no game, I wouldn’t think there is anything to say about rationality in this context. Or so I thought

von-Neumann and Morgenstern are not the only players here. Zermelo, for example, did not think about games in terms of their normal forms. And, as an interesting discussion over at Thoughts, Arguments and Rants blog (which, because of my inferiority complex towards philosophers I am too shy to join) shows, neither do everyone around the blogosphere. They start with an example by Andrew Bacon of a zero-sum game in which each player has a winning strategy in the sense that they win in every play consistent with that strategy. Of course, the outcome is undefined if both players use their `winning strategies’. They use the example to argue about the possibility of being purely rational.

Incidentally, for those of us who don’t like infinite games because the world is finite or something, it might be interesting to note that Andrew describes his example of a game with infinite past using a Zeno-type arguments which I already said I don’t buy: At each , at hours past 12pm a player picks an action.

## 2 comments

May 6, 2010 at 7:16 pm

OriIndeed, the problem of a game where the strategies do not determine the outcome of the game is the main thing that bothered me in the very nice paper of Bollobas, Leader and Walters (http://arxiv.org/abs/0909.2524). The problem also has to do with infinite past, although in a more disguised form.

May 7, 2010 at 6:10 am

EilonThis issue is also present in games in continuous time: there may be a vector of strategies that does not define a unique path. In that literature they resorted to special classes of strategies, that ensure the uniqueness of the play path. But one wonders whether we need to worry about the non-existence of an initial condition in a discrete-time game: in your example, the past is given. Whatever happened before I was born is given. So in a sense there is an initial condition, and therefore the play path is well defined. Maybe there is a problem in modelling this type of game, but this is due to our limited computational capacity.