IMG_8801.jpeg

# Algorithmic Game Theory ## What is Game Theory? * Study of multi-agent decision problems * Also viewed as a language/framework for discussing multi-agent problems ## Selfish Routing ### Model * A directed graph $G(V, E)$ * $r$ source-destination pairs $(s_i, t_i)$ * $r_i$: rate of...

# Algorithmic Game Theory ## What is Game Theory? * Study of multi-agent decision problems * Also viewed as a language/framework for discussing multi-agent problems ## Selfish Routing ### Model * A directed graph $G(V, E)$ * $r$ source-destination pairs $(s_i, t_i)$ * $r_i$: rate of traffic from $s_i$ to $t_i$ * Each edge $e$ has a cost/latency function $l_e(x)$ which is a function of the flow $x$ on edge $e$. * A flow vector $f$ specifies how the traffic from each $(s_i, t_i)$ pair is routed. * $f_p$: flow on path $p$ * Cost of path $p = \sum_{e \in p} l_e(f_e)$ * The cost of the flow is the average latency experienced by the traffic: $$ C(f) = \sum_{p \in P} f_p \cdot l_p(f) = \sum_{e \in E} f_e \cdot l_e(f_e) $$ ### Wardrop Equilibrium A flow is at Wardrop equilibrium if all traffic from $s_i$ to $t_i$ is routed along paths of minimum latency. **Definition:** A flow $f$ is at Wardrop equilibrium if for every source destination pair $(s_i, t_i)$ and every pair of paths $p, p'$ between them with $f_p > 0$, it is the case that $l_p(f) \le l_{p'}(f)$. ### Social Optimality Socially optimal flow is the flow that minimizes the total latency. $$ f^* = argmin_f C(f) $$ ### Example Two parallel links with latency functions: * $l_1(x) = 1$ * $l_2(x) = x$ Rate of traffic is 1. Wardrop Equilibrium: * Flow on link 1: 1/2 * Flow on link 2: 1/2 * Cost: $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$ Social Optimum: * Flow on link 1: 0 * Flow on link 2: 1 * Cost: $1 \cdot 1 = 1$ ### Price of Anarchy **Definition:** Price of anarchy is the ratio between the cost of a Wardrop equilibrium and the cost of a social optimum. $$ PoA = \frac{C(f)}{C(f^*)} $$ Where $f$ is a Wardrop equilibrium and $f^*$ is a social optimum.