From taking the rules as given to designing them

The usual question of game theory is: given the rules, how will the players act and what will the outcome be? Mechanism design turns the question around. We first state the outcome we want (say, that an object ends up with whoever values it most, or that a public project is built only when its total benefit exceeds its cost) and then ask: is there a set of rules under which self-interested people, each holding private information, will bring about exactly this outcome while pursuing their own ends? That is why mechanism design is often called “reverse game theory”.

Hurwicz’s impossibility result is the first of a kind of conclusion that recurs throughout this book: in the face of private information, one cannot have all the good properties at once. Much of the work of mechanism design consists in finding out which properties can be had together, which must be traded off, and how large the cost of the trade-off is.

Mechanisms, types and incentive compatibility

With as little notation as possible: each participant $i$ has a type $\theta_i$ that only she knows (her value for an object, her cost). The designer wants to implement a social choice rule $f(\theta_1, \dots, \theta_n)$, the outcome that ought to occur for each combination of types. A mechanism specifies what messages each person may send (bids, reports, choices) and a rule that maps the messages to an outcome and to payments.

A mechanism is incentive compatible if, under its rules, acting truthfully is in each participant’s best interest. There are two versions of different strength:

• Dominant-strategy incentive compatibility: whatever others do, truthful reporting is never worse than any other report.
• Bayesian incentive compatibility: if everyone else reports truthfully and all share a common belief about the distribution of one another’s types, truthful reporting maximises one’s expected payoff.

Another recurring condition is individual rationality (the participation constraint): taking part leaves each person at least as well off as staying out. Depending on when the judgement is made, it comes in ex ante, interim (knowing one’s own type but not the others’) and ex post versions.

I cut, you choose: allocation without envy

One of the oldest mechanisms is perhaps the way two children share a cake: one cuts, the other chooses first.

The incentive logic of cut and choose is clear. The cutter does not know (or cannot control) which piece the other will take, so her safest course is to cut two pieces that are equal in her own eyes; the chooser takes the piece he prefers and naturally envies no one.

# "I cut, you choose" on a cake [0, 1]. Cutter's density f(x) = 1.6 - 1.2x (likes the left
# end); chooser's g(x) = 0.4 + 1.2x (likes the right end); each values the cake at 1.
f = lambda x: 1.6 - 1.2 * x
g = lambda x: 0.4 + 1.2 * x

def value(dens, a, b, steps=4000):                 # midpoint-rule integral
    h = (b - a) / steps
    return sum(dens(a + (k + 0.5) * h) for k in range(steps)) * h

def play(cut):                                     # chooser takes the piece he prefers
    takes_right = value(g, cut, 1) >= value(g, 0, cut)
    cutter = value(f, 0, cut) if takes_right else value(f, cut, 1)
    return cutter, max(value(g, 0, cut), value(g, cut, 1))

lo, hi = 0.0, 1.0                                  # honest cut: halves equal for HER
for _ in range(50):
    mid = (lo + hi) / 2
    lo, hi = (mid, hi) if value(f, 0, mid) < 0.5 else (lo, mid)
cg, hg = play(hi)
print(f"honest cut at {hi:.3f}: cutter gets {cg:.3f} (other piece {1 - cg:.3f} to her);"
      f" chooser {hg:.3f}")
# An informed cutter moves the knife to the chooser's indifference point.
cuts = [k / 1000 for k in range(1, 1000)]
k = max((c for c in cuts if value(g, c, 1) >= value(g, 0, c)), key=lambda c: play(c)[0])
ci, hi2 = play(k)
print(f"informed cutter cuts at {k:.3f}: she gets {ci:.3f}, chooser {hi2:.3f}")
print(f"sum of values: honest {cg + hg:.3f}, informed {ci + hi2:.3f}, "
      f"best split {value(f, 0, 0.5) + value(g, 0.5, 1):.3f}")
# honest cut at 0.362: cutter gets 0.500 (other piece 0.500 to her); chooser 0.777
# informed cutter cuts at 0.638: she gets 0.777, chooser 0.501
# sum of values: honest 1.277, informed 1.277, best split 1.300

The result shows three properties of the mechanism. First, the cutter cuts truthfully according to her own preferences (at 0.362) and gets exactly half in her own eyes; the chooser gets 0.777 in his eyes, and neither envies the other. Second, what it guarantees is only one half; it does not guarantee a “fair share” of the surplus. If the cutter knows the chooser’s preferences, she moves the knife to the point where he is just indifferent (0.638), keeping 0.777 for herself and leaving him only 0.501: still envy-free, but the gains all go to the cutter. This is exactly the information problem that mechanism design cares about: the outcome of a rule depends on who knows what. Third, it is not necessarily efficient: the sum of the two valuations could reach 1.300 (cut in the middle, each taking the preferred end), whereas cut and choose yields 1.277.

Public goods: free-riding and the Clarke pivot mechanism

A cake is a private good: what one person takes, the other loses. Public goods are different. A road, a piece of shared software, an industry standard: once provided, everyone can use it.

# (1) Voluntary contributions: 4 people, endowment 20; each unit in the pot returns 0.4 to
# EACH member. (2) Clarke pivot: project costs 100, shared 25 each; build if reported net
# values sum to >= 0; a person pays tax only if her report changes the decision.
import random
ENDOW, MPCR, SHARE = 20, 0.4, 25.0
pay = lambda own, others: ENDOW - own + MPCR * (own + others)
best = {max(range(ENDOW + 1), key=lambda c: pay(c, o)) for o in range(3 * ENDOW + 1)}
print(f"voluntary pot: best own contribution for every total from others = {best}")
print(f"all give 0 -> {pay(0, 0):.0f} each; all give 20 -> {pay(20, 60):.0f} each")

def clarke(reports, i):
    net = [r - SHARE for r in reports]
    build, others = sum(net) >= 0, sum(net) - net[i]
    return build, (abs(others) if (others >= 0) != build else 0.0)

def utility(v, reports, i):
    build, tax = clarke(reports, i)
    return (v - SHARE if build else 0.0) - tax

rng = random.Random(7)
gain, taxes, ok = 0.0, [], 0
for _ in range(2000):
    vals = [rng.uniform(0, 60) for _ in range(4)]
    truth = utility(vals[0], vals, 0)
    gain = max([gain] + [utility(vals[0], [r] + vals[1:], 0) - truth
                         for r in range(0, 101, 2)])
    taxes.append(sum(clarke(vals, i)[1] for i in range(4)))
    ok += clarke(vals, 0)[0] == (sum(vals) >= 100)
print(f"Clarke: 2,000 profiles x 51 misreports, largest gain from lying = {gain:.6f}")
print(f"efficient decision in {ok / 20:.1f} % of profiles; taxes (burned) mean "
      f"{sum(taxes) / 2000:.2f}, positive in {sum(t > 0 for t in taxes) / 20:.1f} %")
# voluntary pot: best own contribution for every total from others = {0}
# all give 0 -> 20 each; all give 20 -> 32 each
# Clarke: 2,000 profiles x 51 misreports, largest gain from lying = 0.000000
# efficient decision in 100.0 % of profiles; taxes (burned) mean 5.74, positive in 42.8 %

With voluntary contributions, whatever the others put in, contributing 0 is one’s best reply (each unit contributed returns only 0.4 to oneself); so everyone contributes 0 and gets 20, whereas everyone would get 32 if all contributed fully. That is the free-rider dilemma.

The Clarke pivot mechanism solves the incentive problem: across 2,000 random value profiles, each tested against 51 possible misreports, the largest gain from lying is 0. Truthful reporting is a dominant strategy, and the building decision is efficient in 100 % of cases. The reason is the same as for the Vickrey auction of the next chapter: your report determines only the outcome, while the tax you pay is determined entirely by other people’s reports (Clarke 1971; Groves 1973).

But there is a price. In 42.8 % of cases at least one person is “pivotal” and must pay tax, 5.74 per profile on average. This money cannot be returned to the participants, since that would recreate the incentive to misreport; it must be burned or handed to an outsider. Green and Laffont proved that, under quite general conditions, no mechanism that is dominant-strategy incentive compatible and makes efficient decisions can also balance its budget (Green and Laffont 1977). This is a prelude to the more famous impossibility theorem of Chapter 3.

Chapter summary

Mechanism design first fixes the outcome to be achieved and then seeks rules under which self-interested participants with private information will achieve it voluntarily. Its core concepts are incentive compatibility and individual rationality; the revelation principle shows that in looking for the best mechanism one need only consider direct mechanisms with truthful reporting. Hurwicz’s early result already showed that, with private information, efficiency, voluntary participation and dominant-strategy incentive compatibility cannot all be had. “I cut, you choose” is envy-free but guarantees each person only half, and its outcome depends on who has information about the other’s preferences. In voluntary public-good provision, everyone free-rides in equilibrium; the Clarke pivot mechanism makes truthful reporting dominant and decisions efficient, at the cost that the taxes collected cannot be returned and the budget cannot balance. The next chapter applies the same logic to auctions.