Game Theory
Algorithmic Game Theory
Every morning, millions of drivers independently choose routes in Google Maps. Every second, thousands of servers balance their load. Every TCP connection negotiates its speed. None of this is centrally coordinated-these are strategic systems. Algorithmic Game Theory studies the computational side of equilibria: how far from optimal, and how quickly can we find them.
- **Internet routing:** BGP (Border Gateway Protocol) is a game among ISPs. Price of Anarchy for internet traffic and why centralization (SDN) can help
- **Cloud computing:** allocating jobs across servers is a congestion game. Load balancing algorithms (Amazon, Google) account for PoA and potential functions
- **Google Smart Bidding:** the automatic bidding algorithm is a no-regret learner converging to a correlated equilibrium of the ad auction
Предварительные знания
Price of Anarchy
Every morning, thousands of drivers choose routes that minimize their personal commute time. Nobody thinks about the collective traffic load. The result is the famous Braess Paradox: adding a new road can increase total travel time for everyone. The gap between the "selfish" Nash Equilibrium and the social optimum is called the Price of Anarchy (PoA).
PoA = (worst NE) / (social optimum) PoS = (best NE) / (social optimum) PoA ≥ PoS ≥ 1 (minimizing cost; ≤ 1 for maximization). PoA = 1: equilibrium equals optimum (selfishness costs nothing) PoA = ∞: equilibrium is catastrophically worse than optimum
Braess's Paradox and real-world examples
Dietrich Braess showed in 1968 that adding a zero-latency road to a routing network can make ALL drivers worse off. Counterintuitive. In 1969, closing 42nd Street in New York City actually improved traffic flow. In Seoul, demolishing the Cheonggyecheon elevated highway reduced congestion.
High Price of Anarchy means markets work poorly
PoA depends on the structure of the game. In some problems PoA = 4/3 (routing)-low. In others it's unbounded. High PoA points to a need for regulation or mechanism redesign.
A market with price competition has PoA close to 1 (very efficient). The tragedy of the commons or prisoner's dilemma can have unbounded PoA.
Price of Anarchy (PoA) measures:
Congestion Games and Potential Games
A congestion game: each player chooses a set of resources (roads, servers), and the cost of each resource grows with the number of users. Why do we care about this class? Because it has a remarkable property: a Nash Equilibrium in pure strategies always exists. The proof goes through a **potential function**-a scalar function that increases with every player's improvement move.
A game is a potential game if there exists Φ(s) such that: uᵢ(sᵢ', s₋ᵢ) - uᵢ(sᵢ, s₋ᵢ) = Φ(sᵢ', s₋ᵢ) - Φ(sᵢ, s₋ᵢ) Every move that improves a player's payoff increases Φ. Since Φ is bounded above, Best Response Dynamics converges, so a pure NE exists. Congestion games are potential with Φ(s) = Σ_r Σ_{k=1}^{nᵣ(s)} cᵣ(k)
Potential games are the best-studied class in algorithmic GT. Their properties: guaranteed pure NE, convergence of best-response dynamics, and a tight connection to optimization (minimizing Φ equals the social optimum in some cases). TCP congestion control is a congestion game at the transport layer.
TCP/IP is a purely engineering protocol, unrelated to game theory
TCP congestion control is exactly a congestion game: each connection "chooses" a transmission rate, and the cost (delay/loss) grows with load. The AIMD algorithm (Additive Increase Multiplicative Decrease) is an engineered best-response.
Internet routing, cloud resource allocation-all congestion games. Understanding PoA and potential functions helps design better protocols.
Why does a pure-strategy Nash Equilibrium always exist in congestion games?
Network Routing and Braess's Paradox
Braess's Paradox: adding a zero-latency road to a network can increase travel time for EVERYONE. Why? Everyone wants to use the "fast" road, creating congestion. Worse, that congestion outweighs the benefit of the shortcut. The fix: remove the road. A counterintuitive result with serious practical consequences.
Network: S→A, S→B, A→T, B→T (all latency 1), plus A→B with zero latency. Without A→B: NE = split evenly between S→A→T and S→B→T, latency = 1.5 With A→B: NE = everyone uses S→A→B→T, latency = 2 (worse!) PoA for routing networks with linear latency functions = 4/3 (Roughgarden-Tardos, 2002)
Practical implications of Braess's Paradox: in internet routing, adding a direct link can degrade overall throughput. In finance, adding a new financial instrument (a derivative) can destabilize the market. The regulatory takeaway: network design must account for strategic agent behavior.
Braess's Paradox is purely theoretical and doesn't apply to real transport networks
In Seoul, demolishing the Cheonggyecheon elevated highway in 2003 improved traffic. Similar effects were documented in Stuttgart. In NYC, closing 42nd Street on a Car-Free Day reduced congestion.
Real transport networks have the structure that lets the paradox materialize. This became the basis of "demand management"-deliberately restricting some roads to reduce total congestion.
Braess's Paradox states that in a routing game:
Computational Complexity of Finding NE
Nash proved equilibrium exists. But how is it found? It turns out to be surprisingly hard. Finding a NE in a general game is PPAD-complete (Daskalakis, Goldberg, Papadimitriou, 2006). PPAD is a complexity class where existence is guaranteed but finding the solution is exponentially hard. In other words: a NE always exists, but computing it takes astronomical time in the worst case.
PPAD (Polynomial Parity Arguments on Directed graphs): a class of problems reducible to finding an end-of-path in a graph. GNash = finding NE in a 2-player bimatrix game is PPAD-complete. Corollary: if P ≠ NP (almost certainly true), there is no polynomial algorithm for finding NE in general games. In practice: approximations and special cases work.
| Game Class | NE Finding Complexity | Algorithm |
|---|---|---|
| Zero-sum 2-player | Polynomial | LP (simplex / ellipsoid) |
| 2-player bimatrix | PPAD-complete | Support enumeration, Lemke-Howson |
| Congestion game | Polynomial | Best Response Dynamics (converges) |
| General n-player | PPAD-complete | No efficient algorithm |
If NE is so hard to find, how do real systems work? Several answers: 1. Special structures (zero-sum, potential games) are efficiently solvable. 2. Approximations (ε-NE) are good enough in practice. 3. No-regret online learning converges to a coarse correlated equilibrium, not NE-weaker but efficiently computable. 4. Real markets operate through price signals, not by computing NE.
Since NE is hard to compute, Nash's theorem is useless in practice
PPAD-completeness is a worst-case result. In practice: zero-sum games are solvable via LP; correlated equilibria are computable; no-regret dynamics are practical. Nash's theorem is valuable as a conceptual analysis tool.
Most real systems don't need an exact NE-an epsilon-NE or coarse correlated equilibrium is enough and efficiently computable via no-regret learning.
What does PPAD-completeness of the Nash Equilibrium problem mean?
Key Ideas
- **Price of Anarchy:** PoA = (worst NE) / (social optimum)-the cost of selfishness. For linear routing PoA = 4/3
- **Congestion games:** pure NE always exists via potential function-TCP, routing, cloud computing
- **Braess's Paradox:** adding a road can hurt everyone-a counterintuitive consequence of strategic behavior
- **PPAD-completeness:** finding NE is exponentially hard in general; in practice, approximations and no-regret learning
Related Topics
Algorithmic GT is a bridge between game theory and computer science:
- Zero-Sum Games — Zero-sum NE is findable in polynomial time via LP-an efficient special case
- Mechanism Design — Mechanisms are designed so that PoA = 1 or is minimized
- Game Theory in ML — No-regret learning in ML = approach to correlated equilibrium in AGT
Вопросы для размышления
- Kubernetes automatically schedules pods across nodes-is this a congestion game? What would PoA look like for a naive greedy scheduler?
- Braess's Paradox in software: adding a cache can sometimes slow down a system (cache invalidation storms). How is this analogous to the routing paradox?
- No-regret learning guarantees convergence to a coarse correlated equilibrium, not NE. Is that good enough for practical systems? When does the difference matter?