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 also talk about the price of anarchy (PoA).
Examples.
Another way of expressing PoS is:
In the following prisoner’s dilemma game, since there is a single equilibrium formula_2 we have PoS = PoA = 1/2.
On this example which is a version of the battle of sexes game, there are two equilibrium points, formula_3 and formula_2, 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 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 formula_5 where formula_6 is the number of players. On the other hand, the price of anarchy is about formula_6 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.
Price of anarchy.
The price of anarchy can be formula_23. Consider the following network design game.
Consider two different equilibria in this game. If everyone shares the formula_24 edge, the social cost is formula_24. This equilibrium is indeed optimal. Note, however, that everyone sharing the formula_6 edge is a Nash equilibrium as well. Each agent has cost formula_27 at equilibrium, and
switching to the other edge raises his cost to formula_28.
Lower bound on price of stability.
Here is a pathological game in the same spirit for the Price of Stability, instead.
Consider formula_6 players, each originating from formula_10 and trying to connect
to formula_31. The cost of unlabeled edges is taken to be 0.
The optimal strategy is for everyone to share the formula_28 edge, yielding
total social cost formula_33. However, there is a unique Nash for this game.
Note that when at the optimum, each player is paying formula_34, and player 1 can decrease his cost by switching to the formula_35 edge. Once this has happened, it will be in player 2's interest to switch to the formula_36 edge, and so on. Eventually, the agents will reach the Nash equilibrium of paying for their own edge. This allocation has social cost formula_37, where formula_38 is the formula_6th harmonic number, which is formula_40. Even though it is unbounded, the price of stability is exponentially better than the price of anarchy in this game.
Upper bound on price of stability.
Note that by design, network design games are congestion games.
Therefore, they admit a potential function formula_41.
Theorem. [Theorem 19.13 from Reference 1] Suppose there exist constants formula_42 and formula_43
such that for every strategy formula_44,
Then the price of stability is less than formula_46
"Proof." The global minimum formula_47 of formula_48 is a Nash
equilibrium, so
Now recall that the social cost was defined as the sum of costs over edges, so
We trivially have formula_51, and the computation above gives formula_52, so we may invoke the theorem for an upper bound on the price of stability.