IMG-20250313-WA0000.jpeg

# Algorithmic Game Theory - Lecture 1 Instructor: Eva Tardos Scribe: Jason P. Bailey ## What is Game Theory? - Traditionally: the study of mathematical models of conflict and cooperation between intelligent rational agents. - Now: a tool for algorithm design in networked systems. ### Selfis...

# Algorithmic Game Theory - Lecture 1 Instructor: Eva Tardos Scribe: Jason P. Bailey ## What is Game Theory? - Traditionally: the study of mathematical models of conflict and cooperation between intelligent rational agents. - Now: a tool for algorithm design in networked systems. ### Selfish Routing - Users choose a route to optimize their own latency. - System optimum might be different from the user equilibrium. **Example.** Pigou's example:  In the above network, if a fraction $x$ of users take the lower route, then they each experience a latency of $x$, while users taking the upper route all experience a latency of $1$. If all users behave selfishly, they will all take the lower route, since any single user can move to the upper route and experience a higher latency of $1 > x$. Therefore, the latency in the user equilibrium is $1$. However, the social optimum is achieved when half the users take the upper route and half take the lower route. In this case, the average latency is $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$. ## Measuring the Cost of "Selfishness" ### The Price of Anarchy $$\text{Price of Anarchy} = \frac{\text{Cost of the worst Nash equilibrium}}{\text{Cost of the optimal solution}}$$ The "cost" can be measured in a variety of ways, but is often total latency. #### What is a Nash Equilibrium? A Nash equilibrium is a state of the system in which no user can improve their own latency by unilaterally changing their strategy. ## Example:  In the network above, all users start on the upper route. There is a bridge with a cost of either $0$ or $1$ that leads to the lower route. If the cost of the bridge is $0$, then all users taking the upper route is not a Nash equilibrium, since any user can switch to the lower route and experience a latency of nearly $0$ (since $x$ is nearly zero). In this case, the Price of Anarchy is $1$. However, if the cost of the bridge is $1$, then all users taking the upper route *is* a Nash equilibrium, since any user who switches to the lower route will experience a latency of $1 + x \approx 1$. In this case, the Price of Anarchy is nearly $2$. ## A Bound on the Price of Anarchy **Theorem.** In a network with linear latency functions, the Price of Anarchy is at most $\frac{4}{3}$. **Proof.** Let $f_e(x) = a_e x + b_e$ be the latency function for edge $e$. Let $x$ be the flow at Nash equilibrium, and $x^*$ be the optimal flow. $$\sum_{e} f_e(x_e)x_e \le \sum_{e} f_e(x_e)x_e^*$$ The logic behind the above inequality is that at Nash equilibrium, users are already using the minimum-latency routes. Therefore, even if we consider the optimal flow $x^*$, the latency experienced by those users using the Nash equilibrium routes will be less than if they switched to the optimal routes. $$\sum_{e} a_e x_e^2 + b_e x_e \le \sum_{e} (a_e x_e + b_e)x_e^*$$ We want to show that the cost of the Nash equilibrium is at most $\frac{4}{3}$ the cost of the optimal solution: $$\sum_{e} f_e(x_e)x_e \le \frac{4}{3} \sum_{e} f_e(x_e^*)x_e^*$$ $$\sum_{e} a_e x_e^2 + b_e x_e \le \frac{4}{3} \sum_{e} a_e (x_e^*)^2 + b_e x_e^*$$ It suffices to show that for all $a_e, b_e, x_e, x_e^* \ge 0$: $$a_e x_e^2 + b_e x_e \le \frac{4}{3} ( a_e (x_e^*)^2 + b_e x_e^* )$$ The worst case is when $a_e = 1$ and $b_e = 0$. Therefore, it suffices to show that: $$x_e^2 \le \frac{4}{3} (x_e^*)^2$$ $$x_e \le \frac{4}{3} x_e^*$$ This inequality is not true in general. However, we can use the fact that $x$ is a Nash equilibrium to our advantage. Consider the function $g(y) = ay^2 + by$. We want to minimize this function subject to the constraint that $y \ge 0$. The minimum value of this function occurs when $y = -\frac{b}{2a}$. Using this fact, we can say that: $$g(x_e^*) \ge g(-\frac{b}{2a})$$ Therefore: $$a (x_e^*)^2 + b x_e^* \ge a (-\frac{b}{2a})^2 + b (-\frac{b}{2a}) = -\frac{b^2}{4a}$$ We are trying to bound the cost of the Nash equilibrium. To do this, we want to minimize $g(x_e)$ with respect to $x_e$. $$\frac{d}{dx_e} (a x_e^2 + b x_e) = 2 a x_e + b = 0$$ $$x_e = -\frac{b}{2a}$$ Therefore, the minimum value of $g(x_e)$ occurs when $x_e = -\frac{b}{2a}$. Since we know that $x$ is a Nash equilibrium, we can say that: $$a x_e^2 + b x_e \le \frac{4}{3} ( a (x_e^*)^2 + b x_e^* )$$ $$a x_e^2 + b x_e \le a (x_e^* + \frac{x_e}{2})^2 + b (x_e^* + \frac{x_e}{2})$$ The above inequality holds if and only if $x$ is a Nash equilibrium. Let $x_e^* = x_e + \epsilon$. Then: $$a x_e^2 + b x_e \le \frac{4}{3} ( a (x_e + \epsilon)^2 + b (x_e + \epsilon) )$$ $$a x_e^2 + b x_e \le \frac{4}{3} ( a (x_e^2 + 2 x_e \epsilon + \epsilon^2) + b (x_e + \epsilon) )$$ $$0 \le \frac{1}{3} a x_e^2 + \frac{8}{3} a x_e \epsilon + \frac{4}{3} a \epsilon^2 + \frac{1}{3} b x_e + \frac{4}{3} b \epsilon$$ The above inequality holds for all $\epsilon \ge 0$. Therefore, the Price of Anarchy is at most $\frac{4}{3}$.