Algorithmic Game Theory: Social Optima & Price of Anarchy

• Study notes for Algorithmic Game Theory, covering social optima, price of anarchy (PoA), and Braess' paradox.

Social Cost

• Is a function evaluating the overall quality of a game's outcome
• Maps strategy combinations to real numbers, indicating overall cost or inefficiency: $SC: \prod_{i \in N} S_i \rightarrow \mathbb{R}$
• $S_i$ represents player i's strategy set
• Lower social cost indicates a better outcome.

Social Optimum

• Is the outcome that minimizes the social cost function
• Denoted as $s^$, it satisfies $SC(s^) \leq SC(s)$ for all possible outcomes $s$
• Mathematically: $s^* \in \arg \min_{s \in \prod_{i \in N} S_i} SC(s)$

Price of Anarchy (PoA)

• Quantifies the inefficiency of selfish behavior in a game
• Calculated as the ratio of the social cost of a worst-case Nash equilibrium to the social cost of a social optimum: $PoA = \frac{\max_{s \in NE} SC(s)}{SC(s^*)}$
• $NE$ is the set of Nash equilibria, and $s^*$ is a social optimum
• Always greater than or equal to 1 ($PoA \geq 1$).

Selfish Routing Example

• Illustrates PoA using a network with two nodes (start node $s$, target node $t$) and two parallel links
• $r$ agents route traffic from $s$ to $t, x_1$ is traffic fraction on link 1, $x_2$ on link 2 ($x_1 + x_2 = 1$)
• Link 1 latency: $l_1(x_1) = x_1$, Link 2 latency: $l_2(x_2) = 1$
• Social cost: $SC(x_1, x_2) = x_1 \cdot l_1(x_1) + x_2 \cdot l_2(x_2) = x_1^2 + x_2 = x_1^2 + (1 - x_1)$
• Minimizing social cost yields social optimum at $x_1 = x_2 = \frac{1}{2}$ with $SC = \frac{3}{4}$
• Nash equilibrium occurs when $l_1(x_1) = l_2(x_2) \implies x_1 = 1$, with $SC = 1$
• The PoA in this scenario is $\frac{4}{3}$.

Braess' Paradox

• Is the phenomenon where adding a resource to a network worsens overall performance.

Braess' Paradox Example

• A network of four nodes ($s, w, v, t$) and two paths: $s \rightarrow w \rightarrow t$ and $s \rightarrow v \rightarrow t$
• Link latencies: $l_{sw}(x) = x$, $l_{vt}(x) = x$, $l_{sv}(x) = 1$, $l_{wt}(x) = 1$.
• Adding zero-latency link $w \rightarrow v$ changes traffic flow

Without Link $w \rightarrow v$

• Nash equilibrium results in half the traffic using each path, with total latency 1.5
• Total social cost is 1.5

With Link $w \rightarrow v$

• All traffic shifts to path $s \rightarrow w \rightarrow v \rightarrow t$, increasing the total latency to 2
• Total social cost increases to 2
• Adding the link worsens overall performance

Conclusion

• Social optima and PoA help evaluate game outcome efficiency
• Braess' paradox demonstrates how adding resources can negatively impact performance due to strategic behavior
• Highlights the importance of aligning individual incentives with overall social welfare in system design.

Study notes covering social optima and price of anarchy. It defines and explains social cost functions in game theory, social optimum as the outcome that minimizes social cost, and price of anarchy (PoA) as the ratio of the social cost.