Correlated Equilibria in Game Theory

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!

20 Responses to Correlated Equilibria in Game Theory

  1. 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.

    • John Baez says:

      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.

        Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler [23], and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as application specific methods for computing multivariate expectations over product distributions.

        Clearly quite some elaborate machinery is necessary for it to work.

        • retlav46 says:

          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.

      • John Baez says:

        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.

  2. retlav46 says:

    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).

  3. John Baez says:

    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:

    The equilibrium concept of Nash (1951), together with its refinements, is without doubt the single game-theoretic tool that is most often applied in economics. Yet, though at first the definition seems simple and natural enough, a little reflection leads to some puzzlement as to why and under what conditions the players in an n-person game might be expected to play such an equilibrium. Recall that it is defined as an n-tuple of strategies in which the component strategy of each player maximizes that player’s utility given that the other players are playing their components. Now why should any player assume that the other players will play their components of such an n-tuple, and indeed why should they? This is particularly perplexing when, as often happens, there are multiple equilibria; but it has considerable force even when the equilibrium is unique.

    Indeed, there are games whose Nash equilibria appear quite unattractive even though they are unique (see Harsanyi, 1977, p. 125); and even without such examples, it does not seem clear why the players would play even a unique Nash equilibrium. In a two-person game, for example, Player 1 would play his component only if he believes that 2 will play his; this in turn would be justified only by 2’s belief that 1 will indeed play his component; and so on. To many this will sound like a plain old circular argument: consistent, perhaps, but hardly compelling.

    Nash equilibrium does make sense if one starts by assuming that, for some specified reason, each player knows which strategies the other players are using. But this assumption appears rather restrictive. Another criticism of equilibrium that has been advanced is that it appears inconsistent with the modern subjectivist, Bayesian view of the world. According to the Bayesian view, subjective probabilities should be assignable to every prospect, including that of players choosing certain strategies in certain games. Rather than playing an equilibrium, the players should simply choose strategies that maximize their utilities given their subjective distributions over the other players’ strategy choices.

    It is the purpose of this paper to provide a simple rationale for equilibrium. Surprisingly, our rationale is precisely in terms of the “criticism” in the previous paragraph. We will show that, far from being inconsistent with the Bayesian view of the world, the notion of equilibrium is an unavoidable consequence of that view. It turns out, though, that the appropriate equilibrium notion is not the ordinary mixed strategy equilibrium of Nash (1951), but the more general notion of correlated equilibrium.

    Specifically, we will show the following. Let us be given an n-person game G in strategic (i.e. normal) form. Assume that (i) as in Savage (1954), each player has a subjective probability distribution over the set of all states of the world; and (ii) it is common knowledge that each player chooses a strategy that maximizes his expected utility given his information. Then the strategies chosen by the players constitute a correlated equilibrium of G. Conversely, each correlated equilibrium of G can be obtained in this way for an appropriate choice of the parameters. A precise formulation and proof will be found in Section 3.

    To some readers, this may seem obvious. Once one has the formulation, it is indeed embarrassingly easy to prove, as we shall see. But it should not be confused with certain characterizations of Nash equilibrium, which look similar but are actually much more transparent. There one assumes not only that each player is a utility maximizer, but that he knows the strategies actually being used by all other players. We make no such assumption; indeed, in our treatment, the players do not in general know how others are playing. We assume only that it is common knowledge that all the players are Bayesian utility maximizers, that they are rational in the sense that each one conforms to the Savage theory. Such an assumption underlies most of game theory, and of economic theory as well; we show that it, by itself, is enough to assure that the outcome is a correlated equilibrium.

    In a footnote, he says:

    An event is common knowledge among a set of agents, if it is known to all, it is known to all that it is known to all, and so on ad infinitum. See Lewis (1969) and, for a precise mathematical formulation, Aumann (1976).

  4. 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.

    Even life comes with moral hazards, information filters
    and skewed opportunities. I doubt we can turn back the timer on G+, but 
    it was a good game. Thank you.
    
    P.S. I can't even remove the "Offending" posts now even if I could, and 
    I would. Peace
    
  5. 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.

  6. Allan E says:

    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!)

  7. S Srinivas Rau says:

    Klarreich _ Clear domain 😉

  8. ariascos says:

    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.

    • John Baez says:

      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?

        • John Baez says:

          Kram wrote:

          I assume the two equilibria are both-choose-A and both-choose-B, right?

          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.

  9. John Baez says:

    On G+, Deen Abiola explained some important things it’ll take me time to really understand:

    Interesting. I encountered the concept of correlated equilibrium in the context of regret minimizing algorithms. It might be concrete enough to be more intuitive for more people. Okay, so Nash equilibria are too difficult to compute for finite sum games (this is well known, it looks like what is new is that they are also difficult to approximate); we want something easier. A correlated equilibrium can be computed in polynomial time and is achieved when, given a random signal that tells some agent an action to select, there is no gain from deviating. An example is two cars at an intersection, each trying to decide whether to Go or Wait. The traffic signal helps to coordinate their action unlike Nash, which assumes each player randomizes without communication (much harder to get fair outcomes!).

    In the low regret learning scenario, you have a learner that gets to select an action and suffers a penalty or reward. The actions are offered by N experts/strategies. External regret is minimized when you do not do much worse in hindsight than a best fixed expert. E.g. you’re betting and the experts are a pool of speculators, you allocate weights by a min-regret rules and so aren’t losing much more than the best person. The experts can be abstract. You’re playing rock paper scissors and the experts are rock, paper or scissors. This learns a distribution over outcomes. One solution concept is to randomize according to the weight of an expert which is determined by its accumulated loss. For a 2 player zero sum game, this converges on Nash if both players play this way. This algorithm is so simple and so successful as to be almost offensive :).

    Internal regret and swap regret are stronger notions. They allow you to say, even if I had swapped betting on that team for that other team, I would not have any better regret in expectation. Multiple agents minimizing their swap regret converges on the correlated equilibrium. The dynamics of many learning algorithms converge on correlated equilibrium. Minimizing swap regret is a very simple algorithm and much more efficient than linear programming. It’s also trivial to extend to multiple players (just have them each minimize swap regret) than it is with linear programming which is more mathematically involved.

    I’ve never run into an explanation of swap regret that wasn’t very abstract. It’s not obvious why minimizing swap regret individually leads to a correlated equilibrium but it’s the fact that history serves as a correlator. Then memory and the ability to learn conditional distributions acts as the signal that tells you what to do when (this is formally done in terms of a time correlation->the signal randomly selects a time t and then tells you to perform the action you took at time t, it doesn’t let you know what t it chose. You then set up a correspondence between no swap situation and the no gain from deviating the random signal/correlation device’s suggestion).

    A lot of this work joining game theory, economics and learning theory is done in the setting of ads and click optimization. These are the algorithms that run the digital world. They operate in the shadows so you never hear about them. Another fun thing about them is their link to evolution, so it gives CS/ML people another angle into that field.

  10. […] John Baez on correlated equilibria in game theory. (H/t Qiaochu Yuan, with good comments.) […]

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s