Price of stability

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.

• ${\displaystyle n}$ players;
• Each player ${\displaystyle i}$ aims to connect ${\displaystyle s_{i}}$ to ${\displaystyle t_{i}}$ on a directed graph ${\displaystyle G=(V,E)}$;
• The strategies ${\displaystyle P_{i}}$ for a player are all paths from ${\displaystyle s_{i}}$ to ${\displaystyle t_{i}}$ in ${\displaystyle G}$;
• Each edge has a cost ${\displaystyle c_{i}}$;
• 'Fair cost allocation': When ${\displaystyle n_{e}}$ players choose edge ${\displaystyle e}$, the cost ${\displaystyle \textstyle d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}}$ is split equally among them;
• The player cost is ${\displaystyle \textstyle C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}}$
• The social cost is the sum of the player costs: ${\displaystyle \textstyle SC(S)=\sum _{i}C_{i}(S)=\sum _{e\in S}n_{e}{\frac {c_{e}}{n_{e}}}=\sum _{e\in S}c_{e}}$.

A network design game with ${\displaystyle \Omega (n)}$ Price of Anarchy

The price of anarchy can be ${\displaystyle \Omega (n)}$. Consider the following network design game.

Pathological Price of Stability game

Consider two different equilibria in this game. If everyone shares the ${\displaystyle 1+\varepsilon }$ edge, the social cost is ${\displaystyle 1+\varepsilon }$. This equilibrium is indeed optimal. Note, however, that everyone sharing the ${\displaystyle n}$ edge is a Nash equilibrium as well. Each agent has cost ${\displaystyle 1}$ at equilibrium, and switching to the other edge raises his cost to ${\displaystyle 1+\varepsilon }$.

Here is a pathological game in the same spirit for the Price of Stability, instead. Consider ${\displaystyle n}$ players, each originating from ${\displaystyle s_{i}}$ and trying to connect to ${\displaystyle t}$. The cost of unlabeled edges is taken to be 0.

The optimal strategy is for everyone to share the ${\displaystyle 1+\varepsilon }$ edge, yielding total social cost ${\displaystyle 1+\varepsilon }$. However, there is a unique Nash for this game. Note that when at the optimum, each player is paying ${\displaystyle \textstyle {\frac {1+\varepsilon }{n}}}$, and player 1 can decrease his cost by switching to the ${\displaystyle \textstyle {\frac {1}{n}}}$ edge. Once this has happened, it will be in player 2's interest to switch to the ${\displaystyle \textstyle {\frac {1}{n-1}}}$ edge, and so on. Eventually, the agents will reach the Nash equilibrium of paying for their own edge. This allocation has social cost ${\displaystyle \textstyle 1+{\frac {1}{2}}+\cdots +{\frac {1}{n}}=H_{n}}$, where ${\displaystyle H_{n}}$ is the ${\displaystyle n}$^th harmonic number, which is ${\displaystyle \Theta (\log n)}$. Even though it is unbounded, the price of stability is exponentially better than the price of anarchy in this game.

Note that by design, network design games are congestion games. Therefore, they admit a potential function ${\displaystyle \textstyle \Phi =\sum _{e}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}}$.

Theorem. [Theorem 19.13 from Reference 1] Suppose there exist constants ${\displaystyle A}$ and ${\displaystyle B}$ such that for every strategy ${\displaystyle S}$,

${\displaystyle A\cdot SC(S)\leq \Phi (S)\leq B\cdot SC(S).}$

Then the price of stability is less than ${\displaystyle B/A}$

Proof. The global minimum ${\displaystyle NE}$ of ${\displaystyle \Phi }$ is a Nash equilibrium, so

${\displaystyle SC(NE)\leq 1/A\cdot \Phi (NE)\leq 1/A\cdot \Phi (OPT)\leq B/A\cdot SC(OPT).}$

Now recall that the social cost was defined as the sum of costs over edges, so

${\displaystyle \Phi (S)=\sum _{e\in S}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}=\sum _{e\in S}c_{e}H_{n_{e}}\leq \sum _{e\in S}c_{e}H_{n}=H_{n}\cdot SC(S).}$

We trivially have ${\displaystyle A=1}$, and the computation above gives ${\displaystyle B=H_{n}}$, so we may invoke the theorem for an upper bound on the price of stability.