The Price of Anarchy

The Price of Anarchy (PoA) measures how inefficient selfish routing is compared to centralized routing. For a given congestion game, let $C(\mathrm{UE})$ denote the total system cost at the user equilibrium and $C(\mathrm{SO})$ denote the total system cost at the system optimum. The Price of Anarchy is

$$\mathrm{PoA} = \dfrac{C(\mathrm{UE})}{C(\mathrm{SO})}.$$

Since the system optimum minimizes total cost by definition, $C(\mathrm{UE}) \geq C(\mathrm{SO})$, so $\mathrm{PoA} \geq 1$. A value of $\mathrm{PoA} = 1$ means selfish routing happens to be optimal; a larger PoA means more system-wide efficiency is lost to selfish behavior.

For example, suppose the total delay across all flights on a city pair is $540$ aircraft-minutes under user-equilibrium routing, while a centralized flow manager could achieve $450$ aircraft-minutes. Then

$$\mathrm{PoA} = \dfrac{540}{450} = \dfrac{6}{5} = 1.2,$$

so selfish routing produces $20\%$ more delay than is strictly necessary.