IMG_9687.jpeg

# Algorithmic Game Theory ## What is Algorithmic Game Theory? * **Game Theory**: Study of strategic interactions between rational agents. * **Algorithm Design**: How to design efficient algorithms to solve computational problems. * **Algorithmic Game Theory**: Interplay between game theory a...

# Algorithmic Game Theory ## What is Algorithmic Game Theory? * **Game Theory**: Study of strategic interactions between rational agents. * **Algorithm Design**: How to design efficient algorithms to solve computational problems. * **Algorithmic Game Theory**: Interplay between game theory and algorithm design. It incorporates incentives into the design of algorithms and analyzes strategic behavior in systems. ### Example * **Mechanism Design/Reverse Game Theory**: We want to design a game so that the strategic behavior of the players in the game leads to a desirable outcome. * **Sponsored Search Auctions**: Google and other search engines sell advertisement slots. How should they run the auction? * **Sharing the Cost of a Network**: Suppose we want to build a network to connect *n* players. Each link has a cost. How do we share the cost of the links between the players? ## Selfish Routing ### Model * A network of $n$ players, each of whom wants to route traffic from a source to a destination. * A directed graph $G = (V,E)$. * For each player $i$, a source $s_i \in V$ and a destination $t_i \in V$. * For each player $i$, a demand $d_i > 0$ of traffic that he wants to route from $s_i$ to $t_i$. * For each edge $e \in E$, a cost function $c_e(x)$ which is the cost (or delay) per unit of traffic on edge $e$, as a function of the congestion $x$ on edge $e$. * Cost to player $i$ of using a path $P$ is $\sum_{e \in P} c_e(f_e)$, where $f_e$ is the total flow on edge $e$. * Each player wants to minimize his own cost. ### Definition: Wardrop Equilibrium A Wardrop equilibrium is a flow in which all players are routed on a shortest path from their source to their destination, given the current flow. That is no player has any incentive to deviate from its current path. Let $f_e$ be the total flow on edge $e$ in a Wardrop equilibrium. Then, for every player $i$, and every $s_i-t_i$ path $P$ used by player $i$, we have: $\qquad \sum_{e \in P} c_e(f_e) \le \sum_{e \in P'} c_e(f_e)$ For every $s_i-t_i$ path $P'$. ### The Price of Anarchy * The price of anarchy (POA) is a measure of the degradation of performance of a system due to selfish behavior of its agents. * It is defined as the ratio of the cost of a "bad" equilibrium to the cost of an optimal solution. $POA = \frac{\text{Cost of Wardrop Equilibrium}}{\text{Cost of Optimal Solution}}$ * The price of anarchy is always $\ge 1$. * We want to bound the price of anarchy for different types of cost functions. ### Social Cost The social cost of a flow is the sum of the costs of all players. $SC(f) = \sum_{e \in E} f_e \cdot c_e(f_e)$ That is the total cost incurred by all players. ### Example: Braess's Paradox  * Two paths from $s$ to $t$: $s \rightarrow A \rightarrow t$ and $s \rightarrow B \rightarrow t$ * 1 unit of traffic wants to go from $s$ to $t$. * In equilibrium, half the traffic takes path $s \rightarrow A \rightarrow t$ and half the traffic takes path $s \rightarrow B \rightarrow t$. * Cost to each player is $1.5$. * Social cost is $1.5$.  * Add a zero cost edge from $A$ to $B$. * Now, everyone will take path $s \rightarrow A \rightarrow B \rightarrow t$. * Cost to each player is $2$. * Social cost is $2$. ### What is the Price of Anarchy? $\frac{2}{1.5} = \frac{4}{3}$ ### What if the Cost Functions are Linear? $c_e(x) = a_e \cdot x + b_e$, $a_e, b_e \ge 0$ Then the Price of Anarchy is at most $\frac{4}{3}$.