IMG_2884.HEIC

# Algorithmic Game Theory ## What is Algorithmic Game Theory? * **Game Theory**: mathematical study of strategic interaction * **Algorithm Design**: how to design efficient algorithms ## Example: Selfish Routing ### The Model * A network of $n$ nodes and $m$ edges * Each edge $e$ has a...

# Algorithmic Game Theory ## What is Algorithmic Game Theory? * **Game Theory**: mathematical study of strategic interaction * **Algorithm Design**: how to design efficient algorithms ## Example: Selfish Routing ### The Model * A network of $n$ nodes and $m$ edges * Each edge $e$ has a cost function (or latency function) $l_e(x)$ which denotes the cost incurred per user on edge $e$ when $x$ users choose $e$. Typically assume that $l_e(x)$ is non-decreasing, i.e., more traffic on an edge $\implies$ higher cost. * There is a set of $k$ user populations. Users in population $i$ need to route $r_i$ amount of traffic from source $s_i$ to a destination $t_i$. ### Definition: A flow $f$ specifies how the traffic of each user population is routed. For each user population $i$, the flow $f_i$ must be routed from $s_i$ to $t_i$. ### Goal: Each user wants to minimize their own cost. ### Definition: A flow $f$ is at **Nash Equilibrium** if no user can improve its cost by changing its path ### Definition: The **social cost** of a flow $f$ is $\sum_{e\in E} f(e) \cdot l_e(f(e))$ where $f(e)$ is the total amount of flow on edge $e$. ### Question: How inefficient is a Nash Equilibrium? How does the social cost of a Nash Equilibrium compare to the social cost of an optimal flow? ### Definition: The **Price of Anarchy (PoA)** is the ratio between the social cost of the worst Nash Equilibrium and the social cost of an optimal flow. $PoA = \frac{\text{Social cost of worst NE}}{\text{Social cost of optimal flow}}$ ## Example ### ** экземпляры** * 2 nodes, 2 parallel edges * Edge 1: $l_1(x) = 1$ * Edge 2: $l_2(x) = x$ * 1 unit of traffic from $s$ to $t$ **Optimal Flow:** Route all traffic on Edge 1 Social Cost = $1 \cdot 1 = 1$ **Nash Equilibrium:** Route all traffic on Edge 2 Social Cost = $1 \cdot 1 = 1$ **Nash Equilibrium:** $\frac{1}{2}$ on Edge 1, and $\frac{1}{2}$ on Edge 2 Social Cost = $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$ $PoA = \frac{1}{1} = 1$ ## Example 2 * 2 nodes, 2 parallel edges * Edge 1: $l_1(x) = 1$ * Edge 2: $l_2(x) = x$ * 1 unit of traffic from $s$ to $t$ **Nash Equilibrium:** Route all traffic on Edge 2 Social Cost = $1 \cdot 1 = 1$ **Optimal Flow:** Route all traffic on Edge 1 Social Cost = $1 \cdot 1 = 1$ $PoA = \frac{1}{1} = 1$