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 $N$ 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 $(T_i,{𝒯}_i,{\lambda }_i)$ for each bidder $i=1,\mathrm{...},N$, in which each $t_i\in T_i$ represents a possible type (valuation) for bidder $i$ to have, ${𝒯}_i$ denotes a σ-algebra on $T_i$, and ${\lambda }_i$ a prior and common knowledge probability distribution on $T_i$, which assigns the probability ${\lambda }_i(t_i)$ that a bidder $i$ is of type $t_i$. Finally, we define $𝑻=\prod _{i=1}^N{T}_i$ as the set of type profiles, and ${𝑻}_{-i}=\prod _{j\ne i}{T}_i$ the set of profiles $t_{-i}=(t_1,\mathrm{...},t_{i-1},t_{i+1},\mathrm{...},t_N)$.

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:𝑻\to [0,1{]}^N$ satisfying, for every type profile $t\in 𝑻$

$\sum _{i=1}^N{q}_i(t)\le 1$

where $q_i$ is the $i$-th component of $q=(q_1,q_2,\mathrm{...},q_N)$. 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 $i$, every auction $q$ induces some expected probability that they will win the good given their type, which we can compute as

$Q_i(t_i)=\underset{T_{-i}}{\int }{q}_i(t)d{\lambda }_i(t_{-i}|t_i)$

where ${\lambda }_i(t_{-i}|t_i)$ is conditional probability of other bidders having profile type $t_{-i}$ given that bidder $i$ is of type $t_i$. We refer to such probabilites $Q_i$ 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 $𝑸:𝑻\to [0,1{]}^N$ defined by $𝑸(t)=(Q_1(t_1),\mathrm{...},Q_N(t_N))$ 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 $𝑸:T\to [0,1{]}^N$ is called implementable if there exists an auction $q:𝑻\to [0,1{]}^N$ such that

$Q_i(t_i)=\underset{T_{-i}}{\int }{q}_i(t)d{\lambda }_i(t_{-i}|t_i)$

for every bidder $i$ and type $t_i\in T_i$.

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 $(T_i,{𝒯}_i,{\lambda }_i)=(T,𝒯,\lambda )$ are the same for every bidder $i$, and types $t_i$ are independent. In this case, one only needs to consider symmetric auctions, and thus $Q_i=Q$ also becomes the same for every $i$. Border's theorem in this setting thus states:

Proposition: An interim allocation rule $Q:T\to [0,1]$ is implementable by a symmetric auction if and only if for each measurable set of types $A\in 𝒯$, one has the inequality

$N\underset{A}{\int }Q(t)d\lambda (t)\le 1-\lambda (A^c{)}^N$

Intuitively, the left-hand side represents the probability that the winner of the auction is of some type $t\in A$, and the right-hand side represents the probability that there exists some bidder with type $t\in A$. 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 $T_i$ are finite, the restriction to the i.i.d case can be dropped. In the more general environment developed above, Border thus proved:

Proposition: An interim allocation rule $𝑸:𝑻\to [0,1{]}^N$ is implementable by an auction if and only if for each measurable sets of types $A_1\in {𝒯}_1,A_2\in {𝒯}_2,\mathrm{...},A_N\in {𝒯}_N$, one has the inequality

$\sum _{i=1}^N\underset{A_i}{\int }{Q}_i(t_i)d{\lambda }_i(t_i)\le 1-\prod _{i=1}^N(1-\sum _{t_i\in A_i}{\lambda }_i(t_i))$

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 $i$ with type $t_i\in A_i$, and the right-hand side represents the probability that there exists some bidder $i$ with type $t_i\in A_i$. Once again, the strength of the result comes from it being sufficient to characterize implementable interim allocation rules.