Border's theorem
Border's theorem
In auction-theory and mechanism-design, Border's theorem gives a necessary and sufficient condition for interim allocation rules (or reduced form auctions) to be implementable via an auction.
It was first proven by Kim Border in 1991, expanding on work from Steven Matthews, eric-maskin and John Riley. A similar version with different hypotheses was proven by Border in 2007.
Preliminaries ### Auctions Auctions are a mechanism designed to allocate an indivisible good among <math>N</math> bidders with private valuation for the good – that is, when the auctioneer has incomplete information on the bidders' true valuation and each bidder knows only their own valuation.
Formally, this uncertainty is represented by a family of probability spaces <math>(T_i, \mathcal T_i, \lambda_i)</math> for each bidder <math>i = 1, ..., N</math>, in which each <math>t_i \in T_i</math> represents a possible type (valuation) for bidder <math>i</math> to have, <math>\mathcal T_i</math> denotes a σ-algebra on <math>T_i</math>, and <math>\lambda_i</math> a prior and common knowledge probability distribution on <math>T_i</math>, which assigns the probability <math>\lambda_i (t_i)</math> that a bidder <math>i</math> is of type <math>t_i</math>. Finally, we define <math>\boldsymbol{T} = \prod_{i=1}^N T_i</math> as the set of type profiles, and <math>\boldsymbol{T}_{-i} = \prod_{j \neq i} T_i </math> the set of profiles <math>t_{-i} = (t_1, ..., t_{i-1}, t_{i+1}, ..., t_N)</math>.
Bidders simultaneously report their valuation of the good{{r|g=nb|r=More generally, bidders could report any bid, not necessarily their true valuation. But we can, without loss of generality, concentrate on direct-revelation mechanisms and let the payment functions restrict the auction's incentive compatibility constraints .
- Proposition:** An interim allocation rule <math>\boldsymbol Q : \boldsymbol T \rightarrow [0,1]^N</math> is implementable by an auction if and only if for each measurable sets of types <math>A_1 \in \mathcal T_1, A_2 \in \mathcal T_2, ..., A_N \in \mathcal T_N</math>, one has the inequality
:<math>\sum_{i=1}^N \int_{A_i} Q_i(t_i) d \lambda_i (t_i) \leq 1 - \prod_{i=1}^N \left(1 - \sum_{t_i \in A_i} \lambda_i(t_i)\right)</math>
The intuition of the i.i.d case remains: the left-hand side represents the probability that the winner of the auction is some bidder <math>i</math> with type <math>t_i \in A_i</math>, and the right-hand side represents the probability that there exists some bidder <math>i</math> with type <math>t_i \in A_i</math>. Once again, the strength of the result comes from it being sufficient to characterize implementable interim allocation rules.