Price of stability
||This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (January 2014)|
||This article may be too technical for most readers to understand. (January 2014)|
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.
Background and milestones
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 where is the number of players. On the other hand, the price of anarchy is about in this game.
Network design games
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.
- Each player aims to connect to on a directed graph ;
- The strategies for a player are all paths from to in ;
- Each edge has a cost ;
- 'Fair cost allocation': When players choose edge , the cost is split equally among them;
- The player cost is
- The social cost is the sum of the player costs: .
Price of anarchy
The price of anarchy can be . Consider the following network design game.
Consider two different equilibria in this game. If everyone shares the edge, the social cost is . This equilibrium is indeed optimal. Note, however, that everyone sharing the edge is a Nash equilibrium as well. Each agent has cost at equilibrium, and switching to the other edge raises his cost to .
Lower bound on price of stability
Here is a pathological game in the same spirit for the Price of Stability, instead. Consider players, each originating from and trying to connect to . The cost of unlabeled edges is taken to be 0.
The optimal strategy is for everyone to share the edge, yielding total social cost . However, there is a unique Nash for this game. Note that when at the optimum, each player is paying , and player 1 can decrease his cost by switching to the . edge. Once this has happened, it will be in player 2's interest to switch to the edge, and so on. Eventually, the agents will reach the Nash equilibrium of paying for their own edge. This allocation has social cost , where is the th harmonic number, which is . Even though it is unbounded, the price of anarchy 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 .
Theorem. Suppose there exist constants and such that for every strategy ,
Then the price of stability is less than
Proof. The global minimum of is a Nash equilibrium, so
Now recall that the social cost was defined as the sum of costs over edges, so
We trivially have , and the computation above gives , so we may invoke the theorem for an upper bound on the price of stability.
- Algorithmic Game Theory by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds), Cambridge University Press, 2007. ISBN 0521872820
- L. Agussurja and H. C. Lau. The Price of Stability in Selfish Scheduling Games. Web Intelligence and Agent Systems: An International Journal, 9:4, 2009.
- Jian Li. An upper bound on the price of stability for undirected Shapely network design games. Information Processing Letters 109 (15), 876-878, 2009.