IMG_2213.jpeg

# Algorithmic Game Theory - Lecture 1 Instructor: Ariel Procaccia TAs: Ziv, Yoad, Ezra(Oren) ## What is Game Theory? * Study of strategic interactions between rational agents * Used in economics, political science, biology, computer science ## What is Algorithmic Game Theory? Designing alg...

# Algorithmic Game Theory - Lecture 1 Instructor: Ariel Procaccia TAs: Ziv, Yoad, Ezra(Oren) ## What is Game Theory? * Study of strategic interactions between rational agents * Used in economics, political science, biology, computer science ## What is Algorithmic Game Theory? Designing algorithms for games with strategic agents. AGT = CS + GT ### Examples * Auctions: sponsored search * Social Networks: Formation, dynamics, influence * Fair division * Machine Learning: GANs ## Selfish Routing ### Model * A network represented by a graph $G = (V, E)$. * A set of $k$ players, each controlling some amount of traffic from a source $s_i$ to a target $t_i$. * Each edge $e \in E$ has a cost function $\mathcal{l}_e(x)$ which is the cost per unit of traffic on $e$ when $x$ units of traffic use $e$. * Each player wants to minimize their own cost. ### Definition: Wardrop Equilibrium A flow is in Wardrop equilibrium if all players use only paths with minimum cost. **Note:** Such an equilibrium always exists. ### Question How inefficient is a Wardrop equilibrium? Define the social cost of flow $f$ to be $SC(f) = \sum_{e \in E} f(e) \cdot l_e(f(e))$. Let $f^*$ be the flow that minimizes the social cost, and $f$ be the equilibrium flow. **Price of Anarchy (PoA)** $= \frac{SC(f)}{SC(f^*)}$ **Price of Stability (PoS)** $= \frac{SC(f)}{SC(f^*)}$ where $f$ is the best equilibrium flow. ### Example: Braess's Paradox * Two paths from $s$ to $t$: * $s \rightarrow A \rightarrow t$ * $s \rightarrow B \rightarrow t$  * Assume rate of one unit of traffic. * The cost of each path is $\frac{1}{2} + 1 = 1 + \frac{1}{2} = \frac{3}{2}$. * Social cost is $1 \cdot \frac{1}{2} + 1 \cdot 1 + 1 \cdot 1 + 1 \cdot \frac{1}{2} = 3/2$. Now add a zero cost edge from $A$ to $B$ :  * Now all traffic will go on the path $s \rightarrow A \rightarrow B \rightarrow t$. * The cost is $1 + 0 + 1 = 2$. * The social cost is $1 \cdot 1 + 1 \cdot 0 + 1 \cdot 1 = 2$. **Price of Anarchy** $= \frac{2}{3/2} = \frac{4}{3}$. #### Theorem The price of anarchy is at most $\frac{4}{3}$ with linear cost functions. ### Proof * $SC(f) = \sum_{e \in E} f(e) \cdot l_e(f(e))$ * $SC(f^*) = \sum_{e \in E} f^*(e) \cdot l_e(f^*(e))$ Since $f$ is an equilibrium, $C_i(f) \le C_i(f')$ where $C_i(f)$ is the cost of player $i$ in flow $f$ and $f'$ is any other flow. $SC(f) = \sum_{e \in E} f(e) \cdot l_e(f(e)) = \sum_{p \in P} f(p) \cdot l_p(f)$ where $P$ is the set of all paths and $l_p(f)$ is the cost of path $p$ in flow $f$.