Revenue-maximizing auction

Disadvantages

somehow complicated
require detailed information about the probability distributions of the valuations
much different than the format used in practice.

Review

allocation rule:

$\mathbf x(\mathbf v)=\arg\max_X\sum_i\varphi_i(v_i)\cdot x_i(\mathbf v)$ .

for profile $\mathbf v$ , $\varphi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}$ is the virtual valuation for probability distribution $F_i$ .

Single-item auction

potential buyers with independent valuations drawn form the same distribution $F$ .
optimal w. r. t. the revenue: second-price auction with reserve at value $\varphi^{-1}(0)$ .
basic advantage: simplicity
which we loose if the potential buyers have different distributions
e. g. the highest bidder may not be the one who gets the item

Prophet inequality

先知不等式（？）

A n-step game

game in n step: as step $i$ , we are given a non-negative award $X_i$ from a probability distribution $F_i$ .
the distribution $F_1,F_2,\cdots,F_n$ are known and independent.
whenever we see award $X_i$ , we can either accept and stop the game or reject and continue.
Risk accepting a reasonable award without loosing a higher one later.
The prophet inequality gives us a simple strategy that works very well!

Using Prophet inequality

use an appropriately selected threshold $\tau$ .
select the first award that exceeds the threshold.
obviously, the threshold strategy is suboptimal(why)

There exist a threshold, so that the expected award is at least $\frac{1}{2}\mathbb E_{X\sim F}[\max_iX_i]$

Analysis of a threshold strategy

先证明 $\mathbb E[\max_iX_i]\le Quantitiy$ ，再证 $\mathbb E[ALG]\ge\frac{1}{2}Quantity$ , 最后结合一下就可以证明先知不等式了。

\mathbb E(\max_iX_i)=\mathbb E[\tau+\max_i\{X_i-\tau\}]\\ \leq\tau+\mathbb E[\max_i\{(X_i-\tau)^+\}]\ \ \ (x\leq x^+)\\ \leq \tau+\mathbb E[\sum_{i=1}^n(X_i-\tau)^+]\ \ \ (max\ of\ non-negative\ val\ is\ at\ most\ their\ sum)

the algorithm:

ALG=\sum_{i=1}^n\mathbb E[X_i|X_i\gt\tau,X_j\lt\tau,\forall j\lt i]\cdot\Pr[X_i\ge\tau,X_j\lt\tau,\forall j\lt i]\\ =\tau\cdot\sum_{i=1}^n\Pr[X_i\ge\tau,X_j\lt\tau,\forall j\lt i]+\\ \sum_{i=1}^n\mathbb E[X_i-\tau|X_i\ge\tau,X_j\le\tau,\forall j\lt i]\cdot\Pr[X_i\ge\tau,X_j\lt\tau,\forall j\lt i]\\ =\tau\cdot\Pr[\max_iX_i\ge\tau]+\sum_{i=1}^n\mathbb E[X_i-\tau|X_i\ge\tau]\cdot\Pr[X_i\ge\tau]\cdot\Pr[X_j\lt\tau,\forall j\lt i]\\ \ge\tau\cdot\Pr[\max_iX_i\ge\tau]+\Pr[\max_iX_i\lt\tau]\cdot\sum_{i=1}^n\mathbb E[X_i-\tau|X_i\ge\tau]\cdot\Pr[X_i\ge\tau]\\ =\tau\cdot\Pr[\max_iX_i\ge\tau]+\Pr[\max_iX_i\lt\tau]\cdot\sum_{i=1}^n\mathbb E[(X_i-\tau)^+]\\ =\frac{1}{2}(\tau+\mathbb E[\sum_{i=1}^n(X_i-\tau)^+])\ge\frac{1}{2}\cdot\mathbb E[\max_iX_i]

Simple single-item auction

idea: use a virtual valuation threshold

allocation rule:

select threshold $\tau$ s.t. $\Pr[\max_i\varphi_i(v_i)^+\ge\tau]=\frac{1}{2}$
give the item to the potential buyer with $\varphi_i(v_i)\ge\tau$ and the highest bid
from prophet inequality, $\mathbb E_{v\sim F}[\sum_{i=1}^n\varphi_i(v_i)\cdot x_i(v)]\ge\frac{1}{2}\mathbb E_{v\sim F}[\max_i\varphi_i(v_i)^+]$

Prior-independent auctions

what if we don’t have information about valuations of the potential buyers?

Bulow & Klemperer’s theorem

increasing competition is more important than designing revenue-optimal auctions
the expected revenue of the revenue-maximizing auction with n bidders from F is at most the expected revenue of the second price auction with n+1 bidders from F.

proof

define the artificial auction among n+1 bidders from F as follows:

run the revenue-maximizing auction among n bidders.
If the item is not sold, give it to the (n+1)-th bidder

denote:

REV1: the revenue of the revenue-maximizing auction with n bidders.
REV2: the revenue of the artificial auction with n+1 bidders.
REV3: the revenue of the second-price auction with n+1 bidders.

by the definition of the artificial auction, we have $\mathbb E[REV1]\leq\mathbb E[REV2]$ .

Then we need to prove $\mathbb E[REV2]\leq\mathbb E[REV3]$ :

the artificial auction always sells the item. Then we need to prove the second-price auction has the highest expected revenue among all auctions that always sell the item:

An auction that always sells the item has $\sum_{i=1}^nx_i(v)=1$ , i.e. only one agent has $x_i(v)=1$ the others $x_i(v)=0$ . under this constraint, which auction can maximize $\sum_{i=1}^n\varphi(x_i)x_i(v)$ ? By regularity of F, this auction gives the item to the highest bidder. By Myerson’s Lemma, the only DSIC auction that has this property is the second-price auction.