Correlated Equilibrium
I googled John Nash after the last lecture on equilibria and found out he lived very close to where I grew up, which piqued my interest. So then I googled some more and found this article, which I found fascinating.
https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/
First, the article lays out the main problem with the practical application of game theory. A paper by Aviad Rubenstein and Yakov Babichenko formally shows that in games with increasing numbers of players, it quickly becomes mathematically intractable to find an equilibrium point. This is also kind of common sense; in real life it is obvious that many ‘games’ have far too many moving parts to calculate how to reach an equilibrium point. Furthermore, in many games there can be multiple (or infinite!) equilibrium points. As such, while Nash equilibria are fascinating and almost universally applicable, they are not always useful for the actual task of predicting behavior of people and systems.
The article also introduces the similar concept of correlated equilibrium, proposed by Robert Aumann in 1974. In this scenario there is a “mediator” advising each player on what move to play. Correlated equilibrium is reached when neither player has incentive to deviate from the advisor’s advice, given they both trust the other players will also follow the mediator’s advice. A good example provided in the article is a busy intersection– the traffic light serves as a “mediator” to coordinate a large number of independent actors.
From that example it is easy to see how a mediator can coordinate behavior and facilitate reaching an equilibrium point. Furthermore, Aumann shows that the set of correlated equilibrium contains not just Nash equilibria but also strategies which lead to more mutually beneficial outcomes (e.g. Prisoner’s Dilemma, but now both prisoners have the same lawyer.) Correlated equilibrium is also more mathematically tractable than Nash equilibrium, as it is represented by linear equations and inequalities, while finding Nash equilibrium requires completely finding the fixed point of the system.
The concept of correlated equilibrium also sounds like basically common sense, and is just as ubiquitous as Nash equilibrium. For example, the ideal role of governments, regulations, policies, etc. is simply to act as an efficient mediator to ensure the best outcome for society as a whole. Still, it is not that easy to coordinate correlated equilibrium either– there are real world complications here too. For example, in the framing of the problem we assume mutual trust (which is a different can of worms entirely.) Possibly a future networks blog post.