received_2104812023287009.jpeg

# Algorithmic Game Theory - Lecture 1 Instructor: Professor Yiling Chen Scribe: Zifan Wang ## 1 Course information **Website**: https://users.seas.harvard.edu/~yiling/courses/cs229r/ **Time**: Tuesday & Thursday, 1:30pm - 2:45pm **Location**: Maxwell Dworkin G125 **Pre-requisites**: algorithm...

# Algorithmic Game Theory - Lecture 1 Instructor: Professor Yiling Chen Scribe: Zifan Wang ## 1 Course information **Website**: https://users.seas.harvard.edu/~yiling/courses/cs229r/ **Time**: Tuesday & Thursday, 1:30pm - 2:45pm **Location**: Maxwell Dworkin G125 **Pre-requisites**: algorithms, probability. mathematical maturity **Grading**: * Problem sets 40% * Participation 10% * Final project 50% ## 2 What is Game Theory? Game theory is the study of mathematical models of strategic interactions among rational agents. * **rational**: an agent chooses its best action given its beliefs. * **strategic interaction**: my action affects you, and your action affects me. ### Example: Prisoner's Dilemma Two suspects are arrested for a crime. The police separate them and offer each the following deal: * If one confesses and the other does not, the confessor is freed and the other gets 10 years in prison * If both confess, they each get 5 years in prison * If neither confesses, they each get 1 year in prison | | Player 2: Stay Silent | Player 2: Confess | | :---------- | :-------------------- | :---------------- | | Player 1: Stay Silent | -1, -1 | -10, 0 | | Player 1: Confess | 0, -10 | -5, -5 | Each player's goal is to minimize their time in prison. **Dominant strategy**: confess. **Nash Equilibrium**: (confess, confess). **Social optimum**: (stay silent, stay silent). (But this is not stable!) ## 3 Topics we will cover 1. Solution concepts: Nash equilibrium, Bayes-Nash equilibrium, refinements, correlated equilibrium. 2. Mechanism design: auctions, voting, matching, sponsored search. 3. Price of anarchy. 4. Learning in games. 5. Other selected topics if time permits. ## 4 Selfish Routing ### 4.1 The Model * A network of $n$ agents, each controlling one unit of traffic. * Each agent wants to travel from a source node $s_i$ to a target node $t_i$. * A strategy for agent $i$ is a path from $s_i$ to $t_i$. * Let $x_p$ be the fraction of players choosing path $p$. * Let $l_e(x)$ be the latency (or cost) function on edge $e$, where $x$ is the amount of traffic on edge $e$. We assume that $l_e(x)$ is non-negative and non-decreasing, i.e., larger traffic leads to larger latency * The cost for player $i$ is the sum of latencies on her chosen path. ### 4.2 Wardrop Equilibrium Wardrop equilibrium is a flow $f$ in which all used paths between a given origin-destination pair have equal and minimal latency. > **Definition 1** A flow $f$ is a Wardrop equilibrium if, for every origin-destination pair $s_i, t_i$ and every path $p_1, p_2$ between them, if $f_{p1} > 0$, then $c_{p1} \le c_{p2}$. Here $f_{p1}$ is the amount of flow on $p_1$, and $c_{p1}$ is the cost of $p_1$, i.e., sum of latencies on $p_1$. In a Wardrop equilibrium, no individual agent has an incentive to unilaterally deviate from its current path. ### 4.3 Braess's Paradox Adding a link to a network can increase the latency for all agents at Wardrop equilibrium! **Example:**  **(A)** * 2000 agents want to travel from S to E * Each agent controls one unit of traffic * Path S-A-E: $l_1(x) = x$ * Path S-B-E: $l_2(x) = x$ * Path S-A-B-E: $l_3(x) = c$ * Path S-B-A-E: $l_4(x) = c$ Cost at Wardrop equilibrium: 1000 **(B)** Add edge A-B with latency 0. Cost at Wardrop equilibrium: 2000 ### 4.4 Price of Anarchy How inefficient is a Nash equilibrium compared to the social optimum? $$ PoA = \frac{\text{cost of worst-case Nash equilibrium}}{\text{cost of social optimum}} $$ For the network in the Braess's Paradox, the Price of Anarchy is $\frac{2000}{1000} = 2$.