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), which is the ratio between the worst objective function value of one of its equilibria and that of an optimal outcome.

In the following prisoner’s dilemma game, since there is a single equilibrium

On this example which is a version of the battle of sexes game, there are two equilibrium points,

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 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

On the other hand, the price of anarchy is about

Network design games have a very natural motivation for the Price of Stability.

Consider the following network design game.

edge, the social cost is

edge is a Nash equilibrium as well.

at equilibrium, and switching to the other edge raises his cost to

Here is a pathological game in the same spirit for the Price of Stability, instead.

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

Once this has happened, it will be in player 2's interest to switch to the

Eventually, the agents will reach the Nash equilibrium of paying for their own edge.

This allocation has social cost

Note that by design, network design games are congestion games.

Therefore, they admit a potential function

[Theorem 19.13 from Reference 1] Suppose there exist constants

is a Nash equilibrium, so Now recall that the social cost was defined as the sum of costs over edges, so We trivially have

, so we may invoke the theorem for an upper bound on the price of stability.