Stopping games are simple multi-player sequential games; each player has two actions: to continue or to stop. The game terminates once at least one player decides to stop. The terminal payoff depends on the moment at which the game stopped, on the subset of players who decided to stop at the terminal time, and on a state variable whose evolution is controlled by nature. In other words, the terminal payoff is some stochastic process. If no player ever stops, the payoff is 0 (this is without loss of generality).
Stopping games arise in various contexts: wars of attrition, duels, exiting from a shrinking market to name but a few. Does an equilibrium exist in such games? If the game is played in discrete time and payoffs are discounted, then payoffs are continuous over the strategy space, and an equilibrium exists. What happens if the game is played in continuous time?
Surprisingly, if there are at least three players, an equilibrium may fail to exist, even if the payoffs are constant (that is, they depend only on the subset of players who decide to stop, and not on the moment at which the game is stopped (and there is no state variable). Consider the game in the following figure:
A three player stopping game
In this game, in every time instant t, player 1 chooses a row, player 2 chooses a column, and player 3 chooses a matrix. Each entry except the (continue,continue,continue) entry corresponds to a situation in which at least one player stops, so that the three-dimensional vector in the entry is the terminal payoff in that situation. The sum of payoffs in every entry is 0, and therefore whatever the players play the sum of their payoffs is 0. Each player who stops alone receives 1, and therefore each one would like to be the first to stop. It is an exercise to verify that the game does not terminate at time t=0: termination at time 0 can happen only if there is a player who stops with probability 1 at time 0, but if, say, player 1 stops at time 0 then it is dominant for player 2 to continue at time t=0, and then it is dominant for player 3 to stop at time t=0, but then it is dominant for player 1 to continue at time t=0.
Thus, in this game, the players stop with some positive probability (that is smaller than 1) at time t=0, and, if the game has not terminated at time 0, each one tries to stop before the other. If the game is played in continuous time, there can be no equilibrium. Don’t worry because the payoff is not discounted; adding a discount factor will not affect the conclusion.
It is interesting to note that in discrete time this game has an equilibrium: in discrete time the players cannot fight about who stops first after time t=0, because the first time in which they can stop after time t=0 is time t=1, so they all stop with some positive probability at time t=1, and, in fact, they stop with positive probability at every discrete time t.
So stopping games are one example in which a game in continuous time does not have an equilibrium, while the corresponding game in discrete time does have an equilibrium.
The Leisure of the Theory Class 
8 comments
November 10, 2010 at 6:17 pm
xiaoxili
Dear Eilon, noticed that your recent paper with Rida has actually filled in the study of 2-player stopping games. How about the story for more than 3 players? This example tells something, but still I can’t see further. Do you have some related works on this?
November 11, 2010 at 1:01 am
Eilon
The existence of the value in general two-player stopping games in continuous time was proved in Laraki and Solan (2005, The Value of Zero-sum Stopping Games in Continuous Time), and the existence of an equilibrium in two-player non-zero-sum games in Laraki and Solan (2010, Equilibrium in Two-Player Non-Zero-Sum Dynkin Games in Continuous Time). The three player example in this post is taken from Laraki, Solan and Vieille (2005, Continuous-time games of timing). Because an equilibrium may fail to exist when there are three players, throwing in more players will not help: for every n>=3 there is an n-player stopping game in continuous time without a Nash equilibrium. To see this, take the three-player game provided above, and for each additional player k, set the payoff to player k if he continues to 0 (whatever the other players do), and his payoff is -1 if he stops (whatever the other players do). Then in all equilibria, the additional players will always continue, and we are reduced to the three-player game mentioned in the post.
Where do we go from here? One can look for the existence of a correlated equilibrium (Heller, 2010, Sequential correlated equilibria in stopping games), or the existence of equilibria when the payoff processes satisfy some conditions (for example, my payoff if I stop alone is lower than my payoff if you stop alone; this condition arises naturally in the application of stopping games to the theory of pricing of options: the writer of the option can cancel the deal, but then it has to pay some penalty). Some special cases were studied in the Laraki-Solan-Vieille paper mentioned above, but I am sure there are other interesting cases that still await our attention.
November 11, 2010 at 12:07 pm
xiaoxili
thanks for pointing out thees works to me. It’s a big pleasure to study them.
November 11, 2010 at 6:32 pm
xiaoxili
Dear Eilon, can I ask you a question about the mixed strategy used in your papers?
Sorry but I do feel a bit lost, and I have checked Aumann’s paper (mixed and behavior, 1964). If I understand correctly, in ur model of stopping time, the pure strategy is a function from the Probability Space OMIGA to the time interval [0, T] (or {0, 1, 2,…,…} for discrete time). And this was called stopping time right? But isn’t it a pure strategy of stopping time directly a number in [0, T]? Why should it here be a function from the Probability Space OMIGA to [0, T]?
In Aumann’s paper, the pure strategy was a function from information set X to the action space Y both endowed with measure structure. To make this a probability distribution on Y, this function should be m-transform which is impossible by his result in another paper. So he introduced a directly a random device on [0, 1] and a mixed strategy now corresponds to a measurable function from [0, 1]*X to Y.
As in your model, Y = [0, T], and information set X = OMIGA. What puzzles me is that why does an information set make sense in the stopping time game? The players will make decisions depending on some observation in OMIGA?
Thanks a lot! Perhaps I have misunderstood something basic.
xiaoxi
November 11, 2010 at 11:31 pm
Eilon
Let’s start from the beginning. What is a stopping game? To simplify matters, I will describe the game in discrete time; continuous time adds technical complications. Think of an infinite complete binary tree: the tree starts at the root, the root has two children, each child has two children, etc. Now add probabilities: you start at the root, you then go to one of the root’s children with equal probbility, and you continue this way: if you are in a vertex x, you will move to one of its two children with equal probability.
So far I described a stochastic process. Now I am going to turn it into a game: there are two players. To each vertex x of our binary tree we attach three vectors in R^2: a(x), b(x) and c(x). The play starts at the root of the binary tree, x0. Each of the players has to decide whether to continue of to stop. If player 1 stops and player 2 continues, the game terminates and the terminal payoff is a(x0). If player 2 stops and player 1 continues, the game terminates and the terminal payoff is b(x0). If both stop, the game terminates and the terminal payoff is c(x0). If both continue, the game continues, and moves to one of the two children with equal probabilities. Again, each player decides whether to stop or not, etc.
What is a pure strategy for player 1 in this game? It is an indication when to stop. That is, it is a collection of vertices where player 1 would stop. This collection of vertices should satisfy the following condition: it does not contain a vertex and one of its descendants. Indeed, if you stop at a given vertex, the play will never reach its descendants, and so you will not be able to stop there. This collection of vertices is nothing but a stopping time.
A mixed strategy is as usual a probability distribution over stopping time: with probability 2/3 I use one stopping time, with probability 1/3 another.
A behavior strategy for player 1 is a function that assigns to every vertex in our binary tree a probability: the probability that player 1 stops at that vertex.
By Kuhn’s theorem, if the game is in discrete time, mixed strategies and behavior strategies are equivalent. In continuous time the interpretation of behavior strategies is problematic, because having a continuum of independent random variables is problematic.
In a general stopping game, each vertex may have any number of children (even a continuum of children), and the probability distribution according to which a child is chosen need not be 1/2-1/2, but may be any probability distribution. But the concepts are the same.
I hope that now the concepts are clearer.
November 12, 2010 at 6:39 am
Xiaoxili
Thanks a lot! This explanation makes me quite clear.
I think what really matters is because in the stopping time model, the payoff vectors (a(t), b(t), c(t)) are stochastic processes. So at each period t, there correspends to several vertexes, which were the realizations of the states, and were also the information set (observations) for both players at that stage.
Players make decisions not only by sense of which stage they are at, but also which vertex, or what state, they are located in. I misunderstood the stopping game as that the players were informed the payoff processes at the begaining, and will never see any realization of the process at all. In this sense, player’s pure strategy would be only a stopping point at the begaining of the game independedn of which vertex he would be at.
Would it be intereting to consider the problem of incomplete (imperfect) information? By which I mean removing the assumptions that the payoff processes are completely informed to two players, and that at each stage, alll players know perfectly the state. I think this shoud be linked to the information problems of general stochatic games (on the transition process).
November 12, 2010 at 6:53 am
Eilon
I think it will be interesting to study stopping games with incomplete information. In the following paper http://www.math.ubc.ca/~origurel/papers/GG07.pdf, the first example in section 5 shows that the value of a zero-sum stopping game in discrete time with incomplete information need not exist. If I recall correctly, I also spotted such an example in the Ph.D. thesis of Rida Laraki.
What conditions guarantee the existence of the value? Can one characterize the value in interesting cases? How does the value change with the information flow? These are very interesting questions. For me, at least.
November 19, 2010 at 3:06 am
Stopping Games in Continuous Time: Correlated Equilibrium « The Leisure of the Theory Class
[…] a recent post I described stopping games in continuous time; I mentioned that in this class of games, an […]