Add proof of the counterexample.

1 files changed, 44 insertions, 3 deletions

diff --git a/final/main.tex b/final/main.tex
index 0258e07..2091600 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -563,9 +563,50 @@ constrained case: the main idea is to use induction and
 Lemma~\ref{lemma:marginal} to ``split'' the set of items and reduce to the
 induction hypothesis.
 
-% However, A. Rubinstein identifies the following counterexample to this potential approach:
-% \begin{counterexample}[\citep{rubinstein2},Example 4 adapted] Consider a single-item auction with a single bidder, $m$ items, with each item having an ex-ante allocation probability of $\frac{1}{m^{1/4}}$
-% \end{counterexample}
+However, A. Rubinstein identifies the following counterexample to this
+potential approach:
+\begin{counterexample}[\citep{rubinstein2}, Example 4 adapted]
+    Consider a single-item auction with a single bidder, $m$ items. The values
+    $v_i$ of the items are drawn i.i.d from the following distribution: with
+    probability $1-\frac{1}{n^{3/4}}$, $v_i = 0$, otherwise, $v_i$ is drawn
+    from an equal revenue distribution with support $\{1,\ldots,n^{1/10}\}$,
+    i.e. $\Pr[v_i \geq k] = \frac{1}{kn^{3/4}}$. We will consider the case
+    where the ex-ante allocation constraint is uniform (the same for all items)
+    and equal to $\frac{1}{n^{3/4}}$.
+\end{counterexample}
+
+\begin{proof}
+First, note that the expected value for each item is $\frac{C\log n}{n^{3/4}}$,
+for some constant $C$ (by summation of the CDF of the distribution). We now
+introduce a ``good'' mechanism, and then show that neither the separate posted
+price mechanism nor the grand bundle mechanism are a constant approximation to
+it.
+
+\paragraph{Good Mechanism} Approach the buyer and offer her to select her
+favorite $n^{1/4}$ items at price $(1-\epsilon)\frac{Cn\log n}{n^{3/4}}$. Since
+each item has nonzero value with probability $\frac{1}{n^{3/4}}$, if there are
+many items, the number of items with nonzero values will concentrate and be
+(roughly) equal to $n\cdot\frac{1}{n^{3/4}} = n^{1/4}$. So the $n^{1/4}$
+favorite items of the buyer will coincide with  the $n^{1/4}$ items with
+nonzero value, and their combined value will also concentrate close to their
+expected value of $\frac{Cn\log n}{n^{3/4}}$. Hence, this mechanism has revenue
+$(1-\epsilon)\frac{Cn\log n}{n^{3/4}}$. Also note that this mechanism satisfies
+the ex-ante constraint since and item will sell if and only if it has nonzero
+value, which happens with probability $\frac{1}{n^{3/4}}$.
+
+\paragraph{$\SRev$} The revenue for each item is the same no matter what the
+posted price is and is equal to $\frac{1}{n^{3/4}}$. Hence the overall revenue
+is $\frac{n}{n^{3/4}}$ which is only a $O(\frac{1}{\log n})$ fraction of the
+``good'' mechanism. 
+
+\paragraph{$\BRev$} Since the ex-ante constraint is the same of all the items,
+the grand bundle can be allocated with probability at most $\frac{1}{n^{3/4}}$
+(otherwise, this would violate the ex-ante constraint for one of the items).
+When it is allocated, the revenue is upper-bounded by the expected value of all
+the items, i.e. $\frac{Cn\log n}{n^{3/4}}$. So the revenue of the grand bundle
+mechanism is at most $\frac{1}{n^{3/4}}$ times the one of the ``good''
+mechanism.
+\end{proof}
 
 
 \bibliographystyle{abbrvnat}