Algorithmic Game Theory: Selfish Routing

• Algorithmic Game Theory involves both the mathematical study of strategic interaction and the design of efficient algorithms.

Selfish Routing Model

• A network with $n$ nodes and $m$ edges is considered.
• Each edge $e$ has a cost function $l_e(x)$, representing the cost per user when $x$ users choose that edge; $l_e(x)$ is typically non-decreasing.
• There's a set of $k$ user populations, where population $i$ routes $r_i$ traffic from source $s_i$ to destination $t_i$.

Flows and Equilibrium

• A flow $f$ specifies how traffic is routed for each user population $i$ from $s_i$ to $t_i$.
• A flow $f$ is at Nash Equilibrium if no user can lower their cost by changing their path.
• Social cost quantifies how well resources are used.
• Social cost of a flow $f$ is calculated as $\sum_{e\in E} f(e) \cdot l_e(f(e))$, where $f(e)$ is the total flow on edge $e$.
• How inefficient is a Nash Equilibrium?
• How does the social cost of a Nash Equilibrium compare to the social cost of an optimal flow?

Price of Anarchy

• The Price of Anarchy (PoA) measures inefficiency by comparing the social cost of the worst Nash Equilibrium to the optimal social cost.
• $PoA = \frac{\text{Social cost of worst NE}}{\text{Social cost of optimal flow}}$.

Example 1

• Network consists of 2 nodes and 2 parallel edges.
• Edge 1 has a cost function $l_1(x) = 1$.
• Edge 2 has a cost function $l_2(x) = x$.
• 1 unit of traffic flows from $s$ to $t$.
• For the optimal flow all traffic is routed on Edge 1, resulting in a social cost of $1 \cdot 1 = 1$.
• For one Nash Equilibrium all traffic is routed on Edge 2, resulting in a social cost of $1 \cdot 1 = 1$.
• For another Nash Equilibrium, $\frac{1}{2}$ is routed on Edge 1, and $\frac{1}{2}$ is routed on Edge 2, resulting in a social cost of $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$.
• The Price of Anarchy is $PoA = \frac{1}{1} = 1$

Example 2

• Network consists of 2 nodes and 2 parallel edges.
• Edge 1 has a cost function $l_1(x) = 1$.
• Edge 2 has a cost function $l_2(x) = x$.
• 1 unit of traffic flows from $s$ to $t$.
• For one Nash Equilibrium all traffic is routed on Edge 2, resulting in a social cost of $1 \cdot 1 = 1$.
• For the optimal flow all traffic is routed on Edge 1, resulting in a social cost of $1 \cdot 1 = 1$.
• The Price of Anarchy is $PoA = \frac{1}{1} = 1$