The Price Of Anarchy And Scalable Resource Allocation Mechanisms

Step 1: First-order conditions for each user. $P_r$ is concave in $w_r$, so with $d_r = w_r/\mu$, $(w,\mu)$ is a competitive equilibrium iff

Step 2: These are SYSTEM’s KKT conditions. The Lagrangian of SYSTEM yields exactly (21.8)–(21.10), with $\mu$ as the multiplier on capacity.

Step 3: Existence. SYSTEM has a solution, whose multiplier supplies $\mu$. Set $w_r = \mu d_r$.

∎

Step 1: At least two bids are positive at any equilibrium, from (21.11) (Exercise 17.5). So each $Q_r$ is strictly concave and continuous in $w_r$, and first-order conditions characterize equilibrium:

where $W = \sum_s w_s$. (21.18–21.19)

Step 2: Change variables. Let $\rho = W/C$ and $d_r = w_r/\rho$. Then $1 - w_r/W = 1 - d_r/C$, so the conditions read

Step 3: Recognize GAME. These are (21.8)–(21.10) with $\hat U_r$ in place of $U_r$. Each $\hat U_r$ is strictly concave on $[0,C]$, so the conditions are sufficient for optimality in GAME, with multiplier $\rho$.

Step 4: Uniqueness. GAME has a unique optimum (strictly concave objective, compact set), and the equilibrium bids are recovered as $w_r = \rho\, d_r$.

∎

Step 1: Only $d < \bar d$ matters. If $d \ge \bar d$, then $U(d) - \hat U'(d)(d - \bar d) \ge U(d) - U'(d)(d-\bar d) \ge U(\bar d)$ by concavity and $\hat U' \le U'$, so the quotient is $\ge 1$.

Step 2: Chain for $d < \bar d$.

• (a) $\bar d \le C$ gives $1 - d/C \ge 1 - d/\bar d$, and concavity gives $U'(d)(\bar d - d) \ge U(\bar d) - U(d)$.
• (b) Rewrite the left side as $\frac{d}{\bar d}U(d) + (1 - \frac{d}{\bar d})U(\bar d)$. By concavity and $U(0) \ge 0$, $U(d) \ge \frac{d}{\bar d}U(\bar d)$.
• (c) $x^2 - x + 1 \ge 3/4$, with the minimum at $x = 1/2$.

∎

Step 1: Construct the instance. Fix $U$ and $d < \bar d$, and set $C = \bar d$. User 1 has $U_1 = U$. Users $2..R$ are linear with slope $\hat U'(d) = U'(d)(1 - d/C)$.

Step 2: Optimum. Giving everything to user 1 is feasible, so $\mathrm{OPT} \ge U(\bar d)$.

Step 3: Equilibrium as $R \to \infty$. The equilibrium is unique and symmetric among users $2..R$, so each small user’s share $\to 0$. Their equilibrium condition forces the price $\rho \to \hat U'(d)$. User 1’s condition $\hat U_1'(d_1) = \rho$ then gives $d_1 \to d$. The small users share $\bar d - d$, each worth $\hat U'(d)$ per unit.

Step 4: Limiting ratio. Nash welfare $\to U(d) + \hat U'(d)(\bar d - d)$, so the ratio is at most the quotient in (21.24). Hence the price of anarchy gets arbitrarily close to $\beta$.

Step 5: Evaluate. $U(x) = x$, $d = 1/2$, $\bar d = 1$ gives $\frac{1/2 + \frac12\cdot\frac12}{1} = \frac34$. Together with Step A, $\beta = 3/4$.

∎

• (a) Definition of $\beta$, applied user by user with $d = d^G_s$ and $\bar d = d^S_s$.
• (b) Corollary 21.3 with $\bar d = d^S$: the sum of linear terms is $\le 0$.

The key step: exactly as in routing, the variational inequality lets per-user inequalities, each blind to the rest of the system, sum to a system-wide bound.

∎

Step 1: Price-taking payoffs are concave. Uniqueness of the clearing price for every $C$ forces $D$ to be strictly monotone in $p$, with a consistent direction across $\theta$. Fix $\mu,\theta > 0$ and let capacity grow, $C^R = R\,D(\mu,\theta)$, with users $2..R$ bidding $\theta$. The clearing price $\to\mu$ whatever user 1 bids. So user 1’s price-anticipating payoff, concave by condition (2), converges to its price-taking payoff, which must therefore be concave. Large markets turn anticipators into price takers.

Step 2: $D$ is linear in $\theta$. Apply Step 1 with linear utilities of very large slope, which forces $D$ concave in $\theta$, and very small slope, which forces it convex. So $D(p,\cdot)$ is affine. Conditions (3) and (4) kill the intercept and make the slope positive: $D = \theta/B(p)$ with $B > 0$.

Step 3: Competitive equilibria exist and are efficient. By expressiveness, a price taker picks its optimal quantity and then a $\theta$ to express it. So the conditions are (21.8)–(21.10), sufficient by Step 1. For existence, take SYSTEM’s solution $d^S$ with multiplier $\mu$ and set $\theta_r = d_r^S B(\mu)$.

Step 4: Allocation and payment are separately concave/convex. The same large/small linear-slope trick applied to condition (2) shows $D(p_D(\theta),\theta_r)$ is concave and the payment $w_r(\theta) = p_D(\theta)D(p_D(\theta),\theta_r)$ is convex in $\theta_r$.

Step 5: $B$ is concave, increasing and invertible. $B$ is onto $(0,\infty)$, because $\sum\theta_r/C$ takes all positive values, and one-to-one, by uniqueness of the clearing price. Let $\Gamma = B^{-1}$. The payment

is convex in $\theta_r$. Taking $\theta_{-r} = 0$ shows $\Gamma$ is convex, and a limit $\theta_r\to0$ shows it is strictly increasing. So $B$ is concave and strictly increasing.

∎

$\theta \ge 0$ is a Nash equilibrium iff at least two components are positive, and there are $d \ge 0$ with $\sum_r d_r = C$ and $\mu > 0$ with $\theta_r = \mu\,d_r$ and

Then $\mu = \sum_r\theta_r/C$, $\Gamma(\mu) = p_D(\theta)$, and the equilibrium is unique.

Derivation. With $d_r = C\theta_r/\Theta$ and $w_r = \Gamma(\mu)\,d_r$, the first-order condition $U_r'\,\partial d_r/\partial\theta_r = \partial w_r/\partial\theta_r$ uses $\partial d_r/\partial\theta_r = \frac1\mu(1 - \frac{d_r}{C})$ and $\partial w_r/\partial\theta_r = \frac{\Gamma'(\mu)}{C}d_r + \frac{\Gamma(\mu)}{\mu}(1 - \frac{d_r}{C})$. Multiply by $\mu$.

Check. For proportional allocation, $\Gamma(\mu) = \mu$, and the right side collapses to $\mu$, recovering (21.20).

The chapter omits the rest of the proof and refers to Johari (2004).

∎

Step 7: Build the bad instance. Take $C = 1$ and fix $\mu$. User 1 is linear with slope $A > \Gamma(\mu)$. From (21.31),

Users $2..R$ are linear with common slope

which is valid (and $\alpha \le A$) once $R$ is large (21.35). As $R\to\infty$, $\alpha\to\Gamma(\mu)$, and OPT gives all capacity to user 1 (value $AC$). The limiting ratio is $d_1 + \frac{\Gamma(\mu)}{A}(1 - d_1)$. (21.36)

Set $x = \Gamma(\mu)/A\in(0,1)$ and let the elasticity be $\Psi(\mu) = \mu\Gamma'(\mu)/\Gamma(\mu) \ge 1$ (by convexity of $\Gamma$ with $\Gamma(0^+) = 0$). The ratio becomes $$F(x;\mu) = \frac{(1-x)^2}{1 + (\Psi(\mu) - 1)x} + x. \tag{21.37}$$ $F$ is strictly convex in $x$. Its minimum is

attained at $x = 1/(\sqrt\Psi + 1)$. $G$ is continuous and strictly decreasing from $G(1) = 3/4$, so the worst case uses the $\mu$ maximizing $\Psi(\mu)$, and $\rho(D) \le 3/4$ always.

Step 8: Only linear $B$ reaches 3/4. For proportional allocation, $\Gamma(\mu) = \mu$, so $\Psi\equiv1$ and $\rho = 3/4$ (Theorem 21.4). If $B$ is nonlinear, then $\sup_\mu\Psi(\mu) > 1$, so $G < 3/4$ on some instance.

∎

Step 1: Effective payoff. $h_r$ doesn’t depend on $\theta_r$, so user $r$ maximizes $U_r(d_r(\theta)) + \sum_{s\ne r}U(d_s(\theta);\theta_s)$ (21.45). The optimum of (21.44) is an upper bound on this.

Step 2: Sufficiency. If (21.44) holds, $r$ already attains the upper bound, so no deviation helps.

Step 3: Necessity. Suppose (21.44) fails for $r$, and let $d^*$ solve it. $d^*$ satisfies first-order conditions involving only the marginals $U_r'(d_r^*)$ and $U'(d_s^*;\theta_s)$. By Assumption 2(ii), $r$ can pick $\theta'_r$ with $U'(d_r^*;\theta'_r) = U_r'(d_r^*)$. Then $d^*$ satisfies the optimality conditions of (21.41) under $(\theta'_r,\theta_{-r})$, and uniqueness gives $d(\theta'_r,\theta_{-r}) = d^*$. User $r$‘s payoff rises strictly, so $\theta$ is not an equilibrium.

The key step: matching one marginal value is enough to steer the mechanism to any allocation you like. That is why a scalar suffices.

∎

Step 1: Every allocation is positive. In user $r$‘s problem (21.44), the true marginal at 0 is infinite, so $d_r(\theta) > 0$.

Step 2: Marginals line up. With every user interior, optimality of $d(\theta)$ in user $r$‘s problem gives $U_r'(d_r) = U'(d_s;\theta_s)$ for all $s\ne r$. Optimality in the mechanism’s own problem (21.41) equalizes the declared marginals. Hence all true marginals $U_r'(d_r)$ are equal.

Step 3: Conclude. Equal marginals and full allocation are sufficient for SYSTEM.

∎