## How is equilibrium achieved?

https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/

In class, we focused for some time on analyzing games abstracted from a variety of situations, many of which contained pure and/or mixed Nash equilibria. Knowing about these equilibria is important because it provides a framework of choices that, if followed by each player involved, ensures that no player is benefited by deviating from these equilibrium choices. In essence, it is much easier to make predictions about optimality in various situations when given the equilibria, but the problem is the following: How do the players in a game actually find and adhere to equilibrium choices?

Equilibrium models make a major assumption that all players in a game are fully aware of all opponents’ strategy distributions, when in reality, each player likely only has a good idea of his or her own inclinations and potential when playing for the first time. Yet, apparently, economists use equilibrium models all the time in order to justify policy proposals, despite the fact that a paper published in September 2016 by Rubinstein and Babichenko managed to prove that it is impossible to come up with response strategies that converge efficiently to even a *near*-equilibrium for every game. That is, these mathematical models must be justified with a mechanism for achieving equilibrium, given that it is not a given that equilibrium can be achieved efficiently. (In the worst-case scenario, all players must communicate all preferences to all other players in order to determine an equilibrium, which is not feasible if there are many players or limitations on communication. For 100 directly-competing players, there are 2^100 ~= 10^30 outcomes, i.e. 10^18 times more information than there are bytes on a terabyte hard drive, i.e. we can’t even store all that info…

Thankfully, this does not mean that all many-player games cannot quickly reach equilibrium, as it is absurd to think that all games require everyone to know everyone’s info. Perhaps we only need to know how many people are engaging in an activity, rather than precisely *who* is engaging in that activity. This greatly limits the amount of information that must be distributed.

Another way of reaching equilibrium more quickly is to modify Nash equilibrium with “correlated equilibrium”, which exists when each player is compelled by a “mediator” not to deviate from their current strategy. This can be as simple as not running a red light, with the light being the mediator. In situations where players do not know what advice the other players are receiving, the possibilities can be more complicated and equilibria can be achieved that actually contain more overall benefit than any Nash equilibrium.

A particular form of correlated equilibrium is regret-minimization, in which players become more likely over time to make a move that they regret not playing in a prior round. This leads to situations where players periodically converge to different strategies over time, as if they were obtained a different mentor every once in a while. Yet, as with any human endeavor, regret minimization isn’t “the” optimal approach — regrets aren’t always pursued rationally!

The bottom line is that the mechanism of achieving equilibrium is perhaps even more important than the existence of the equilibrium itself.