Phase VII — Game Theory for Optimization & Robotics | Week 16 | 2.5 hours When selfish agents optimize a shared potential function, decentralized behavior can be surprisingly efficient — or catastrophically wasteful.
Warehouse aisle routing is a textbook congestion game: each AMR chooses a path, and delay increases with the number of robots on each segment. The Price of Anarchy determines how much worse decentralized routing is compared to a centralized dispatcher. Understanding this gap drives OKS fleet architecture decisions — when to let robots self-route vs. when central coordination is worth the overhead.
A game is an exact potential game if there exists a function $\Phi: \mathcal{S} \to \mathbb{R}$ such that for every player $i$, every strategy pair $(s_i, s_i')$, and every opponent profile $s_{-i}$:
$$u_i(s_i, s_{-i}) - u_i(s_i', s_{-i}) = \Phi(s_i, s_{-i}) - \Phi(s_i', s_{-i})$$
Key property: Any sequence of unilateral improvements (a player switching to increase their payoff) also increases $\Phi$. Since $\Phi$ is bounded, this process terminates at a pure Nash equilibrium. Every potential game has at least one pure NE.
A congestion game has: - Players $N = \{1, \ldots, n\}$ - Resources $E = \{e_1, \ldots, e_m\}$ - Strategy sets $\mathcal{S}_i \subseteq 2^E$ (subsets of resources) - Delay functions $d_e: \mathbb{N} \to \mathbb{R}$ for each resource $e$
Player $i$'s cost: $c_i(s) = \sum_{e \in s_i} d_e(n_e(s))$ where $n_e(s) = |\{j : e \in s_j\}|$.
Rosenthal's Theorem: Every congestion game is a potential game with:
$$\Phi(s) = \sum_{e \in E} \sum_{k=1}^{n_e(s)} d_e(k)$$
The social cost is $C(s) = \sum_i c_i(s)$. The Price of Anarchy (PoA) measures the worst-case ratio:
$$\text{PoA} = \frac{\max_{s \in \text{NE}} C(s)}{\min_{s} C(s)} = \frac{\text{worst NE cost}}{\text{optimal cost}}$$
The Price of Stability (PoS) uses the best NE instead.
Braess's Paradox: Adding a road to a network can increase equilibrium travel time for all users. Consider a network with $n$ users, origin $O$, destination $D$: - Upper path: $O \to A \to D$ with costs $d_{OA}(x) = x/n$, $d_{AD}(x) = 1$ - Lower path: $O \to B \to D$ with costs $d_{OB}(x) = 1$, $d_{BD}(x) = x/n$
Without bridge $A \to B$: equilibrium splits traffic equally, cost = $3/2$ per user. Add bridge $A \to B$ with $d_{AB}(x) = 0$: everyone uses $O \to A \to B \to D$, cost = $2$ per user.
Theorem (Roughgarden & Tardos 2002): For linear delay functions $d_e(x) = a_e x + b_e$, the PoA $\leq 4/3$.
"""Congestion Games: equilibrium computation and Price of Anarchy."""
import numpy as np
from itertools import product
from typing import Callable
class CongestionGame:
"""A congestion game with n players and m resources."""
def __init__(self, n_players: int, strategies: list,
delay_fns: dict):
"""
Args:
n_players: number of players
strategies: list of lists, strategies[i] = list of resource subsets
delay_fns: dict mapping resource -> delay function (int -> float)
"""
self.n = n_players
self.strategies = strategies
self.delay_fns = delay_fns
self.resources = list(delay_fns.keys())
def congestion(self, profile: tuple) -> dict:
"""Compute congestion on each resource."""
counts = {e: 0 for e in self.resources}
for i, si in enumerate(profile):
for e in self.strategies[i][si]:
counts[e] += 1
return counts
def cost(self, profile: tuple, player: int) -> float:
"""Cost for player given strategy profile."""
counts = self.congestion(profile)
return sum(self.delay_fns[e](counts[e])
for e in self.strategies[player][profile[player]])
def social_cost(self, profile: tuple) -> float:
"""Total cost across all players."""
return sum(self.cost(profile, i) for i in range(self.n))
def potential(self, profile: tuple) -> float:
"""Rosenthal potential function."""
counts = self.congestion(profile)
return sum(sum(self.delay_fns[e](k) for k in range(1, counts[e] + 1))
for e in self.resources)
def find_all_ne(self) -> list:
"""Find all pure Nash equilibria by exhaustive search."""
equilibria = []
n_strats = [len(s) for s in self.strategies]
for profile in product(*[range(k) for k in n_strats]):
is_ne = True
for i in range(self.n):
current_cost = self.cost(profile, i)
for alt in range(n_strats[i]):
if alt != profile[i]:
alt_profile = list(profile)
alt_profile[i] = alt
if self.cost(tuple(alt_profile), i) < current_cost - 1e-10:
is_ne = False
break
if not is_ne:
break
if is_ne:
equilibria.append(profile)
return equilibria
def price_of_anarchy(self) -> float:
"""Compute Price of Anarchy."""
nes = self.find_all_ne()
n_strats = [len(s) for s in self.strategies]
worst_ne = max(self.social_cost(ne) for ne in nes)
opt = min(self.social_cost(p)
for p in product(*[range(k) for k in n_strats]))
return worst_ne / opt if opt > 0 else float('inf')
def braess_paradox_demo():
"""Demonstrate Braess's paradox with 2 players."""
# Without bridge: 2 paths (upper, lower)
# Upper: O->A (x/2), A->D (1)
# Lower: O->B (1), B->D (x/2)
delay_no_bridge = {
'OA': lambda x: x / 2, 'AD': lambda x: 1.0,
'OB': lambda x: 1.0, 'BD': lambda x: x / 2,
}
# Player strategies: 0 = upper (OA, AD), 1 = lower (OB, BD)
strats_no = [
[['OA', 'AD'], ['OB', 'BD']], # Player 0
[['OA', 'AD'], ['OB', 'BD']], # Player 1
]
game_no = CongestionGame(2, strats_no, delay_no_bridge)
# With bridge: add path O->A->B->D
delay_bridge = {
'OA': lambda x: x / 2, 'AD': lambda x: 1.0,
'OB': lambda x: 1.0, 'BD': lambda x: x / 2,
'AB': lambda x: 0.0, # free bridge
}
strats_br = [
[['OA', 'AD'], ['OB', 'BD'], ['OA', 'AB', 'BD']],
[['OA', 'AD'], ['OB', 'BD'], ['OA', 'AB', 'BD']],
]
game_br = CongestionGame(2, strats_br, delay_bridge)
print("=== Braess's Paradox ===")
nes_no = game_no.find_all_ne()
for ne in nes_no:
print(f" No bridge NE: {ne}, social cost = {game_no.social_cost(ne):.2f}")
nes_br = game_br.find_all_ne()
for ne in nes_br:
print(f" With bridge NE: {ne}, social cost = {game_br.social_cost(ne):.2f}")
print(f" PoA without bridge: {game_no.price_of_anarchy():.3f}")
print(f" PoA with bridge: {game_br.price_of_anarchy():.3f}")
braess_paradox_demo()
# Warehouse aisle congestion game
print("\n=== Warehouse Aisle Congestion ===")
delay_aisle = {
'aisle_A': lambda x: 1 + 2 * x,
'aisle_B': lambda x: 3 + x,
'aisle_C': lambda x: 2 + 1.5 * x,
}
# 3 robots, each chooses one aisle
strats_wh = [[['aisle_A'], ['aisle_B'], ['aisle_C']]] * 3
game_wh = CongestionGame(3, strats_wh, delay_aisle)
nes_wh = game_wh.find_all_ne()
print(f"Found {len(nes_wh)} NE")
for ne in nes_wh:
print(f" NE: {ne} (aisles: {[['A','B','C'][s] for s in ne]}), "
f"social cost = {game_wh.social_cost(ne):.2f}")
print(f" PoA: {game_wh.price_of_anarchy():.3f}")
P1: Verify that the warehouse aisle game above is a potential game by computing $\Phi$ for two strategy profiles that differ by one player's deviation.
P2: Construct a 4-player, 2-resource congestion game with linear delays. Compute all NE and the PoA.
P3: Prove that every finite potential game has at least one pure NE.
E1: Prove the Roughgarden-Tardos bound: PoA $\leq 4/3$ for linear congestion games.
E2: Implement best-response dynamics for a 10-player congestion game and verify convergence to a NE.
E3: Model OKS warehouse routing as a congestion game with 6 robots, 4 corridors, and quadratic delay. Compute the PoA and suggest when centralized routing is justified.