Stopping Games in Continuous Time: Correlated Equilibrium

In a recent post I described stopping games in continuous time; I mentioned that in this class of games, an equilibrium exists if there are at most two players, and it does not necessarily exist if there are at least three players. David Rahman, who visited Tel Aviv, asked me about the existence of correlated equilibrium in stopping games in continuous time. My first guess was that the three-player game that I described in that post had no correlated equilibrium. Last night I did the necessary calculations, and I was surprised to learn that this game possesses a correlated equilibrium: a mediator chooses a pair of players, each pair is chosen with probability 1/3, and that pair should stop at time 0, while the third player continues. There are additional correlated equilibria, but this is the simplest one. Does there always exist a correlated equilibrium in stopping games in continuous time? I bet that the answer is negative, but I am ready to be surprised again. Can anyone come up with a proof that a correlated equilibrium always exists, or with an example of a game without a correlated equilibrium?

6 comments

November 19, 2010 at 2:04 pm

Jonia

Great post, will now visit site on a regular basis :D

November 20, 2010 at 7:33 am

xiaoxili

Dear Eilon, thanks for your continued post of your thinking on the stopping game. This question does attract me. I have some thinkings and also questions to pose here which I hope might partially solve the problem.

The first point I want to address is that we can classify the correlated equilibriums in the continuous time stopping game into two sorts. One is to assign ZERO probability on the (C,C,C) strategy, that is to say, the mediator would recommend players to terminate the game in t=0; the other kind of CE is to assign some positive probability on (C,C,C).

I want to argue that in the second case, Prob(C,C,C)>0 could not be a CE in the continuous time stopping game since after the players have realized the the outcome of being (C,C,C), they all would like to stop immediately, the same analysis as the non-existence of NE in continuous time.

If you agree me with the point above, we could focus on the first case only, where the CE assigns ZERO probability on (C,C,C). This could be regarded as a general characterizing of the geometry of CE. What I want to know is, by posing some constraints on the probability distribution vector x on the whole joint strategies, for example here x(C,C,C)=0, does the CE still exist? We know that the CE is defined by several inequalities, thus a polytope. So, does the polytope always intersect with every boundary of the strategy simplex? If it does not intersect with at least one boundary, then the constraint of omitting the opposite strategy (vertex) of this edge would make CE not exist.

This would of course not work in general, with one counterexample the “matching pennies”
+1, -1
-1, +1
which has only symmetric CEs and are in the interior of the simplex thus no intersection with any edges at all.

From this two-player zero-sum stopping game, we can go easily to an example of 3-player zero-sum stopping game which has no CE. Here we add player 3 into the game, but he has no interest at all, by which I mean, he always gets payoff 0, and his action does not impact at all the payoff of the others. So any probability distribution assigning (C,C,C) ZERO probability not a CE at all.

So I think this should be a very naive counterexample to the existence of CE in several players continuous time zero-sum stopping game. And I believe there should be some more regular games with no CE in continuous time.

Anyway, what really interested me from this problem is the geometric characterizing of CE set. This could provide answers for existence of CE for not only this particular game, and but also general games with some constraints. To do this, perhaps we could go back to Hart and Schmeidler’s paper using the dual linear programming approach with now some more constraints .

November 21, 2010 at 9:02 am

Eilon

I think that the classification into two types of CE is fine, and indeed we should ask whether always there is a CE where the game terminates at time t=0. I did not follow your construction for a stopping game where such a CE does not exist: it was not clear to me whether the matching pennies game can be transformed into a stopping game. Quite a few people worked on the geometry of the set of CE. The name of Yannick Viossat immeidately jumps into my mind, but I am sure others have worked on this topic as well.

November 21, 2010 at 6:19 pm

To make my claim clear, just add some more words.
A zero-sum stopping game
C S
C -1
S -1 +1
was transformeded from a “matching pennies” by replacing the payoff of 1 by a next stage repetition. At t=0, the CE in this game with Proba(C,C)=0 does not exist.

November 21, 2010 at 6:20 pm

To make my claim clear, just add some more words.
A zero-sum stopping game
C S
C -1
S -1 +1
was transformeded from a “matching pennies” by replacing the payoff of 1 at (C,C) by a next stage repetition. At t=0, the CE in this game with Proba(C,C)=0 does not exist.

November 21, 2010 at 6:22 pm

sorry, but the matrix should be like this

f(C,C)=blanket
f(C,S)=-1
f(S,C)=-1
f(S,S)=+1

Stopping Games in Continuous Time: Correlated Equilibrium

Email Subscription

Entries by:

Recent Posts

Recent Comments

Blogroll

Archives

Meta

6 comments

Follow “The Leisure of the Theory Class”

Stopping Games in Continuous Time: Correlated Equilibrium

Related

Email Subscription

Entries by:

Recent Posts

Recent Comments

Blogroll

Archives

Meta

6 comments

Follow “The Leisure of the Theory Class”