This week

Revenue-maximizing DSIC auctions
completely different goal than social welfare maximization
average-case analysis

Review

Spectrum auction’s problem: VERY LOW REVENUE

many applications

makes sense even in cases where revenue maximization seems to be more important (e.g. keeping customers compared to competitors)

educational value: ideal auctions and ideal mechanisms always exist

Single item auction with a single potential buyer

revenue?

what other truthful auctions exist?

posted prices, take it or leave it offers

is it possible to maximize revenue without knowledge of private valuations?

for example, a fixed price of 10 work fine for valuations higher than 10 while it will be disastrous for smaller prices.

Revenue maximization

Average case analysis

single-parameter environment

Independent random variables representing valuations with distributions $F_1,F_2,\cdots,F_n$ with continuous probability density functions $f_1,f_2,\cdots,f_n$ , defined in $[0,+\infty)$

participant $i$ selects random valuation from distribution $F_i$ .

crucial assumption: the mechanism designer knows the distributions of valuations

F_i(z)=\Pr[v_i\le z]=\int_0^zf_i(x)\mathrm dx

the potential buyer has a random valuation, drawn from a known probability distribution $F$ .

Fixed price $r$

What is the best choice of $r$ ?

\mathbb E(Revenue)=r\times(1-F(r))

Two potential buyers in revenue maximization

assume $F$ is uniform distribution in $[0,1]$

what’s the revenue of the second-price auction?

i.e. smallest valuation among the two.

\mathbb E_{x,y\sim F}[\min\{x,y\}]=\int_0^1\int_0^1\min\{x,y\}f(y)\mathrm{d}yf(x)\mathrm{d}x\\ =\int_0^1[\int_0^xyf(y)\mathrm{d}y+\int_x^1xf(y)\mathrm{d}y]f(x)\mathrm{d}x\\ =\int_0^1[\int_0^xy\mathrm{d}y+x\int_x^1\mathrm{d}y]\mathrm{d}x\\ =\int_0^1(x-\frac{1}{2}x^2)\mathrm dx=\frac{1}{3}

the highest bid wins the item if it is higher than the reserve price $r$
pays the maximum between the lowest bid and $r$

what do we gain?

Better revenue in cases of very small lowest bid.

what do we loose?

The item is not always sold.

for revenue:

\mathbb E_{x,y\sim F}[revenue(r)]=2r^2(1-r)+\int_r^1\int_r^1\min\{x,y\}\mathrm dy\mathrm dx\\ =\frac{1}{3}+r^2-\frac{4}{3}r^3

maximized for $r=\frac{1}{2}$ at the value $\frac{5}{12}$ .

Revenue-optimal auctions

participant $i$ selects random valuation from distribution $F_i$ .

probability distributions $\mathbf F$ with continuous probability density function $\mathbf f$ . defined in $[0,+\infty)$

Assumption

the mechanism designer knows the distributions of valuations.
the valuations of different potential buyers are independent

virtual valuations: $\phi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}$

here $v_i$ stands for desired revenue, $\frac{1-F_i(v_i)}{f_i(v_i)}$ stands for discount.

Revenue and virtual valuation

Lemma: for every single-parameter environment with $n$ participant having independent valuations drawn from distribution $\mathbf F$ . every DSIC mechanism $(\mathbf x,\mathbf p)$ , every participant $i$ and every vector $\mathbf v_{-i}$ of valuations

\mathbb E_{v_i\sim F_i}[p_i(\mathbf v)]=\mathbb E_{v_i\sim F_i}[\varphi_i(v_i)\cdot x_i(\mathbf v)]

theorem: expected revenue=expected virtual valuations

\mathbb E_{\mathbf v\sim\mathbf F}[\sum_{i=1}^np_i(\mathbf v)]=\mathbb E_{\mathbf v\sim\mathbf F}[\sum_{i=1}^n\varphi_i(v_i)\cdot x_i(\mathbf v)]

proof using the lemma above and linearity of expectation.

Proof of the lemma

\mathbb E_{v_i\sim F_i}[p_i(\mathbf v)]=\int_0^\infty p_i(\mathbf v)\cdot f_i(v_i)\mathrm dv_i\\ =\int_0^\infty[\int_0^{v_i}z\cdot x_i'(z,\mathbf v_{-i})\mathrm dz]\cdot f_i(v_i)\mathrm dv_i\\ =\int_0^\infty[\int_z^\infty f_i(v_i)\mathrm dv_i]z\cdot x_i'(z,\mathbf v_{-i})\mathrm dz\\ =\int_0^\infty(1-F_i(z))z\cdot x_i'(z,\mathbf v_{-i})\mathrm dz\\ =\int_0^\infty[z-\frac{1-F_i(z)}{f_i(z)}]x_i(z,\mathbf v_{-i})f_i(z,\mathbf v_{-i})\mathrm dz\\ =\mathbb E_{v_i\sim F_i}[\varphi_i(v_i)\cdot x_i(\mathbf v)]

Revenue-optimal auction design

new goal: select an allocation rule that maximizes the virtual social welfare

\mathbb E_{\mathbf v\sim\mathbf F}[\sum_{i=1}^n\varphi_i(v_i)\cdot x_i(\mathbf v)]

we restrict ourselves to regular distributions that have the property that the virtual valuation function $\varphi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}$ is non-decreasing

then, the allocation rule that maximizes the virtual social welfare is monotone.

process: $n$ potential buyer with regular distributions

compute the virtual valuation $\phi_i(v_i)$ of the truthfully reported valuation $v_i$ .
select the feasible allocation that maximizes the virtual social welfare $\sum_{i=1}^n\varphi_i(v_i)x_i(\mathbf v)$
charge payments according to Myerson’s lemma