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.

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.

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.

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.

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 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 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.