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}$