Introduction to Mechanism Design

Motivation: economics with an engineering perspective

Mechanism Design is a subfield of economic theory that is rather unique within economics in having an engineering perspective. It is interested in designing economic mechanisms, just as computer scientists are interested in designing algorithms, protocols, or systems.

ImportantThe goal, abstractly

The goals are best viewed in the very abstract terms of social choice: an aggregation of the preferences of different participants toward a single joint decision. Mechanism Design attempts to implement desired social choices in a strategic setting — assuming each member of society acts rationally in a game-theoretic sense. Such strategic design is necessary because the preferences of the participants are usually private.

Setting	The social choice being made
Elections	each voter has preferences among candidates; the outcome is one choice
Markets	classical theory assumes a “perfect market”; in reality there are only interactions governed by protocols, whose outcome is a reallocation of goods and money
Auctions	the extreme opposite of a perfect market — a single seller; the auction rules define the social choice, namely the identity of the winner
Government policy	build the bridge? how much pollution to allow? each citizen differs, one choice is made

IntuitionWhy the Internet made this a computer science subject

The main new ingredient found on the Internet is that it is owned and operated by different parties with different goals. These preferences, and the behavior they induce, must be taken into account by every protocol in such an environment — so a protocol should be viewed as aggregating the participants’ preferences into a social choice: the outcome of its run.

Two complementary motivations:

Economics for CS. Take any algorithmic challenge in a network — routing messages, scheduling tasks, allocating memory. With multiple owners of resources or requests, the algorithm must function well assuming strategic selfish behavior. This is Algorithmic Mechanism Design.
CS for economics. Take any economic interaction — a market, an auction, a supply chain. Implemented over a computerized platform, it admits unprecedented sophistication handled by hyperrationally designed software. This is Electronic Market Design.

NoteThe bias of this treatment

The presentation is not very different from the standard economic approach, but is somewhat biased toward the worst-case (non-Bayesian) point of view common in computer science — dominant strategies first, Bayesian analysis later.

Condorcet’s paradox

ExampleMajority fails with three candidates

With two candidates, majority vote is intuitively fine. With three, Condorcet (1785) pointed out the problem. Three candidates $a,b,c$ and three voters:

$a\prec_1 b\prec_1 c \quad\text{reading } a\succ_1 b\succ_1 c$

— more precisely, voter 1 prefers $a$ to $b$ to $c$ ; voter 2 prefers $b$ to $c$ to $a$ ; voter 3 prefers $c$ to $a$ to $b$ .

A majority (1 and 3) prefers $a$ to $b$ ; a majority (1 and 2) prefers $b$ to $c$ ; a majority (2 and 3) prefers $c$ to $a$ . The joint majority choice is $a\succ b\succ c\succ a$ — inconsistent. For any candidate chosen, a majority would want to change the outcome.

So whenever there are more than two alternatives we must design some more complex voting method.

WarningVoting methods invite strategic voting

Two simple methods: plurality (the candidate placed first by the most voters wins) and Borda count (a candidate gets $n-i$ points from each voter ranking him $i$ th). Each has nice properties and problematic ones.

The main difficulty is strategic voting. Suppose a voter’s true preference is $a\succ b\succ c$ but he knows $a$ will not win. He may be motivated to vote for $b$ instead, so that $b$ is chosen rather than $c$ . This is problematic because it is not transparent, depends closely on others’ votes, and the interaction of many strategic voters is complex.

The Gibbard–Satterthwaite theorem says this vulnerability is unavoidable.

DefinitionSocial welfare and social choice functions

With alternatives $A$ , voters $I$ of size $n$ , and $L$ the set of linear orders on $A$ (total, antisymmetric, transitive):

$F : L^n\to L$ is a social welfare function — it aggregates preferences into a full social order.
$f : L^n\to A$ is a social choice function — it aggregates into a single chosen candidate.

Arrow’s theorem

DefinitionThree desiderata for a social welfare function

Unanimity: $F(\prec,\ldots,\prec) = \prec$ — if all voters agree, the social preference is theirs.
Dictatorship: voter $i$ is a dictator if $F(\prec_1,\ldots,\prec_n) = \prec_i$ always, ignoring everyone else. $F$ is not a dictatorship if no $i$ is a dictator.
Independence of irrelevant alternatives (IIA): the social preference between $a$ and $b$ depends only on the voters’ preferences between $a$ and $b$ .

IntuitionWhat IIA is really doing

The first two are simple and clearly desirable. IIA is trickier. Intuitively it seems natural — why should my preferences about $c$ affect the social ranking of $a$ and $b$ ? More careful inspection reveals it captures a consistency property of the voting system, and lack of such consistency is exactly what enables strategic manipulation.

TheoremArrow

Every social welfare function over $|A|\ge3$ candidates satisfying unanimity and IIA is a dictatorship.

ProofPairwise neutrality, then find the pivotal voter

Claim (pairwise neutrality). Let $\prec_1,\ldots,\prec_n$ and $\prec_1',\ldots,\prec_n'$ be profiles with $a\prec_i b\iff c\prec_i' d$ for every $i$ . Then $a\prec b\iff c\prec' d$ .

WLOG assume $a\prec b$ and $c\ne b$ . Merge each $\prec_i$ and $\prec_i'$ into a single $\prec_i''$ by putting $c$ just above $a$ (unless $c=a$ ) and $d$ just below $b$ (unless $d=b$ ), preserving the internal order within the pairs $(a,b)$ and $(c,d)$ . By unanimity $c\prec'' a$ and $b\prec'' d$ , and by transitivity $c\prec'' d$ . IIA then transfers this to the original profiles.

Finding the dictator. Fix $a\ne b$ and for $0\le i\le n$ let $\pi^i$ be the profile in which exactly the first $i$ voters rank $a$ above $b$ (other rankings irrelevant). By unanimity $b\prec a$ in $F(\pi^0)$ is false — we have $b\succ a$ — while in $F(\pi^n)$ , $a\succ b$ . Somewhere the ranking flips: there is $i^*$ with $b\succ a$ in $F(\pi^{i^*-1})$ and $a\succ b$ in $F(\pi^{i^*})$ .

Claim: $i^*$ is a dictator. Take any $c\ne d$ with $c\succ_{i^*}d$ , and an alternative $e\notin\{c,d\}$ . For $i<i^*$ move $e$ to the top; for $i>i^*$ move $e$ to the bottom; for $i^*$ place it so $c\succ_{i^*}e\succ_{i^*}d$ — by IIA none of this changes the social ranking of $c$ vs. $d$ . Now the profile of preferences on $(c,e)$ is identical to that on $(a,b)$ in $\pi^{i^*}$ , and on $(e,d)$ identical to $(a,b)$ in $\pi^{i^*-1}$ . By pairwise neutrality, $c\succ e$ and $e\succ d$ , so by transitivity $c\succ d$ .

∎

The Gibbard–Satterthwaite theorem

DefinitionManipulation, incentive compatibility, monotonicity

$f$ can be strategically manipulated by voter $i$ if for some profile and some $\prec_i'$ , writing $a = f(\prec_i,\prec_{-i})$ and $a' = f(\prec_i',\prec_{-i})$ , we have $a\prec_i a'$ — a voter preferring $a'$ can get it chosen by misrepresenting his preferences. $f$ is incentive compatible if it cannot be manipulated.

$f$ is monotone if $f(\prec_i,\prec_{-i}) = a\ne a' = f(\prec_i',\prec_{-i})$ implies $a'\prec_i a$ and $a\prec_i' a'$ — if the choice changed when one voter changed his vote, it must be because he switched his preference between exactly those two alternatives.

ProofIncentive compatible

\iff

monotone

Quantifying out $\prec_{-i}$ : logically, “not monotone between $\prec$ and $\prec'$ ” is equivalent to “a voter with preference $\prec$ can manipulate by declaring $\prec'$ ” or “a voter with $\prec'$ can manipulate by declaring $\prec$ .”

∎

TheoremGibbard–Satterthwaite

Let $f$ be an incentive compatible social choice function onto $A$ with $|A|\ge3$ . Then $f$ is a dictatorship.

NoteWhy “onto” is needed

Without it the bound on $|A|$ has no bite — one can restrict the range to two alternatives and take a majority vote, breaking ties using preference information about points outside the range.

ProofBuild a social welfare function from

f

and invoke Arrow

The idea: to decide whether $a\prec b$ , move $a$ and $b$ to the top of every voter’s preference and see which $f$ chooses.

Notation. For $S\subseteq A$ , $\prec^S$ moves all of $S$ to the top of $\prec$ while preserving order within $S$ and within its complement. The extension $F$ is defined by $a\prec b$ iff $f(\prec_1^{\{a,b\}},\ldots,\prec_n^{\{a,b\}}) = b$ .

Key claim: for any profile and any $S$ , $f(\prec_1^S,\ldots,\prec_n^S)\in S$ . Take $a\in S$ ; since $f$ is onto, some profile gives $f = a$ . Now change $\prec_i$ to $\prec_i^S$ one voter at a time. At no point can the output be some $b\notin S$ , since by monotonicity $b\prec_i^S a'$ for the previous outcome $a'\in S$ .

From this claim everything follows:

Antisymmetry: the outcome lies in $\{a,b\}$ .
Transitivity: if $a\prec b\prec c\prec a$ , take $S=\{a,b,c\}$ and WLOG $f(\prec^S) = a$ ; changing each $\prec_i^S$ to $\prec_i^{\{a,b\}}$ , monotonicity keeps the outcome $a$ , so $a\succ b$ — contradiction.
Unanimity: if all prefer $a$ to $b$ , then $(\prec_i^{\{a,b\}})^{\{a\}} = \prec_i^{\{a,b\}}$ , so by the claim the outcome is $a$ .
IIA: flipping $\prec_i^{\{a,b\}}$ to $\prec_i'^{\{a,b\}}$ one voter at a time cannot change the outcome, by monotonicity and the claim.
Nondictatorship: obvious.

∎

ImportantThe Procrustean bed

Gibbard–Satterthwaite seems to quash any hope of incentive compatible social choice. The whole field of Mechanism Design is an attempt to escape this impossibility by modifying the model. Two escape routes structure this note:

Add money — Mechanisms with money onward.
Restrict the domain of preferences — Escaping without money: restricted domains.

(Other escapes not covered: randomization, making preferences common knowledge, and weaker notions of implementation.)

Mechanisms with money

DefinitionQuasilinear preferences

We no longer model a preference as an order but as a valuation function $v_i : A\to\mathbb{R}$ , where $v_i(a)$ is the value $i$ assigns to $a$ in terms of currency. If $a$ is chosen and $i$ is additionally given $m$ money, his utility is

$u_i = v_i(a) + m$

Such quasilinear preferences denote the separable, linear dependence on money.

IntuitionWhat money adds

In the order model, $a\succ_i b$ says nothing about by how much. Money is a yardstick allowing us to measure this — and, crucially, it can be transferred between players. Its existence is an assumption, but a fairly reasonable one, and it lets us do things otherwise impossible.

Vickrey’s second price auction

A single item among $n$ players, player $i$ willing to pay $w_i$ . In our terms $A = \{i\text{-wins}\}$ , with $v_i(i\text{-wins}) = w_i$ and 0 otherwise. The natural social choice is to give the item to $\arg\max_j w_j$ — but we don’t know the $w_i$ ; each player does. Our degree of freedom is the payment.

WarningThe two obvious payment rules both fail

No payment. Every player benefits by exaggerating $w_i'\gg w_i$ , winning even when his real value is not highest.
Pay your bid. A winner paying exactly $w_i$ gets utility 0, so he should bid some $w_i'<w_i$ , still winning but getting $u_i = w_i - w_i' > 0$ . What $w_i'$ then? If he knew the second highest bid he would bid just above it. But what if he doesn’t?

DefinitionVickrey’s second price auction

The winner is the player with highest declared $w_i$ , and he pays the second highest declared bid $p^* = \max_{j\ne i}w_j$ .

ProofManipulation never helps

If $i$ wins by bidding $w_i$ , with second highest $p^*$ , then $u_i = w_i - p^*\ge0$ . Any manipulation $w_i'>p^*$ still wins and still pays $p^*$ , so $u_i' = u_i$ ; any $w_i'\le p^*$ loses, so $u_i' = 0\le u_i$ .

If $i$ loses, $u_i = 0$ ; let $j$ win, so $w_j\ge w_i$ . Any $w_i'<w_j$ still loses. Any $w_i'\ge w_j$ wins but pays $w_j$ , giving $u_i' = w_i - w_j\le0 = u_i$ .

∎

ImportantWhat this elegant idea achieves

It reliably computes a function ( $\arg\max$ ) of $n$ numbers each held secretly by a different self-interested player. Philosophically this may be seen as the mechanics implementing Adam Smith’s invisible hand: despite private information and pure selfish behavior, social welfare is achieved. All of Mechanism Design is a generalization of this possibility.

Incentive compatible mechanisms and VCG

ConventionThe $-i$ notation

$v_{-i} = (v_1,\ldots,v_{i-1},v_{i+1},\ldots,v_n)$ , so $v = (v_i, v_{-i})$ ; similarly $V_{-i}$ , $t_{-i}$ , $x_{-i}$ .

DefinitionDirect revelation mechanism, incentive compatibility

A (direct revelation) mechanism is a social choice function $f : V_1\times\cdots\times V_n\to A$ together with payment functions $p_i : V_1\times\cdots\times V_n\to\mathbb{R}$ .

It is incentive compatible (also strategy-proof, truthful) if for every $i$ , every profile, and every $v_i'$ , writing $a = f(v_i,v_{-i})$ and $a' = f(v_i',v_{-i})$ :

$v_i(a) - p_i(v_i,v_{-i}) \ge v_i(a') - p_i(v_i',v_{-i})$

Intuitively, $i$ prefers telling the truth to any possible lie.

DefinitionVCG mechanism

$(f,p_1,\ldots,p_n)$ is a Vickrey–Clarke–Groves mechanism if

$f(v)\in\operatorname{argmax}_{a\in A}\sum_i v_i(a) \quad\text{(maximizes social welfare)}$

and for some functions $h_i : V_{-i}\to\mathbb{R}$ (not depending on $v_i$ ),

$p_i(v) = h_i(v_{-i}) - \sum_{j\ne i}v_j\big(f(v)\big)$

IntuitionWhy this aligns incentives

The term $-\sum_{j\ne i}v_j(f(v))$ means each player is paid the sum of the values of all others. Added to his own $v_i(f(v))$ , the sum is exactly the total social welfare. So the mechanism aligns every player’s incentive with the social goal, which truth-telling achieves. The other term $h_i(v_{-i})$ has no strategic implication for $i$ — from his point of view it is just a constant — though it does change how much money moves and in which direction.

TheoremVCG

Every VCG mechanism is incentive compatible.

ProofSubtract the same constant from both sides

Fix $i, v_{-i}, v_i, v_i'$ , and let $a = f(v_i,v_{-i})$ , $a' = f(v_i',v_{-i})$ . The utility when declaring $v_i$ is $v_i(a) + \sum_{j\ne i}v_j(a) - h_i(v_{-i})$ , and when declaring $v_i'$ it is $v_i(a')+\sum_{j\ne i}v_j(a')-h_i(v_{-i})$ . Since $a$ maximizes social welfare, $v_i(a)+\sum_{j\ne i}v_j(a)\ge v_i(a')+\sum_{j\ne i}v_j(a')$ , and subtracting the same $h_i(v_{-i})$ preserves the inequality.

∎

The Clarke pivot rule

Warning $h_i = 0$ is legal but silly

It is simple, but the mechanism then pays a great amount of money to the players. We would prefer players to pay the mechanism — but not more than their gain.

DefinitionTwo desirable properties, and the rule that gives them

(Ex-post) individually rational: players always get non-negative utility, $v_i(f(v)) - p_i(v)\ge0$ .
No positive transfers: no player is ever paid, $p_i(v)\ge0$ .

The Clarke pivot payment is $h_i(v_{-i}) = \max_{b\in A}\sum_{j\ne i}v_j(b)$ , giving

$p_i(v) = \max_b\sum_{j\ne i}v_j(b) - \sum_{j\ne i}v_j(a), \qquad a = f(v)$

IntuitionInternalizing externalities

$i$ pays the total damage he causes the others — the difference between the social welfare of the others with and without his participation. The payments make each player internalize the externalities that he causes.

ProofVCG with Clarke pivot has both properties

Let $a$ maximize $\sum_jv_j$ and $b$ maximize $\sum_{j\ne i}v_j$ .

Individual rationality (assuming $v_i\ge0$ ): $i$ ‘s utility is $v_i(a)+\sum_{j\ne i}v_j(a) - \sum_{j\ne i}v_j(b)\ge\sum_jv_j(a)-\sum_jv_j(b)\ge0$ , the first inequality since $v_i(b)\ge0$ and the second since $a$ maximizes.

No positive transfers: $p_i(v) = \sum_{j\ne i}v_j(b)-\sum_{j\ne i}v_j(a)\ge0$ since $b$ maximizes.

∎

NoteWhen valuations are negative

With costs rather than values, the Clarke rule has players always paying the mechanism, while the natural reading is the opposite. Its spirit is captured by choosing $b$ to maximize welfare “when $i$ does not participate”, whose exact meaning turns out natural in most applications.

Examples

Setting	Social choice	VCG / Clarke payment
Single item	highest value wins	exactly Vickrey’s second price auction
Reverse (procurement) auction	lowest cost supplies	pay the lowest bidder the second lowest bid — “what would happen without $i$ “
Multiunit, unit demand	the $k$ highest bidders win	each winner pays the $(k{+}1)$ st highest offered price; losers pay 0
Bilateral trade	trade iff $v_b > v_s$	buyer pays $v_s$ , seller is paid $v_b$ — the mechanism subsidizes the trade
Public project	build iff $\sum_i v_i > C$	only pivotal players pay: if $\sum_{j\ne i}v_j\le C$ but $\sum_jv_j>C$ , then $p_i = C - \sum_{j\ne i}v_j$
Buying a path	the shortest $s$ – $t$ path	each $e_0$ on the path is paid $\sum_{e\in p'}c_e - \sum_{e\in p-\{e_0\}}c_e$ , where $p'$ is the shortest path avoiding $e_0$

WarningTwo deficits that turn out to be unavoidable

In bilateral trade, since $v_b>v_s$ whenever trade occurs, the mechanism pays out more than it collects. In the public project, one may verify $\sum_i p_i < C$ unless $\sum_iv_i = C$ — the payments never cover the project’s cost. Uniqueness of prices shows neither can be fixed.

NoteModelling the public project

This is not technically a subcase of welfare maximization as defined, since we assumed no costs to the designer — but it becomes one by adding an extra “government” player whose singleton valuation gives cost $C$ to undertaking the project and 0 otherwise.

Implementation in dominant strategies

The wider context. So far mechanisms extract information by motivating players to “tell the truth.” More generally one might devise a complex protocol that achieves the required social choice when players act strategically. This section formalizes those more general mechanisms.

DefinitionGame with strict incomplete information

For $n$ players: action sets $X_i$ ; type sets $T_i$ , where $t_i\in T_i$ is $i$ ‘s private information; and utilities $u_i : T_i\times X_1\times\cdots\times X_n\to\mathbb{R}$ .

Independent private values means $i$ ‘s utility depends fully on his own private information, independent of others’. Strict incomplete information — sometimes “pre-Bayesian” — means no probabilistic information is in the model; from a CS perspective, worst-case analysis over unknown information.

ImportantWhy the interplay is delicate

Each player must choose $x_i$ knowing $t_i$ but not the other $t_j$ . The $t_j$ do not affect his utility, but they do affect how the others behave. A player’s total behavior is captured by a strategy $s_i : T_i\to X_i$ , and it is these strategies we want in equilibrium.

DefinitionEx-post Nash and dominant strategies

$s_1,\ldots,s_n$ is an ex-post-Nash equilibrium if for every profile of types the actions are in Nash equilibrium in the full-information game: for all $i,t,x_i$ , $u_i(t_i,s_i(t_i),s_{-i}(t_{-i}))\ge u_i(t_i,x_i,s_{-i}(t_{-i}))$ .
$s_i$ is (weakly) dominant if for all $t_i$ , all $x_{-i}$ , all $x_i$ : $u_i(t_i,s_i(t_i),x_{-i})\ge u_i(t_i,x_i,x_{-i})$ .

IntuitionThe difference, and why both seem too good to be true

Ex-post Nash requires $s_i(t_i)$ to be a best response to $s_{-i}(t_{-i})$ for every $t_{-i}$ — i.e. knowing nothing about $t_{-i}$ but knowing the forms of the others’ strategies. Dominant strategy requires it against any $x_{-i}$ — knowing nothing about $t_{-i}$ or $s_{-i}$ .

How likely is a single action to be a best response to everything? In usual cases one does not expect such equilibria to exist at all. But in Mechanism Design we get to design the game, so we can sometimes make sure they do.

PropositionThe gap is only about unused actions

If $s$ is an ex-post-Nash equilibrium, define $X_i' = \{s_i(t_i) : t_i\in T_i\}$ — the actual range of $s_i$ . Then $s$ is a dominant strategy equilibrium in the game with action spaces $X_i'$ .

ProofEvery action in the range is some type’s action

Let $x_i = s_i(t_i)$ , $x_i'\in X_i'$ , and $x_j'\in X_j'$ for $j\ne i$ . By definition each $x_j' = s_j(t_j)$ for some $t_j$ . Ex-post Nash gives $u_i(t_i,s_i(t_i),s_{-i}(t_{-i}))\ge u_i(t_i,x_i',s_{-i}(t_{-i}))$ , and since $x_{-i}' = s_{-i}(t_{-i})$ this is exactly the dominance condition.

∎

DefinitionGeneral mechanism and implementation

A mechanism is type spaces $T_i$ , action spaces $X_i$ , alternatives $A$ , valuations $v_i : T_i\times A\to\mathbb{R}$ , an outcome function $a : X_1\times\cdots\times X_n\to A$ , and payments $p_i : X_1\times\cdots\times X_n\to\mathbb{R}$ . The induced game has $u_i(t_i,x) = v_i(t_i,a(x)) - p_i(x)$ .

It implements $f$ in dominant strategies if for some dominant strategy equilibrium $s$ , $f(t) = a(s_1(t_1),\ldots,s_n(t_n))$ for all $t$ ; similarly for ex-post.

NoteA weak requirement

Our definition requires only that some equilibrium yields $f$ , allowing others to exist. Stronger requirements would demand all equilibria do, or that the equilibrium be unique.

The revelation principle

TheoremRevelation principle

If any mechanism implements $f$ in dominant strategies, then an incentive compatible (direct revelation) mechanism implements $f$ — with identical payments to those obtained at equilibrium in the original.

ProofSimulate the equilibrium strategies

Let $s$ be a dominant strategy equilibrium. Define $f(t) = a(s_1(t_1),\ldots,s_n(t_n))$ and $p_i'(t) = p_i(s_1(t_1),\ldots,s_n(t_n))$ . Since each $s_i$ is dominant, for every $t_i,x_{-i},x_i$ : $v_i(t_i,a(s_i(t_i),x_{-i})) - p_i(s_i(t_i),x_{-i}) \ge v_i(t_i,a(x_i,x_{-i})) - p_i(x_i,x_{-i})$ . Taking $x_{-i} = s_{-i}(t_{-i})$ and $x_i = s_i(t_i')$ gives exactly incentive compatibility.

∎

CorollaryEx-post too

Restrict the action spaces to the ranges as in the proposition above, making $s$ dominant; then apply the revelation principle.

ImportantWhat the principle does not say

It does not mean indirect mechanisms are useless. General mechanisms may be adaptive (multiround), significantly reducing the communication or computation burden on the players or the auctioneer relative to a nonadaptive direct mechanism — combinatorial auctions being the example.

Characterizing incentive compatible mechanisms

The driving question. We can implement welfare maximization. What other social choice functions can we implement?

IntuitionWhy we want others

In economics, chiefly to increase revenue or introduce fairness. In computing, there are many natural optimization goals — in scheduling, the makespan, very different from total welfare. And crucially, computational considerations: often $A$ is complex and maximizing welfare is NP-complete, while efficient approximation algorithms exist. Such an algorithm is in effect a social choice function approximating welfare maximization but differing from it. Can it be implemented?

Direct characterization

TheoremIncentive compatibility, spelled out

A mechanism is incentive compatible iff for every $i$ and every $v_{-i}$ :

The payment does not depend on $v_i$ , only on the alternative chosen. That is, there are prices $p_a$ for $a\in A$ with $p(v_i,v_{-i}) = p_a$ whenever $f(v_i,v_{-i}) = a$ .
The mechanism optimizes for each player: $f(v_i,v_{-i})\in\operatorname{argmax}_a\big(v_i(a)-p_a\big)$ , over the range of $f(\cdot,v_{-i})$ .

ProofBoth directions

(If) With $a,a'$ the outcomes and $p_a,p_{a'}$ the payments, $i$ ‘s truthful utility $v_i(a)-p_a$ is at least $v_i(a')-p_{a'}$ precisely because the mechanism optimizes for him.

(Only if, condition 1) If two declarations give the same outcome but different payments, a player with the more expensive type declares the cheaper one. (Only if, condition 2) If some $a'$ in the range beats $f(v_i,v_{-i})$ for player $i$ , he declares whichever $v_i'$ produces $a'$ .

∎

Weak monotonicity

DefinitionWMON

$f$ satisfies weak monotonicity if for all $i, v_{-i}$ : $f(v_i,v_{-i}) = a \ne b = f(v_i',v_{-i})$ implies

$v_i(a)-v_i(b)\ \ge\ v_i'(a)-v_i'(b)$

— if the social choice changes when one player changes his valuation, it must be because he increased his value of the new choice relative to the old.

TheoremWMON characterizes, on convex domains

If a mechanism is incentive compatible then $f$ satisfies WMON. If all domains $V_i$ are convex, then for every WMON social choice function there exist payments making it incentive compatible.

ProofThe easy direction

Fix $i,v_{-i}$ ; by the direct characterization there are fixed prices $p_a$ . If $f(v_i,v_{-i}) = a\ne b = f(v_i',v_{-i})$ , then $v_i$ not preferring to declare $v_i'$ gives $v_i(a)-p_a\ge v_i(b)-p_b$ , and $v_i'$ not preferring $v_i$ gives $v_i'(a)-p_a\le v_i'(b)-p_b$ . Subtracting yields WMON.

∎

WarningWMON is local, and not sufficient in general

The converse direction is quite involved and is not given here; WMON is known not to be sufficient on general non-simply-connected domains.

Even where it holds, WMON leaves something to be desired: it is a local condition, for each player and each $v_{-i}$ separately. Is there a global characterization? That depends intimately on the domain $V_i$ . Two extremes have good answers — $V_i$ unrestricted and $V_i$ essentially single dimensional. The intermediate range, where most computationally interesting problems lie, is still wide open.

Roberts’ theorem: unrestricted domains

DefinitionAffine maximizer

$f$ is an affine maximizer if for some subrange $A'\subseteq A$ , player weights $w_i\in\mathbb{R}^+$ , and outcome weights $c_a\in\mathbb{R}$ ,

$f(v)\in\operatorname{argmax}_{a\in A'}\Big(c_a+\sum_i w_iv_i(a)\Big)$

PropositionWeighted VCG works

With $p_i(v) = h_i(v_{-i}) - \sum_{j\ne i}(w_j/w_i)v_j(a) - c_a/w_i$ , the mechanism is incentive compatible.

ProofMultiply by

w_i>0

Assume WLOG $h_i=0$ . Player $i$ ‘s utility is $v_i(a)+\sum_{j\ne i}(w_j/w_i)v_j(a)+c_a/w_i$ ; multiplying by $w_i>0$ , this is maximized exactly when $c_a+\sum_jw_jv_j(a)$ is — which is what truthful reporting produces.

∎

TheoremRoberts

If $|A|\ge3$ , $f$ is onto $A$ , $V_i = \mathbb{R}^A$ for every $i$ , and the mechanism is incentive compatible, then $f$ is an affine maximizer.

NoteBoth hypotheses matter

The restriction $|A|\ge3$ is crucial, as in Arrow’s theorem, since $|A|=2$ falls into the single-parameter case below, where non-weighted-VCG mechanisms exist. It remains open how far $V_i = \mathbb{R}^A$ can be relaxed.

Single-parameter domains

DefinitionSingle parameter domain

Defined by a publicly known winning set $W_i\subseteq A$ and a range $[t^0,t^1]$ : $V_i$ consists of those $v_i$ for which, for some $t^0\le t\le t^1$ , $v_i(a) = t$ for $a\in W_i$ and $v_i(a) = 0$ otherwise. We abuse notation and use $v_i$ as the scalar $t$ .

The point: all winning alternatives are equivalent to $i$ , and so are all losing ones. All the examples above fall into this category — in a single-item auction $W_i$ is the single outcome where $i$ wins; in buying a path, $W_i$ is the set of all paths containing edge $i$ .

DefinitionMonotone rules and critical values

$f$ is monotone in $v_i$ if $v_i\le v_i'$ and $f(v_i,v_{-i})\in W_i$ imply $f(v_i',v_{-i})\in W_i$ — a higher valuation still wins.

For a monotone $f$ there is a critical value $c_i(v_{-i}) = \sup_{v_i : f(v_i,v_{-i})\in W_i}v_i$ , below which $i$ loses and above which he wins (undefined if $i$ can never win). In a second price auction the critical value is the highest other declared value.

TheoremCharacterization on single-parameter domains

A normalized mechanism (losers pay 0) is incentive compatible iff

$f$ is monotone in every $v_i$ , and
every winning bid pays the critical value: $p_i(v_i,v_{-i}) = c_i(v_{-i})$ whenever $f(v_i,v_{-i})\in W_i$ .

ProofAll three parts

(If) Whatever $i$ declares, winning gives $v_i - c_i(v_{-i})$ and losing gives 0, so he prefers to win iff $v_i>c_i(v_{-i})$ — which is exactly what truth produces.

(Only if, monotonicity) If $v_i'>v_i$ with $v_i$ winning at price $p$ and $v_i'$ losing: $v_i$ not preferring to lose gives $v_i - p\ge0$ ; $v_i'$ not preferring to win gives $v_i' - p\le0$ . Contradiction.

(Only if, payment) If a winner pays $p>c_i(v_{-i})$ then by the direct characterization all winners pay $p$ , including one with $c_i(v_{-i})<v_i<p$ — who would rather lose by bidding below $c_i(v_{-i})$ . Conversely if $p<c_i(v_{-i})$ , a loser with $c_i(v_{-i})>v_i>p$ would rather win.

∎

ImportantAmple room beyond affine maximization

We can implement e.g. maximizing the Euclidean norm $\operatorname{argmax}_a\sqrt{\sum_iv_i^2(a)}$ or the egalitarian $\operatorname{argmax}_a\min_iv_i(a)$ . In many cases this flexibility allows computationally efficient approximation mechanisms for problems whose exact optimization is intractable.

Uniqueness of prices

TheoremPayments are determined up to an additive constant

Assume the domains $V_i$ are connected. If $(f,p)$ is incentive compatible, then $(f,p')$ is incentive compatible iff $p_i'(v) = p_i(v) + h_i(v_{-i})$ for some functions $h_i$ .

ProofClose alternatives first, then connectedness

The “if” is clear since $h_i$ has no strategic implication. For “only if”: fix $i,v_{-i}$ ; by the direct characterization the payment is a constant $p_a$ on $V^a = \{v_i : f(v_i,v_{-i}) = a\}$ , and likewise $p_a'$ . It suffices to show $p_a - p_b = p_a'-p_b'$ for all $a,b$ .

Call $a,b$ close if for every $\epsilon>0$ there are $v_i^a,v_i^b$ with $\lVert v_i^a - v_i^b\rVert\le\epsilon$ mapping to $a$ and $b$ respectively. For close $a,b$ : $v_i^a$ not preferring $v_i^b$ gives $v_i^a(a)-p_a\ge v_i^a(b)-p_b$ , and symmetrically, so

$v_i^a(b)-v_i^a(a)\ \le\ p_b-p_a\ \le\ v_i^b(b)-v_i^b(a)$

and identically for $p'$ . Since $\lVert v_i^a-v_i^b\rVert\le\epsilon$ , the two bounds are at most $2\epsilon$ apart, so $|(p_b-p_a)-(p_b'-p_a')|\le2\epsilon$ ; as $\epsilon$ was arbitrary they are equal.

For general $a,b$ : let $B = \{b : p_b-p_a = p_b'-p_a'\}$ . By transitivity of the relation, no alternative outside $B$ is close to one inside, so $V^B$ has positive distance from $V^{A-B}$ — contradicting connectedness of $V_i$ .

∎

ImportantThree consequences

The only incentive compatible mechanisms maximizing social welfare are those with VCG payments.
In bilateral trade, the only welfare-maximizing incentive compatible mechanism making no payments under no-trade is the one that subsidizes trade. More generally, an ex-post individually rational mechanism cannot dictate positive payments under no-trade, so it must subsidize.
In the public project, no ex-post individually rational welfare-maximizing mechanism can recover the cost. Players with value 0 pay 0 (as much as individual rationality permits), so their payments must be identical to the Clarke pivot ones.

NoteConnectedness is essential

If valuations are restricted to be integral, modifying $p_i$ by any small constants $\epsilon<1/2$ preserves incentive compatibility.

Randomized mechanisms

DefinitionTwo notions of incentive compatibility

A randomized mechanism is a distribution over deterministic mechanisms. It is incentive compatible

in the universal sense if every deterministic mechanism in the support is incentive compatible;
in expectation if truth is dominant in the game induced by expectation.

Universal implies in-expectation. In-expectation is the more natural requirement for most purposes; the universal definition matters if players are not risk neutral, or if the mechanism’s internal randomization is not completely hidden from the players.

TheoremRandomized single-parameter characterization

Writing $w_i(v_i,v_{-i}) = \Pr[f(v_i,v_{-i})\in W_i]$ and letting $p_i$ denote the expected payment, a normalized randomized mechanism on a single parameter domain is incentive compatible in expectation iff for every $i$ and $v_{-i}$ :

$w_i(v_i,v_{-i})$ is monotonically nondecreasing in $v_i$ , and
$\displaystyle p_i(v_i,v_{-i}) = v_i\cdot w(v_i,v_{-i}) - \int_{v_i^0}^{v_i}w(t,v_{-i})\,dt$

ProofBoth directions, dropping the indices

(If) We need $vw(v)-p(v)\ge vw(v')-p(v')$ . Substituting the payment formula reduces this to $\int_{v}^{v'}w(t)dt\le(v'-v)w(v')$ for $v'>v$ and the reverse for $v'<v$ — both true by monotonicity.

(Only if) Combining the incentive constraints at $v$ and at $v'$ and subtracting gives $(v'-v)w(v)\le(v'-v)w(v')$ , i.e. monotonicity. Rearranging the same two constraints,

$v\cdot(w(v')-w(v))\ \le\ p(v')-p(v)\ \le\ v'\cdot(w(v')-w(v))$

Setting $v'=v+\epsilon$ , dividing by $\epsilon$ , and letting $\epsilon\to0$ , both sides approach $v\cdot dw/dv$ , so $dp/dv = v\cdot dw/dv$ . Integrating with $p(v^0)=0$ and then integrating by parts gives the formula. (This appears to need differentiability of $w$ , but monotonicity gives it almost everywhere, which suffices since we immediately integrate.)

∎

WarningWhose randomness

The randomization here is completely controlled by the mechanism designer and has nothing to do with distributional assumptions on players’ valuations — which is the subject of the next section.

Bayesian–Nash implementation

Why relax. Dominant strategies model situations where a player has no information about others — not even a prior — and must operate under worst-case assumptions. This is usually considered too strict in economic theory, whose working definition assumes a commonly known prior and Bayesian optimization.

DefinitionGame with incomplete information

As before but with a prior distribution $D_i$ on each type space $T_i$ . A profile $s_1,\ldots,s_n$ is a Bayesian–Nash equilibrium if for all $i$ , all $t_i$ , all $x_i$ :

$\mathbb{E}_{D_{-i}}\big[u_i(t_i,s_i(t_i),s_{-i}(t_{-i}))\big]\ \ge\ \mathbb{E}_{D_{-i}}\big[u_i(t_i,x_i,s_{-i}(t_{-i}))\big]$

A mechanism is truthful in the Bayesian sense if it is direct revelation and the truthful strategies $s_i(t_i)=t_i$ form a Bayesian–Nash equilibrium. The revelation principle holds here too, preserving expected payments.

NoteThe containment

Every ex-post-Nash implementation is by definition a Bayesian implementation for any distributions. But in general Bayesian implementation depends on the $D_i$ , and there are many cases where a Bayesian–Nash equilibrium exists though no dominant-strategy one does — the first price auction being the example.

First price auction

Two players, Alice with value $a$ and Bob with value $b$ . Alice will not bid $a$ (utility 0 even winning), so she bids $x<a$ — but how much lower? If she knew Bob’s bid $y$ she would bid $y+\epsilon$ . But she knows neither $y$ nor $b$ , only the distribution $D_{Bob}$ .

LemmaEquilibrium of the first price auction

With values uniform on $[0,1]$ , the strategies $x(a) = a/2$ and $y(b) = b/2$ are in Bayesian–Nash equilibrium.

ProofMaximize

2x(a-x)

Alice’s expected utility from bid $x$ is $\Pr[\text{win}]\cdot(a-x)$ . Against $y = b/2$ she wins iff $x\ge b/2$ , which for $b$ uniform on $[0,1]$ has probability $2x$ for $0\le x\le1/2$ (and 1 above, 0 below). The optimum is clearly in $[0,1/2]$ , so maximize $2x(a-x)$ : differentiating, $2a-4x = 0$ , giving $x = a/2$ .

∎

NoteTwo observations

$x<y$ iff $a<b$ , so the winner is also the player with the highest value — the first price auction maximizes social welfare too, just like second price. And finding Bayesian–Nash equilibria is generally not easy; the closed form here relies on the symmetric case, though similar arguments work for arbitrary nonatomic distributions and any number of bidders.

Revenue equivalence

IntuitionThe surprising numerical coincidence

Second price revenue is $\min(a,b)$ ; first price revenue is $\max(a/2,b/2)$ . Each is higher for certain values. But in expectation over $a,b$ uniform on $[0,1]$ , both equal exactly $1/3$ . This is no coincidence.

TheoremRevenue equivalence

Under weak assumptions, for every two Bayesian–Nash implementations of the same social choice function: if for some type $t_i^0$ the expected payment of player $i$ is the same in both, then it is the same for every type $t_i$ . In particular, if for each player there exists such a type, the two mechanisms have identical expected revenues.

ProofPath from

t^0

t^1

through the convex valuation space

By the revelation principle restrict to Bayesian-truthful mechanisms. Assumption 1: each $V_i$ is convex (or path-connected, with a messier proof).

Take $t_i^1$ and derive the expected payment from that at $t_i^0$ and from $f$ alone. Write $v^0 = v(t_i^0,\cdot)$ , $v^1 = v(t_i^1,\cdot)$ , and the convex combinations $v^\lambda = v^0+\lambda(v^1-v^0)$ ; convexity gives a type $t_i^\lambda$ realizing each. Let $p^\lambda$ be the expected payment at $t_i^\lambda$ , and $w^\lambda(a) = \Pr_{t_{-i}}[f(t_i^\lambda,t_{-i}) = a]$ . Assumption 2: $w^\lambda$ is continuously differentiable in $\lambda$ .

The expected utility of type $t_i^\lambda$ declaring $t_i^{\lambda'}$ is $v^\lambda\cdot w^{\lambda'} - p^{\lambda'}$ . Truthfulness at $\lambda$ and at $\lambda+\epsilon$ gives

$v^\lambda(w^{\lambda+\epsilon}-w^\lambda)\ \le\ p^{\lambda+\epsilon}-p^\lambda\ \le\ v^{\lambda+\epsilon}(w^{\lambda+\epsilon}-w^\lambda)$

Dividing by $\epsilon$ and letting $\epsilon\to0$ , both sides approach $v^\lambda\cdot w'(\lambda)$ , so $dp/d\lambda$ exists and is continuous. Integrating, $p^1 = p^0 + \int_0^1 v^\lambda\cdot w'(\lambda)\,d\lambda$ .

∎

ImportantCompare with uniqueness of prices

The similarity to Uniqueness of prices should be noted: in both, the allocation rule determines the payments up to a normalization — there for every fixed $v_{-i}$ , here in expectation over $t_{-i}$ . The proofs look different for technical reasons but the underlying idea is the same: take two close types and put together the two constraints saying neither gains by misrepresenting as the other.

Consequently all the corollaries of Uniqueness of prices hold in expectation for all Bayesian–Nash implementations.

ExampleRaising revenue requires changing the allocation

Two bidders uniform on $[0,1]$ . Put a reservation price of $1/2$ , selling to the highest bidder at the maximum of the low bid and $1/2$ , with no sale if both bid below. This is incentive compatible, and its expected revenue is $5/12 > 1/3$ . Revenue equivalence is not violated because the social choice function changed — sometimes nobody wins.

Further models

NoteRisk aversion

All the Bayesian discussion assumed risk neutrality: utility 2 with probability $1/2$ equals utility 1 for sure, which is why we could just take expectations. Real players are often risk-averse, preferring lower but more certain utility. The revenue equivalence principle fails for such players: it is known that first price auctions generate more revenue than second price when bidders are risk-averse.

NoteInterdependent values

We assumed independent private values. In general there is a joint distribution over “states of the world”, and players get signals — partial information providing some about their own valuation and some about others’. Most results in this chapter cease holding.

The extreme opposite is the common value model: the object has exactly the same value for everyone, but nobody knows it (e.g. bonds, whose value depends on future interest rates and default probability). Here an auction serves as an information aggregation vehicle. The pitfall is the winner’s curse: if each bidder bids his own signal-based estimate, the winner will likely regret winning — winning means other signals implied a lower value. So in equilibrium bidders must bid an estimate conditioned on the fact that they win.

A common formalization combining both components is affiliated signals, where each player’s signal is positively correlated (in the strong technical sense of affiliation) with others’ values. There, ascending English auctions generate more revenue than the nonadaptive second price auction: as bidding progresses, each bidder gets information raising his estimate.

NoteComplete information models

Sometimes all players have complete information and only the mechanism designer lacks it. The prototype is King Solomon: two women each claiming the baby. Both know the truth; Solomon must design a mechanism eliciting it from their differing preferences. Mechanism design is much easier here, and many implementations without money are possible.

NoteHidden actions

All of Mechanism Design addresses private information. A complementary difficulty is hidden actions not visible to the mechanism — widely studied in economics and recently in computer science.

Escaping without money: restricted domains

ImportantThe Procrustean bed, and the second escape route

The Gibbard–Satterthwaite theorem is a Procrustean bed — escaped only by relaxing its assumptions. (Procrustes boasted of a bed whose length exactly matched its occupant; he neglected to mention this was achieved by stretching or butchering his guests to fit.)

In many applications it is clearly unreasonable to assume preferences are completely unrestricted. Where money can be transferred, we get the rich class of rules above. But there are important environments where money cannot be used as compensation — from ethical or institutional constraints: many political decisions must be made without transfers; organ donations can be arranged by “trade” among needy patients and their relatives, yet monetary compensation is illegal.

PropositionSmaller domains are easier

Consider problems $(N,A,R_1,\ldots,R_n)$ and $(N,A,R_1',\ldots,R_n')$ with $R_i'\subseteq R_i$ . If $f$ is strategy-proof for the former, its restriction $f|_{\times R_i'}$ is strategy-proof for the latter.

Why: on a smaller domain, strategy-proofness imposes strictly fewer constraints. This justifies searching for reasonable (or at least nondictatorial) rules on smaller domains.

NotePublic versus private goods

The single-peaked model is a canonical public good setting ( $R_i = R_j$ for all $i,j$ ). The matching problems are private good problems: each $R_i$ contains only preferences sensitive to certain dimensions of $A$ — each agent cares only about his own consumption — so $R_i\ne R_j$ whenever $i\ne j$ .

Single-peaked preferences over policies

DefinitionThe model

Policy space $A = [0,1]$ ; an outcome is a point $x\in A$ . Agent $i$ ‘s preference $\succeq_i$ is single-peaked if there is a peak $p_i$ such that for all $x\ne p_i$ and all $\lambda\in[0,1)$ ,

$(\lambda x + (1-\lambda)p_i)\ \succ_i\ x$

— preference is strictly decreasing as one moves away from the peak. Let $R$ denote the class of such preferences; a rule is $f : R^n\to A$ .

IntuitionWhat this models

An income tax rate; a conservative/liberal political issue; the location of a public facility on a road; a group deciding the temperature of a shared office. In each, agents have an ideal policy and prefer decisions close to it.

DefinitionOnto, unanimity, Pareto-optimality

$f$ is onto if every $x\in A$ is chosen for some profile — it cannot preclude an outcome ex ante. Unanimity requires that if all peaks coincide, that point is chosen. Pareto-optimality requires no $x$ that all agents prefer to $f(\succeq)$ .

WarningOnto is not without loss of generality

Fix $x,y$ and consider the rule choosing whichever a majority prefers (ties to $x$ ). That is strategy-proof but not onto. Such rules can even break ties using preference information about points $x',y'$ not in the range.

LemmaAmong strategy-proof rules, all three coincide

If $f$ is strategy-proof then onto $\iff$ unanimous $\iff$ Pareto-optimal.

ProofOne agent at a time

Pareto-optimality trivially implies the others. Onto $\Rightarrow$ unanimous: fix $x$ with $f(\succeq) = x$ , and any unanimous $\succeq'$ with all peaks at $x$ . By strategy-proofness $f(\succeq_1',\succeq_2,\ldots) = x$ (else agent 1 manipulates); repeating agent by agent gives $f(\succeq') = x$ .

Unanimous $\Rightarrow$ Pareto-optimal: suppose not, so WLOG $f(\succeq)<p_i$ for all $i$ , with agents labelled so $p_1\le\cdots\le p_n$ . If $p_1 = p_n$ , unanimity is violated. Otherwise let $j<n$ be the number of agents at the minimum peak. For $i>j$ let $\succeq_i'$ have $p_i' = p_1$ and $f(\succeq)\succ_i' p_i'$ . Let $x_n = f(\succeq_1,\ldots,\succeq_{n-1},\succeq_n')$ . Strategy-proofness gives $x_n\in[f(\succeq),p_n]$ (else agent $n$ with $\succeq_n$ manipulates via $\succeq_n'$ ) and $x_n\notin(f(\succeq),p_n]$ (else agent $n$ with $\succeq_n'$ manipulates via $\succeq_n$ ), so $x_n = f(\succeq)$ . Repeating for each $i>j$ contradicts unanimity.

∎

The rules

IntuitionWhy the median works

With $n$ odd, the rule choosing the median of the peaks is strategy-proof. If an agent’s peak lies below the median, he can change the median only by reporting a peak above the true median — moving the outcome further from his own peak, making him worse off. Symmetrically above. And if his peak is the median, he cannot gain.

More generally the $k$ th highest peak is strategy-proof for the same reason: an agent can only move the $k$ th peak further from his own. The median is $k = (n+1)/2$ .

WarningAverages are manipulable

The rule choosing the average of the peaks is manipulable by any agent whose peak is not the average: he reports a more extreme peak (closer to 0 or 1). The same holds for any weighted average — with one exception: putting all weight on one agent, giving a dictatorial rule, which is strategy-proof and onto.

ImportantStrategy-proofness buys informational simplicity for free

A rule technically requires reporting an entire ordering over $[0,1]$ . The rules above need only the peak — a single number. Under the onto assumption this informational property is a consequence of strategy-proofness: all strategy-proof onto rules can be computed from the peaks alone.

DefinitionAnonymity and the phantom-voter rules

$f$ is anonymous if $f(\succeq^\sigma) = f(\succeq)$ for any permutation — agents’ names play no role. Dictatorial rules are strategy-proof and onto but not anonymous.

Generalizing $k$ th-statistic rules: fix points $y_1,\ldots,y_{n-1}\in A$ and choose the median of the $2n-1$ points consisting of the $n$ peaks and the $n-1$ fixed points. For some $y$ and some profiles this may choose a point that is no agent’s peak — yet it is strategy-proof for the same reason.

TheoremCharacterization with anonymity

$f$ is strategy-proof, onto and anonymous iff there exist $y_1,\ldots,y_{n-1}\in[0,1]$ with

$f(\succeq) = \operatorname{med}\{p_1,\ldots,p_n,y_1,\ldots,y_{n-1}\}$

ProofConstruct the

y_m

from extreme profiles, then two cases

Let $\succeq_i^0$ and $\succeq_i^1$ be the (unique, since preferences are ordinal) preferences with peaks at 0 and 1. Construct $y_m$ as the outcome when exactly $m$ agents have $\succeq^1$ and the rest $\succeq^0$ . Strategy-proofness implies monotonicity: $y_m\le y_{m+1}$ .

Take a profile with peaks ordered $p_i\le p_{i+1}$ and let $x^* = \operatorname{med}\{p_1,\ldots,p_n,y_1,\ldots,y_{n-1}\}$ .

Case 1: $x^* = y_m$ for some $m$ . By monotonicity $p_{n-m}\le y_m\le p_{n-m+1}$ , and by construction $y_m$ is the outcome at the extreme profile. Replace $\succeq_1^0$ by $\succeq_1$ : strategy-proofness forces the outcome to stay $x^*$ (moving down would let the $\succeq^0$ -agent manipulate; moving up would let the $\succeq_1$ -agent manipulate, since $p_1\le y_m$ ). Repeating for each $i\le n-m$ and symmetrically for $i>n-m$ gives $f(\succeq) = x^*$ .

Case 2: $y_m<x^*<y_{m+1}$ , so $x^* = p_{n-m}$ . It suffices to show $f(\succeq_1^0,\ldots,\succeq_{n-m-1}^0,\succeq_{n-m},\succeq_{n-m+1}^1,\ldots) = x^*$ , after which repeated strategy-proofness finishes as in Case 1.

Suppose instead the outcome is $x'<x^*$ (the case $x'>x^*$ is symmetric). Since reporting $\succeq_{n-m}^0$ would give $y_m$ , strategy-proofness gives $y_m\le x'<x^*$ . Let $O$ be the option set — the outcomes agent $n-m$ can obtain by varying his report with the others fixed. Then $x',y_m,y_{m+1}\in O$ , and strategy-proofness forces $x' = \max\{x\in O : x\le x^*\}$ . One shows $x'' \equiv\inf\{x\in O : x\ge x^*\}$ is attained, so $x''>x^*$ and $O\cap(x',x'')=\emptyset$ .

Now take symmetric preferences $\succeq^L,\succeq^H$ with peaks just below and just above $(x'+x'')/2$ . Strategy-proofness gives outcome $x''$ under $\succeq^H$ , and repeated application shows this persists when all the $\succeq^0$ ‘s become $\succeq^L$ . But Pareto-optimality (the earlier lemma) then forces the outcome under $\succeq^L_{n-m}$ to be at least $p^L$ , hence $x''$ — while a separate chain of strategy-proofness arguments forces it into $[x',x''-2\varepsilon]$ . Contradiction.

∎

IntuitionThe $y_m$ as degrees of compromise

They are the rule’s compromise when agents are extremists. If $m$ agents want 1 and $n-m$ want 0, a true median rule picks whichever extreme has more peaks; these rules may instead pick an intermediate $y_m$ . The degree of compromise can depend on how divided opinion is (the size of $m$ ).

DefinitionGeneralized median voter scheme

$f$ is a g.m.v.s. if there are $2^n$ points $\{\alpha_S\}_{S\subseteq N}$ with

$S\subseteq T\implies\alpha_S\le\alpha_T$ ,
$\alpha_\emptyset = 0$ , $\alpha_N = 1$ , and
$f(\succeq) = \max_{S\subseteq N}\min\{\alpha_S,\ p_i : i\in S\}$ .

Two remarks. Condition (1) is redundant — parameters failing it still define a strategy-proof rule, just one expressible by other parameters satisfying it. Condition (2) merely guarantees ontoness; parameters failing it give a strategy-proof rule with range $[\alpha_\emptyset,\alpha_N]$ .

ExampleReading off the power of coalitions

If every agent in $S$ has peak 1 and the rest peak 0, the rule chooses $\alpha_S$ — so the $\alpha_S$ are a nonanonymous degree of compromise at extreme profiles.

Without anonymity some coalitions are more powerful. A large $\alpha_{\{3\}}$ means more instances where agent 3’s peak is a candidate outcome; a small $\alpha_{\{1\}}$ means more instances where agent 1 has no impact (whenever $p_1>\alpha_{\{1\}}$ ).

TheoremFull characterization

$f$ is strategy-proof and onto iff it is a generalized median voter scheme. (Proof omitted; it has much in common with the anonymous case.)

ExampleLabor for a public good

$n$ agents share a machine requiring the simultaneous labor of all of them. They jointly decide the number of hours $\ell$ ; after $\ell$ hours the machine outputs $y = Y(\ell)$ units of a public good, with $Y$ increasing, strictly concave, $Y(0)=0$ . Agent $i$ has utility $u_i(\ell,y)$ increasing in $y$ , decreasing in $\ell$ , and quasi-concave.

Since outcomes lie on the graph of $Y$ , and given the assumptions, agents have single-peaked preferences over this consumption space — so any strategy-proof onto rule is a g.m.v.s. operating along the graph of $Y$ .

NoteThree technicalities glossed over

The outcome space is not bounded (though bounding it is reasonable); one should verify the preference domain yields all the single-peaked preferences needed for the characterization (the proof used symmetric ones); and one should show a strategy-proof rule here is invariant to utility information away from the graph of $Y$ .

ImportantAdding individual rationality pins down a unique rule

$f$ is individually rational if every agent weakly prefers the outcome to walking away ( $\ell=0$ , $y=0$ ). Translated to $[0,1]$ : which g.m.v.s. has every agent weakly preferring the outcome to $x = 0$ ?

There is a unique such rule: choose the minimum peak — i.e., ask each agent their most preferred labor level and take the minimum.

The house allocation problem

DefinitionThe model

$N$ agents, each owning a unique house and having a strict preference ordering over all $n$ houses. Reallocate the houses appropriately. (A modern version replaces houses with kidneys.)

Why Gibbard–Satterthwaite does not apply: although any strict ordering over houses is permitted, preferences over allocations are restricted — an agent is indifferent between all allocations giving her the same house.

ImportantWhy the core is the right solution concept

A new feature: agents control the resources to be allocated. An allocation can therefore be subverted by a subset who break away and trade among themselves. So we focus on allocations invulnerable to opting out.

DefinitionBlocking coalitions and the core

Number each house by its owner, so the initial allocation is $a_i = i$ ; feasibility means $a_i\ne a_j$ for $i\ne j$ . For $S\subseteq N$ let $A(S)$ be the allocations achievable by $S$ trading among themselves alone.

$S$ is a blocking coalition for $a$ if there is $z\in A(S)$ with, for all $i\in S$ , either $z_i\succ_i a_i$ or $z_i = a_i$ , and strict for at least one. The core is the set of unblocked allocations.

(This is the natural modification of the transferable-utility core to a nontransferable-utility game.)

AlgorithmTop Trading Cycle Algorithm (TTCA)

Build a directed graph with one vertex per agent; if house $j$ is agent $i$ ‘s $k$ th choice, insert edge $i\to j$ coloured $k$ . (An edge $(i,i)$ is a loop.)

First identify all cycles and loops using only colour-1 edges; strictness of preferences implies these are node-disjoint. Let $N_1$ be their vertices. Each cycle $i_1\to i_2\to\cdots\to i_r$ implies swaps: give house $i_1$ to $i_r$ , house $i_r$ to $i_{r-1}$ , and so on. Delete all colour-1 edges and repeat with colour 2, giving $N_2$ , and so on.

TheoremThe core is a singleton

The core of the house allocation problem consists of exactly one matching — the one returned by TTCA.

ProofPeel off

N_1

, then

N_2

, and so on

Under TTCA each agent in $N_1$ receives his favourite house, so $N_1$ blocks any allocation not assigning them those houses — any core allocation must agree with TTCA on $N_1$ . Given that, each agent in $N_2$ receives his favourite house excluding those endowed by $N_1$ , so any core allocation must agree on $N_2$ too. Continuing for each $N_k$ shows at most one core allocation exists. (That the TTCA allocation is indeed unblocked is left to the reader.)

∎

TheoremTTC is strategy-proof

The direct mechanism associated with TTCA is strategy-proof.

ProofA misreporter cannot improve on his round

Let $a$ be the TTCA allocation at profile $\pi$ and suppose $j\in N_k$ misreports, giving $\pi'$ and $a'$ . Observe $a_i' = a_i$ for all $i\in\bigcup_{r=1}^{k-1}N_r$ , so $a_j'\in N\setminus\bigcup_{r<k}N_r$ . But TTCA chooses $a_j$ to be $j$ ‘s top-ranked choice from exactly that set — contradicting $a_j'\succ_j a_j$ .

∎

NoteTwo extensions, both fragile

Indifference. With weak preferences one distinguishes the core (blocking requires all members strictly better) from the strict core (weak blocking). With strict preferences the two coincide: given a weakly blocking $S$ , remove any member not strictly better — he must have kept his own house — and repeat. With indifference, the strict core can be empty, or non-unique; deciding emptiness is polynomial in $|N|$ .

Multiple goods per agent. Endow each agent with a home and a car. With sufficiently rich preferences over pairs the core can be empty — and it turns out the core can be empty even under severe restrictions, e.g. separable preferences, where one’s ranking over homes is independent of which car one has.

Stable matchings

DefinitionThe model

A set $M$ of men and $W$ of women, each with a strict preference ordering over the other side. A matching assigns each man to at most one woman and vice versa. Remaining single is accommodated by including a dummy partner for each agent, so we may assume $|M| = |W|$ .

A matching is unstable if there are $m,m'$ and $w,w'$ with $m$ matched to $w$ , $m'$ to $w'$ , and $w'\succ_m w$ and $m\succ_{w'}m'$ — the pair $(m,w')$ is blocking. A matching with no blocking pair is stable.

ExampleThree men, three women

$m_1$	$m_2$	$m_3$	$w_1$	$w_2$	$w_3$
$w_2$	$w_1$	$w_1$	$m_1$	$m_3$	$m_1$
$w_1$	$w_3$	$w_2$	$m_3$	$m_1$	$m_3$
$w_3$	$w_2$	$w_3$	$m_2$	$m_2$	$m_2$

$\{(m_1,w_1),(m_2,w_2),(m_3,w_3)\}$ is unstable — $(m_1,w_2)$ blocks. But $\{(m_1,w_1),(m_3,w_2),(m_2,w_3)\}$ is stable.

AlgorithmDeferred acceptance (male-proposal)

Each man proposes to his top choice. Each woman with at least two proposals keeps (tentatively) her top one and rejects the rest. Each rejected man proposes to his top choice among women who have not rejected him. Repeat until no man has a woman to propose to, or every woman has at most one proposal.

This terminates in a matching: no man is assigned more than one woman, and since each woman keeps only one proposal, no woman is assigned more than one man.

ExampleRunning it on the table above

Round 1: $m_1\to w_2$ , $m_2\to w_1$ , $m_3\to w_1$ . Only $w_1$ has two proposals; she ranks $m_3$ above $m_2$ , so she rejects $m_2$ . Round 2: $m_2\to w_3$ . Every woman now has one proposal. The result is $\{(m_1,w_2),(m_2,w_3),(m_3,w_1)\}$ — stable, and different from the one found earlier.

TheoremThe algorithm produces a stable matching

Suppose $(m_1,w_1)$ blocks, with $m_1$ matched to $w_2$ and $w_1$ to $m_2$ . Since $w_1\succ_{m_1}w_2$ , $m_1$ proposed to $w_1$ before $w_2$ ; since he was not matched to her, she must have received a proposal she ranked higher, and since the algorithm matched her to $m_2$ , $m_2\succ_{w_1}m_1$ — contradicting blocking.

DefinitionOptimality

$\mu$ is male-optimal if there is no stable $\nu$ with $\nu(m)\succeq_m\mu(m)$ for all $m$ and strict for at least one. Similarly female-optimal.

TheoremMale-proposal gives the male-optimal stable matching

Suppose not; then some stable $\nu$ dominates $\mu$ for the men, so in the algorithm some man $j$ proposes to $\nu(j)$ before $\mu(j)$ and is rejected. Consider the first such rejection. Woman $\nu(j)$ rejected $j$ for some $i$ she prefers; since this is the first such rejection, $i$ ranks $\nu(j)$ above $\nu(i)$ . So $i\succ_{\nu(j)}j$ and $\nu(j)\succ_i\nu(i)$ — $\nu$ is not stable, a contradiction.

ImportantNo matching is optimal for both sides

Running the algorithm with the women proposing also yields a stable matching, generally a different one. In the example, at least one woman is strictly better off under the female-optimal matching and none worse off — and symmetrically for the men. There is no matching optimal for both sides.

TheoremThe core equals the set of stable matchings

Define $\mu'$ to dominate $\mu$ if there is $S\subseteq M\cup W$ with (i) $\mu'(m),\mu'(w)\in S$ for all $m,w\in S$ and (ii) $\mu'$ preferred by all of $S$ . Stability is the special case of $S$ a single couple, and the set of undominated matchings — the core — is exactly the set of stable matchings.

TheoremStrategy-proofness, for one side only

The direct mechanism associated with the male-propose algorithm is strategy-proof for the males.

ProofReduce to a top-ranked misreport, then show nobody is worse off

Suppose $m_1$ can misreport $\succ^*$ and obtain $\nu(m_1)\succ_{m_1}\mu(m_1)$ , where $\mu,\nu$ are the male-propose outcomes at $\pi$ and $\pi^1$ .

Step 1: assume the misreport ranks $\nu(m_1)$ first. Let $\bar\succ$ rank $\nu(m_1)$ first and $\pi^2 = (\bar\succ,\succ_{m_2},\ldots)$ . $\nu$ is stable w.r.t. $\pi^2$ : any blocking pair cannot involve $m_1$ (he gets his top choice), and the others’ preferences are unchanged, so it would block under $\pi^1$ too. Since the male-propose matching $\lambda$ for $\pi^2$ is male optimal, $\lambda(m_1) = \nu(m_1)$ .

Step 2: show $B = \{m_j : \mu(m_j)\succ_{m_j}\nu(m_j)\}$ is empty. If not, each $m_j\in B$ is rejected by $\mu(m_j)$ during the run on $\pi^1$ ; consider the first such rejection, say of $m_j$ . Then $\mu(m_j)$ has a proposal from some $m_k$ with $m_k\succ_{\mu(m_j)}m_j$ , and since $m_k$ was not matched to $\mu(m_j)$ under $\mu$ , $\mu(m_k)\succ_{m_k}\mu(m_j)$ — so $m_k\in B$ , else $\mu(m_j)\succeq_{m_k}\nu(m_k)\succeq_{m_k}\mu(m_k)\succ_{m_k}\mu(m_j)$ , a contradiction. But then $m_k$ must have been rejected by $\mu(m_k)$ before $m_j$ was rejected, contradicting the choice of $m_j$ .

Since $B=\emptyset$ , all men are no worse off under $\nu$ , contradicting male optimality of $\mu$ .

∎

WarningNot strategy-proof for the other side

In the example, the male-propose algorithm gives $\{(m_1,w_2),(m_2,w_3),(m_3,w_1)\}$ and $w_1$ gets her second choice. Had she rejected $m_3$ instead of $m_2$ , then $m_3\to w_2$ , who prefers $m_3$ to $m_1$ and rejects $m_1$ , who then proposes to $w_1$ — whom she prefers to $m_2$ . She ends up with her first choice by lying.

IntuitionThe analogy with Walrasian equilibrium

Walrasian equilibria exist and are solutions of a fixed point problem; where computable, it is because the equilibrium set is described by convex inequalities. The same holds here: stable matchings are the fixed points of a nondecreasing function on a lattice, and they are also the solutions of a system of linear inequalities. Both formulations follow.

Lattice formulation

DefinitionSemimatchings and the partial order

A male semimatching assigns each man at most one woman (but a woman may be assigned to more than one man); similarly female. A semimatching is a pair of these. Write $\mu(m) = m$ if $m$ is unassigned.

$\mu\preceq\nu$ if all men are weakly better off under $\mu$ and all women weakly worse off. The join $\mu\vee\nu$ takes, for each man, whichever of $\mu(m),\nu(m)$ he prefers, and for each woman whichever she likes less; the meet reverses both. With these, the semimatchings form a compact lattice.

FormulaThe map whose fixed point we seek

$f(\mu)(m)$ is $m$ ‘s most preferred woman from $\{w : m\succ_w\mu(w),\ m\ne\mu(w)\}$ , or $m$ himself if that set is empty; and symmetrically $f(\mu)(w)$ .

TheoremExistence via Tarski

There is a semimatching with $f(\mu) = \mu$ , and it is a stable matching.

ProofMonotonicity, then verify the fixed point is a stable matching

$f$ is nondecreasing. If $\mu\preceq\nu$ then the women are worse off under $\mu$ , so $\{w : m\succ_w\nu(w)\}\subseteq\{w : m\succ_w\mu(w)\}$ , giving $f(\mu)(m)\succeq_m f(\nu)(m)$ ; symmetrically for women. Tarski’s theorem then gives a fixed point $\mu$ .

$\mu$ is a matching. Suppose $\mu(m_1) = \mu(m_2) = w^*$ . Since $f(\mu)=\mu$ , $w^*$ is the top choice of both $m_1$ and $m_2$ in their respective sets, so $\mu(w^*) = m_3$ with $m_1,m_2\succ_{w^*}m_3$ . But $m_3 = f(\mu)(w^*)$ is $w^*$ ‘s top choice in $\{m : w^*\succ_m\mu(m),\ \mu(m)\ne w^*\}$ , a set containing $m_1,m_2$ — contradiction.

$\mu$ is stable. If $(m^*,w^*)$ blocks, with $w' = \mu(m^*)$ , then $w^*\succ_{m^*}w'$ . But $w' = f(\mu)(m^*)$ is $m^*$ ‘s top choice in a set containing $w^*$ — contradiction.

∎

Linear programming formulation

FormulaThe stable matching polytope

With $x_{mw} = 1$ iff $m$ is matched to $w$ :

$\sum_{w\in W}x_{mw} = 1\ \ \forall m, \qquad \sum_{m\in M}x_{mw} = 1\ \ \forall w$ $\sum_{j\prec_m w}x_{mj} + \sum_{i\prec_w m}x_{iw} + x_{mw}\ \le\ 1\ \ \forall m,w, \qquad x_{mw}\ge0$

IntuitionWhat the third constraint says

If $\sum_{j\prec_m w}x_{mj} = 1$ and $\sum_{i\prec_w m}x_{iw} = 1$ , then $m$ is matched to a woman he ranks below $w$ and $w$ to a man she ranks below $m$ — i.e. $(m,w)$ is a blocking pair. The constraint forbids exactly this.

TheoremIntegrality

$P$ is the convex hull of all stable matchings.

Extensions

NoteThree directions, with differing robustness

Indifference. Male- and female-optimal stable matchings need not exist, so the optimality theorem fails; the other theorems continue to hold.

Many-to-one. The college admissions market: each student attends one college, each college admits many, so colleges have preferences over subsets. Without restrictions a stable matching need not exist. One restriction under which everything carries over unchanged is the quota model: a strict ordering over students plus a quota $r$ , where between two size- $r$ sets differing in one student, the college prefers the one with the more preferred student.

Nonbipartite — the stable roommates problem. Partition $|N|$ (even) individuals into pairs, each with strict preferences over the others. Stable matchings need not exist:

1	2	3	4
2	3	1	1
3	1	2	2
4	4	4	3

Pairing 1 with 4 is blocked by $(1,2)$ ; 2 with 4 by $(2,3)$ ; 3 with 4 by $(3,1)$ . An $O(|N|^2)$ algorithm decides existence, and there is an associated system of linear inequalities feasible exactly when a solution exists.

Future directions

NoteMultiple locations on a graph

For the single-peaked model: choose multiple locations on an interval or more general graph, when each agent’s preference depends only on the closest one. When downloading files one cares only about the nearest mirror. If a planner elicits preferences to place $k$ mirrors on a network, how can this be done strategy-proofly?

NoteDynamic matching and kidney exchange

Both the house allocation and stable matching models are static, yet many resembling environments are dynamic. Kidney patients used to wait in a queue for a compatible organ; more recently exchange systems let patients “swap” incompatible but willing donors. (Alice needs a kidney and her friend Bob is willing but incompatible; Carmina and Dijen likewise. If Alice matches Dijen and Carmina matches Bob, a swap can be arranged.) Static versions have been analyzed; if donors and recipients arrive dynamically, how should swaps be arranged?

Quick reference

Object	Statement
Condorcet	majority can cycle: $a\succ b\succ c\succ a$
Arrow	unanimity $+$ IIA $+$ $
Incentive compatible $\iff$ monotone	a changed choice must reflect a switched pairwise preference
Gibbard–Satterthwaite	incentive compatible $+$ onto $+$ $
Quasilinear utility	$u_i = v_i(a) + m$
Vickrey	highest bidder wins, pays the second highest bid
VCG	$f$ maximizes $\sum_iv_i$ ; $p_i = h_i(v_{-i}) - \sum_{j\ne i}v_j(f(v))$
Clarke pivot	$h_i = \max_b\sum_{j\ne i}v_j(b)$ — internalizes externalities; gives IR and no positive transfers
Revelation principle	any dominant-strategy (or ex-post) implementation $\Rightarrow$ an incentive compatible one, same payments
Direct characterization	payment depends only on the alternative; the mechanism optimizes for each player
WMON	$v_i(a)-v_i(b)\ge v_i'(a)-v_i'(b)$ ; necessary always, sufficient on convex domains
Roberts	unrestricted domains, $
Single parameter	incentive compatible $\iff$ monotone $+$ winners pay the critical value
Uniqueness of prices	payments determined up to $h_i(v_{-i})$ , on connected domains
Randomized, single parameter	$w_i$ monotone and $p_i = v_iw(v_i) - \int_{v^0}^{v_i}w(t)dt$
First price, uniform $[0,1]$	equilibrium $x(a) = a/2$
Revenue equivalence	same social choice $+$ one matching type $\Rightarrow$ same expected revenue
Single-peaked, anonymous	median of the $n$ peaks and $n-1$ phantom points $y_m$
Single-peaked, general	generalized median voter schemes, parameters $\{\alpha_S\}$
Public good labor $+$ IR	the minimum peak rule, uniquely
House allocation	core is the unique TTCA allocation; TTC is strategy-proof
Stable matching	deferred acceptance gives a stable, male-optimal matching; core $=$ stable matchings
Matching, strategy-proofness	holds for the proposing side only
Matching, alternative views	fixed points of a monotone map on a lattice; integral LP polytope

Facts to keep to hand:

Gibbard–Satterthwaite is the pivot of the whole subject: money and restricted domains are the two escape routes, and this note is organized around them.
VCG works because the payment makes each player’s utility equal the total social welfare, so his interest and the designer’s coincide. Everything else about $h_i$ is strategically irrelevant.
The allocation rule determines the payments, twice over: exactly up to $h_i(v_{-i})$ in dominant strategies, and in expectation up to a constant in the Bayesian setting. So raising revenue requires changing the allocation.
Bilateral trade must be subsidized and public projects cannot recover their cost — both are corollaries of that uniqueness, not accidents of the Clarke rule.
Single-parameter domains are where most algorithmic mechanism design lives, because monotonicity plus critical-value pricing is checkable and leaves room for non-affine objectives such as egalitarian welfare.
Without money, every positive result comes from a domain restriction that defeats the Gibbard–Satterthwaite construction: single-peakedness, indifference among allocations giving the same house, or indifference among matchings giving the same partner.
Both matching results are one-sided: deferred acceptance is optimal and strategy-proof for the proposing side and manipulable by the other. No two-sided optimum exists.

References

Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory — chapters 9 (Nisan) and 10 (Schummer & Vohra)
Mas-Colell, Whinston & Green, Microeconomic Theory; Krishna, Auction Theory; Roth & Sotomayor, Two-Sided Matching

Related

Introduction to Mechanism Design

Motivation: economics with an engineering perspective

Condorcet’s paradox

Arrow’s theorem

The Gibbard–Satterthwaite theorem

Mechanisms with money

Vickrey’s second price auction

Incentive compatible mechanisms and VCG

The Clarke pivot rule

Examples

Implementation in dominant strategies

The revelation principle

Characterizing incentive compatible mechanisms

Direct characterization

Weak monotonicity

Roberts’ theorem: unrestricted domains

Single-parameter domains

Uniqueness of prices

Randomized mechanisms

Bayesian–Nash implementation

First price auction

Revenue equivalence

Further models

Escaping without money: restricted domains

Single-peaked preferences over policies

The rules

The house allocation problem

Stable matchings

Lattice formulation

Linear programming formulation

Extensions

Future directions

Quick reference

References

Mentioned in

Related

Motivation: economics with an engineering perspective

Social choice, and two impossibility theorems

Condorcet’s paradox

Arrow’s theorem

The Gibbard–Satterthwaite theorem

Mechanisms with money

Vickrey’s second price auction

Incentive compatible mechanisms and VCG

The Clarke pivot rule

Examples

Implementation in dominant strategies

The revelation principle

Characterizing incentive compatible mechanisms

Direct characterization

Weak monotonicity

Roberts’ theorem: unrestricted domains

Single-parameter domains

Uniqueness of prices

Randomized mechanisms

Bayesian–Nash implementation

First price auction

Revenue equivalence

Further models

Escaping without money: restricted domains

Single-peaked preferences over policies

The rules

Application: public good cost sharing

The house allocation problem

Stable matchings

Lattice formulation

Linear programming formulation

Extensions

Future directions

Quick reference

References

Mentioned in