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,[1] expanding on work from Steven Matthews,[2] Eric Maskin and John Riley.
[3] A similar version with different hypotheses was proven by Border in 2007.
[4] Auctions are a mechanism designed to allocate an indivisible good among
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
represents a possible type (valuation) for bidder
a prior and common knowledge probability distribution on
Bidders simultaneously report their valuation of the good[nb 1], and an auction assigns a probability that they will receive it.
Intuitively, this only means that the probability that some bidder will receive the good is no greater than 1.
induces some expected probability that they will win the good given their type, which we can compute as where
is conditional probability of other bidders having profile type
as interim allocation rules, as they give the probability of winning the auction in the interim period: after each player knowing their own type, but before the knowing the type of other bidders.
is often referred to as a reduced form auction.
Working with reduced form auctions is often much more analytically tractable for revenue maximization.
is called implementable if there exists an auction
Border proved two main versions of the theorem, with different restrictions on the auction environment.
[1][4] The auction environment is i.i.d if the probability spaces
In this case, one only needs to consider symmetric auctions[nb 2],[3] and thus
Border's theorem in this setting thus states:[1] Proposition: An interim allocation rule
is implementable by a symmetric auction if and only if for each measurable set of types
, one has the inequality Intuitively, the right-hand side represents the probability that the winner of the auction is of some type
, and the left-hand side represents the probability that there exists some bidder with type
The fact that the inequality is necessary for implementability is intuitive; it being sufficient means that this inequality fully characterizes implementable auctions, and represents the strength of the theorem.
are finite, the restriction to the i.i.d case can be dropped.
In the more general environment developed above, Border thus proved:[4][5] Proposition: An interim allocation rule
is implementable by an auction if and only if for each measurable sets of types
, one has the inequality The intuition of the i.i.d case remains: the right-hand side represents the probability that the winner of the auction is some bidder
, and the left-hand side represents the probability that there exists some bidder
Once again, the strength of the result comes from it being sufficient to characterize implementable interim allocation rules.