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
Tags
apple
axiom of choice
bayesianism
behavioral economics
Blackwell
bloggingheads
computability
computability theory
Dawkins
Elsevier
expert testing
falsifiability
fixed point
game theory
global warming
healthcare
infinite games
israel
krugman
latex
macfreedom
measurability
michael rabin
mixed strategies
modeling
morgenstern
multiple selves
Nash equilibrium
normal form
notworking
pdf
peer review
prisoner's dilemma
projective determinacy
quantum games;
Samuelson; martingales; probability
springer
Springer-Verlag
statistics
strategy
the greatest show on earth
von Neumann
zeno
zermelo
zero-sum games
Blogroll
Archives
- 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
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
xiaoxili
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
xiaoxili
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
xiaoxili
sorry, but the matrix should be like this
f(C,C)=blanket
f(C,S)=-1
f(S,C)=-1
f(S,S)=+1