In the last few months I’ve become a fan of the TCS stack exchange, a question-and-answer forum for theoretical computer science. Some of this activity is in AGT. I certainly sometimes feel that this is yet another time sink to be found on the Internet (like writing a blog…) , allowing me to keep away from “real work”. However on the whole, I would evaluate my time spent there as productive. On the question side, this a good place to check out whether someone knows an answer to some small obstacle that got you stuck in your research, or to check a point of view when looking at a new subject, or finding a reference, etc. I also feel that the “answer side” is beneficial for me: questions that I’m able to answer often look at something that I know from a different perspective — a perspective that it’s good to gain. In other cases, I look at a question, think that I should know the answer and, when thinking about it a few more minutes, realize that there is a gap in my knowledge — one that I didn’t realize existed. In such cases, it sometimes means that I get to fill this gap, or sometimes that I find a real “hole” worthy of research. A recent question asked about efficiency gaps between correlated equilibria and coarse equilibria. The fact that I wasn’t able to answer it, demonstrated to me that I don’t understand coarse equilibria well enough. When someone finally answers the question (as I’m quite sure will happen — this can’t be hard…), I will learn something.
[...] This post was mentioned on Twitter by Suresh Venkat, TCS blog aggregator. TCS blog aggregator said: AGT on TCS Stack-Exchange « Algorithmic Game-Theory/Economics: http://bit.ly/b2EFy7 [...]
I did have one example in mind already when I asked this question: in an upcoming SODA paper, Roughgarden and Schoppmann define the “Local Smoothness” of a game, and show that local smoothness is a property that can be used to separate the efficiency of correlated and coarse correlated equilibria in atomic splittable congestion games.
However, local smoothness is a property defined only for games with convex strategy sets, and when you make your favorite finite game convex by just throwing in the set of all mixed strategies, local smoothness turns out to be equivalent to Tim’s previous notion of smoothness. And smoothness is one of those techniques that cannot be used to separate the efficiency of coarse correlated equilibria from correlated equilibria.
So what I am really hoping to get from the question is an example of an (elementary?) argument that is used to separate the efficiency of these two concepts in a finite game.
(Here is the link to their paper: http://theory.stanford.edu/~tim/papers/scg.pdf)
After spending a few hours on Aaron’s question, I found an answer. The most interesting thing that I learned from this exercise is that coarse equilibria may be supported on strictly dominated strategies.