Border's theorem explained
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]
Preliminaries
Auctions
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
for each bidder
, in which each
represents a possible type (valuation) for bidder
to have,
denotes a
σ-algebra on
, and
a prior and common knowledge probability distribution on
, which assigns the probability
that a bidder
is of type
. Finally, we define
as the set of type profiles, and
\boldsymbol{T}-i=\prodjTi
the set of profiles
t-i=(t1,...,ti-1,ti+1,...,tN)
.
Bidders simultaneously report their valuation of the good, and an auction assigns a probability that they will receive it. In this setting, an auction is thus a function
q:\boldsymbol{T} → [0,1]N
satisfying, for every type profile
where
is the
-th component of
. Intuitively, this only means that the probability that some bidder will receive the good is no greater than 1.
Interim allocation rules (reduced form auctions)
From the point of view of each bidder
, every auction
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
given that bidder
is of type
. We refer to such probabilites
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.
The function
\boldsymbolQ:\boldsymbol{T} → [0,1]N
defined by
\boldsymbol{Q}(t)=(Q1(t1),...,QN(tN))
is often referred to as a
reduced form auction. Working with reduced form auctions is often much more analytically tractable for revenue maximization.
Implementability
Taken on its own, an allocation rule
is called
implementable if there exists an auction
such that
for every bidder
and type
.
Statement
Border proved two main versions of the theorem, with different restrictions on the auction environment.
i.i.d environment
The auction environment is i.i.d if the probability spaces
are the same for every bidder
, and types
are independent. In this case, one only needs to consider symmetric auctions, and thus
also becomes the same for every
. Border's theorem in this setting thus states:
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
N\intAQ(t)dλ(t)\leq1-λ(Ac)N
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.
Finite sets of types
If all the sets
are finite, the restriction to the i.i.d case can be dropped. In the more general environment developed above, Border thus proved:
[5] Proposition: An interim allocation rule
\boldsymbolQ:\boldsymbolT → [0,1]N
is implementable by an auction if and only if for each measurable sets of types
A1\inlT1,A2\inlT2,...,AN\inlTN
, one has the inequality
Qi(ti)dλi(ti)\leq1-
\left(1-
λi(ti)\right)
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
with type
, and the left-hand side represents the probability that
there exists some bidder
with type
. Once again, the strength of the result comes from it being sufficient to characterize implementable interim allocation rules.
Notes and References
- Border . Kim C. . Implementation of Reduced Form Auctions: A Geometric Approach . Econometrica . 1991 . 59 . 4 . 1175–1187 . 10.2307/2938181 . 2938181 . 3 April 2021 . 0012-9682 . Kim Border.
- Matthews . Steven . On the Implementability of Reduced Form Auctions . Econometrica . 1984 . 52 . 6 . 1519–1522. 10.2307/1913517. 10419/220920 . free .
- Maskin . Eric . Riley . John . Eric Maskin . Optimal Auctions with Risk Averse Buyers . Econometrica . 1984 . 52 . 6 . 1473–1518 . 10.2307/1913516.
- Border . Kim . Kim Border . Reduced form auctions revisited . Economic Theory . 2007 . 31 . 1 . 167–181 . 10.1007/s00199-006-0080-z.
- 1 Gopalan. Parikshit. Nisan. Noam . Roughgarden . Tim . Noam Nisan . Tim Roughgarden. 2015. Public projects, Boolean functions and the borders of Border's theorem. 1504.07687. cs.GT.
