Mechanism design

Mechanism design chooses allocation and payment rules while accounting for how agents' information and incentives affect their reports. Social choice theory studies collective choice from preferences, while auction design also uses monetary transfers.

Dependence of a participant's utility on assignments made to other participants, beyond the identity of that participant's own assigned object. In room allocation with friendship externalities, the same room can become more valuable when a friend receives an adjacent room. An early participant in a sequential allocation must therefore anticipate later choices.

An allocation procedure using a fixed priority order: each participant in turn selects one remaining object, which is permanently assigned to them. For participants whose utilities depend only on their own assigned objects, strict rankings give a unique best available choice and the resulting allocation is Pareto optimal. If a proposed Pareto improvement changes an assignment, its earliest changed participant loses their unique best available object. With ties or allocation externalities, that argument requires additional assumptions.

Assign distinct rooms along a hallway to participants. A participant's utility is their own room value plus a positive bonus if their designated friend receives a physically adjacent room; participants without friends receive only their room value. When friendships form disjoint pairs, consecutive choosing slots allow each pair to settle its own adjacency before later participants act. Consecutive slots in serial dictatorship do not themselves require adjacent allocated rooms.

Suppose each participant has at most one mutual friend, each friendship pair chooses consecutively, room values lie in $[0,1]$ and are distinct for each participant, and each friendship bonus exceeds $1$. Then every subgame perfect equilibrium outcome of serial dictatorship is Pareto optimal.

For a friend pair, if any remaining adjacent room pair exists, the leader chooses their uniquely best room having an available neighbor; the follower chooses their uniquely best available neighbor. Adjacency dominates every possible difference in own-room value for both friends. If no adjacent room pair remains, neither friend can obtain a bonus and each chooses their unique best available room. A participant without a friend also chooses their unique best available room.

For the proof, compare a purported Pareto improvement block by block, where a block is a single participant without a friend or one consecutive friendship pair. Earlier fixed blocks leave the same rooms available. A block receiving adjacency cannot lose it in a weak improvement. Its leader must retain the uniquely best eligible room, and its follower must retain the uniquely best neighboring room. Without available adjacency, both rooms are fixed by strict own-room rankings. Mathematical induction fixes every assignment, excluding a strict improvement.

The expectation of the seller's total receipts over the buyers' valuation types and any randomization in the sales mechanism. In an auction it is the sum of the bidders' expected payments; with a posted price it is price times sale probability. It does not subtract selling costs or the seller's opportunity cost of retaining the item, so it is revenue rather than profit.

A seller commits to a fixed price and sells if at least one buyer accepts. With two independent valuations having common cumulative distribution $F$, the sale probability is $1-F(p{)}^2$ and expected revenue is $p(1-F(p{)}^2)$. The winner's selection among multiple willing buyers does not affect this revenue.

A mechanism specifies participants' available messages, an allocation rule, and any payment rule. Mechanism design chooses these rules to achieve an objective while respecting participants' incentive compatibility and individual rationality.

In a single-parameter mechanism, player $i$ has one private scalar value $v_i$, receives an allocation amount $x_i$, and has quasilinear utility $v_i{x}_i-p_i$. The allocation-payment relation is governed by incentive compatibility and the interim payment identity.

For an absolutely continuous valuation distribution with density $f(v)>0$, its virtual valuation is $v-(1-F(v))/f(v)$. The virtual-surplus revenue identity converts expected incentive-compatible payments into expected allocations weighted by virtual valuations. A regular prior makes this quantity nondecreasing.

Virtual surplus weights allocation amounts by the corresponding virtual valuations. Under the hypotheses of the virtual-surplus revenue identity, maximizing it subject to implementability and feasibility yields a revenue-optimal mechanism when lowest-type utilities can be normalized to zero.

For an independent private values model, let $X_i(v)$ and $P_i(v)$ be interim allocation and payment. The interim payment identity gives $P_i(v)=v{X}_i(v)-U_i({\underline{v}}_i)-{\int }_{{\underline{v}}_i}^v{X}_i(t)dt$. Applying Fubini's theorem to reverse the order of integration yields $\mathbb{E}{\int }_{{\underline{v}}_i}^{V_i}{X}_i(t)dt=\int X_i(t)(1-F_i(t))dt$. Subtracting this term from $\int v{X}_i(v)f_i(v)dv$ proves the identity. Interim individual rationality bounds the lowest-type utilities below by zero.

In a public-project single-parameter mechanism, all players receive the same binary allocation. For independent regular priors and voluntary participation with zero outside utility, maximizing virtual surplus means providing the project exactly when ${\sum }_i{\varphi }_i(v_i)\ge 0$. The allocation is monotone in each value, so critical-value payments implement it with dominant-strategy incentive compatibility and ex post individual rationality. For independent uniform values on $[0,1]$, the condition is ${\sum }_i{v}_i\ge n/2$, with winning payment $\max \{0,n/2-{\sum }_{j\ne i}{v}_j\}$.

A valuation distribution is regular when its virtual valuation is a nondecreasing function of value. This is an auction-theory condition, not the unrelated regularity notions used elsewhere in mathematics.

A direct revelation mechanism asks agents to report their types directly, then computes allocation and payments from those reports. Being direct does not itself imply strategyproofness; the allocation and payment rules must supply the incentive guarantee.

An equilibrium outcome of a mechanism can be reproduced by asking for types and then sending the messages prescribed by the original equilibrium strategies. Truthful reports are then a Bayesian Nash equilibrium: a profitable false report would induce a profitable original deviation. This reduces optimization over indirect mechanisms to direct revelation mechanisms with Bayesian incentive compatibility, under the same information and participation assumptions.

The pivot form chooses a reported-welfare-maximizing allocation and charges each agent the maximum welfare achievable by the others without that agent minus the others' welfare in the chosen allocation. With quasilinear utility, truthful reporting is a dominant strategy because the first term in the payment depends only on other reports. For two identical items and three unit-demand bidders, each winner pays the lowest reported valuation and the loser pays zero.

Incentive compatibility makes the prescribed truthful or type-dependent strategy optimal under the specified solution concept. Dominant-strategy incentive compatibility holds for every other report profile; Bayesian incentive compatibility compares expected utilities over the other agents' types.

Dominant-strategy incentive compatibility means truthful reporting maximizes a player's utility for every fixed profile of the other reports. It is the monetary-mechanism version of strategyproofness and implies Bayesian incentive compatibility under any independent prior.

A monotone binary allocation is made truthful by charging its winning threshold, truncated below at the lowest allowed value, and charging zero to losers. The displayed integral formula sets the lowest type's utility to zero. To check it, hold the other reports fixed: a type above the threshold benefits from winning at that price, while a type below it benefits from losing. At a threshold, either deterministic tie choice is compatible with indifference.

Truthful reporting is Bayesian incentive compatible when every type maximizes its expected utility over the other players' types by reporting truthfully. In an independent private values model, the displayed inequality uses the same interim allocation and payment functions for every possible true type.

Individual rationality means participation yields at least the outside-option utility, normalized here to zero. A risk-neutral zero-value bidder with nonnegative payments and no positive-valued allocation must have zero expected payment and utility if participation is individually rational.

Ex post individual rationality requires nonnegative participation utility at every realized profile of types. A truthful threshold allocation with its critical-value payment satisfies this condition for nonnegative valuations.

Interim individual rationality requires a nonnegative expected participation utility for each private type, averaging over the other types with the player's conditional beliefs. It differs from requiring nonnegative utility at each realized profile, which is ex post individual rationality.

An auction allocates goods using submitted messages and a specified payment rule. Private-value auctions model each bidder's valuation as its own private information. Equilibrium bids depend on the allocation and payment rules, not only on valuations.

A single-item auction in which the highest bidder wins and pays the highest competing bid. Under private values and quasilinear utility, bidding one's valuation is a dominant strategy: if the competing maximum is below one's value, winning at that price is best; if it is above one's value, losing is best; equality gives zero utility either way. Thus truthful bidding is an ex post Nash equilibrium.

The highest bidder wins a single item but pays the lowest submitted bid, while losers pay nothing. This differs from a lowest unique bid auction. With at least two bidders using increasing strategies, the winning bidder pays the smallest opponent bid.

// Target: mathematical-optimization.bigb

For $n\ge 2$ risk-neutral bidders with independent uniform distributions on $[0,1]$, the lowest-price auction has a symmetric Bayesian Nash equilibrium $b(v)=(n-1)v$. A deviation bidding $(n-1)z$, with $0\le z\le 1$, wins with probability $z^{n-1}$ and has expected payment $(n-1)z^n/n$. Its expected profit is $v{z}^{n-1}-(n-1)z^n/n$, whose derivative is $(n-1)z^{n-2}(v-z)$, proving optimality at $z=v$. Bids above $n-1$ give the same outcome as $z=1$. The seller receives $(n-1)$ times the minimum of $n$ independent uniform valuations, with expected revenue $(n-1)/(n+1)$.

// Target: mathematical-optimization.bigb

A reserve price is the seller's minimum acceptable price. In an English auction it changes both the sale rule and the payment rule: the highest valuation must exceed the reserve and the winner pays at least the reserve. Mechanisms with different reserves generally have different allocation probabilities, so revenue equivalence need not equate their expected revenues.

In an ideal continuous-price auction with independent private values, bidders remain active up to their valuations. Without a reserve, the last remaining bidder wins at the second-highest valuation. With a reserve price $r$, there is no sale if every valuation is below $r$; otherwise the winner pays the larger of $r$ and the second-highest valuation. Strict versus weak inequalities at the reserve have no revenue effect for continuous valuation distributions. This payment rule is distinct from a first-price sealed-bid auction.

Each bidder chooses a permitted amount. The bidder with the smallest amount submitted by exactly one bidder wins and pays that amount; if no amount is unique, nobody wins. With object value $V$, the winner's payoff is $V$ minus their bid, and losers pay nothing. Unlike a first-price sealed-bid auction, repeated lowest bids can be disqualified.

For bids $1,2$ and $V>2$, write $p_i$ for player $i$'s probability of bidding $1$. The two expected payoffs are $(V-1)(1-p_j)(1-p_k)$ and $(V-2)p_j{p}_k$. Their unique symmetric equilibrium uses the displayed probability. Every permutation of $(1,0,t)$, $0\le t\le 1$, is also a Nash equilibrium: the mixed bidder is indifferent, while the two pure bidders weakly prefer their prescribed bids. There are no further equilibria. Three interior probabilities must all coincide, since subtracting two indifference equations gives a nonzero positive factor times their difference. Two interior probabilities with a pure opponent are impossible, and a single interior probability requires the other two bids to differ. Thus the nonsymmetric equilibria form six line segments with six pure endpoints, and their number is uncountable.

In a standard all-pay auction, every player pays its bid or effort cost, and the highest bid receives the prize. With a value $v_i$, unit effort cost, and winning probability $x_i(b)$, player $i$ has quasilinear utility $v_i{x}_i(b)-b_i$. Equal highest bids require an explicit tie rule.

For effective prizes $A_1\ge A_2>0$ and unit effort costs, equilibrium effort CDFs on $[0,A_2]$ are $G_1(b)=b/A_2$ and $G_2(b)=1-A_2/A_1+b/A_1$. The weaker player has an atom at zero. Incremental utilities are $A_1-A_2$ and zero, and winning probabilities are $1-A_2/(2A_1)$ and $A_2/(2A_1)$. Direct payoff indifference and exclusion of larger bids verify the Nash equilibrium. A further player with effective prize at most $A_2$ cannot profit by entering against these distributions.

Each bidder submits one private bid; the highest bidder wins and pays its own bid, while losers pay nothing. A multi-unit version can award one item to each of the highest bidders, each paying its own bid. In a monotone symmetric equilibrium, a bidder can imitate another type's bid when checking incentive constraints.

In a first-price sealed-bid auction with at least two bidders, continuous nonnegative bids, quasilinear utility and positive private value $v$, no bid is a dominant strategy. Against opponents all bidding zero, any positive bid can be lowered while still winning, increasing the payoff. Bid zero fails against an opposing bid $v/2$, since bidding $3v/4$ earns $v/4>0$. Nor does randomizing create a dominant strategy. Against all-zero opponents, a random bid has expected payoff strictly below $v$ unless it is identically zero and receives the item with certainty under the tie rule. In the strict case, a sufficiently small positive fixed bid earns more. In the exceptional case, the deviation against $v/2$ again improves the payoff. Finite expected utility is implicit; an expected payoff of negative infinity cannot dominate finite-payoff bids. The positive-value condition matters: a zero-value bidder weakly prefers bid zero.

For $n\ge 2$ risk-neutral bidders with independent uniform valuations on $[0,1]$, this rule is a symmetric Bayesian Nash equilibrium. If opponents use $\beta (v)=av$, a bid $b\in [0,a]$ has expected utility $(v-b)(b/a{)}^{n-1}$. Its derivative has the sign of $(n-1)v-nb$, so with $a=(n-1)/n$ the best bid is $av$. Bids above $a$ guarantee winning but only increase payment. The type-$v$ equilibrium utility is $v^n/n$.

For a risk-neutral single-parameter bidder with incentive-compatible type reports, interim utility satisfies $u^{\prime }(\theta )=G(\theta )$ wherever the winning probability is continuous. Consequently expected payment is determined by allocation probabilities and the utility of the lowest type. The common normalization $u(0)=0$ must be justified, not obtained from allocation alone.

Two auctions with the same interim allocation probabilities and the same lowest-type utilities have the same interim expected payments under the usual risk-neutral single-parameter incentive conditions. Equal realized payments are not required. This conclusion follows directly from the interim payment identity.

A private-value auction gives each bidder its own value for receiving an item; the value is determined by its own type rather than by another bidder's information. An independent private values model also assumes independence between types.

A bidder with unit demand values receiving one item but obtains no additional value from extra identical units. Selecting two winners means awarding one item to each of two bidders, not two units to one bidder.

This model assigns independent private valuation types to the bidders. Symmetry adds identical type distributions and bidder roles. These assumptions determine interim winning probabilities from the valuation distribution in a monotone symmetric equilibrium.

The independent private values model is symmetric when bidders have identical roles and draw their valuations independently from the same distribution. For revenue equivalence in the usual single-object setting, bidders additionally have risk neutrality and quasilinear utility. Under a strictly increasing symmetric equilibrium bidding rule, a type $v$ wins with probability $F(v{)}^{n-1}$.

// Target: mathematical-optimization.bigb

For two independent uniform valuations on $[0,1]$, optimal posted price revenue is $2/(3\sqrt{3})$, attained at $p=1/\sqrt{3}$. An English auction without reserve earns the expected minimum, $1/3$. With reserve $r\in [0,1]$, revenue is $r\mathrm{Pr}(\text{exactly one valuation exceeds }r)$ plus the expected smaller valuation when both exceed $r$, namely $1/3+r^2-4r^3/3$. It is maximized at $r=1/2$, giving $5/12$. Different reserve-dependent allocation probabilities explain why this differs from the no-reserve revenue without violating revenue equivalence.

A mechanism or social choice function is strategyproof if truthful reporting is a weakly dominant strategy: for every true type and every collection of other reports, no misreport yields strictly higher utility or a strictly preferred outcome. This is stronger than merely requiring truthful reports to form a Nash equilibrium.

If a strategyproof social choice function selects $a$, raising $a$ in one agent's order without moving any formerly lower alternative above it preserves the outcome. A different outcome would make one of the changes between the old and new reports a profitable deviation. Arbitrary changes among alternatives wholly above or wholly below $a$ are allowed.

With a finite set of at least three alternatives and unrestricted strict preference orders, every onto deterministic strategyproof social choice function is a dictatorship in social choice. Restricting to two alternatives or to a restricted preference domain removes essential hypotheses.

For an onto strategyproof rule on unrestricted strict preference orders, rank-raising monotonicity implies unanimity and respect for unanimous pairwise preference. Promote each alternative pair to the top two positions in all reports. The selected member depends only on each voter's comparison of that pair. These binary choices form a strict transitive social order: a directed three-cycle would contradict the rule's choice when that triple is placed above all other alternatives, because the chosen member must win both of its binary comparisons. The original outcome is the top of this order. This creates a social ordering with pairwise independence without presuming it as an axiom of the original choice rule.

For two voters and at least three alternatives, pairwise unanimity, pairwise independence and transitivity force the binary social ordering from strategyproof choice to follow one fixed voter. If voter one wins a conflict $a$ against $b$, use profiles $(a>b>c,b>c>a)$ and $(c>a>b,b>c>a)$ to show it also wins $a$ against $c$ and $c$ against $b$. Repeating this implication yields both directions of every pair. If the initial conflict instead follows voter two, exchange the roles. The social choice, being the top of that ordering, is a dictatorship in social choice. This proves the two-voter case of the Gibbard-Satterthwaite theorem.

For two agents and a strategyproof social choice function, if an alternative is selected when one agent ranks it first and the other ranks it last, it is selected whenever the first agent ranks it first, whatever the other agent reports. Changing the first agent's order preserves its attainable top choice; changing the second agent's order cannot offer it an improvement over a selected bottom alternative.

Social choice theory studies how individual preferences determine a collective decision. A social choice function selects one alternative from a preference profile; strategyproofness asks whether agents can benefit by misrepresenting their preferences.

A Condorcet winner defeats every other alternative by a strict majority in pairwise voting. It is unique when it exists. For an odd electorate with single-peaked preferences, the median peak is a Condorcet winner: alternatives on either side lose to the majority whose peaks lie at or beyond the median in the other direction. With an even electorate ties may prevent a strict winner.

A weak Condorcet winner is never defeated by a strict pairwise majority, allowing ties. For even electorates with single-peaked preferences, all alternatives between the two middle peaks have this property. A single-valued selection requires a tie convention; arbitrary tie selection is not automatically strategyproof.

A strict preference order is single-peaked on an axis when moving away from its most preferred alternative along either one side of the axis makes alternatives less preferred. Comparisons between opposite sides need not follow symmetric physical distance. A profile is single-peaked when all voters' orders share such an axis. This restricted domain admits the median voter rule, unlike the unrestricted-domain conclusion of the Gibbard-Satterthwaite theorem.

On a fixed common axis, select the median of reported peaks. For odd $n$ this is the unique Condorcet winner. For even $n$, a fixed lower-median or upper-median convention selects a weak Condorcet winner. Holding other peaks fixed, the attainable outcomes form an interval between two order statistics. Truthful reporting obtains the true peak if it is inside that interval, or its nearest interval endpoint otherwise, so no allowed report improves the outcome under single-peaked preferences.

A deterministic social choice function maps profiles of preference orders to single alternatives. Unrestricted domain permits every profile in ${\mathcal{R}}^n$; onto means every alternative lies in the range. A unanimous rule selects an alternative whenever every agent ranks it first.

With an odd number of agents and two alternatives, select the alternative ranked first by a strict majority. The rule is onto, strategyproof, and for at least three agents has no dictator in social choice. A pivotal agent already gets its preferred alternative by reporting truthfully; a nonpivotal agent cannot change the outcome alone.

A dictatorship always selects the top alternative of one fixed agent $d$. Other agents cannot alter the selection against that agent's preference. This is the social-choice meaning of dictatorship, rather than a political classification.

A dictator is the fixed agent whose top-ranked alternative is always selected by a dictatorship in social choice.