Erica Klarreich is one of the few science journalists who explains interesting things I don’t already know clearly enough so I can understand them. I recommend her latest article:
• Erica Klarreich, In game theory, no clear path to equilibrium, Quanta, 18 July 2017.
Economists like the concept of ‘Nash equilibrium’, but it’s problematic in some ways. This matters for society at large.
In a Nash equilibrium for a multi-player game, no player can improve their payoff by unilaterally changing their strategy. This doesn’t mean everyone is happy: it’s possible to be trapped in a Nash equilibrium where everyone is miserable, because anyone changing their strategy unilaterally would be even more miserable. (Think ‘global warming’.)
The great thing about Nash equilibria is that their meaning is easy to fathom, and they exist. John Nash won a Nobel prize for a paper proving that they exist. His paper was less than one page long. But he proved the existence of Nash equilibria for arbitrary multi-player games using a nonconstructive method: a fixed point theorem that doesn’t actually tell you how to find the equilibrium!
Given this, it’s not surprising that Nash equilibria can be hard to find. Last September a paper came out making this precise, in a strong way:
• Yakov Babichenko and Aviad Rubinstein, Communication complexity of approximate Nash equilibria.
The authors show there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other almost everything about their preferences. This makes finding the Nash equilibrium prohibitively difficult to find when there are lots of players… in general. There are particular games where it’s not difficult, and that makes these games important: for example, if you’re trying to run a government well. (A laughable notion these days, but still one can hope.)
Klarreich’s article in Quanta gives a nice readable account of this work and also a more practical alternative to the concept of Nash equilibrium. It’s called a ‘correlated equilibrium’, and it was invented by the mathematician Robert Aumann in 1974. You can see an attempt to define it here:
• Wikipedia, Correlated equilibrium.
The precise mathematical definition near the start of this article is a pretty good example of how you shouldn’t explain something: it contains a big fat equation containing symbols not mentioned previously, and so on. By thinking about it for a while, I was able to fight my way through it. Someday I should improve it—and someday I should explain the idea here! But for now, I’ll just quote this passage, which roughly explains the idea in words:
The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy (assuming the others don’t deviate), the distribution is called a correlated equilibrium.
According to Erica Klarreich it’s a useful notion. She even makes it sound revolutionary:
This might at first sound like an arcane construct, but in fact we use correlated equilibria all the time—whenever, for example, we let a coin toss decide whether we’ll go out for Chinese or Italian, or allow a traffic light to dictate which of us will go through an intersection first.
In [some] examples, each player knows exactly what advice the “mediator” is giving to the other player, and the mediator’s advice essentially helps the players coordinate which Nash equilibrium they will play. But when the players don’t know exactly what advice the others are getting—only how the different kinds of advice are correlated with each other—Aumann showed that the set of correlated equilibria can contain more than just combinations of Nash equilibria: it can include forms of play that aren’t Nash equilibria at all, but that sometimes result in a more positive societal outcome than any of the Nash equilibria. For example, in some games in which cooperating would yield a higher total payoff for the players than acting selfishly, the mediator can sometimes beguile players into cooperating by withholding just what advice she’s giving the other players. This finding, Myerson said, was “a bolt from the blue.”
(Roger Myerson is an economics professor at the University of Chicago who won a Nobel prize for his work on game theory.)
And even though a mediator can give many different kinds of advice, the set of correlated equilibria of a game, which is represented by a collection of linear equations and inequalities, is more mathematically tractable than the set of Nash equilibria. “This other way of thinking about it, the mathematics is so much more beautiful,” Myerson said.
While Myerson has called Nash’s vision of game theory “one of the outstanding intellectual advances of the 20th century,” he sees correlated equilibrium as perhaps an even more natural concept than Nash equilibrium. He has opined on numerous occasions that “if there is intelligent life on other planets, in a majority of them they would have discovered correlated equilibrium before Nash equilibrium.”
When it comes to repeated rounds of play, many of the most natural ways that players could choose to adapt their strategies converge, in a particular sense, to correlated equilibria. Take, for example, “regret minimization” approaches, in which before each round, players increase the probability of using a given strategy if they regret not having played it more in the past. Regret minimization is a method “which does bear some resemblance to real life — paying attention to what’s worked well in the past, combined with occasionally experimenting a bit,” Roughgarden said.
(Tim Roughgarden is a theoretical computer scientist at Stanford University.)
For many regret-minimizing approaches, researchers have shown that play will rapidly converge to a correlated equilibrium in the following surprising sense: after maybe 100 rounds have been played, the game history will look essentially the same as if a mediator had been advising the players all along. It’s as if “the [correlating] device was somehow implicitly found, through the interaction,” said Constantinos Daskalakis, a theoretical computer scientist at the Massachusetts Institute of Technology.
As play continues, the players won’t necessarily stay at the same correlated equilibrium — after 1,000 rounds, for instance, they may have drifted to a new equilibrium, so that now their 1,000-game history looks as if it had been guided by a different mediator than before. The process is reminiscent of what happens in real life, Roughgarden said, as societal norms about which equilibrium should be played gradually evolve.
In the kinds of complex games for which Nash equilibrium is hard to reach, correlated equilibrium is “the natural leading contender” for a replacement solution concept, Nisan said.
As Klarreich hints, you can find correlated equilibria using a technique called linear programming. That was proved here, I think:
• Christos H. Papadimitriou and Tim Roughgarden, Computing correlated equilibria in multi-player games, J. ACM 55 (2008), 14:1-14:29.
Do you know something about correlated equilibria that I should know? If so, please tell me!
That Wikipedia article is weird. They say, as you did, that calculating the correlated equilibrium is, in general, easier than calculating the Nash equilibrium, which is fine.
But their example application of a correlated equilibrium actually involves first knowing all the Nash equilibria, and then basically assigning a probability to those.
If you had to actually know the Nash equilibria to find the correlated equilibria, then it could hardly be easier to find them.
So I’d have preferred to see how to do that reasoning with no references to Nash equilibria. As well as a construction of the optimal equilibrium with maximal expected payoffs. With the simple game of chicken example they showed, it should be a small enough calculation to basically show it all in a transparent manner.
The explanation that’s already there could still exist to show how the two types of equilibrium are actually related, assuming that’s general and not an artifact of their particular example.
Wikipedia aside, what I wondered is whether, as would be implied by the latter “being more general”, all Nash equilibria are also correlated equilibria.
I understand your complaint, but….
It could be more complicated to find all correlated equilibria than the Nash equilibria in this tiny example, even if correlated equilibria can be more efficiently found in the limit where the example becomes very large. This paper showed correlated equilibria can be found by linear programming:
• Christos H. Papadimitriou and Tim Roughgarden, Computing correlated equilibria in multi-player games, J. ACM 55 (2008), 14:1-14:29.
Since a polynomial-time algorithm is known for linear programming, this means that finding correlated equilibria is ‘easy’ in a certain technical sense. But I think it would be hard to explain this paper in a Wikipedia article!
That’s fair enough. It just seemed weird to me.
Clearly quite some elaborate machinery is necessary for it to work.
I don’t have time to read that paper, but they must be trying to do something more sophisticated than simply finding the correlated equilibria of a finite game. The set of correlated equilibria of a finite game is defined by a finite number of linear inequalities in finitely many variables, so linear programming is more than enough.
Pretty elaborate stuff indeed! It’s worth noting that Khachiyan’s work on linear programming was considered a breakthrough because it showed this problem could be solved in polynomial time, even though his algorithm was too slow to be practical.
You may like Peyton Young’s short book on Strategic Learning and Its Limits. It may be a bit old (2004) and miss on connections with computer scientists’ game theoretical work, but it’s short, well-written and covers the material (above the basics you can find in introductory game theory textbooks like Osborne and Rubinstein’s) that one needs to know anyway.
Btw, yes, all Nash equilibria are correlated equilibria: they are the correlated equilibria in which everybody simply ignores the public signals (if everybody else does so, there is never any gain from conditioning your own strategy to the public signals).
Thanks! 2004 is not too old for me, given that I just heard about Aumann’s 1974 discovery of correlated equilibria yesterday!
Ok, that makes sense, thanks!
Aumann has a nice paper on correlated equilibria:
• Robert Aumann, Correlated equilibria as an expression of Bayesian rationality, Econometrica: Journal of the Econometric Society (1987), 1–18.
He begins:
In a footnote, he says:
Attn: John Baez, Unrelated to games and theory, I mistaken posted too many blog links on your G+ post on G+ functionality. I don’t know the rules on how to distinguish signals from a poorly documented social media platform. I have been penalized by getting blocked and have had my accounts frozen. In sixty days I may loose the game of G+ all together. If you were understandably concerned about me wasting the 500 limit cue for comments, I accept the feedback. Oddly however, my blog links were on the history of the G+ conversion and it’s loss of functionality essentially changing the rules mid game. I very much enjoy your posts on Math and the Sciences, and I particularly like your adroitness with information graphics. I too liked G+ for it’s original Math graphics utility, much more problematic today post G+ design changes.
Phillip Johnson here one last time. The blog in question is called Zenophile and is at ppireader.blogspot.com
My blog now says I’m posting as “Unknown.”
Thanks again. It was fun.
It is a popular area of study in machine learning — you might like this paper: http://rob.schapire.net/papers/correl-equil.pdf
applying maximum entropy as a means of choosing between correlated equilibria (by my old roommate Sham!)
Klarreich _ Clear domain 😉
It took me a while to get that joke.
Dear John: Thanks for you interesting posts. Correlated equilibrium is a very nice concept that has also been put forward as embracing some sort of social epistemology (The Bounds of Reason: Game Theory and the Unification of the Behavioral Sciences – Gintis). However, it introduces a continuum of equilibria when there are only finitely many Nash equilibria (two or more). I believe this introduces many challenges from a positive perspective in which one would like to pin down more narrowly what agents will do in a strategic situation.
I’ll have to read that book—thanks for pointing it out!
In the game where both players choose A or B, and both win $1 if they make the same choice but $0 if they make different choices, there are two Nash equilibria. But if this game is played just once, in the absence of communication, there is no reasonable way for either player to decide which choice to make. So, we shouldn’t expect that the Nash equilibrium is what actually occurs.
What are the correlated equilibria in this game?
Going by the example of how it’s done on Wikipedia:
I assume the two equilibria are both-choose-A and both-choose-B, right?
Now consider a third party that draws one of two cards labelled (A,A) and (B,B) with some probability p and 1-p respectively.
After drawing the card the third party informs the players of the strategy assigned to them on the card (but not the strategy assigned to their opponent). Suppose a player is assigned A. They would not want to deviate supposing the other player played their assigned strategy since they will get 1 (the highest payoff possible). Likewise for B.
So there is a continuum of correlated equilibria all behaving precisely the same in outcome, though the probability of what strategy is selected will be p. The two Nash equilibria would happen for p = 0 or p = 1, respectively.
Is that correct?
Kram wrote:
Those are two Nash equilibria, but apparently not the only ones!
Let’s work it out. Suppose player 1 has probability > 1/2 of choosing A. Then to maximize his expected payoff, player 2 will choose A all the time. By the same token if player 2 has probability > 1/2 of choosing A, to maximize his expected payoff player 1 will choose A all the time.
The same is true if we change “A” to “B” everywhere in the previous paragraph.
This gives the two Nash equilibria you mentioned: the one where both players choose A with probability 1, and the one where both players choose B with probability 1.
The only case not considered is where both players choose A with probability 1/2. This is a Nash equilibrium as well, since neither player can improve their payoff by unilaterally changing the probability that they chose A.
So there appear to be 3 Nash equilibria.
On G+, Deen Abiola explained some important things it’ll take me time to really understand:
[…] John Baez on correlated equilibria in game theory. (H/t Qiaochu Yuan, with good comments.) […]
I’ve just discovered your nice post. The Aumann paper you cite introduced correlated equilibrium. The observation that CE are solutions to linear programs was made by Hart and Schmeidler Mathematics of Operations Research 1989, who also give an example of a game with a correlated equilibrium but no Nash equilibrium. (Obviously not a finite game, but lp works on large vector spaces too.)
Thanks!
It’s a bit ironic that a number of economists (Mises, Hayek, Lachmann) have been pointing at problems with equilibrium concept decades ago, and mainstream economics starts acknowledging the issue in XXI century. It’s meaningless to explain economic behavior assuming equilibrium already exists. But that’s what most models do.
Lachmann pointed at a bigger issue with equilibrium: people make choices not only based on information they have (which is limited, imprecise and possibly erroneous), but also on expectations. It follows that even perfect information is not sufficient for equilibrium to be reachable.
Correlated equilibrium in specific contexts work (if we take it in a “weak” sense), but often for the worse. North Korea may be in a correlated equilibrium in a sense due to state propaganda. Government being able to control information can manipulate everyone else and lead to choices that benefit the government at the expense of everyone. In fact, it is done everywhere to varying extent.