Skip to content

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_i X_i)=\mathbb E[\tau+\max_i\{X_i-\tau\}]\)

\(\leq\tau+\mathbb E[\max_i\{(X_i-\tau)^+\}]\), because \(x\leq x^+\)

\(\leq \tau+\mathbb E[\sum_{i=1}^n(X_i-\tau)^+]\), because 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:

  1. select threshold \(\tau\) s.t. \(\Pr[\max_i\varphi_i(v_i)^+\ge\tau]=\frac{1}{2}\)

  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:

  1. run the revenue-maximizing auction among n bidders.
  2. 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.

How to simulate auctions on computer

second-price auction with reserve

two bidder drawing values from the uniform distribution in \([a,b]\).

reserve price of \(R\).

Data: revenue is lowest bid or reserve \(R\) or 0.

column A: bidder 1's bid

column B: bidder 2's bid

column C: revenue

let \(a=157,b=280,R=200\)

revenue=max(R,min(a,b)) if max(a,b)>=R else 0