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.