CO 759: Algorithmic Game Theory

These notes synthesize material from three primary sources: Tim Roughgarden’s Twenty Lectures on Algorithmic Game Theory (Stanford CS364A, Fall 2013) and the accompanying YouTube lecture videos; the textbook Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani (Cambridge, 2007); and Chaitanya Swamy’s CO 759 course at the University of Waterloo. Research papers by Lavi–Swamy, Dughmi–Roughgarden, Christodoulou–Koutsoupias, and Bhawalkar–Roughgarden are cited where their results appear.

Chapter 1: Games and Solution Concepts

Algorithmic game theory sits at the intersection of two intellectual traditions. Economics has long studied how rational agents interact — what equilibria look like, when they exist, and whether they are efficient. Computer science brings a complementary set of questions: Can equilibria be computed efficiently? Can we design systems where strategic behavior leads to approximately optimal outcomes, even when exact optimization is intractable? The field was born from the realization that neither discipline alone could answer the questions raised by the Internet, online markets, and large-scale decentralized systems.

This chapter establishes the foundational language: games, strategies, equilibria, and the metrics that quantify how badly selfish behavior can damage social welfare.

1.1 Strategic-Form Games and Dominant Strategies

The basic object of study is a strategic-form game (also called a normal-form game). Such a game consists of three ingredients:

When we say a player is “rational,” we mean the player chooses a strategy to minimize its own cost (or maximize its own utility), taking the other players’ behavior into account. The simplest — and strongest — form of rational behavior is playing a dominant strategy: one that is optimal regardless of what everyone else does.

Dominant-strategy equilibria are the gold standard: they require no assumptions about others’ rationality, no coordination, no beliefs about the game. Unfortunately, most interesting games do not possess them. The Prisoner’s Dilemma is a celebrated exception.

The Prisoner’s Dilemma teaches a lesson that will recur throughout these notes: rational behavior by individuals can produce outcomes that are socially suboptimal. The entire field of mechanism design (Chapters 2–6) is, in a sense, the science of closing this gap by carefully choosing the rules of the game.

1.2 Pure and Mixed Nash Equilibria

When dominant strategies do not exist, we need a weaker solution concept. The most fundamental is the Nash equilibrium, where each player’s strategy is a best response to the strategies of the others — no one can unilaterally improve.

Every dominant-strategy equilibrium is a Nash equilibrium, but not conversely. In a Nash equilibrium, a player’s strategy need only be optimal given the specific strategies chosen by the others — not for all possible strategies of the others.

Not every game has a pure Nash equilibrium. The canonical example is Rock-Paper-Scissors. Whatever pure strategy profile is proposed, one player can switch and improve:

A crucial idea, developed largely by John von Neumann, is to allow players to randomize. A mixed strategy for player \(i\) is a probability distribution \(\sigma_i\) over \(S_i\). In Rock-Paper-Scissors, if both players randomize uniformly over the three strategies, neither can improve their expected payoff by deviating — this is a mixed-strategy Nash equilibrium.

Every PNE is a special case of an MNE (where each \(\sigma_i\) is a point mass). The remarkable guarantee is that mixed Nash equilibria always exist:

Nash’s theorem is proved via Brouwer’s (or Kakutani’s) fixed-point theorem. It is an existence result, not an algorithmic one. As we will see in Chapter 12, computing a Nash equilibrium is PPAD-complete even for two-player games — a complexity class that captures problems where existence is guaranteed by a parity argument but efficient computation is believed to be impossible.

1.3 Correlated and Coarse Correlated Equilibria

The computational intractability of Nash equilibria motivates the search for more permissive equilibrium concepts. The key relaxation is to allow players’ strategies to be correlated — coordinated by a trusted mediator or public signal — rather than independently randomized.

The equilibrium concepts we study form a nested hierarchy:

where each inclusion is strict in general. Moving outward enlarges the set of equilibria, which trades off stronger existence and tractability guarantees against weaker behavioral assumptions.

The interpretation is elegant. A trusted third party (the “mediator”) samples an outcome \(\mathbf{s}\) from \(\sigma\), then privately tells each player \(i\) its recommended strategy \(s_i\). Player \(i\) observes \(s_i\) but not the full outcome. Knowing the distribution \(\sigma\) and its own recommendation, player \(i\) conditions on \(s_i\) and checks: is following the recommendation at least as good as any deviation? If so for every player and every recommendation, \(\sigma\) is a correlated equilibrium.

An even more permissive concept drops the conditioning:

The difference is subtle but important. In a CE, a player considers deviating after seeing its recommendation — a conditional guarantee. In a CCE, a player commits to a deviation before seeing its recommendation — an unconditional guarantee. Since the unconditional constraint is weaker, every CE is a CCE, but not conversely.

Why should we care about CCE? Two reasons. First, as we will prove in Chapter 10, natural learning dynamics (specifically, no-regret algorithms) converge to the set of CCE. This means that if players repeatedly play a game and adjust their strategies using simple, well-studied learning rules, the empirical distribution of play approaches a CCE. Second, for a large and important class of games — the smooth games of Chapter 9 — price-of-anarchy bounds extend automatically from PNE all the way to CCE. This means we can prove efficiency guarantees for the outcomes of learning dynamics, not just for idealized equilibria.

1.4 Price of Anarchy and Price of Stability

The central quantitative question of algorithmic game theory is: how much efficiency is lost due to selfish behavior? The two standard metrics compare equilibrium outcomes to the social optimum.

When the PoA is close to 1, selfish behavior is essentially benign — there is little reason to intervene. When the PoA is large, mechanism design or regulation may be needed to improve outcomes.

The most vivid illustration of PoA > 1 is Braess’s paradox, which shows that adding capacity to a network can make all users worse off.

         v
        / \
  c=x  /   \ c=1
      /     \
  s          t
      \     /
  c=1  \   / c=x
        \ /
         w

Braess’s paradox is not a mathematical curiosity. Real road networks exhibit this phenomenon: Seoul, South Korea, demolished a major highway through the city center in 2003 and found that traffic flow improved. The paradox arises in electrical networks too — Cohen and Horowitz (1991) demonstrated a mechanical analogue with strings and springs where severing a taut string causes a heavy weight to rise, in direct correspondence with removing the zero-cost link in Braess’s network.

The overarching theme of Part III (Chapters 7–9) will be to identify broad classes of games where the PoA is provably small — where selfish behavior, despite being suboptimal, is not too far from the social optimum.

Chapter 2: Mechanism Design Foundations

Chapter 1 took games as given and asked how players behave. Mechanism design inverts the question: given strategic players, how should we design the rules of the game so that self-interested behavior leads to a desirable outcome? As Hartline and Kleinberg memorably put it after the 2012 Olympic badminton scandal — in which teams deliberately tried to lose matches to secure favorable bracket positions — “the next time we bemoan people exploiting loopholes to subvert the intent of the rule makers, instead of asking ‘What’s wrong with these people?’ let’s instead ask ‘What’s wrong with the rules?’ and then adopt a scientifically principled approach to fixing them.”

Mechanism design is the science of rule-making. Its killer applications include Internet search auctions, wireless spectrum sales, matching medical residents to hospitals, school choice, and kidney exchange markets. This chapter builds the foundational framework: single-parameter environments, dominant-strategy incentive compatibility, Myerson’s Lemma, the Revelation Principle, and the VCG mechanism.

2.1 Single-Parameter Environments

The cleanest setting for mechanism design is one where each participant’s private information is captured by a single number. This abstraction covers a remarkable range of applications.

The term “single-parameter” refers to the fact that each bidder’s private information is the single number \(v_i\). The feasible set \(X\) is public knowledge. Examples include:

• Single-item auction: \(X = \{0,1\}^n\) with \(\sum_i x_i \leq 1\). Each \(x_i\) indicates whether bidder \(i\) wins the item.
• \(k\) identical items: \(X = \{0,1\}^n\) with \(\sum_i x_i \leq k\).
• Sponsored search: \(X\) consists of assignments of bidders to advertising slots, where \(x_i = \alpha_j\) if bidder \(i\) is assigned to slot \(j\) with click-through rate \(\alpha_j\), and \(x_i = 0\) if unassigned.

A sealed-bid mechanism in this setting operates in three steps: (1) collect bids \(\mathbf{b} = (b_1, \ldots, b_n)\); (2) choose an allocation \(\mathbf{x}(\mathbf{b}) \in X\) via an allocation rule; (3) choose payments \(\mathbf{p}(\mathbf{b}) \in \mathbb{R}^n\) via a payment rule.

2.2 Dominant-Strategy Incentive Compatibility

The designer’s goal is to construct mechanisms where bidders willingly reveal their true valuations, regardless of what others do.

DSIC mechanisms are desirable for two reasons. From a bidder’s perspective, participating is risk-free: bid truthfully and you can’t lose money. From the designer’s perspective, outcomes are predictable: since truthful bidding is a dominant strategy, the mechanism’s performance doesn’t depend on assumptions about bidder sophistication or beliefs about others.

The prototype of a DSIC mechanism is the Vickrey auction (or second-price auction) for a single item.

The Vickrey auction is remarkable: it simultaneously achieves DSIC, maximizes social surplus (the item goes to the bidder who values it most), and runs in linear time. Roughgarden calls such mechanisms “awesome” — they satisfy all three desiderata of incentive compatibility, welfare maximization, and computational efficiency. The central question of mechanism design is: for which problems beyond single-item auctions can we design “awesome” mechanisms?

2.3 Myerson’s Lemma

The Vickrey auction solves Step 2 of mechanism design (determining payments) for single-item auctions. But what about more complex allocation problems — sponsored search with multiple slots, knapsack auctions, scheduling? Myerson’s Lemma provides a universal answer for all single-parameter environments.

The key definitions concern the allocation rule alone:

Monotonicity is a natural condition: bidding higher should only get you more stuff. The allocation rule that gives the item to the highest bidder is monotone. The rule that gives the item to the second-highest bidder is not — raising your bid enough causes you to go from winner to loser.

Myerson’s Lemma is the foundation of single-parameter mechanism design. Part (a) says that monotonicity completely characterizes which allocation rules can be part of a DSIC mechanism — a clean, checkable condition replaces the unwieldy DSIC definition. Part (b) says there is no design freedom left once the allocation rule is fixed: the payments are uniquely determined. Part (c) gives a constructive formula.

Myerson’s payment formula has a beautiful geometric interpretation: \(p_i\) equals the area to the left of the allocation curve \(x_i(z, \mathbf{b}_{-i})\) in the range \([0, b_i]\). The bidder’s utility — the area under the allocation curve — is the “consumer surplus.”

As a sanity check, consider the single-item auction with the highest-bidder-wins allocation rule. The allocation curve \(x_i(z, \mathbf{b}_{-i})\) jumps from 0 to 1 at \(z = B = \max_{j \neq i} b_j\). The payment formula gives \(p_i = B \cdot 1 = B\) — exactly the second-price rule. Myerson’s Lemma subsumes the Vickrey auction as a special case.

Application to Sponsored Search. Consider \(k\) slots with click-through rates \(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_k\). The welfare-maximizing allocation assigns the \(j\)-th highest bidder to the \(j\)-th best slot. Re-index so \(b_1 \geq b_2 \geq \cdots \geq b_n\). For the bidder assigned to slot \(i\), the allocation \(x_i(z, \mathbf{b}_{-i})\) increases from 0 to \(\alpha_1\) as \(z\) rises from 0 to \(b_1\), with a jump of \(\alpha_j - \alpha_{j+1}\) at each breakpoint \(b_{j+1}\) (where \(\alpha_{k+1} = 0\)). Applying Myerson’s payment formula yields:

This is the unique DSIC payment rule for sponsored search. The actual payment used by Google and Bing is the simpler Generalized Second Price (GSP) auction, where each bidder pays the next-lowest bid per click. Since GSP differs from the Myerson payment, Myerson’s Lemma immediately tells us that GSP is not DSIC — though it has other nice equilibrium properties.

2.4 Social Choice Functions and the Revelation Principle

Myerson’s Lemma is powerful but limited to single-parameter settings. For problems where agents have preferences over multiple items — combinatorial auctions, resource allocation, facility location — we need a more general framework.

The outcome set \(\Omega\) can be very large. In a combinatorial auction with \(n\) bidders and \(m\) items, \(\Omega\) consists of all \((n+1)^m\) allocations of items to bidders (each item goes to one bidder or remains unallocated), and each bidder’s type is a valuation over all \(2^m\) bundles — an exponentially large object.

A social choice function \(f\) maps the agents’ types to an outcome: \(f(v_1, \ldots, v_n) \in \Omega\). The goal of mechanism design is to implement a desirable social choice function — that is, to design a game whose equilibrium outcome coincides with the output of \(f\), even though the agents’ types are private.

A direct mechanism asks each agent to report its type and then applies \(f\) and a payment rule. The Revelation Principle (whose proof extends to multi-parameter settings) says this is without loss of generality:

The Revelation Principle vastly simplifies the design problem: instead of searching over all possible game forms, we need only consider direct mechanisms where agents report their types truthfully.

2.5 The VCG Mechanism

The most important social choice function is welfare maximization: choose the outcome \(\omega^*\) that maximizes the sum of agents’ values. In single-parameter environments, the Vickrey auction solves this. The Vickrey-Clarke-Groves (VCG) mechanism extends the idea to arbitrary multi-parameter environments.

The Clarke pivot payment has a beautiful interpretation: agent \(i\) pays the damage its presence inflicts on the other agents. In a single-item Vickrey auction, the winning bidder’s externality is \(b_2\) (the second-highest bid), since without the winner, the second-highest bidder would have won at zero cost. VCG thus generalizes the second-price rule.

The VCG mechanism is the crown jewel of mechanism design: it works in any environment and always maximizes welfare. But it has three significant limitations that motivate the rest of our study:

1. Computational intractability. The allocation rule requires solving \(\arg\max_{\omega \in \Omega} \sum_i b_i(\omega)\), which is NP-hard for combinatorial auctions and many other settings. You cannot simply plug in an approximation algorithm — swapping the exact welfare maximizer for an approximation can destroy the DSIC property.

2. Communication complexity. In a combinatorial auction with \(m\) items, each bidder’s type has \(2^m\) parameters. No protocol can elicit these types with polynomial communication in the worst case.

3. Revenue pathology. The VCG mechanism can generate zero revenue even in competitive environments. Consider two items \(A, B\) and three bidders: bidder 1 values \(\{A,B\}\) at 1 and everything else at 0; bidder 2 values \(\{A\}\) at 1 and everything else at 0; bidder 3 values \(\{B\}\) at 1 and everything else at 0. The welfare-maximizing allocation gives \(A\) to bidder 2 and \(B\) to bidder 3 (total welfare 2, versus 1 for giving both to bidder 1). But each winning bidder’s Clarke pivot payment is 0: removing bidder 2, the optimal welfare from the others is still 1 (give \(\{A,B\}\) to bidder 1); with bidder 2, the others get welfare 1 (bidder 3 gets \(B\)). No externality, no payment.

These limitations drive the three major research directions we pursue in the following chapters: characterizing implementability beyond VCG (Chapter 3), maximizing revenue rather than welfare (Chapter 4), and designing computationally efficient approximate mechanisms (Chapter 5).

Chapter 3: Characterizing Implementability

Myerson’s Lemma (Theorem 2.5) gave a complete characterization of DSIC mechanisms in single-parameter environments: an allocation rule is implementable if and only if it is monotone. But many important problems — combinatorial auctions, multi-facility location, scheduling with multiple job types — are inherently multi-parameter: each agent’s private type is a vector of valuations, not a single number. In such settings, what characterizes implementability? This chapter develops the answer, following Swamy’s treatment of weak monotonicity, Roberts’ theorem, and the role of randomization.

3.1 Weak Monotonicity (WMON)

The natural generalization of monotonicity to multi-parameter domains is weak monotonicity, sometimes called WMON or 2-cycle monotonicity.

The intuition is clean: if agent \(i\) changes its reported type from \(\mathbf{v}_i'\) to \(\mathbf{v}_i\), the change in the outcome should be “aligned” with the change in the agent’s preferences. When \(i\) reports a type that values outcome \(\omega\) more highly, the mechanism should be more likely to choose \(\omega\).

In single-parameter environments, WMON reduces to ordinary monotonicity: if there is only one dimension of private information (a scalar valuation \(v_i\)), then the condition says that increasing \(v_i\) should lead to a weakly larger allocation \(x_i\) — exactly the monotonicity condition of Myerson’s Lemma.

WMON is a necessary condition for implementability. The deep question is: when is it sufficient?

3.2 Characterization in Single-Dimensional and Convex Domains

For single-parameter environments, Myerson’s Lemma tells us that WMON (which reduces to monotonicity) is both necessary and sufficient for implementability. This extends to certain multi-parameter settings.

A domain \(V_i\) for agent \(i\) is the set of possible types. The domain is convex if for any two types \(\mathbf{v}_i, \mathbf{v}_i' \in V_i\) and any \(\lambda \in [0,1]\), the type \(\lambda \mathbf{v}_i + (1-\lambda)\mathbf{v}_i'\) is also in \(V_i\). Many natural domains are convex: the set of all additive valuations, the set of all submodular valuations over a continuous relaxation, or the full type space \(\mathbb{R}^{|\Omega|}\).

The proof, which we omit, proceeds by showing that WMON implies the absence of negative-weight cycles in a certain “type graph” whose nodes are types and whose edge weights encode the incentive constraints. The absence of negative cycles allows one to construct payments via shortest-path distances from a reference type — a beautiful connection to network optimization.

For non-convex domains, WMON is generally not sufficient. One needs the stronger condition of cycle monotonicity (no negative-weight cycles of any length in the type graph, not just length 2). Cycle monotonicity is always necessary and sufficient, but it is much harder to verify in practice than WMON.

3.3 Roberts’ Theorem and Affine Maximizers

What happens when the domain is completely unrestricted — when agents can have arbitrary valuations over all outcomes? Roberts’ theorem gives a striking and restrictive answer.

Affine maximizers are a slight generalization of welfare maximization: instead of maximizing the unweighted sum of values, they maximize a weighted sum plus outcome-specific bonuses. The VCG mechanism is the special case where all \(\lambda_i = 1\) and all \(\gamma_\omega = 0\).

Roberts’ theorem is the multi-parameter analogue of the Gibbard-Satterthwaite theorem (which concerns settings without money). Its message is both elegant and discouraging: in unrestricted domains, the only truthful mechanisms are minor variants of VCG. There is essentially no room for creative mechanism design. Revenue maximization, approximate welfare maximization, fairness objectives — none of these can be achieved truthfully in unrestricted domains.

This impossibility is what makes restricted domains so important. The positive results in algorithmic mechanism design (Chapter 5) work precisely because the domains are restricted — single-minded bidders, submodular valuations, single-parameter environments — where WMON is weaker than full cycle monotonicity and a richer class of mechanisms becomes implementable.

3.4 Truthful-in-Expectation Mechanisms

Another way to escape the straitjacket of Roberts’ theorem is to relax the solution concept from deterministic DSIC to randomized truthfulness.

This is weaker than universal truthfulness, which requires that truthfulness hold for every realization of the mechanism’s randomness (i.e., every deterministic mechanism in the support is DSIC). In a universally truthful mechanism, a risk-averse agent has no incentive to lie; in a TIE mechanism, an agent who dislikes variance might prefer to misreport.

Despite this weakness, TIE mechanisms are tremendously useful in algorithmic mechanism design because they are much easier to construct. The key insight, developed by Lavi and Swamy (2011), is that any LP-based approximation algorithm can be converted into a TIE mechanism with the same approximation guarantee — a black-box reduction that we will develop in detail in Chapter 5.

The gap between deterministic DSIC and TIE can be dramatic. For combinatorial auctions with submodular valuations, the best deterministic DSIC mechanism achieves an \(O(\sqrt{m})\)-approximation to welfare, while TIE mechanisms can achieve a \((1 - 1/e)\)-approximation — exponentially better in terms of the number of items.

Chapter 4: Revenue-Maximizing Auctions

Chapters 2–3 focused on welfare maximization: choosing the outcome that maximizes the sum of agents’ values. But in many settings — a seller on eBay, a government auctioning spectrum licenses, a search engine selling keyword ads — the designer’s goal is to maximize revenue: the total payment collected from the agents. This chapter develops the theory of revenue-optimal auctions, from Myerson’s foundational characterization through the prophet inequality and the Bulow-Klemperer theorem.

4.1 The Revenue Maximization Challenge

Revenue maximization is fundamentally different from welfare maximization in one crucial respect: there is no input-independent optimal mechanism. For welfare, the VCG mechanism is optimal regardless of agents’ valuations. For revenue, the best mechanism depends on what the valuations are — which are, of course, private information.

Consider a single bidder and a single item. The only DSIC mechanisms are posted prices: set a price \(r\), and the bidder buys if and only if \(v \geq r\). If you knew \(v\), you would set \(r = v\) and extract the full surplus. Without knowing \(v\), different prices perform differently on different inputs. A price of 20 is excellent when \(v = 25\) but terrible when \(v = 5\).

This input-dependence forces a Bayesian approach: assume bidders’ valuations are drawn from known distributions and optimize expected revenue. The distributions are typically estimated from historical data (past auction outcomes, bidding histories, market research).

4.2 Virtual Valuations and Myerson’s Optimal Auction

The key insight of Myerson (1981) is that expected revenue can be expressed purely in terms of the allocation rule — no reference to payments — via a change of variables called virtual valuations.

The virtual valuation has a compelling economic interpretation. The first term, \(v_i\), is what the mechanism designer would ideally charge bidder \(i\). The second term, \(\frac{1-F_i(v_i)}{f_i(v_i)}\), is the information rent — the inevitable revenue loss due to not knowing \(v_i\) in advance. A bidder with high valuation earns a surplus because the mechanism cannot distinguish it from a lower-valuation bidder without giving up revenue. The virtual valuation accounts for this trade-off.

For a bidder drawn from the uniform distribution on \([0,1]\): \(F(v) = v\), \(f(v) = 1\), so \(\varphi(v) = 2v - 1\). The virtual valuation is negative for \(v < 1/2\), meaning that selling to a low-valuation bidder actually decreases expected revenue — the information rent exceeds the payment.

This identity transforms the revenue-maximization problem into a virtual-welfare-maximization problem. Instead of searching over the complex space of DSIC mechanisms, we simply choose the allocation that maximizes the sum of virtual valuations — then apply Myerson’s payment formula.

Regular distributions include uniform, exponential, normal, and lognormal distributions. Irregular distributions (e.g., bimodal distributions with sufficiently heavy tails) have non-monotone virtual valuation functions.

When distributions are regular, the virtual-welfare-maximizing allocation rule is monotone (because \(\varphi_i\) is increasing, a higher \(v_i\) means a higher \(\varphi_i(v_i)\), which leads to a weakly larger allocation), so Myerson’s Lemma guarantees that the corresponding payments yield a DSIC mechanism.

For a single-item auction with i.i.d. regular bidders, the optimal auction has a beautifully simple form: run a Vickrey auction with a reserve price of \(\varphi^{-1}(0)\). Since all bidders share the same increasing virtual valuation function, the bidder with the highest real valuation also has the highest virtual valuation — so the item goes to the highest bidder, just as in a Vickrey auction. The reserve price ensures that bidders with negative virtual valuations (those below \(\varphi^{-1}(0)\)) are excluded. For uniform \([0,1]\) valuations, the reserve price is \(\varphi^{-1}(0) = 1/2\).

For irregular distributions, the virtual valuation function is not monotone, and the virtual-welfare-maximizing allocation rule may not be monotone either. Myerson’s solution is to iron the virtual valuation function — replace non-monotone portions with their ironed (flattened) versions — to recover monotonicity while preserving expected virtual welfare. We refer to Hartline’s book for the details.

4.3 The Prophet Inequality

The theory of Bayesian optimal auctions is powerful but requires detailed knowledge of the distributions \(F_1, \ldots, F_n\). The prophet inequality, from optimal stopping theory, leads to simpler mechanisms that are approximately optimal without requiring identical distributions.

The connection to mechanism design is elegant. In a single-item auction with non-i.i.d. regular bidders, regard the nonnegative virtual valuation \(\varphi_i(v_i)^+\) as the “prize” \(\pi_i\). The optimal auction’s expected revenue is \(\mathbf{E}[\max_i \varphi_i(v_i)^+]\). By the prophet inequality, the following simple auction achieves at least half this revenue:

1. Set a bidder-specific reserve price \(r_i = \varphi_i^{-1}(t)\) for each bidder \(i\), where \(t\) is the prophet threshold.
2. Give the item to the highest bidder among those meeting their reserve.

This auction is qualitatively simpler than the optimal auction: the highest real bidder wins (not the highest virtual bidder), and the reserve prices depend only on a single threshold rather than on the full distributions.

4.4 Simple Near-Optimal Auctions and the Bulow-Klemperer Theorem

The most celebrated result on simple auctions is the Bulow-Klemperer theorem, which shows that competition is more valuable than optimization: a simple Vickrey auction with one extra bidder generates more revenue than the optimal auction.

The left-hand side is a Vickrey auction — the simplest possible format, with no reserve price — in an environment with \(n+1\) i.i.d. bidders. The right-hand side is the best possible auction in an environment with only \(n\) bidders but with full knowledge of \(F\). The Vickrey auction is prior-independent: its description doesn’t depend on \(F\). Yet it outperforms the tailored optimal auction, simply by having one more participant.

The practical lesson of Bulow-Klemperer is profound: invest in attracting more bidders rather than in optimizing the auction format. This insight applies far beyond formal auctions — it suggests that, in many market settings, encouraging competition is more effective than fine-tuning pricing.

Case study: Yahoo! keyword auctions. Ostrovsky and Schwarz (2009) tested Myerson’s theory on Yahoo!’s sponsored search auctions. They fitted lognormal distributions to half a million keywords and computed theoretically optimal reserve prices. Yahoo! had been using a uniform reserve of $0.10 across all keywords — far below the optimal reserve for valuable keywords like “divorce lawyer” (optimal reserve: $0.30–$0.40) and above it for cheap keywords. Implementing keyword-specific optimal reserve prices increased auction revenue by several percent — a substantial gain given Yahoo!’s multi-billion-dollar search revenue.

Chapter 5: Combinatorial Auctions and Approximation

The VCG mechanism (Theorem 2.8) provides a DSIC welfare-maximizing mechanism for any multi-parameter environment. But in combinatorial auctions — where \(n\) bidders compete for bundles of \(m\) items — the VCG mechanism requires solving an NP-hard welfare-maximization problem as a subroutine. Worse, one cannot simply substitute an approximation algorithm: replacing the exact welfare maximizer with an approximation can destroy the DSIC property. This chapter develops the theory of computationally efficient truthful approximation mechanisms, following Swamy’s treatment of the key results by Lavi–Swamy and Dughmi–Roughgarden.

5.1 Valuations: Subadditive, Submodular, XOS, Single-Minded

In a combinatorial auction, each bidder \(i\) has a private valuation function \(v_i : 2^M \to \mathbb{R}_{\geq 0}\), assigning a value to every bundle of items \(S \subseteq M = \{1, \ldots, m\}\). We normalize \(v_i(\emptyset) = 0\) and assume free disposal: \(v_i(S) \leq v_i(T)\) whenever \(S \subseteq T\). The structure of valuations dramatically affects both the computational complexity of welfare maximization and the possibility of truthful approximation.

Items are substitutes when \(v(S \cup T) \leq v(S) + v(T)\) (subadditivity — having one item doesn’t make others more valuable) and complements when \(v(S \cup T) > v(S) + v(T)\) (synergies). In spectrum auctions, adjacent frequency licenses are often complements (a contiguous block is more useful than scattered frequencies). Submodular valuations model pure diminishing returns, common in advertising (additional ad impressions have decreasing marginal value).

A particularly tractable special case is single-minded bidders: each bidder \(i\) desires a specific bundle \(S_i^*\) and has valuation \(v_i(S) = v_i^*\) if \(S_i^* \subseteq S\) and 0 otherwise.

5.2 VCG Limitations and the Need for Approximation

The fundamental barrier is computational. For general valuations, the welfare-maximization problem \(\max \sum_i v_i(S_i)\) subject to the bundles \(\{S_i\}\) being a partition of items is NP-hard. Even for single-minded bidders, it reduces to weighted set packing. For submodular valuations, the problem is NP-hard to approximate within a factor of \(1 - 1/e + \varepsilon\).

The crucial observation, emphasized by Nisan and Ronen (2001), is that you cannot simply plug an approximation algorithm into VCG. The VCG payment formula \(p_i = \max_{\omega \in \Omega} \sum_{j \neq i} b_j(\omega) - \sum_{j \neq i} b_j(\omega^*)\) requires exactly solving the welfare-maximization problem both with and without agent \(i\). If you replace the exact solution with an approximation, the resulting mechanism is generally not DSIC — agents can gain by manipulating their reports to steer the approximation algorithm.

This motivates the search for new mechanisms — not based on VCG — that are simultaneously truthful, computationally efficient, and approximately welfare-maximizing.

5.3 Maximal-in-Range and MIDR Mechanisms

The most natural approach to combining truthfulness with approximation is to restrict the set of outcomes that the mechanism considers, then optimize exactly over this restricted set.

MIR mechanisms are automatically DSIC (they are VCG mechanisms on a restricted outcome space). The challenge is choosing \(R\) so that (a) optimizing over \(R\) is computationally tractable and (b) the welfare of the best outcome in \(R\) is close to the unconstrained optimum.

For certain valuation classes, MIR mechanisms can achieve good approximations. For single-minded bidders, an MIR mechanism based on greedy selection achieves an \(O(\sqrt{m})\)-approximation.

A more powerful generalization is maximal-in-distributional-range (MIDR): instead of a fixed range \(R\), the mechanism uses a distribution over outcomes, and the allocation rule maximizes the expected declared welfare over this distribution. MIDR mechanisms are truthful-in-expectation (TIE) rather than deterministically DSIC, but they can achieve significantly better approximation ratios.

5.4 LP-Based Black-Box Reductions (Lavi-Swamy)

The breakthrough result of Lavi and Swamy (2011) shows that any LP-based approximation algorithm can be converted into a truthful-in-expectation mechanism with the same approximation guarantee — a black-box reduction that requires no mechanism-specific analysis.

The setting is a general allocation problem where the welfare-maximization problem can be written as an integer program (IP), and we have access to its LP relaxation. The LP relaxation, being a convex program, can be solved in polynomial time (using the ellipsoid method, given a separation oracle).

The key idea is elegant. Rather than rounding a fixed LP solution (which could destroy monotonicity), the mechanism randomizes over integral solutions in the support of the LP optimum. The LP optimal solution can be expressed as a convex combination of integer solutions (vertices of the LP polytope). The mechanism samples an integer solution from this decomposition and applies VCG payments to the sampled outcome. Because the expectation over the randomization matches the LP objective, the expected welfare achieves the LP bound. Because the randomization is over outcomes (not payments), the mechanism is truthful-in-expectation.

More precisely, the construction proceeds as follows:

1. Solve the LP relaxation of the welfare-maximization problem using reported valuations as the objective coefficients.
2. Decompose the fractional LP solution into a convex combination of integral solutions.
3. Sample an integral solution from this decomposition.
4. Charge VCG payments for the sampled outcome, computed over the restricted range of outcomes in the decomposition.

The decomposition step uses the fact that any point in a polytope can be written as a convex combination of at most \(d+1\) vertices, where \(d\) is the dimension of the polytope. This decomposition can be computed efficiently via Carathéodory’s theorem.

5.5 FPTAS to Truthful FPTAS (Dughmi-Roughgarden)

For problems where an FPTAS (fully polynomial-time approximation scheme) exists, Dughmi and Roughgarden (2010) showed that this can be converted into a truthful FPTAS — a \((1-\varepsilon)\)-approximation truthful-in-expectation mechanism for any \(\varepsilon > 0\).

The key technical challenge is that standard FPTAS constructions (based on dynamic programming with rounded values) are not monotone. A bidder who increases its reported valuation might get less allocation due to rounding artifacts.

The proof uses a technique called smoothed analysis of monotonicity: by slightly perturbing the rounding in the FPTAS, one can ensure that the resulting allocation rule is monotone in a distributional sense, enabling a truthful-in-expectation mechanism. The perturbation does not significantly affect the approximation ratio — the mechanism still achieves a \((1-\varepsilon)\)-approximation.

5.6 Applications

These black-box reduction frameworks have been applied to several concrete problems from Swamy’s course:

Set cover. The greedy set cover algorithm achieves an \(O(\log n)\)-approximation to welfare for set cover auctions (where items are elements to be covered and bidders own sets). The greedy algorithm is inherently monotone — adding an element to a set can only help the set’s coverage ratio — so it directly yields a DSIC \(O(\log n)\)-approximation mechanism without needing the Lavi-Swamy reduction.

Facility location (Mettu-Plaxton). In metric facility location, the goal is to open facilities and assign clients to them, minimizing the total connection cost plus facility opening cost. The Mettu-Plaxton algorithm gives a constant-factor approximation. Combined with the Lavi-Swamy framework, this yields a constant-factor TIE mechanism for facility location with strategic clients.

Makespan minimization on related machines. Jobs arrive online and must be assigned to machines with different speeds. The goal is to minimize the maximum load (makespan). This is a single-parameter environment (each machine’s private information is its speed), so Myerson’s Lemma applies. The key insight is that the natural greedy algorithm (assign each job to the machine that increases makespan least) is monotone: a faster machine is always assigned at least as much work. Combined with the approximation guarantee of the greedy algorithm, this yields a DSIC mechanism with a small constant-factor approximation to the optimal makespan.

Chapter 6: Advanced Auction Design

This chapter covers three important settings that extend mechanism design beyond the standard quasi-linear framework: spectrum auctions (where the stakes are billions of dollars and the item space is combinatorial), auctions with budget constraints (where agents cannot pay more than a fixed amount), and matching markets (where monetary transfers are forbidden entirely).

6.1 Spectrum Auctions

Wireless spectrum is among the most valuable resources auctioned by governments. Since the mid-1990s, spectrum auctions have raised hundreds of billions of dollars worldwide. The design challenges are formidable: items (spectrum licenses) are non-identical, bidders have complex combinatorial preferences (adjacent frequencies in the same geographic area are complements), and the stakes are enormous.

Simultaneous ascending auctions (SAAs) are the dominant format. Conceptually, an SAA runs parallel English auctions for all items simultaneously. Each round, bidders can place new bids on any items, subject to an activity rule that forces them to stay engaged (the number of items a bidder bids on can only decrease as prices rise). The auction ends when a round passes with no new bids.

The main advantage of SAAs over sequential or sealed-bid formats is price discovery: as the auction progresses, bidders learn about likely selling prices and can adjust their strategies accordingly — abandoning licenses whose prices are too high, snapping up bargains, and rethinking which packages to assemble. This is dramatically better than sealed-bid formats, which produced notorious disasters. In the 1990 New Zealand spectrum auction (simultaneous sealed-bid Vickrey), one license received a high bid of $100,000 and a second-highest bid of $6; another had bids of $7 million and $5,000. The revenue was a fraction of expectations.

SAAs have two well-known vulnerabilities:

1. Demand reduction. A bidder may bid for fewer items than it truly wants, to reduce competition and lower prices. Consider two identical items and two bidders: bidder 1 values each at 10 (and both at 20), bidder 2 values each at 8. In the VCG outcome, bidder 1 gets both items for revenue 8 each. But in an SAA, bidder 2 bids up to 8 on both items. If bidder 1 targets just one item, it wins cheaply; if it insists on both, it pays 16 for value 20. The temptation to reduce demand is strong.

2. The exposure problem. When items are complements, a bidder who needs a package of items faces risk: it might win some items in the package at high prices but lose others, leaving it with items it doesn’t value. Consider two non-identical items that bidder 1 values at 100 together but 0 separately. Bidder 2 will pay up to 75 for either item. Bidder 1 faces a no-win situation: to get both items, it must outbid bidder 2 on each, paying 150+ for items worth 100 together. This often leads to cautious, tentative bidding by bidders with complementary preferences.

Modern spectrum auctions address these issues through package bidding (allowing bids on bundles of items, not just individual items) and proxy rounds (an extra round after the SAA phase where bidders can submit package bids that compete with individual-item bids from the main phase). The 2017 FCC Incentive Auction — a groundbreaking “double auction” that used a reverse auction to buy back TV broadcasting licenses and a forward auction to resell the freed spectrum to wireless carriers — represented the cutting edge of spectrum auction design, incorporating greedy approximate welfare-maximization algorithms with DSIC-compatible payment rules.

6.2 Budget Constraints and the Clinching Auction

All mechanism design theory so far has assumed quasi-linear utility: bidder \(i\)’s utility is \(v_i(\omega) - p_i\), with no upper bound on payments. In practice, agents have budgets that cap their total spending. Budget constraints fundamentally change the landscape: the VCG mechanism can violate budgets, and no DSIC mechanism can simultaneously maximize welfare and respect budgets.

The clinching auction (Dobzinski, Lavi, and Nisan, 2012) elegantly handles budget constraints for identical goods. It is an ascending-price auction where goods are sold incrementally as the price rises:

Clinching Auction for Budgeted Bidders:

1. Initialize price \(p = 0\), supply \(s = m\), residual budget \(\hat{B}_i = B_i\) for each bidder.
2. While \(s > 0\): increase \(p\) until some bidder \(i\) can clinch goods — meaning the remaining supply exceeds the total demand of the other bidders: \(s - \sum_{j \neq i} \hat{D}_j(p) > 0\). Give bidder \(i\) those \(k\) excess goods at price \(p\) each. Decrease \(s\) by \(k\) and \(\hat{B}_i\) by \(p \cdot k\).
3. Here \(\hat{D}_i(p) = \min\{\lfloor \hat{B}_i / p \rfloor, s\}\) if \(p < v_i\), and 0 otherwise.

The clinching auction respects budgets by construction (goods are sold at or below a bidder’s value, and total spending never exceeds the budget). Different goods may be clinched at different prices, with prices increasing over time.

The proof of DSIC compares the utility from truthful bidding to that from any deviation. Underbidding (\(b_i < v_i\)) causes the bidder to miss goods clinched in the price interval \([b_i, v_i]\), all of which would have generated positive utility. Overbidding (\(b_i > v_i\)) causes the bidder to acquire goods in the price interval \([v_i, b_i]\), generating negative utility per good. In both cases, truthful bidding is strictly better.

6.3 Matching Without Money

Some of the most important allocation problems prohibit monetary transfers. Kidney exchange, school choice, and organ donation are governed by legal and ethical constraints that rule out payments. This is mechanism design without money — and it is, in many ways, harder than mechanism design with money. Without payments to incentivize truthfulness, the designer must rely entirely on the structure of the allocation rule.

The housing allocation problem. Each of \(n\) agents initially owns one house, and agents have ordinal preferences (rankings) over all houses. The Top Trading Cycle Algorithm (TTCA), credited to Gale by Shapley and Scarf (1974), works as follows:

1. Each remaining agent points to the owner of its favorite remaining house.
2. The resulting directed graph has at least one cycle (self-loops count).
3. Execute all cycles: each agent on a cycle gives its house to its predecessor on the cycle.
4. Remove those agents and houses. Repeat.

Kidney exchange is a celebrated real-world application. Each incompatible patient-donor pair is an “agent” who initially “owns” an incompatible kidney. The TTCA finds beneficial exchange cycles. However, long cycles are impractical in kidney exchange because all surgeries in a cycle must be performed simultaneously (otherwise, after receiving a kidney, a donor pair might renege on donating). This motivates restricting to short cycles (typically pairwise or three-way exchanges), modeled as maximum matching in a compatibility graph.

Stable matching. The canonical example of mechanism design without money in two-sided markets is the Gale-Shapley proposal algorithm for stable matching. Given \(n\) men and \(n\) women, each with ranked preferences over the other side, the algorithm works as follows:

1. Each unmatched man proposes to his highest-ranked woman who hasn’t yet rejected him.
2. Each woman entertains the best offer she has received so far, rejecting all others.
3. Repeat until all men are matched.

The proposal algorithm, remarkably, was essentially the same algorithm that had been used since the 1950s to assign medical residents to hospitals through the National Resident Matching Program. Gale and Shapley formalized it independently in 1962. Alvin Roth’s work connecting stable matching theory to practical market design — including the redesign of the NRMP and the creation of kidney exchange clearinghouses — earned him (jointly with Shapley) the 2012 Nobel Memorial Prize in Economics.

A deep property of the proposal algorithm is that it computes the man-optimal stable matching: each man is matched to the highest-ranked woman with whom he could be matched in any stable matching. This is simultaneously the woman-pessimal stable matching. Truthful reporting is a dominant strategy for the proposing side (men), but women can sometimes benefit by misreporting preferences — an inherent asymmetry of the algorithm.

Chapter 7: Selfish Routing

We now shift from designing games to analyzing games “in the wild.” In many settings — road traffic, Internet packet routing, bandwidth sharing — the game already exists and we cannot redesign its rules. The question becomes: how much efficiency is lost because players act selfishly rather than cooperatively? This chapter develops the theory of selfish routing in networks, culminating in tight bounds on the price of anarchy that depend only on the class of edge cost functions, not on the network topology.

7.1 Nonatomic Routing and Wardrop Equilibrium

In a nonatomic selfish routing game, traffic consists of a continuum of infinitesimally small players, each choosing a path through a network to minimize its own travel time. No single player has a measurable effect on congestion — but their collective choices determine edge costs.

The Wardrop condition captures the idea that no infinitesimal driver can improve its travel time by switching routes. It is the continuous analogue of Nash equilibrium: at equilibrium, all used routes have equal cost, and no unused route is cheaper.

7.2 Existence and Uniqueness via Convex Optimization

A remarkable feature of nonatomic routing is that equilibria can be characterized as solutions to a convex optimization problem, guaranteeing both existence and uniqueness.

Since cost functions are nonnegative and nondecreasing, \(\Phi\) is a convex function of the flow. The space of feasible flows (nonneg vectors summing to \(r\)) is a compact convex set. Therefore \(\Phi\) has a global minimum.

The uniqueness of edge loads (though not necessarily of path flows) follows from the strict convexity of \(\Phi\) in the edge-load variables when cost functions are strictly increasing. The first-order optimality (KKT) conditions for minimizing \(\Phi\) are precisely the Wardrop equilibrium conditions — the cost of every used path equals the common “shortest path” distance from \(s\) to \(t\).

This convex optimization characterization means equilibria can be computed in polynomial time, in sharp contrast to Nash equilibria in general games (which are PPAD-hard).

7.3 Price of Anarchy for Nonatomic Routing

We now prove the central result: for nonatomic routing with cost functions from a class \(\mathcal{C}\), the worst-case PoA is completely determined by simple two-link “Pigou networks” — no matter how complex the actual network is.

The striking message: the only obstacle to near-optimal selfish routing is nonlinear cost functions, not complex network structure. For affine (linear) costs \(c(x) = ax + b\), the Pigou bound evaluates to \(\frac{4}{3}\). For polynomial costs of degree \(d\), the PoA grows as \(\Theta(d/\ln d)\) — quartic costs give PoA ≈ 2.2, still quite modest.

7.4 Braess’s Paradox and Network Over-Provisioning

Braess’s paradox (Example 1.12) shows that adding capacity to a network can increase equilibrium cost. This raises a natural question: can we quantify how bad the paradox can be?

For nonatomic routing with affine costs, Roughgarden (2006) showed that removing edges can improve the equilibrium cost by at most a factor of \(\frac{4}{3}\) — exactly the PoA bound. More generally, for cost functions of degree \(d\), removing edges can improve costs by at most the Pigou bound for degree-\(d\) polynomials.

The practical implication is network over-provisioning: if we build a network with \(\alpha(\mathcal{C})\) times the optimal capacity, selfish routing achieves at most the optimal cost. This is a much cheaper intervention than trying to control individual routing decisions.

Chapter 8: Congestion Games and Load Balancing

Nonatomic routing models a continuum of infinitesimal players. In many settings — packet routing on the Internet, job scheduling on parallel machines, players choosing resources in a shared system — players are large enough that each individual’s choice measurably affects congestion. These are atomic games, and their theory differs significantly from the nonatomic case.

8.1 Atomic Routing and Rosenthal’s Potential

In an atomic selfish routing game, there are \(k\) players, each choosing an \(s_i\)-\(t_i\) path. Player \(i\)’s cost is the sum of edge costs along its chosen path, where each edge’s cost depends on the total number of players using it.

This proof extends beyond routing to congestion games: any game where players choose subsets of resources, each resource has a cost depending on its load, and players pay the sum of costs on their chosen resources.

Rosenthal’s theorem applies to all congestion games: the potential \(\Phi(\mathbf{s}) = \sum_e \sum_{i=1}^{f_e} c_e(i)\) guarantees PNE existence. Moreover, better-response dynamics — repeatedly letting some unhappy player switch to a better strategy — always converge to a PNE in finite steps, since \(\Phi\) strictly decreases at each step and can only take finitely many values. (The convergence time, however, can be exponential — see Chapter 12.)

8.2 PoA for Atomic Routing

The PoA for atomic routing with affine cost functions \(c_e(x) = a_e x + b_e\) was pinned down by Christodoulou and Koutsoupias (2005).

The bound of \(\frac{5}{2}\) is significantly worse than the nonatomic bound of \(\frac{4}{3}\) for the same cost functions. The reason is the “lumpiness” of atomic players: when a large player switches routes, it causes a discrete jump in congestion that affects many other players. The proof follows the canonical four-step PoA recipe: (1) invoke the PNE condition for each player, (2) sum over players, (3) disentangle the cross-terms using algebraic bounds specific to affine costs (\(\sum_i C_i(s_i^*, \mathbf{s}_{-i}) \leq \frac{5}{3} \text{cost}(\mathbf{s}^*) + \frac{1}{3} \text{cost}(\mathbf{s})\)), (4) solve for the PoA.

8.3 Load Balancing Games

A fundamental special case of congestion games is load balancing: \(k\) jobs must be assigned to \(m\) machines, where machine \(j\) has speed \(s_j\). Each job \(i\) has a weight \(w_i\), and the load on machine \(j\) is \(\ell_j = \sum_{i : \text{job } i \to j} w_i / s_j\). Each job’s cost is the load on its machine.

For identical machines (\(s_j = 1\) for all \(j\)), this is a congestion game with one resource per machine, and Rosenthal’s theorem guarantees PNE existence. The PoA measures how much worse the equilibrium makespan is compared to optimal scheduling.

For related machines (machines with different speeds), the situation is more nuanced. As discussed in Section 5.6, the makespan-minimization problem on related machines is closely connected to mechanism design: each machine’s speed is private information, and the natural greedy allocation rule is monotone, enabling a DSIC mechanism.

8.4 Cost-Sharing and Network Design Games

In the games studied so far — routing and load balancing — players impose negative externalities on each other: more congestion means higher costs. Some games exhibit positive externalities, where additional players reduce costs. The canonical example is network cost-sharing.

This is a congestion game (with decreasing per-player costs), so pure Nash equilibria exist. However, the PoA can be terrible: in the “VHS vs. Betamax” example, two technologies (edges) with costs \(1 + \varepsilon\) and \(k\) lead to a bad equilibrium where everyone picks the expensive option, giving PoA = \(k\) — linear in the number of players. The PoA is unbounded even for games with a unique Nash equilibrium.

This motivates studying the price of stability (PoS): how good is the best equilibrium?

The “opt-out” example shows this is tight: \(k\) players share a common destination, with a shared edge of cost \(1 + \varepsilon\) and individual direct edges of cost \(1/i\) for player \(i\). The unique equilibrium (everyone opts out) has cost \(\mathcal{H}_k\), while the optimum (everyone shares) has cost \(1 + \varepsilon\).

Chapter 9: The Smooth Games Framework

The PoA proofs in Chapters 7–8 share a common four-step structure: (1) invoke the equilibrium condition per player with a hypothetical deviation to the optimal strategy, (2) sum over players, (3) disentangle the cross-term \(\sum_i C_i(s_i^*, \mathbf{s}_{-i})\) and bound it in terms of \(\text{cost}(\mathbf{s})\) and \(\text{cost}(\mathbf{s}^*)\), (4) solve for the PoA. Roughgarden (2009) observed that step 3 — the “disentanglement” step — never actually uses the fact that \(\mathbf{s}\) is a Nash equilibrium. This seemingly minor observation has a powerful consequence: any PoA bound proved via this recipe automatically extends to coarse correlated equilibria, approximate equilibria, and no-regret learning outcomes.

9.1 Smoothness Definition

The smoothness condition captures precisely the “disentanglement” step. For atomic routing with affine costs, the algebraic bound \(\sum_i C_i(s_i^*, \mathbf{s}_{-i}) \leq \frac{5}{3}\text{cost}(\mathbf{s}^*) + \frac{1}{3}\text{cost}(\mathbf{s})\) establishes \((\frac{5}{3}, \frac{1}{3})\)-smoothness. For location games (a class of payoff-maximization games studied by Vetta), the bound establishes \((1,1)\)-smoothness.

9.2 Robust Price of Anarchy

The payoff of the smooth games framework is that PoA bounds extend automatically to much larger equilibrium sets.

Since the equilibrium hierarchy satisfies PNE ⊂ MNE ⊂ CE ⊂ CCE, the PoA for PNE is at most the PoA for CCE. But Theorem 9.2 shows the bound is the same for CCE as we proved for PNE! The PoA bounds of \(\frac{5}{2}\) for atomic routing and \(\frac{4}{3}\) for nonatomic routing with affine costs extend unchanged to CCE. This is remarkable: CCE is a much larger set, yet the worst case is no worse.

The theorem also extends to \(\varepsilon\)-approximate Nash equilibria (where no player can reduce cost by more than a \((1+\varepsilon)\) factor): the PoA becomes \(\frac{(1+\varepsilon)\lambda}{1 - \mu(1+\varepsilon)}\) for \(\varepsilon < \frac{1}{\mu} - 1\).

9.3 Non-Truthful Mechanisms and Simultaneous Item-Bidding

The smooth games framework applies beyond routing to non-truthful mechanisms — auction formats where bidders play strategically rather than truthfully.

Bhawalkar and Roughgarden (2011) studied simultaneous second-price item-bidding auctions: \(m\) items are sold in parallel second-price auctions, and bidders with subadditive valuations bid independently on each item. This is not DSIC (a bidder’s optimal bid on one item depends on whether it wins others), but the resulting game has Nash equilibria.

This bound of 2 applies to the welfare (not revenue) of equilibrium outcomes. It says that even though simultaneous item-bidding is not DSIC, the equilibrium welfare is at least half of optimal — achieved through a smoothness argument. For the more restrictive class of submodular bidders, a pure NE always exists and can be computed by a greedy algorithm (assigning items to the bidder with the highest marginal value).

9.4 Unifying Theme

The smooth games framework reveals a deep unity across seemingly disparate PoA results. The following table summarizes the key instances:

The last row illustrates a limitation: smoothness gives PoA bounds, but network cost-sharing has unbounded PoA. The logarithmic price of stability bound in Theorem 8.6 requires the potential function argument, which is not captured by the smoothness framework.

Chapter 10: Best-Response and No-Regret Dynamics

Equilibrium concepts are useful for analyzing the steady states of strategic interaction, but they beg the question: how do players reach an equilibrium? This chapter studies natural learning dynamics — algorithms that individual players can use to adapt their strategies over time — and connects these dynamics to the equilibrium concepts of Chapter 1. The central result is that no-regret learning converges to the set of coarse correlated equilibria, closing the loop with the smooth games framework: if players learn via no-regret algorithms in a smooth game, the long-run outcome is approximately as efficient as any Nash equilibrium.

10.1 Best-Response Dynamics in Potential Games

In a potential game (Section 8.1), the simplest learning dynamic is better-response dynamics: in each round, some player with a profitable deviation switches to a better strategy.

The convergence time, however, can be exponential. For congestion games with linear cost functions, Ackermann, Röglin, and Vöcking (2008) showed that better-response dynamics can take an exponential number of steps even for simple network structures. This exponential convergence time motivates the search for faster dynamics that converge to approximate equilibria.

For symmetric congestion games with \(n\) players and \(m\) resources, better-response dynamics find a \((1+\varepsilon)\)-approximate PNE in time \(\text{poly}(n, m, 1/\varepsilon)\) via a careful potential-based argument. In smooth potential games, the approximate PNE found by such dynamics is automatically near-optimal by the smooth games framework (Theorem 9.2 extended to \(\varepsilon\)-PNE).

10.2 The Multiplicative Weights Algorithm

We now introduce a far more general approach that does not require a potential function. The multiplicative weights algorithm (also known as Hedge, or the randomized weighted majority algorithm) is an online learning algorithm that works in any repeated game.

The setup: a player faces \(T\) rounds. In each round \(t\), the player chooses an action \(i_t \in \{1, \ldots, n\}\) and incurs a cost \(c_t(i_t) \in [0,1]\). The costs are revealed after the player’s choice. The player’s goal is to minimize regret: the difference between its total cost and the total cost of the best single action in hindsight.

The update rule penalizes actions that incurred high cost: their weights decrease multiplicatively, making them less likely to be chosen in the future. Actions with low cost retain their weights.

The Multiplicative Weights algorithm is remarkably versatile. It is the algorithmic backbone of boosting in machine learning (Freund and Schapire’s AdaBoost), approximate solutions to linear programs and semidefinite programs, and — as we see next — convergence to equilibria in games.

10.3 No-Regret Implies Convergence to CCE

The connection between no-regret learning and equilibria is one of the most beautiful results in algorithmic game theory.

Combined with the smooth games framework (Theorem 9.2), this yields a powerful corollary: in any \((\lambda, \mu)\)-smooth game, if all players use no-regret algorithms, the time-averaged social cost is at most \(\frac{\lambda}{1-\mu}\) times optimal — the same bound as for pure Nash equilibria. Players don’t need to know the game structure, the number of players, or even that they are in a game. They just need to minimize their own regret.

10.4 Swap Regret and Correlated Equilibria

External regret compares the player’s performance to the best fixed action. A stronger notion is swap regret, which compares to the best function mapping actions to actions.

Swap regret is strictly stronger than external regret: choosing \(\pi\) to be a constant function \(\pi(\cdot) = i^*\) recovers external regret. No-swap-regret learning converges to the set of correlated equilibria (not just coarse correlated):

The Blum-Mansour construction converts any no-external-regret algorithm into a no-swap-regret algorithm using a black-box reduction. The idea: maintain \(n\) copies of the external-regret algorithm (one for each action), and when action \(i\) is played, feed the costs to the \(i\)-th copy. The overall strategy is the stationary distribution of a Markov chain defined by the \(n\) copies’ recommendations. The swap regret of the combined algorithm is bounded by the sum of external regrets of the copies, giving per-round swap regret \(O(n \sqrt{\ln n / T})\).

Chapter 11: Zero-Sum Games and the Minimax Theorem

The theory of no-regret learning yields a striking algorithmic proof of the most fundamental theorem in game theory: von Neumann’s minimax theorem for two-player zero-sum games.

11.1 Two-Player Zero-Sum Games

The row player wants to maximize \(a_{ij}\); the column player wants to minimize it. Each player can randomize: the row player chooses a distribution \(\mathbf{p}\) over rows, the column player chooses \(\mathbf{q}\) over columns, and the expected payoff is \(\mathbf{p}^T A \mathbf{q}\).

The maximin value is \(\max_{\mathbf{p}} \min_{\mathbf{q}} \mathbf{p}^T A \mathbf{q}\): the best guarantee the row player can secure, assuming the column player responds optimally. The minimax value is \(\min_{\mathbf{q}} \max_{\mathbf{p}} \mathbf{p}^T A \mathbf{q}\): the least the column player can be forced to concede.

A simple inequality always holds: \(\max_{\mathbf{p}} \min_{\mathbf{q}} \leq \min_{\mathbf{q}} \max_{\mathbf{p}}\) (committing first is never an advantage). Von Neumann’s theorem says these are equal.

11.2 Von Neumann’s Minimax Theorem

There are many proofs: von Neumann’s original used Brouwer’s fixed-point theorem; later proofs use LP duality (the maximin and minimax problems are dual linear programs). We give an algorithmic proof via no-regret learning.

This proof is constructive: Multiplicative Weights computes an approximate minimax equilibrium in \(O(\frac{\ln n}{\varepsilon^2})\) rounds for an \(\varepsilon\)-approximate solution — polynomial in the game size and \(1/\varepsilon\). This is in dramatic contrast to computing Nash equilibria of general games, which is PPAD-hard.

The minimax theorem also implies the existence of a mixed Nash equilibrium in any finite two-player zero-sum game (the maximin strategy for each player), predating Nash’s general existence theorem (1950) by 22 years.

Chapter 12: Computing Equilibria

We have seen that Nash equilibria exist in all finite games (Theorem 1.6), that pure Nash equilibria exist in all congestion games (Theorem 8.1), and that correlated equilibria can be computed efficiently via linear programming. This chapter addresses the computational complexity of finding equilibria: which equilibrium concepts are tractable, and which are fundamentally hard?

12.1 PLS-Completeness and Pure Nash Equilibria

Better-response dynamics converge to a pure Nash equilibrium in potential games — but the convergence can take exponentially many steps. This exponential behavior is not an artifact of a particular algorithm but reflects a deep computational barrier.

Every PLS problem has a solution (since the number of feasible solutions is finite and the objective has a global optimum, which is also a local optimum). But finding a local optimum may require following an exponentially long sequence of improving moves. A problem is PLS-complete if every PLS problem can be reduced to it — implying that no polynomial-time algorithm exists unless PLS = P.

This result explains why better-response dynamics can take exponential time in congestion games: finding a PNE is, in general, as hard as any local search problem. However, for special cases — symmetric congestion games, singleton congestion games (each strategy is a single resource), or games with a polynomial number of strategies — PNE can be computed efficiently.

12.2 PPAD and Brouwer’s Fixed Point

For games without a potential function, even the existence of pure Nash equilibria is not guaranteed. Nash’s theorem ensures a mixed Nash equilibrium exists, but this guarantee comes via Brouwer’s fixed-point theorem — a non-constructive existence result. The complexity of finding a Nash equilibrium is captured by a different class.

The defining problem of PPAD is finding a second “end of a line” in a directed path. The directed graph has exponentially many nodes, each with in-degree and out-degree at most 1. Given a known source, there must be at least one sink (by a parity argument: the number of sources equals the number of sinks modulo 2). But finding it may require following the path, which can be exponentially long.

Brouwer’s fixed-point theorem — “every continuous function from a compact convex set to itself has a fixed point” — can be formulated as a PPAD problem. The discrete analogue is Sperner’s lemma: in any properly colored triangulation of a simplex, there exists a “trichromatic” cell. Finding this cell is PPAD-complete.

12.3 PPAD-Completeness of Nash Equilibrium

This is one of the landmark results in algorithmic game theory. Its message is that Nash’s existence theorem, despite being a beautiful mathematical result, does not yield an efficient algorithm. Even for two-player games (the simplest case where Nash equilibria may require randomization), no polynomial-time algorithm is known or believed to exist.

The proof reduces from the Brouwer fixed-point problem. Given any Brouwer instance (a continuous function \(f\) on a simplex), one constructs a two-player game whose Nash equilibria correspond to approximate fixed points of \(f\). The construction uses a sequence of gadgets that encode arithmetic operations, comparisons, and function evaluations as incentive constraints in the game.

The PPAD-completeness of Nash equilibrium stands in sharp contrast to several related problems:

12.4 Computing Correlated Equilibria

The tractability of correlated equilibria provides a remarkable contrast. A CE of a game with \(k\) players and strategy sets \(S_1, \ldots, S_k\) is a distribution \(\sigma\) over \(S_1 \times \cdots \times S_k\) satisfying the linear constraints of Definition 1.7. This is a linear feasibility problem with \(\sum_i |S_i|^2\) constraints and \(\prod_i |S_i|\) variables.

While the number of variables can be exponential in \(k\), there are two efficient approaches:

1. LP with separation oracle. For games where the constraint set has polynomial-size representation, the ellipsoid method can find a CE in polynomial time using a separation oracle for the CE polytope.

2. No-regret dynamics. As shown in Theorem 10.5, if all players run no-regret algorithms (such as Multiplicative Weights), the empirical distribution converges to a CCE. For swap-regret algorithms (Theorem 10.7), convergence is to CE. This approach is fully distributed — each player only needs to know its own costs — and runs in time polynomial in the game size and \(1/\varepsilon\) for an \(\varepsilon\)-approximate CE.

The gap between polynomial CE computation and PPAD-hard Nash computation justifies the focus on CCE in the smooth games framework: not only do CCE yield the same PoA bounds as PNE in smooth games, they are also computationally tractable.

Chapter 13: Market Equilibria

We conclude with a different model of strategic interaction: markets where agents trade goods at prices determined by supply and demand. Unlike the games of Chapters 1–12, markets are governed by the price mechanism rather than by explicit game rules. The central question is whether competitive prices exist and can be computed efficiently.

13.1 Exchange Economies and Walrasian Equilibrium

The existence of Walrasian equilibria is a foundational result in mathematical economics, proved by Arrow and Debreu (1954) using Kakutani’s fixed-point theorem — the same tool that underlies Nash’s equilibrium existence theorem. The Arrow-Debreu theorem applies to the more general exchange economy model, where each agent starts with an endowment of goods (rather than money) and trades.

13.2 Computing Market Equilibria

For Fisher markets with linear utilities — \(u_i(x_i) = \sum_j u_{ij} x_{ij}\) — the equilibrium computation problem has a beautiful convex programming formulation.

The Eisenberg-Gale program is a remarkable result: it reduces the economic equilibrium problem to a tractable optimization problem. The objective — maximizing the weighted sum of log-utilities — is a Nash bargaining solution, and the dual variables automatically yield market-clearing prices. This provides both an existence proof and an efficient algorithm.

For more complex utility functions (e.g., CES utilities, Leontief utilities), the equilibrium computation landscape is more varied:

13.3 Welfare Theorems

The classical welfare theorems connect competitive equilibria to social efficiency.

The welfare theorems provide the deepest connection between mechanism design and market theory. The First Welfare Theorem says that the price mechanism automatically achieves Pareto optimality — a form of efficiency without any central planner. This is Adam Smith’s “invisible hand” made precise. The Second Welfare Theorem says that any desired efficient outcome can be achieved through the market, given the right initial distribution of resources.

From the perspective of algorithmic game theory, markets are games where the “mechanism” is the price system. The First Welfare Theorem is a PoA = 1 result: equilibria are always optimal (in the Pareto sense). The computational challenge is finding the equilibrium prices — which, as we have seen, ranges from polynomial (for linear Fisher markets) to PPAD-hard (for general exchange economies). The close parallel between the complexity of Nash equilibria in games and the complexity of Walrasian equilibria in markets reflects a deep structural connection: both are fixed-point problems, and both can be PPAD-hard when the underlying structure is sufficiently complex.