IMG_0633.jpeg

# Algorithmic Game Theory - Summer Term 2023 ## Lecture 7: The Price of Anarchy ### 1. Selfish Routing #### Definition 1 Let $G = (V, E)$ be a graph, where each edge $e \in E$ has a cost function $c_e(x)$ that is a function of the congestion $x$ on edge $e$. #### Definition 2 Let $s, t \in V$...

# Algorithmic Game Theory - Summer Term 2023 ## Lecture 7: The Price of Anarchy ### 1. Selfish Routing #### Definition 1 Let $G = (V, E)$ be a graph, where each edge $e \in E$ has a cost function $c_e(x)$ that is a function of the congestion $x$ on edge $e$. #### Definition 2 Let $s, t \in V$ be two terminals with a rate of traffic $r$ that needs to be routed from $s$ to $t$. #### Definition 3 A flow $f$ from $s$ to $t$ is a function that assigns each path $P$ from $s$ to $t$ a non-negative flow rate $f_p$, such that $\sum_{P: s \rightarrow t} f_P = r$. The flow on edge $e$ is defined as $f_e = \sum_{P: e \in P} f_P$. #### Definition 4 The cost of flow $f$ is $\sum_{e \in E} f_e \cdot c_e(f_e)$. ### 2. Wardrop Equilibrium #### Definition 5 A flow $f$ is in Wardrop equilibrium if all flow-carrying paths have the same cost, and all other paths have a higher cost. #### Definition 6 The cost of path $P$ is $\sum_{e \in P} c_e(f_e)$. Formally, for all paths $P_1, P_2$ from $s$ to $t$: If $f_{P_1} > 0$, then $\sum_{e \in P_1} c_e(f_e) \le \sum_{e \in P_2} c_e(f_e)$. ### 3. Social Optimum #### Definition 7 A flow $f^*$ is a social optimum if it minimizes the total cost, i.e., $f^* = \text{argmin}_f \sum_{e \in E} f_e \cdot c_e(f_e)$. ### 4. Price of Anarchy #### Definition 8 The price of anarchy (PoA) is the ratio between the cost of the Wardrop equilibrium and the cost of the social optimum: $PoA = \frac{\text{Cost of Wardrop Equilibrium}}{\text{Cost of Social Optimum}}$ ### 5. Braess's Paradox #### Example Consider the following network: ``` r s ----> a | ^ | | v | b ----> t ``` Edge costs: - $c_{sa}(x) = x$ - $c_{ab}(x) = 0$ - $c_{bt}(x) = x$ - $c_{sb}(x) = c_{at}(x) = 1$ If $r = 1$, the social optimum is to split the flow evenly between the paths $s \rightarrow b \rightarrow t$ and $s \rightarrow a \rightarrow t$. The cost of the social optimum is $1 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} = 2 \cdot 1 \cdot \frac{1}{2} + 2 \cdot \frac{1}{2} \cdot 1 = 1.5 + 0.5 = 2$ In Wardrop equilibrium, all traffic takes the path $s \rightarrow a \rightarrow b \rightarrow t$, with a cost of $1 + 0 + 1 = 2$. If we remove the edge from a to b. The cost of the social optimum is $1$, achieved by sending all traffic via $s \rightarrow b \rightarrow t$ or $s \rightarrow a \rightarrow t$. In Wardrop equilibrium, all traffic takes the path $s \rightarrow b \rightarrow t$, with a cost of $1 + 1 = 2$ or $s \rightarrow a \rightarrow t$, with a cost of $1 + 1 = 2$. ### 6. Bounding the Price of Anarchy #### Theorem 1 If the cost functions $c_e(x)$ are linear, i.e., $c_e(x) = a_e x + b_e$ with $a_e, b_e \ge 0$, then the price of anarchy is at most $\frac{4}{3}$. #### Proof Let $f$ be the Wardrop equilibrium flow and $f^*$ be the social optimum flow. We want to show that $\sum_{e \in E} f_e \cdot c_e(f_e) \le \frac{4}{3} \sum_{e \in E} f^*_e \cdot c_e(f^*_e)$. We have $\sum_{e \in E} f_e \cdot c_e(f_e) = \sum_{e \in E} f_e \cdot (a_e f_e + b_e) = \sum_{e \in E} a_e f_e^2 + b_e f_e$. Since $f$ is a Wardrop equilibrium, if $f^*_P > 0$ then $\sum_{e \in P} c_e(f_e) \le \sum_{e \in P} c_e(f^*_e)$. Thus, $\sum_{e \in E} f^*_e c_e(f_e) \ge \sum_{e \in E} f_e c_e(f_e)$ because $f$ is the equilibrium flow. We consider $\sum_{e \in E} f^*_e c_e(f_e) = \sum_{e \in E} f^*_e (a_e f_e + b_e) = \sum_{e \in E} a_e f^*_e f_e + b_e f^*_e$. We want to bound this term by $\sum_{e \in E} f^*_e c_e(f^*_e)$. We use the fact that $f_e c_e(f_e) - f^*_e c_e(f^*_e) \le \frac{1}{4} \frac{c_e(f_e)^2}{a_e}$. Therefore: $\sum_{e \in E} f_e c_e(f_e) \le \frac{4}{3} \sum_{e \in E} f^*_e c_e(f^*_e)$. Which proves the price of anarchy is at most $\frac{4}{3}$. ### 7. Tolls #### Definition 9 A toll is a fee that is added to the cost of an edge. #### Theorem 2 If we add tolls to the edges such that the cost of each edge is equal to the marginal cost, then the social optimum flow is also a Wardrop equilibrium. #### Proof Let $f^*$ be the social optimum flow. The marginal cost of edge $e$ is $c_e(f^*_e) + f^*_e \cdot c'_e(f^*_e)$. If we add tolls $t_e = f^*_e \cdot c'_e(f^*_e)$ to the edges, then the cost of edge $e$ becomes $c_e(x) + t_e = c_e(x) + f^*_e \cdot c'_e(f^*_e)$. The total cost is now $\sum_{e \in E} f_e (c_e(f_e) + f^*_e \cdot c'_e(f^*_e))$, where $f$ is a flow with tolls. The social optimum flow minimizes $\sum_{e \in E} f_e c_e(f_e)$. Since $f^*$ is the social optimum, if $f^*_P > 0$, then $\sum_{e \in P} c_e(f^*_e) \le \sum_{e \in P} c_e(f_e)$ for any other flow $f$. With tolls, the cost of a path $P$ is $\sum_{e \in P} c_e(f^*_e) + f^*_e \cdot c'_e(f^*_e)$. Since $f^*$ minimizes the cost, it is also a Wardrop equilibrium.