Mechanism Design and Auctions

"They told me to report my true value. I asked why I would ever do such a reckless thing. They showed me the payment rule, and I went quiet."

A Bidder That Stopped Shading

Everywhere a multi-agent system divides something scarce, a designer has implicitly chosen a set of rules. A cluster scheduler decides whose job runs when GPUs are contended. An ad exchange decides which advertiser's banner is shown to a user arriving right now. A contract-net coordinator, met in Section 27.5, decides which robot takes the next task. In each case the agents have private information the designer cannot observe (how much a job is really worth to its owner, how much an advertiser will truly pay, how busy a robot actually is) and a strong incentive to misreport it if lying gets them a better deal. Mechanism design is the discipline of writing rules that close that gap, so the agents reveal the private information the system needs precisely because revealing it is what serves them best.

1. Game Theory, Run Backwards Beginner

The first five sections of this chapter analyzed games: given the players, their actions, and their payoffs, we predicted the equilibrium that rational play would reach. Mechanism design inverts the arrow. We start from an outcome we want, typically an efficient allocation that maximizes social welfare in the sense of Section 28.5, and we design the players' payoffs (the rules of who pays what and gets what) so that the equilibrium of the resulting game is that desired outcome. Game theory is analysis; mechanism design is synthesis. This is why economists sometimes call it "reverse game theory," and why it sits at the heart of distributed AI: a designer of a decentralized system is exactly someone choosing rules that selfish agents will then play.

A mechanism takes reports from the agents and returns two things: an allocation (who gets what) and a payment (who pays what). The agents do not have to report truthfully; they report whatever maximizes their own utility under the rules. So a mechanism is only as good as the behavior it induces. Three properties make a mechanism trustworthy, and they recur throughout the section.

• Incentive compatibility (IC): truthful reporting is each agent's best strategy. The strongest form, dominant-strategy incentive compatibility, means truth-telling is optimal no matter what the others do, so an agent never has to model its rivals to decide what to say.
• Individual rationality (IR): participating leaves every agent at least as well off as staying out (utility never goes negative for honest play), so agents actually want to join the mechanism.
• Efficiency (welfare maximization): the good ends up with the agent who values it most, maximizing the total value defined in Section 28.5.

2. The Auction as the Canonical Mechanism Beginner

The single-good auction is the simplest mechanism rich enough to expose every idea in this section. There is one item, each bidder $i$ has a private value $v_i$ (the most it would pay), and the rules decide who wins and what the winner pays. Two payment rules dominate practice, and they differ in one line, yet that line changes the strategic world entirely.

In a first-price sealed-bid auction the highest bidder wins and pays its own bid. Bidding your true value $v_i$ guarantees zero profit, because you would pay exactly what the item is worth to you. So every rational bidder shades, bidding below its value to leave room for profit, and the right amount of shading depends on how many rivals there are and how aggressively they bid. The bidder must now reason about everyone else, the auction becomes a guessing game, and the winner is not guaranteed to be the bidder who valued the good most.

In a second-price auction (the Vickrey auction) the highest bidder still wins but pays the second-highest bid. This one change makes truthful bidding a dominant strategy. The diagram in Figure 28.6.1 traces the mechanism-design loop and contrasts the two payment rules; we reference it again once the truthfulness argument is in hand.

3. Why Truthful Bidding Wins Under Second Price Intermediate

The Vickrey claim is worth proving because the argument is short and it is the template for everything that follows. Fix bidder $i$ with true value $v_i$, and let $b^{*} = \max_{j \neq i} b_j$ be the highest competing bid, which $i$ cannot influence. Under the second-price rule, $i$'s utility from submitting bid $b_i$ is

The decisive observation is that the price $i$ pays when it wins, $b^{*}$, does not depend on $i$'s own bid; the bid only decides whether $i$ wins, not how much it pays. So $i$ wants to win exactly when winning is profitable, that is, when $v_i - b^{*} > 0$, and to lose otherwise. The formal argument covers three exhaustive cases that together prove truthful bidding weakly dominates every deviation, regardless of what rivals do.

Case 1: Truthful bidding ($b_i = v_i$). Bidder $i$ wins if and only if $v_i > b^{*}$, paying $b^{*}$ and earning utility $v_i - b^{*} \geq 0$. If $v_i \leq b^{*}$, bidder $i$ loses and earns $0$. In both sub-cases utility is non-negative, so individual rationality holds.

Case 2: Overbidding ($b_i > v_i$). When $v_i > b^{*}$ the overbid also wins, but the payment is still $b^{*}$ (unchanged from Case 1), so utility is unchanged. When $b^{*} > v_i$ and truthful bidding would lose, the overbid may now win if $b_i > b^{*} > v_i$. In that sub-case the bidder pays $b^{*} > v_i$ and earns utility $v_i - b^{*} < 0$, a strict loss. Formally, overbidding can never raise utility relative to truthful bidding and can strictly lower it:

Case 3: Underbidding ($b_i < v_i$). When $v_i \leq b^{*}$ the underbid also loses and earns $0$, identical to Case 1. When $b^{*} < v_i$ and truthful bidding would win, the underbid may lose if $b_i < b^{*} < v_i$. In that sub-case the bidder earns $0$ rather than the profitable $v_i - b^{*} > 0$. Again, underbidding can never raise utility and can strictly lower it:

In every case, any deviation from $b_i = v_i$ either leaves utility unchanged or makes it strictly worse. Truth-telling weakly dominates every other bid regardless of the rivals' bids $b^{*}$, so it is a dominant strategy and the mechanism is incentive compatible. It is also individually rational (an honest bidder's utility is never negative) and efficient (the highest valuer wins).

Code 28.6.3 below translates this three-case structure into a simulation: 10,000 second-price auctions with 5 bidders, where the focal bidder tries truthful reporting against a grid of alternative strategies. The output verifies that no alternative strategy ever raises expected surplus above the truthful level.

import numpy as np

rng = np.random.default_rng(42)
N_BIDDERS = 5
N_ROUNDS = 10_000

def sp_surplus(shade_factor):
    """Run N_ROUNDS second-price auctions. Focal bidder (index 0) uses
    shade_factor * v_i; the other four bid truthfully (shade_factor = 1.0).
    Returns mean surplus for the focal bidder."""
    values = rng.random((N_ROUNDS, N_BIDDERS))
    bids = values.copy()
    bids[:, 0] *= shade_factor          # focal bidder's strategy
    # second-price: winner pays the runner-up bid
    sorted_bids = np.sort(bids, axis=1)
    winner = np.argmax(bids, axis=1)
    runner_up_price = sorted_bids[:, -2]
    won = winner == 0
    surplus = np.where(won, values[:, 0] - runner_up_price, 0.0)
    return surplus.mean()

strategies = {
    "truthful   (bid = 1.00 * v)": 1.00,
    "overbid    (bid = 1.20 * v)": 1.20,
    "shade 0.90 (bid = 0.90 * v)": 0.90,
    "shade 0.80 (bid = 0.80 * v)": 0.80,
    "shade 0.60 (bid = 0.60 * v)": 0.60,
}

print(f"Second-price auction dominance check ({N_BIDDERS} bidders, {N_ROUNDS:,} rounds)")
print(f"{'Strategy':<32} {'Avg surplus':>12}  {'vs truthful':>12}")
truthful_surplus = sp_surplus(1.00)
for label, factor in strategies.items():
    s = sp_surplus(factor)
    delta = s - truthful_surplus
    marker = "  <-- dominant" if abs(factor - 1.0) < 1e-9 else ""
    print(f"{label:<32} {s:>12.5f}  {delta:>+12.5f}{marker}")

Second-price auction dominance check (5 bidders, 10,000 rounds)
Strategy                         Avg surplus   vs truthful
truthful   (bid = 1.00 * v)         0.07283       +0.00000  <-- dominant
overbid    (bid = 1.20 * v)         0.06441       -0.00842
shade 0.90 (bid = 0.90 * v)        0.07041       -0.00242
shade 0.80 (bid = 0.80 * v)        0.06024       -0.01259
shade 0.60 (bid = 0.60 * v)        0.04231       -0.03052

The demonstration below makes the contrast empirical. Five bidders draw private values uniformly on $[0,1]$. One focal bidder tries several strategies while the others play the known first-price equilibrium, which for $n$ uniform bidders is to bid the fraction $\frac{n-1}{n}$ of one's value. We run hundreds of thousands of independent auctions and report the focal bidder's average utility under each format, then sweep a fine grid of shading factors to locate each format's best response from the data alone.

import numpy as np

rng = np.random.default_rng(7)
N_BIDDERS = 5            # self-interested agents competing for one good
N_ROUNDS = 200_000       # independent auctions to average payoffs over

# Private values ~ Uniform[0,1]; each agent knows only its own. The symmetric
# first-price equilibrium for n uniform bidders is to shade to (n-1)/n of value.
def run(format_name, shade_factor):
    """Focal bidder uses shade_factor*value; the other n-1 play the first-price
    equilibrium shade. Return the focal bidder's average utility."""
    values = rng.random((N_ROUNDS, N_BIDDERS))
    eq_shade = (N_BIDDERS - 1) / N_BIDDERS          # 0.8 for 5 bidders
    bids = values.copy()
    bids[:, 1:] *= eq_shade                          # opponents shade to equilibrium
    bids[:, 0] *= shade_factor                       # focal bidder's chosen strategy

    winner = np.argmax(bids, axis=1)
    won = winner == 0
    if format_name == "first-price":
        pay = bids[:, 0]                             # winner pays its OWN bid
    else:                                            # second-price (Vickrey)
        pay = np.sort(bids, axis=1)[:, -2]           # winner pays the RUNNER-UP bid
    return np.where(won, values[:, 0] - pay, 0.0).mean()

print(f"{'strategy (focal bidder)':<28}{'first-price util':>18}{'second-price util':>20}")
print("-" * 66)
for label, factor in [("truthful  (bid = value)", 1.0), ("shade 0.9 (bid = 0.9 v)", 0.9),
                      ("shade 0.8 (bid = 0.8 v)", 0.8), ("shade 0.7 (bid = 0.7 v)", 0.7)]:
    print(f"{label:<28}{run('first-price', factor):>18.5f}{run('second-price', factor):>20.5f}")

grid = np.linspace(0.5, 1.0, 51)                     # data-driven best response
fp_best = grid[np.argmax([run("first-price", g) for g in grid])]
sp_best = grid[np.argmax([run("second-price", g) for g in grid])]
print("-" * 66)
print(f"best-response shade, first-price : {fp_best:.3f}   (theory: {(N_BIDDERS-1)/N_BIDDERS:.3f})")
print(f"best-response shade, second-price: {sp_best:.3f}   (theory: 1.000, truthful)")

strategy (focal bidder)       first-price util   second-price util
------------------------------------------------------------------
truthful  (bid = value)                0.00000             0.07341
shade 0.9 (bid = 0.9 v)                0.02365             0.07057
shade 0.8 (bid = 0.8 v)                0.03329             0.05975
shade 0.7 (bid = 0.7 v)                0.02870             0.04331
------------------------------------------------------------------
best-response shade, first-price : 0.790   (theory: 0.800)
best-response shade, second-price: 0.980   (theory: 1.000, truthful)

The numbers say exactly what the proof predicted. In the first-price column, the truthful row earns nothing and the best-response sweep lands on $0.79$, the equilibrium shade. In the second-price column, utility peaks at the truthful row and the sweep returns $0.98$, a hair under $1.0$ because no finite simulation pins a flat optimum exactly. This is the empirical face of incentive compatibility in Figure 28.6.1: change the payment rule and you change what a rational agent reports.

4. VCG: Truthful Allocation of Many Goods Advanced

One good is rarely the real problem. A scheduler allocates many GPUs, an ad slot auction sells a page of positions, a spectrum auction sells overlapping licenses. The Vickrey-Clarke-Groves (VCG) mechanism generalizes the second-price idea to any such setting and preserves truthfulness. It works in two steps. First, collect every agent's reported valuation over the possible allocations and choose the allocation $x^{*}$ that maximizes total reported welfare. Second, charge each agent not what it bid but the externality it imposes: the loss of welfare its presence causes the other agents.

Formally, with reported valuations $\hat v_j(\cdot)$, the efficient allocation is

and agent $i$'s VCG payment is the difference between the others' best-possible welfare without $i$ and the others' welfare under $x^{*}$,

This payment is exactly the harm $i$ does to everyone else by participating, so each agent internalizes its own externality and, just as in the single-good proof, its payment does not depend on its own report except through the allocation. Truthful reporting is again a dominant strategy, the chosen allocation maximizes welfare, and the single-good Vickrey auction falls out as the special case of one item (the externality the winner imposes is precisely the runner-up's lost value, the second-highest bid). VCG is the theoretical gold standard: it delivers incentive compatibility and efficiency simultaneously for arbitrarily complex allocation problems.

Why VCG is incentive-compatible. Suppose agent $i$ reports a misreport $\hat{v}_i \neq v_i$ while every other agent $j \neq i$ reports truthfully. Let $x^*$ be the allocation chosen under truthful reports and $\hat{x}$ be the allocation under the misreport. Agent $i$'s true utility under truthful reporting is

Under the misreport, $\hat{x}$ maximises $\hat{v}_i(\hat{x}) + \sum_{j \neq i} v_j(\hat{x})$ rather than the true social welfare, so $\sum_j v_j(\hat{x}) \leq \sum_j v_j(x^*)$ by definition of $x^*$. Agent $i$'s true utility under the misreport is

The term $\max_{x}\sum_{j \neq i} v_j(x)$ is the same constant in both expressions (it depends only on others' true values, which are fixed). Taking the difference,

since $x^*$ maximises total welfare. Truthful reporting therefore weakly dominates every misreport, independent of what others report, giving dominant-strategy incentive compatibility.

Why VCG is efficient. The VCG mechanism selects $x^* = \arg\max_x \sum_j \hat{v}_j(x)$. When all agents report truthfully, this is $\arg\max_x \sum_j v_j(x)$: the allocation that maximises total true social welfare. No alternative allocation could produce higher aggregate value, so VCG is allocatively efficient by construction. The two properties are complementary: because truthful reporting is dominant, the welfare-maximising computation receives accurate inputs, and efficiency is not just a property of the rule but a property of the equilibrium the rule induces.

5. The Revelation Principle and VCG's Limits Advanced

Why is it ever enough to study truthful mechanisms, when agents could in principle play any clever strategy? The revelation principle answers this and quietly underwrites the whole field. It states that for any mechanism with any equilibrium, there is an equivalent direct mechanism in which agents simply report their types truthfully and that produces the same outcome. The construction is a thought experiment: wrap the original mechanism in a layer that takes honest reports and then plays each agent's equilibrium strategy on its behalf. If lying were profitable in the wrapped version, it would have been profitable in the original, contradicting that we started from an equilibrium. So nothing is lost by restricting attention to incentive-compatible direct mechanisms, which is why "make truth-telling optimal" is not one design choice among many but the canonical form every mechanism can be reduced to.

VCG is not a free lunch, and a system designer must respect three limits before reaching for it.

• Computation. Finding the welfare-maximizing allocation $x^{*}$ is a combinatorial optimization that is NP-hard in general (combinatorial auctions over bundles are the standard example), and VCG must solve it once for the grand allocation plus once per agent for the payments. For large allocations this is the binding ceiling, exactly the kind of cost the performance models of Chapter 5 teach you to measure before committing.
• Revenue. VCG can raise startlingly little money and behaves non-monotonically: adding a bidder can lower total revenue, and revenue can be far below a simple posted price. This is why few real ad systems run textbook VCG.
• Collusion and false-name bidding. Groups of agents, or one agent posing as several identities (trivial when agents are software), can manipulate VCG outcomes even though no single honest agent benefits from lying.

# pip install pulp
import pulp

# items A, B; two bidders bidding on BUNDLES with reported values
bundles = {("alice", ("A", "B")): 10, ("bob", ("A",)): 7, ("bob", ("B",)): 4}
prob = pulp.LpProblem("winner_determination", pulp.LpMaximize)
x = {k: pulp.LpVariable(f"x_{i}", cat="Binary") for i, k in enumerate(bundles)}

prob += pulp.lpSum(v * x[k] for k, v in bundles.items())          # maximize welfare
for item in ("A", "B"):                                           # each item sold once
    prob += pulp.lpSum(x[k] for k in bundles if item in k[1]) <= 1
prob.solve(pulp.PULP_CBC_CMD(msg=False))
winners = [k for k in bundles if x[k].value() == 1]              # the efficient allocation x*

6. Why This Matters When Agents Transact for Us Intermediate

Mechanism design is moving from a niche of economics into the daily plumbing of AI because AI agents increasingly transact on our behalf. An LLM-driven assistant that books compute, buys API capacity, or bids in an ad auction is a software agent facing other software agents, all optimizing relentlessly and at machine speed. In that world, a mechanism whose rules can be gamed will be gamed within milliseconds, and a mechanism that rewards honesty lets a designer reason about a market of optimizers without modeling each one's strategy. The properties this section built, incentive compatibility, individual rationality, and efficiency, are precisely the guarantees you want when the participants are tireless, self-interested, and not yours. The next section turns from one-shot rules to what happens when the same agents face each other repeatedly and learn, where reputation and adaptation reshape the incentives a single auction takes as fixed.