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 also talk about the price of anarchy (PoA), which is the ratio between the worst objective function value of one of its equilibria and that of an optimal outcome.
Examples Another way of expressing PoS is:
PoS = value of best Nash equilibrium value of optimal solution , PoS ≥ 0. {\displaystyle {\text{PoS}}={\frac {\text{value of best Nash equilibrium}}{\text{value of optimal solution}}},\ {\text{PoS}}\geq 0.}
In particular, if the optimal solution is a Nash equilibrium, then the PoS is 1. In the following prisoner’s dilemma game, since there is a single equilibrium ( B , R ) {\displaystyle (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 ) {\displaystyle (T,L)} and ( B , R ) {\displaystyle (B,R)} , with values 3 and 15, respectively. The optimal value is 15. Thus, PoS = 1 while PoA = 1/5.
Background and milestones The price of stability was first studied by A. Schulz and N. Stier-Moses, while the term was coined by E. Anshelevich et al. Schulz and Stier-Moses focused on equilibria in a selfish routing game in which edges have capacities. Anshelevich et al. studied network design games and showed that a pure strategy Nash equilibrium always exists with the price of stability in this game being at most the nth harmonic number in directed graphs. For undirected graphs, Anshelevich et al. 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 O ( log n / log log n ) {\displaystyle O(\log n/\log \log n)} where n {\displaystyle n} is the number of players. On the other hand, the price of anarchy is about n {\displaystyle n} in this game.
Network design games
Setup Network design games have a very natural motivation for the Price of Stability. In these games, the Price of Anarchy can be much worse than the Price of Stability. Consider the following game.
n {\displaystyle n} players; Each player i {\displaystyle i} aims to connect s i {\displaystyle s_{i}} to t i {\displaystyle t_{i}} on a directed graph G = ( V , E ) {\displaystyle G=(V,E)} ; The strategies P i {\displaystyle P_{i}} for a player are all paths from s i {\displaystyle s_{i}} to t i {\displaystyle t_{i}} in G {\displaystyle G} ; Each edge has a cost c i {\displaystyle c_{i}} ; 'Fair cost allocation': When n e {\displaystyle n_{e}} players choose edge e {\displaystyle e} , the cost d e ( n e ) = c e n e {\displaystyle \textstyle d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}} is split equally among them; The player cost is C i ( S ) = ∑ e ∈ P i c e n e {\displaystyle \textstyle C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}}
… excerpt ends here. Continue reading the full article.
