IMG_9591.jpeg

# Algorithmic Game Theory ## What is Game Theory? * **Game Theory**: Study of multi-agent decision problems. * **Applications**: * E-commerce * Auctions * Social Networks * Security * Routing ### Selfish Routing #### Model * **Network**: $G=(V, E)$ * **Late...

# Algorithmic Game Theory ## What is Game Theory? * **Game Theory**: Study of multi-agent decision problems. * **Applications**: * E-commerce * Auctions * Social Networks * Security * Routing ### Selfish Routing #### Model * **Network**: $G=(V, E)$ * **Latency Function**: $l_{e}(x)$ * $x$ is the fraction of traffic on edge $e$ * **Total Latency**: $\sum_{e \in E} l_{e}(f_{e}) \cdot f_{e}$ * $f_{e}$ is the flow on edge $e$ #### Example: Braess's Paradox **Without the dashed edge:** * Cost is $1.5$ * 1/2 go up then right, cost $1+0.5=1.5$ * 1/2 go right then up, cost $0.5+1=1.5$ **Adding the dashed edge:** * Everyone goes $A \to C \to D \to B$ * Cost is $2$ #### Questions * Does equilibrium exist? * How bad is the equilibrium? * How to reach the equilibrium? ## Example: Prisoner's Dilemma Two suspects are arrested for a crime. They are questioned in separate cells. * If both stay silent, they get a short sentence. * If one confesses, he goes free and the other gets a long sentence. * If both confess, they get a medium sentence. ### Payoff Matrix | | **Player 2: Silent** | **Player 2: Confess** | | :---------- | :-------------------- | :-------------------- | | **Silent** | -1, -1 | -10, 0 | | **Confess** | 0, -10 | -5, -5 | * **Dominant Strategy**: Confess * **Nash Equilibrium**: (Confess, Confess) * **Social Optimum**: (Silent, Silent) ## Example: Stag-Hunt Game Two hunters can either hunt a stag or a hare. * Hunting a stag requires both hunters to cooperate. * Hunting a hare can be done alone but yields less reward. ### Payoff Matrix | | **Player 2: Stag** | **Player 2: Hare** | | :-------- | :----------------- | :----------------- | | **Stag** | 4, 4 | 0, 3 | | **Hare** | 3, 0 | 3, 3 | * Two Nash Equilibria: (Stag, Stag), (Hare, Hare) * Which one is more likely to be played? ## Definitions * **Players**: Set of participants $N=\{1, \ldots, n\}$ * **Strategy**: Available choices $S_{i}$ * **Strategy Profile**: $s=\left(s_{1}, \ldots, s_{n}\right)$ * **Payoff Function**: $u_{i}(s)$ * $u_{i}: S_{1} \times \ldots \times S_{n} \rightarrow \mathbb{R}$ ### Example: Prisoner's Dilemma * $N=\{1,2\}$ * $S_{i}=\{\text { Silent, Confess }\}$ * $s=$ (Silent, Confess) * $u_{1}(s)=-10, u_{2}(s)=0$ ## Nash Equilibrium A strategy profile $s=\left(s_{1}, \ldots, s_{n}\right)$ is a Nash Equilibrium if no player can unilaterally improve their payoff by changing their strategy. ### Formally $$ \forall i, \forall s_{i}^{\prime}, u_{i}\left(s_{i}^{\prime}, s_{-i}\right) \leq u_{i}\left(s_{i}, s_{-i}\right) $$ * $s_{-i}$: strategies of all players except $i$ ### Example: Prisoner's Dilemma * (Confess, Confess) is a Nash Equilibrium * No player can improve their payoff by unilaterally changing their strategy. ## Existence of Nash Equilibrium ### Theorem(Nash, 1950) Every game with a finite number of players and a finite number of strategies has at least one Nash Equilibrium (possibly in mixed strategies). ### Proof Uses Brouwer's fixed-point theorem. ## Complexity of Nash Equilibrium * **Question**: How hard is it to compute a Nash Equilibrium? * **Result**: Computing a Nash Equilibrium is PPAD-complete. * PPAD: Polynomial Parity Argument Directed * Informally: guaranteed to exist, hard to find ### Implications * No polynomial-time algorithm is known. * Even approximating a Nash Equilibrium is hard.