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
Academic Politics
advertising
alfred tarski
apple
Ariel Rubinstein
auctions
axiom of choice
bayesian
bayesianism
behavioral economics
Blackwell
bloggingheads
chairing
computability
covid-19
Dawkins
dynamic programming
economics
Elsevier
ergodic
erice
experiments
expert testing
falsifiability
fixed point
game theory
global warming
healthcare
infinite games
intermediate microeconomics
ipad
israel
krugman
large games
latex
learning
macfreedom
matching
measurability
mechanism design
merging
michael rabin
mixed strategies
modeling
morgenstern
multiarmed bandit
multiple selves
Nash equilibrium
normal form
notworking
open problems
pararallel sessions
pdf
peer review
pricing
prisoner's dilemma
projective determinacy
purification
quantum games;
Samuelson; martingales; probability
shapley-folkman
Simpsons did it
springer
Springer-Verlag
stability
statistics
strategy
teaching
the greatest show on earth
Trump
uncertainty
von Neumann
zeno
zermelo
zero-sum games
Blogroll
Archives
- May 2022
- August 2020
- July 2020
- May 2020
- April 2020
- March 2020
- February 2020
- January 2020
- April 2019
- December 2018
- November 2018
- June 2018
- February 2018
- December 2017
- September 2017
- August 2017
- July 2017
- June 2017
- September 2016
- August 2016
- June 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- 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
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