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?

### Recent Posts

### Recent Comments

- Shapley-Folkman-Starr Lemma (2) | The Leisure of the Theory Class on The Shapley-Folkman-Starr Lemma
- Anonymous on Red coin, green coin
- rvohra on Rethinking Intermediate (Day 17- 19)
- rvohra on Rethinking Intermediate (Day 17- 19)
- Red coin, green coin | The Leisure of the Theory Class on Bonus question

alfred tarski
apple
Ariel Rubinstein
aumann
axiom of choice
bayesian
bayesianism
behavioral economics
binary quadratic programming
Blackwell
bloggingheads
Cambridge
chairing
combinatorial auctions
common knowledge
computability
Dawkins
dynamic programming
economics
Elsevier
ergodic
erice
experiments
expert testing
falsifiability
fixed point
game theory
global warming
Hawking Chair
healthcare
infinite games
intermediate microeconomics
ipad
israel
krugman
large games
latex
learning
macfreedom
matching
measurability
merging
michael rabin
mixed strategies
modeling
morgenstern
multiple selves
Nash equilibrium
normal form
notworking
open problems
pararallel sessions
pdf
peer review
prisoner's dilemma
projective determinacy
purification
puzzles
quantum games;
Samuelson; martingales; probability
shapley-folkman
Simpsons did it
springer
Springer-Verlag
statistics
strategy
teaching
the greatest show on earth
uncertainty
von Neumann
Warren Center
Warren Postdoctoral Fellowships
zeno
zermelo
zero-sum games

### Archives

- November 2014
- October 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- February 2014
- January 2014
- December 2013
- November 2013
- October 2013
- August 2013
- July 2013
- June 2013
- March 2013
- February 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009

## 6 comments

November 19, 2010 at 2:04 pm

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

November 20, 2010 at 7:33 am

xiaoxiliDear 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

EilonI 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

xiaoxiliTo 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

xiaoxiliTo 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

xiaoxilisorry, but the matrix should be like this

f(C,C)=blanket

f(C,S)=-1

f(S,C)=-1

f(S,S)=+1