CS364A: Algorithmic Game Theory Lecture #14: Robust Price-of-Anarchy Bounds in Smooth Games∗

In Lecture 12 we proved that the price of anarchy (POA) in every atomic selfish routing game with affine cost functions is at most 5 2. To review, the proof had the following high-level steps. 1. Given an arbitrary pure Nash equilibrium (PNE) s, the PNE hypothesis is invoked once per player i with the hypothetical deviation si ∗, where s ∗ is an optimal outcome, to derive the inequality Ci(s) ≤ Ci(si∗, s−i) for each i. Importantly, this is the only time that the PNE hypothesis is invoked in the entire proof. 2. The k inequalities that bound individuals ’ equilibrium costs are summed over the players. The left-hand side of the resulting inequality is the cost of the PNE s; the right-hand side is a strange entangled function of s and s ∗ (involving terms of the form fef e). 3. The hardest step is to relate the entangled term ∑k i=1Ci(si ∗, s−i) generated by the previous step to the only two quantities that we care about, the costs of s and s∗. Specifically, we proved an upper bound of 5 3 cost(s∗) + 1 3 cost(s). Importantly, this step is just algebra, and is agnostic to our choices of s and s ∗ as a PNE and an optimal outcome, respectively. 4. Solve for the POA. Subtracting 1 3 · cost(s) from both sides and multiplying through by 3