Game Theory

Algorithmic Game Theory: Price of Anarchy

Algorithmic game theory studies the computational complexity of finding equilibria and the price of decentralization. Key questions: how much worse is equilibrium than the optimum (PoA), and how do you design mechanisms with the right incentives?

  • **Google AdWords:** the generalized second-price (GSP) auction earns 237 billion dollars per year; the design is inspired by VCG
  • **Transport networks:** Braess's paradox explains why closing roads sometimes improves traffic; PoA = 4/3 for linear delays
  • **Distributed computing:** Tor (anonymity) and BitTorrent (tit-for-tat) protocols are mechanism-design implementations with the right incentives

Предварительные знания

  • Prev Lesson

Price of Anarchy

Braess's paradox: adding a new road to Stuttgart's transport network in 1969 increased the average travel time for every driver. This runs counter to intuition. The price of anarchy for routing with linear latencies is at most 4/3 - a result of Roughgarden and Tardos (2002).

PoA = 4/3 for network routing with linear delays means...

Mechanism Design

In 2002 Google launched the AdWords auction system using second-price pricing (Vickrey auction). By 2023 Google's advertising revenue reached 237 billion dollars. The Vickrey auction is the only dominant-strategy mechanism that maximizes total value under truthful reporting.

Why is truthful bidding a dominant strategy in a Vickrey (second-price) auction?

Smoothness Framework for PoA Bounds

Roughgarden (2009) proposed a unified smoothness framework for proving upper bounds on the price of anarchy across a wide class of games. Key advantage: the method applies to correlated equilibria, not just Nash, which makes the results far more general.

The smoothness framework unifies PoA proofs across different game classes: congestion games, pay-per-click auctions (GSP), knapsack-type problems. Unlike potential functions, smoothness applies even where no potential exists.

Why is Roughgarden's smoothness framework stronger than directly proving PoA bounds for Nash equilibria?

The smoothness framework proves a single inequality that holds for all equilibrium types (Nash, correlated, coarse correlated). That makes the result more general: PoA <= lambda/(1 - mu) is guaranteed for the entire equilibrium class.

Key ideas

  • **Price of Anarchy PoA:** max(Nash_cost)/opt_cost; for routing with linear delays PoA = 4/3 (Roughgarden-Tardos)
  • **Price of Stability PoS:** min(Nash_cost)/opt_cost; PoS = 1 means the optimum is itself an equilibrium
  • **VCG mechanisms:** IC + IR + efficiency; payment = the agent's externality on the others
  • **Myerson's theorem:** IC <=> monotonicity of x_i + the payment formula; the maximum-revenue auction formula
  • **Smoothness framework:** a (lambda, mu)-smooth game has PoA <= lambda/(1 - mu); the result extends to correlated equilibria

Вопросы для размышления

  • Why does Braess's paradox arise from selfish play rather than from a network design mistake?
  • How are IC compatibility of a mechanism and monotonicity of the allocation function related (Myerson's theorem)?
  • Why does the Myerson-Satterthwaite theorem make the ideal mechanism impossible?
Algorithmic Game Theory: Price of Anarchy

0

1

Sign In