Exercise

Exercise 3.4

sponsored search auctions

$n$ bidders, $n$ slots. each bidder $i$ has a value of $v_i$.

the j-th slot has CTR $a_j$, with $a_1\ge a_2\ge\cdots\ge a_n$

maximize social welfare

denoting by $\delta(i)$ the slot bidder $i$ occupies, this means that the quantity $\sum_ia_{\delta(i)}v_i$ is as high as possible

Q: design a DSIC mechanism that maximizes social welfare

allocation rule should be monotone.

focus on bidder $i$ and compute the amount of stuff bidder $i$ gets for given bids by the remaining bidders.

assuming that bids $b_1\ge b_2\ge\cdots\ge b_{i-1}\ge b_{i}\ge\cdots\ge b_n$.

可以画一个获得位次 - 出价函数（台阶形状的）

payment rule is generated by Myerson's lemma according allocation rule.

$payment_i(z,b_{-i})=\sum_{j=1}^lb_{n-j+1}\times(a_{n-j}-a_{n-j+1})$

$l$ is number of jumps of the allocation rule $x_i(z,b_{-i})$.

Exercise 4.2

$X$: feasible solutions (set of agents). downward closures, if $S$ is a feasible solution w.r.t. $X$ then any subset of $S$ is also feasible.

select set $S$ of agents in $X$ s.t. the social welfare $\sum_{i\in S}v_i$ is maximized.

payment of an agent = externalities

Q: how much damage the existence of the agent causes to the remaining agents?

consider:

maximum social welfare of the instance without agent $i$. ($n-1$ agents)

social welfare of the remaining agents in the social welfare maximizing solution including agent $i$. $n$ agents)

for agent $i$, its payment will be value of step 1 - value of step 2. (damage cause to the remaining agents)

Exercise 4.3

$n+1$ execution of ALG are enough to compute both the allocation and the payments

0: solve the maximum $SW$ problem to get the allocation

keep $SW_{-i}$ for each agent $i$.

for $i=1,\cdots,n$: solve the maximum $SW$ problem for the instance that doesn't include agent $i$, keep $\widetilde{SW_{-i}}$.

payment=$\widetilde{SW_{-i}}-SW_{-i}$

Exercise 6.1

$n$ agents, agent $i$ has random value $v_i$ drawn independently from the p. d. $F_i$.

(a) compute an allocation that maximize expected revenue.

$F_i$: virtual valuation $\varphi_i(v)=v-\frac{1-F_i(v)}{f_i(v)}$

$\mathbb E[revenue(x)]=\mathbb E[\sum_i\varphi(v)x_i(v)]$

to maximize expected revenue, x should maximize $\sum_i\varphi(v)^+x_i(v)$.

(b) $F_i$ is uniform is $[a,b]$, $F_i(v)=\frac{v-a}{b-a}$, $f_i(v)=\frac{1}{b-a}$. $\varphi(v)=2v-b$.

in some cases, the highest bidder not win, even if it has a positive virtual valuation.

$F_1$ uniform in $[a_1,b_1]$, $F_2$ uniform in $[a_2,b_2]$.

there exist cases s.t. $2v_1-b_1\gt2v_2-b_2$ where $v_1\lt v_2$.

Exercise 6.4

expected revenue of the second price auction with n bidder is at least $1-\frac{1}{n}$ times the optimal expected revenue.

Denote:

$n$ bidders, p.d. F.

$REV1$: revenue of the revenue-maximizing auction with $n$ bidders

$REV2$: revenue of the revenue-maximizing auction with $n-1$ bidders.

$REV3$: revenue of the second-price auction with $n$ bidders.

According to Bulow & Klemperer's theorem, we know that $\mathbb E[REV3]\ge\mathbb E[REV2]$. Then we need to prove $\mathbb E[REV2]\geq(1-\frac{1}{n})\mathbb E[REV1]$.

We have

\[ (n-1)\mathbb E[REV1]=(n-1)\mathbb E[\sum_{i=1}^n\varphi(v_i)^+x_i(v)]\\ \]

\[ =\mathbb E[\sum_{j=1}^n\sum_{i=1,i\neq j}^n\varphi(v_i)^+x_i(v)]\\ \]

\[ =\sum_{j=1}^n\mathbb E[\sum_{i=1,i\neq j}^n\varphi(v_i)^+x_i(v)]\\ \]

\[ \leq\sum_{j=1}^n\mathbb E[REV2]=n\mathbb E[REV2]\\ \]

$$ \Rightarrow\mathbb E[REV2]\geq(1-\frac{1}{n})\mathbb E[REV1] $$ Q. E. D.

剩下时间的讲 Assignment 2 的题目。