Everyone has some papers that influenced his or her research. I have too. One of my favorite papers was written by the Dutch group, Janos Flesch, Frank Thuijsman and Koos Vrieze. They considered the following game.

Anne, Bill and Chris are neighbors. Anne likes Bill and dislikes Chris, Bill likes Chris and dislikes Anne, and Chris likes Anne and dislikes Bill. Every morning each one has to decide whether to invite someone to the five-o’clock tea. Plainly, if Anne decides to invite someone, it would be Bill. Similarly, if Bill invites someone, it would be Chris, and if Chris invites someone, it would be Anne.

The three neighbors make their decisions simultaneously, so when Anne decides whether to send an invitation to Bill, she does not know whether she is going to receive an invitation from Chris.

The game ends once at least one invitation is sent. Thus, the game goes on as long as no-one sends an invitation. This game is a combination of a repeated game and of a one-shot game: the game is repeated if no-one send invitations, and it terminates if someone sends an invitation.

What about payoffs? The payoffs are described by the following table:

Surprisingly, the numbers can be related to the story about tea time. Each player gets a utility of 3 if s/he is invited and s/he did not send an invitation, and a utility of 0 if s/he sent an invitation and was invited, a utility of 1 if s/he sends an invitation and the invited neighbor also sends an invitation, and a utility of 1 if s/he receives an invitation and the inviting neighbor received an invitation. Payoffs are not discounted.

What are the equilibria of this game? Though this game is symmetric, there is no symmetric equilibrium. Also, there is no stationary equilibrium. The simplest equilibrium is periodic with period 3:

At period 1: with probability 1/2 Anne sends an invitation to Bill, and with probability 1/2 she does not send an invitation. Meanwhile, Bill and Chris do not send invitations.

At period 2: with probability 1/2 Bill sends an invitation to Chris, and with probability 1/2 he does not send an invitation. Meanwhile, Chris and Anne do not send invitations.

At period 3: with probability 1/2 Chris sends an invitation to Anne, and with probability 1/2 he does not send an invitation. Meanwhile, Anne and Bill do not send invitations.

At period 4: like period 1.

And so on.

Plainly there are two additional equilibria, symmetric to the one provided above:

1) Bill is the first to randomize between sending an invitation and not sending an invitation, followed by Chris, who is follows by Anne.

2) Chris is the first to randomize between sending an invitation and not sending an invitation, followed by Anne, who is follows by Bill.

There are other periodic equilibria, but they all share the same structure as the three equilibria described above. Why do I like this paper? The game that I described above is a simple stochastic game. Whereas discounted stochastic games have stationary equilibria, this is not the case with undiscounted stochastic games. It is known that undiscounted two-player stochastic games have an epsilon-equilibrium (Vieille, 2000), but the equilibrium strategies may be complex, and they involve threats of punishment. It is not known whether undiscounted stochastic games with more than two players have an epsilon-equilibrium: we do not have a proof that an epsilon-equilibrium exists, nor do we have an example of a stochastic game without an epsilon-equilibrium. The paper by the Dutch suggests that in multi-player stochastic games we should expect to find periodic equilibria. This was a new observation, and in my view, quite important. In fact I used it in subsequent papers, and I think that more can be said about periodic equilibria than what we know at present. I never forget where it all started.

## Recent Comments