Algorithmic Game Theory: Selfish Routing

Algorithmic Game Theory (AGT)

• AGT merges game theory and algorithm design
• It focuses on strategic behavior in algorithm design

Game Theory

• Predicts rational agent strategic interactions

Algorithm Design

• Designs efficient algorithms

Example: Selfish Routing

• Users choose routes to minimize delay
• Users are considered players
• Routes are strategies
• Delays are costs
• Goal is to design networks robust against selfish routing

Selfish Routing Model

• Network consists of a graph $G = (V, E)$ with source $s$ and destination $t$
• Infinitesimal users control only a negligible amount of traffic
• Strategies are paths from $s$ to $t$
• Cost is that each edge $e$ has a cost function $l_e(x)$, where $x$ is the fraction of flow on $e$
• Social Cost is the average latency experienced by all users
• $SC(f) = \sum_{e \in E} f_e \cdot l_e(f_e)$, where $f_e$ is the flow on edge $e$

Wardrop Equilibrium

• All used paths have the same cost with unused paths having higher cost
• No user can unilaterally improve their cost by changing paths

Braess's Paradox

• Adding an edge to a network can increase the social cost at equilibrium
• Original network: $s \xrightarrow{x} v \xrightarrow{ } t$ plus $s \xrightarrow{ } w \xrightarrow{x} t$
• Cost functions: $l_{sv}(x) = 1$, $l_{vt}(x) = x$, $l_{sw}(x) = x$, $l_{wt}(x) = 1$
• Equilibrium flow: 0.5 on $s \rightarrow v \rightarrow t$ and 0.5 on $s \rightarrow w \rightarrow t$
• Social cost: $0.5(1 + 0.5) + 0.5(0.5 + 1) = 1.5$
• Added edge is a zero-latency edge $v \rightarrow w$
• Flow now goes through $s \rightarrow v \rightarrow w \rightarrow t$
• Social cost increases to: $1 + 0 + 0 + 1 = 2$

Price of Anarchy (PoA)

• Measures the loss of efficiency due to selfish behavior
• $PoA = \frac{SC(f)}{SC(f^)}$, where $f$ is the Wardrop equilibrium flow and $f^$ is the optimal flow

Bounding the Price of Anarchy

• If edge latency functions are linear, then $PoA \leq \frac{4}{3}$
• For polynomials of degree $p$, $PoA \leq p + 1$

Computing Equilibria

• Finding Wardrop equilibria can be computationally hard
• Techniques used: linear programming, convex programming, simulation, and iterative methods

Mechanism Design for Selfish Routing

• The goal is to design rules to incentivize better outcomes
• Taxes are used to charge tolls on edges to discourage inefficient routes
• Capacity investments add capacity to edges to reduce latency
• Information provision provides users with better information about network conditions

Summary

• Algorithmic Game Theory analyzes strategic interactions in networked systems
• It also quantifies the impact of selfish behavior
• It designs mechanisms to improve system performance