diff options
| -rw-r--r-- | ps2/main.tex | 44 |
1 files changed, 35 insertions, 9 deletions
diff --git a/ps2/main.tex b/ps2/main.tex index d7c0a91..5cc2b96 100644 --- a/ps2/main.tex +++ b/ps2/main.tex @@ -44,7 +44,33 @@ \maketitle \section*{Exercise 4.13} -\section*{Exercise 4.14*}\begin{claim} For any constant $\beta$, there is a matroid environment and an i.i.d. non-regular distribution such that the approximation ratio of the optimal mechanism with the surplus maximization with anonymous reserve is at least $\beta$. \begin{proof} \end{proof} \end{claim} +\section*{Exercise 4.14*}\begin{claim} For any constant $\beta$, there is a matroid environment and an i.i.d. non-regular distribution such that the approximation ratio of the optimal mechanism with the surplus maximization with anonymous reserve is at least $\beta$. +\end{claim} + +\begin{proof} +Since we know that the claim is not true for a $k$-uniform matroid (where any +subset of at most $k$ agents is feasible), we need to look at a more general +matroid. We consider a transversal matroid with $n+1$ agents and $n$ items. + +Let us denote by $\{0,\ldots,n\}$ the set of agents. By setting the edges of +the bipartite graph appropriately, we can ensure that any set containing agent +0 and any other agent in $\{1,\ldots n\}$ is not feasible. + +Now we can set the probability distribution so that the value $v_i$ of agent +$i$ is: +\begin{displaymath} + v_i = \begin{cases} + 1& \text{w.p. } 1-\frac{1}{n}\\ + H& \text{w.p. } \frac{1}{n} + \end{cases} +\end{displaymath} +we think that by choosing $H$ appropriately (probably $\Omega(n)$), we can +prove that the multiplicative gap between the optimal mechanism and the surplus +maximizing mechanism with reserve prize goes to infinity as $n$ goes to +infinity. Unfortunately, it seems that a fine balance between the $\frac{1}{n}$ +probability and the growth rate of $H$ is required, and we haven't been able to +find it. +\end{proof} \section*{Exercise 4.19} \begin{claim} In regular, matroid environments, the revenue of the surplus maximization mechanism with monopoly reserves is a 2-approximation to the optimal mechanism revenue. @@ -152,20 +178,20 @@ simply $a$. Hence we can apply Lemma 4.13 to $g$ for subsets of $A$ and obtain: \paragraph{General distributions} We first look at a continuous distribution $\mathbf{F}$ with bounded support. On the support of $\mathbf{F}$, it is -possible to approximate its CDF arbitrarily well in the $L^\infty$ norm (hence in -the $L^2$ norm since we are on a bounded set) by simple functions (convex -combination of step functions). But a step function is simply the CDF of -a Dirac distribution. Hence, we can approximate $\mathbf{F}$ arbitrarily well -in the $L^2$ norm with finite support distributions. But convergence in the $L^2$ norm -implies weak convergence by the Cauchy-Schwarz inequality. That is, we have -a sequence $F_n$ of finite support distributions such that: +possible to approximate its CDF arbitrarily well in the $L^\infty$ norm (hence +in the $L^2$ norm since we are on a bounded set) by staircase functions (convex +combination of indicator functions). But an indicator function is simply the +CDF of a Dirac distribution. Hence, we can approximate $\mathbf{F}$ arbitrarily +well in the $L^2$ norm with finite support distributions. But convergence in +the $L^2$ norm implies weak convergence by the Cauchy-Schwarz inequality. That +is, we have a sequence $F_n$ of finite support distributions such that: \begin{displaymath} \E_{F_n}[\max_i v_i] \xrightarrow[n\rightarrow \infty]{} \E_F[\max_i v_i] \end{displaymath} we can apply the previous result for each of the $F_n$ and take the limit to obtain again: \begin{displaymath} - \E_{\mathbf{F}}[\max_i v_i] \geq \E_{\mathbf{F^I}}[\max_i v_i] + \E_{\mathbf{F}}[\max_i v_i] \geq \frac{e}{e-1}\E_{\mathbf{F^I}}[\max_i v_i] \end{displaymath} When $\mathbf{F}$ does not have bounded support, we can truncate $\mathbf{F}$ |