Chapter 14: Smooth Games - The Universal Bound - Algorithimic Game Theory with Python

We know that for Traffic Games with linear costs, the Price of Anarchy is exactly $\frac{5}{2}$ (2.5). But what if the game is slightly different? Or what if players aren’t perfectly rational?

The “Smoothness” Framework¶

Instead of analyzing games one by one, we define a property called $(\lambda, \mu)$ -Smoothness. A game is smooth if, for any two outcomes $s$ (current) and $s^*$ (optimal), the costs satisfy:

\sum \text{Cost}_i(s_i^*, s_{-i}) \le \lambda \cdot \text{Cost}(s^*) + \mu \cdot \text{Cost}(s)

(1)

The Robust PoA Theorem: If a game is $(\lambda, \mu)$ -smooth, then the Price of Anarchy is always:

\text{PoA} \le \frac{\lambda}{1 - \mu}

(2)

Why is this “Robust”? This bound holds everywhere:

Pure Nash Equilibria (Standard).
Mixed Nash Equilibria (Randomized strategies).
No-Regret Learning (Outcomes from learning algorithms like in Chapter 17).
Coarse Correlated Equilibria.

Case Study: Affine Routing¶

Traffic games with linear costs (Affine) are proven to be $(\frac{5}{3}, \frac{1}{3})$ -smooth. Let’s plug that into the formula:

\text{PoA} \le \frac{5/3}{1 - 1/3} = \frac{5/3}{2/3} = \frac{5}{2} = 2.5

(3)

This recovers the exact result we found in Chapter 12, but now we know it applies even if players are “learning” over time!

import random

def check_smoothness_bound():
    """
    Simulates a random Traffic Game (Affine Costs) and checks if
    the outcome respects the Smoothness Bound (PoA <= 2.5).
    """
    
    # --- SETUP: A Simple Network ---
    # Two paths. Total Traffic = 1.0
    # Path A: Cost = a1 * x + b1
    # Path B: Cost = a2 * x + b2
    
    print("--- Robust Price of Anarchy Simulation ---")
    
    # Let's generate random affine cost functions
    a1, b1 = 2, 0   # Path A: 2x
    a2, b2 = 1, 10  # Path B: x + 10
    
    def cost_A(x): return a1 * x + b1
    def cost_B(x): return a2 * x + b2
    
    def total_social_cost(traffic_on_A):
        x_A = traffic_on_A
        x_B = 1.0 - x_A
        return (x_A * cost_A(x_A)) + (x_B * cost_B(x_B))
    
    # 1. Find OPTIMAL (Dictator)
    # Brute force search for x_A that minimizes cost
    xs = [i/1000 for i in range(1001)]
    costs = [total_social_cost(x) for x in xs]
    
    min_cost = min(costs)
    opt_x = xs[costs.index(min_cost)]
    
    # 2. Find NASH (Selfish)
    # Drivers assume x_A and x_B are fixed and join the cheaper one.
    # Equilibrium is where Cost_A(x) = Cost_B(1-x)
    # 2x = (1-x) + 10 => 3x = 11 => x = 11/3 > 1.0
    # So all traffic goes to A.
    
    # Let's verify via simulation
    # If Cost A(1) < Cost B(0), everyone takes A.
    nash_x = 0
    if cost_A(1) < cost_B(0):
        nash_x = 1.0
    elif cost_B(1) < cost_A(0):
        nash_x = 0.0
    else:
        # Intersection
        # a1*x + b1 = a2*(1-x) + b2
        # (a1+a2)x = a2 + b2 - b1
        nash_x = (a2 + b2 - b1) / (a1 + a2)
        # Clamp to [0,1]
        nash_x = max(0.0, min(1.0, nash_x))
        
    nash_total_cost = total_social_cost(nash_x)
    
    # 3. CHECK THEOREM
    poa = nash_total_cost / min_cost
    theoretical_max = 2.5 # 5/2
    
    print(f"Game Parameters:")
    print(f"Path A: {a1}x + {b1}")
    print(f"Path B: {a2}x + {b2}")
    
    print(f"\nResults:")
    print(f"Optimal Cost: {min_cost:.4f} (Traffic Split: {opt_x:.2f})")
    print(f"Selfish Cost: {nash_total_cost:.4f} (Traffic Split: {nash_x:.2f})")
    print(f"Actual PoA:   {poa:.4f}")
    
    print(f"\nRobust Bound Check:")
    print(f"Theory says PoA <= {theoretical_max}")
    
    if poa <= theoretical_max:
        print("SUCCESS: The theoretical bound holds.")
    else:
        print("FAIL: Something is wrong with the math!")

check_smoothness_bound()

--- Robust Price of Anarchy Simulation ---
Game Parameters:
Path A: 2x + 0
Path B: 1x + 10

Results:
Optimal Cost: 2.0000 (Traffic Split: 1.00)
Selfish Cost: 2.0000 (Traffic Split: 1.00)
Actual PoA:   1.0000

Robust Bound Check:
Theory says PoA <= 2.5
SUCCESS: The theoretical bound holds.

Analysis: The Power of Abstraction¶

In the code above, we simulated a specific routing game.

Optimal Cost: The best possible arrangement.
Selfish Cost: The result of uncoordinated drivers.
Ratio: The Price of Anarchy.

You will notice that no matter how we change the cost functions ( $a$ and $b$ ), the ratio never exceeds 2.5.

Why is Chapter 14 important? The “Smoothness” argument means we don’t have to worry about whether the system has converged to a Pure Nash Equilibrium. Even if the system is cycling, or if users are using simple learning algorithms (like “Regret Minimization”), the efficiency loss is capped at 2.5.

This gives engineers confidence: “Even if the network is chaotic, it won’t be more than 2.5x worse than perfect.”