IMG_2851.jpeg

# Algorithmic Game Theory ## What is Game Theory? * Study of interacting decision makers (agents) * Each agent acts to maximize its own utility * Agent's utility depends on actions of other agents ### Examples: 1. Auctions: * Each bidder wants to win the item at the lowest possible...

# Algorithmic Game Theory ## What is Game Theory? * Study of interacting decision makers (agents) * Each agent acts to maximize its own utility * Agent's utility depends on actions of other agents ### Examples: 1. Auctions: * Each bidder wants to win the item at the lowest possible price. * Each bidder's utility depends on other bids. 2. Network Routing: * Each router wants to send traffic on the fastest route. * Each router's delay depends on traffic on each link. 3. Social Networks: * Each individual wants to maximize its connections * Each individual's utility depends on who its friends are. ## What is Algorithmic Game Theory? * Brings together game theory and algorithm design. * Designing algorithms for strategic agents. * Games that arise in computer science. ### Examples: 1. Mechanism Design: * Designing auctions that incentivize truthful bidding. * Design protocols (mechanisms) so that agents behave according to system designer's objective. 2. Price of Anarchy: * How much is performance degraded due to selfish behavior? * Quantifying the inefficiency of "selfish" outcomes. 3. Computation of Equilibria: * Finding stable solutions in games. * What is a good notion of "stability"? * How hard is it to find such a solution? ## Selfish Routing * A game played on a network. * $n$ agents. * Agent $i$ wants to route $r_i$ units of traffic from $s_i$ to $t_i$ * Each agent chooses a path from $s_i$ to $t_i$. * Each edge $e$ has a cost function $\mathcal{C}_e(x)$ which is the cost (or delay) per unit of traffic on $e$ when $x$ units of traffic use $e$. ### Example: * Two agents want to route 1 unit of traffic from $s$ to $t$. * Agent 1 chooses the top path. * Agent 2 chooses the bottom path. *Cost to each agent is 1.* * Agent 1 switches to the bottom path. *Cost to agent 1 is now 1.5. The other agent's cost stays at 1.* ## Nash Equilibrium * A Nash Equilibrium is a stable outcome. * No agent has an incentive to unilaterally deviate. * A set of paths such that if agent $i$ switched to a different path, its cost would not decrease. *In the previous example, the Nash Equilibrium is when both agents take the path with cost $\mathcal{C}_e(x) = x$* ## Price of Anarchy * Measures the degradation in performance due to selfish routing. * Cost of Nash Equilibrium / Optimal Cost * Optimal Cost: the cost when agents cooperate to minimize overall cost. *In the previous example, the Price of Anarchy is 1.5* ## Braess's Paradox * Adding an edge to a network can hurt overall performance! ### Example: * Two agents want to route 1 unit of traffic from $s$ to $t$. * In the Nash Equilibrium, each agent takes one of the original paths. * Each agent's cost is 1. * Total cost is 2. * Add an edge of cost 0 from $A$ to $B$. * Now each agent takes the path $s \rightarrow A \rightarrow B \rightarrow t$. * Each agent's cost is now 2. * Total cost is 4. * The optimal solution (without the extra edge) is better than the Nash Equilibrium with the extra edge! * The Price of Anarchy is 2.