../

2026-11-15 Online Opt Scribe

$\newcommand{\E}{\mathbb{E}}$

Price of anarchy and smooth games

So far we have let players play for their own selfish benefit. This has resulted in numerous equilibria. One might ponder if this style of play might be worse for the society as a whole. Would the cumulative cost be lower if there was some centralized planning? Are we paying a cost by letting players go wild? This is captured by Price of Anarchy (PoA)

Definition 1: PoA for Cost minimization games

$$\begin{gather*} \text{PoA} = \frac{\max_{\sigma\in\text{Eq}} C(\sigma)}{\min_{a} C(a)} \end{gather*}$$

Where we define $C(a) = \sum_j c_j(a)$

Similarly we can define it for a Utility maximization games as well

Definition 2: PoA for Utility Maximization game

$$\begin{gather*} \text{PoA} = \frac{\max_a U(a)}{\min_{a\in\text{Eq}} U(\sigma)} \end{gather*}$$

Where we define $U(a) = \sum_j u_j(a)$

We define $C(\sigma) = \E_{a\sim\sigma}[C(a)]$

Motivation

You can decipher from the way we’ve written these equations that there is some cost to allowing anarchy. If we are the government or some planner we obviously want everyone to play $\min_a C(a)$.

Smooth games

As we live in the land of the free, we shan’t utter the phrase centralized planning. But we also don’t absolute anarchy to the point of a zero-sum all-player game. It would be nice if this cost could be bounded. Smooth games are such special games where we can bound PoA.

Definition 3: Definition

A cost minimization game is a $(\lambda, \mu)$-smooth, $\lambda \ge 0, \mu < 1$ if $\exists$ a strategy $a^*$ such that

$$\sum_j C_j(a^*_j, a_{-j}) \le \lambda C(a^*) + \mu C(a)$$

for any action profile $a$

Theorem 4: Theorem

For any $(\lambda, \mu)$-smooth game

$$\text{PoA}(\text{CCE})\le \frac{\lambda}{1-\mu}$$

We only give the theorem in terms of CCE as $NE\subseteq CE \subseteq CCE \implies \text{PoA}(NE)\le \text{PoA}(CE)\le \text{PoA}(CCE)$

Proof

Let $\sigma$ be some CCE of a $(\lambda, \mu)$-smooth game

By its smoothness we know that

$$ \sum_j C(a^*_j, a_{-j}) \le \lambda C(a^*) + \mu C(a) $$

Let us pick $a\sim\lambda$ and convert all the $C(a)$ to be expectations

$$ \E_{a\sim\sigma}[\sum_j C(a^*_j, a_{-j})] \le \lambda C(a^*) + \mu \E_{a\sim\sigma}[C(a)] $$

As $\sigma$ is a CCE

$$ \begin{align*} \E_{a\sim\sigma}[C(a)] \le \E_{a\sim\sigma}[\sum_j C(a^*_j, a_{-j})] &\le \lambda C(a^*) + \mu\E_{a\sim\sigma}[ C(a)]\\ \E_{a\sim\sigma}[C(a)] &\le \lambda C(a^*) + \mu \E_{a\sim\sigma}[C(a)]\\ \E_{a\sim\sigma}[C(a)] - \mu \E_{a\sim\sigma}[C(a)] &\le \lambda C(a^*) \\ \E_{a\sim\sigma}[C(a)](1 - \mu) &\le \lambda C(a^*) \\ \frac{\E_{a\sim\sigma}[C(a)]}{C(a^*)}&\le \frac{\lambda}{(1 - \mu)} \\ \text{PoA}(CCE) &\le \frac{\lambda}{(1 - \mu)} \\ \end{align*} $$

Corollary

If all the players are playing a No-Regret algorithm in a $(\lambda, \mu)$-smooth game then the average cost of each player will be

$$ \frac{1}{T}\sum_t \sum_j c_j(a_t) \le \frac{\lambda}{1 - \mu} \min_a\sum_j c_j(a) + o(1) $$

The LHS has a time component. We know that the average play of NR converges to CCE. So we can think of a single round of this games played with the strategy given by repeated play of NR.

TODO(dbk)