Price of stability

In game theory, the price of stability (PoS) of a game is the ratio between the best objective function value of one of its equilibria and that of an optimal outcome. The PoS is relevant for games in which there is some objective authority that can influence the players a bit, and maybe help them converge to a good Nash equilibrium. When measuring how efficient a Nash equilibrium is in a specific game we often time also talk about the price of anarchy (PoA).

Another way of expressing PoS is:

In the following prisoner’s dilemma game, since there is a single equilibrium (B, R) we have PoS = PoA = 1/2.

On this example which is a version of the battle of sexes game, there are two equilibrium points, (T, L) and (B, R), with values 3 and 15, respectively. The optimal value is 15. Thus, PoS = 1 while PoA = 1/5.

The price of stability was first studied by A. Schulzan and N. Moses and was so-called in the studies of E. Anshelevich. They showed that a pure strategy Nash equilibrium always exists and the price of stability of this game is at most the nth harmonic number in directed graphs. For undirected graphs Anshelevich and others presented a tight bound on the price of stability of 4/3 for a single source and two players case. Jian Li has proved that for undirected graphs with a distinguished destination to which all players must connect the price of stability of the Shapely network design game is ${\displaystyle O(\log n/\log \log n)}$ where ${\displaystyle n}$ is the number of players. On the other hand, the price of anarchy is about ${\displaystyle n}$ in this game.

...
Wikipedia