Price of Stability

The best-case ratio between the social cost of a Nash equilibrium and the social optimum.

Ask the Game theory assistant 1 min read · Updated September 9, 2026

Definition

$\mathrm{PoS}(G)=\dfrac{\min_{s\in NE(G)} \mathrm{cost}(s)}{\min_{s}\mathrm{cost}(s)}$ — the ratio of the best Nash equilibrium to the social optimum.

Always $\ge 1$ and $\le \mathrm{PoA}$ . It measures whether there exists an acceptably efficient equilibrium.

Intuition

While PoA looks at worst-case selfish outcomes, PoS checks if coordination failure is guaranteed or avoidable.

A low PoS means that even if agents play selfishly, the best equilibrium may still be near-efficient.

Worked example

For network design (Shapley cost-sharing), PoS is $O(\log n)$ while PoA can be as high as $n$ (Anshel`evich et al. 2004).

In congestion games with linear costs, PoS $= 1$ (the best equilibrium is optimal).

The math

Anshel`evich et al. (2008) gave the first general PoS bounds for network cost-sharing games.

The smoothness framework can bound PoA but not always PoS; potential methods are often used.

Where it is used

Network design, cost-sharing, and mechanism design where the designer can recommend an equilibrium.

Complements PoA in the efficiency analysis of games.

More in Game theory

Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.