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

Bidders simultaneously report their valuation of the good ^{[nb 1]} , and an auction assigns a probability that they will receive it. In this setting, an auction is thus a function ${\displaystyle q:{\boldsymbol {T}}\rightarrow [0,1]^{N}}$ satisfying, for every type profile ${\displaystyle t\in {\boldsymbol {T}}}$

${\displaystyle \sum _{i=1}^{N}q_{i}(t)\leq 1}$

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

${\displaystyle Q_{i}(t_{i})=\int _{T_{-i}}q_{i}(t)d\lambda _{i}(t_{-i}|t_{i})}$

where ${\displaystyle \lambda _{i}(t_{-i}|t_{i})}$ is conditional probability of other bidders having profile type ${\displaystyle t_{-i}}$ given that bidder ${\displaystyle i}$ is of type ${\displaystyle t_{i}}$. We refer to such probabilites ${\displaystyle 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 ${\displaystyle {\boldsymbol {Q}}:{\boldsymbol {T}}\rightarrow [0,1]^{N}}$ defined by ${\displaystyle {\boldsymbol {Q}}(t)=(Q_{1}(t_{1}),...,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. ^[3]

Implementability

Taken on its own, an allocation rule ${\displaystyle {\boldsymbol {Q}}:T\rightarrow [0,1]^{N}}$ is called implementable if there exists an auction ${\displaystyle q:{\boldsymbol {T}}\rightarrow [0,1]^{N}}$ such that

${\displaystyle Q_{i}(t_{i})=\int _{T_{-i}}q_{i}(t)d\lambda _{i}(t_{-i}|t_{i})}$

for every bidder ${\displaystyle i}$ and type ${\displaystyle t_{i}\in T_{i}}$.

Statement

Border proved two main versions of the theorem, with different restrictions on the auction environment. ^{[1] [4]}

i.i.d environment

The auction environment is i.i.d if the probability spaces ${\displaystyle (T_{i},{\mathcal {T}}_{i},\lambda _{i})=(T,{\mathcal {T}},\lambda )}$ are the same for every bidder ${\displaystyle i}$, and types ${\displaystyle t_{i}}$ are independent. In this case, one only needs to consider symmetric auctions ^{[nb 2]} , ^[3] and thus ${\displaystyle Q_{i}=Q}$ also becomes the same for every ${\displaystyle i}$. Border's theorem in this setting thus states: ^[1]

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

${\displaystyle N\int _{A}Q(t)d\lambda (t)\leq 1-\lambda (A^{c})^{N}}$

Intuitively, the right-hand side represents the probability that the winner of the auction is of some type ${\displaystyle t\in A}$, and the left-hand side represents the probability that there exists some bidder with type ${\displaystyle 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 ${\displaystyle 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: ^{[4] [5]}

Proposition: An interim allocation rule ${\displaystyle {\boldsymbol {Q}}:{\boldsymbol {T}}\rightarrow [0,1]^{N}}$ is implementable by an auction if and only if for each measurable sets of types ${\displaystyle A_{1}\in {\mathcal {T}}_{1},A_{2}\in {\mathcal {T}}_{2},...,A_{N}\in {\mathcal {T}}_{N}}$, one has the inequality

${\displaystyle \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)}$

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

Notes

1. 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 . ^[1]
2. An auction ${\displaystyle q}$ is symmetric if, for any permutation ${\displaystyle \pi }$ over ${\displaystyle \{1,...,N\}}$ and every bidder ${\displaystyle i}$, we have ${\displaystyle q_{i}(t)=q_{\pi ^{-1}(i)}(t_{\pi (1)},...,t_{\pi (N)})}$. Intuitively, this means that a bidder ${\displaystyle i}$'s identity does not matter, only their valuation ${\displaystyle t_{i}}$.

References

1. Border, Kim C. (1991). "Implementation of Reduced Form Auctions: A Geometric Approach". Econometrica. 59 (4): 1175–1187. doi:10.2307/2938181. ISSN   0012-9682. JSTOR   2938181 . Retrieved 3 April 2021.
2. Matthews, Steven (1984). "On the Implementability of Reduced Form Auctions" (PDF). Econometrica. 52 (6): 1519–1522. doi:10.2307/1913517. hdl: 10419/220920 . JSTOR   1913517.
3. Maskin, Eric; Riley, John (1984). "Optimal Auctions with Risk Averse Buyers". Econometrica. 52 (6): 1473–1518. doi:10.2307/1913516. JSTOR   1913516.
4. Border, Kim (2007). "Reduced form auctions revisited". Economic Theory. 31 (1): 167–181. doi:10.1007/s00199-006-0080-z.
5. 1 Gopalan, Parikshit; Nisan, Noam; Roughgarden, Tim (2015). "Public projects, Boolean functions and the borders of Border's theorem". arXiv: 1504.07687 [cs.GT].