Final updates

1 files changed, 38 insertions, 36 deletions

diff --git a/final/main.tex b/final/main.tex
index 2091600..0615c19 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -55,6 +55,7 @@
 \newtheorem*{definition}{Definition}
 \newtheorem*{goal}{Goal}
 \newtheorem*{counterexample}{Counterexample}
+\newtheorem*{desiredresult}{Desired Result}
 
 \newenvironment{proofsketch}[1][Proof Sketch]{\proof[#1]\mbox{}\\*}{\endproof}
 
@@ -68,14 +69,16 @@
 \maketitle
 
 \blfootnote{We are grateful to Jason Hartline who provided the original idea
-for this project.}
+for this project. We also appreciate the helpful suggestions of Aviad Rubinstein.}
 
 \begin{abstract}
 In this paper, given the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$, we focus on finding a simple mechanism obeying the allocation constraint whose revenue is a constant approximation to the revenue of the optimal mechanism with this constraint. 
 
 In particular, following a suggestion by J.D. Hartline, we define a mechanism based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then draw a connection with a technique from \citep{yao}, in which we relate this mechanism to a $\beta$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints.
 
-We also explore an adaptation of the Core Decomposition lemma in \citep{babaioff}, as suggested by A. Rubinstein. While we did not solve the ex-ante pricing problem, we provide an exposition of our current understanding of the problem and what we perceive to be some of the obstacles remaining for a solution.
+We also explore an adaptation of the Core Decomposition lemma in \citep{babaioff}, as suggested by A. Rubinstein. However, this approach to finding a simple mechanism has a counterexample, which we discuss.
+
+While we did not solve the ex-ante pricing problem, we provide an exposition of our current understanding of the problem and what we perceive to be some of the obstacles remaining for a solution.
 \end{abstract}
 
 \section{Introduction}
@@ -158,7 +161,7 @@ and a type distribution $F$, is there a simple mechanism whose ex-ante
 allocation rule is upper-bounded by $\hat{x}$ and whose revenue is a constant
 approximation to $\Rev(\hat{x},F)$?}
 
-While we have not been able to answer this question, we provide an exposition of two potential approaches: a mechanism based on a two-part tariff approach, as suggested by J. D. Hartline and as an adaptation of the Core Decomposition Lemma from \citep{babaioff}, as suggested by A. Rubinstein. Thus, this problem remains open, but we hope that our discussion could suggest paths towards an eventual solution.
+While we have not been able to answer this question, we provide an exposition of two potential approaches: a mechanism based on a two-part tariff approach, as suggested by J. D. Hartline and as an adaptation of the Core Decomposition Lemma from \citep{babaioff}, as suggested by A. Rubinstein. The latter candidate mechanism has a counterexample, which we discuss in Section \ref{sec:counterexample}. Thus, this problem remains open, but we hope that our discussion could suggest paths towards an eventual solution.
 
 \subsection{Examples and Motivations}
 
@@ -459,7 +462,7 @@ While this mechanism's revenue does indeed provide a constant approximation to t
 
 We have discussed the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$. Following a suggestion by J.D. Hartline, we have proposed a mechanism $\M$ based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then drew a connection with a technique from \citep{yao}, in which we relate this mechanism to a $\beta$-exclusive mechanism. We also surveyed the $n$-to-1 buyer reduction techniques within \citep{alaei} and \citep{yao}, unifying the exposition and terminology. 
 
-Our proposed mechanism $\M$ can be viewed as a generalization of the work of \citep{babaioff}, but with the addition of allocation constraints. We showed, via a counterexample, that the approximation ratio of the revenue for the optimal $\beta$-exclusive mechanisms to the optimal revenue of the two-party tariff mechanism $\M$ is unbounded. Whether the optimal revenue of the two-party tariff mechanism is a constant approximation to the revenue of the optimal mechanism with allocation constraints remains an open and interesting path for future research.
+Our proposed mechanism $\M$ can be viewed as a generalization of the work of \citep{babaioff}, but with the addition of allocation constraints. We showed, via a counterexample, that for a discrete, non-regular distribution the approximation ratio of the revenue for the optimal $\beta$-exclusive mechanisms to the optimal revenue of the two-party tariff mechanism $\M$ is unbounded. Assuming regularity of the distribution, this may yet yield an approach to finding the desired simple mechanism. Whether the optimal revenue of the two-party tariff mechanism is a constant approximation to the revenue of the optimal mechanism with allocation constraints remains an open and interesting path for future research.
 
 \appendix
 
@@ -552,59 +555,58 @@ decomposition lemma:
 
 However, if we keep pushing in this direction, it seems that the approach fails
 when trying to obtain the following:
-\begin{conjecture}
+\begin{desiredresult}
     $\Rev(\hat{x}, D) \leq m\SRev(\hat{x}, D)$.
-\end{conjecture}
+\end{desiredresult}
 
-This conjecture would be required if we wanted to apply the same proof technique as
+This result would be required if we wanted to apply the same proof technique as
 \cite{babaioff} to the proof of the approximation ratio of our mechanism.
-Unfortunately, the proof of this lemma does not transpose easily to the ex-ante
-constrained case: the main idea is to use induction and
+Unfortunately, the proof of this lemma does not transpose to the ex-ante
+constrained case: the main idea in a putative proof would be to use induction and
 Lemma~\ref{lemma:marginal} to ``split'' the set of items and reduce to the
 induction hypothesis.
-
+\label{sec: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}}$.
+    Consider an $m$-item auction with a single bidder. The values
+    $v_i$ of the items are drawn i.i.d. from the following distribution: with
+    probability $1-\frac{1}{m^{3/4}}$, $v_i = 0$; otherwise, $v_i$ is drawn
+    from an equal revenue distribution with support $\{1,\ldots,m^{1/10}\}$,
+    i.e. $\Pr[v_i \geq k] = \frac{1}{km^{3/4}}$. We suppose that the ex-ante allocation constraint is uniform (the same for all items)
+    and equal to $\frac{1}{m^{3/4}}$.
 \end{counterexample}
 
 \begin{proof}
-First, note that the expected value for each item is $\frac{C\log n}{n^{3/4}}$,
+First, note that the expected value for each item is $\frac{C\log m}{m^{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
+introduce a ``good'' mechanism, which can guarantee almost the entire social welfare, and then show that neither the separate posted
 price mechanism nor the grand bundle mechanism are a constant approximation to
-it.
+it (and therefore that the maximum of their revenues is not a constant approximation to it either).
 
-\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
+\paragraph{Good Mechanism} Approach the buyer and offer for her to select her
+most-preferred $m^{1/4}$ items at price $(1-\epsilon)\frac{Cm\log m}{m^{3/4}}$. Since
+each item has nonzero value with probability $\frac{1}{m^{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
+(roughly) equal to $m\cdot\frac{1}{m^{3/4}} = m^{1/4}$. So the $m^{1/4}$
+favorite items of the buyer will coincide with the $m^{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}}$.
+expected value of $\frac{Cm\log m}{m^{3/4}}$. Hence, this mechanism has revenue
+$(1-\epsilon)\frac{Cm\log m}{m^{3/4}}$. Also note that this mechanism satisfies
+the ex-ante allocation constraints since an item will be sold if and only if it has nonzero
+value, which happens with probability $\frac{1}{m^{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
+\paragraph{Computing the Single Item Revenue, $\SRev$} The revenue for each item is the same no matter what the
+posted price is and is equal to $\frac{1}{m^{3/4}}$. Hence the overall revenue
+is $\frac{m}{m^{3/4}}$ which is only a $O(\frac{1}{\log m})$ fraction of the revenue 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}}$
+\paragraph{Computing the Grand Bundle Revenue, $\BRev$} Since the ex-ante constraint is the same for all of the items,
+the grand bundle can be allocated with probability at most $\frac{1}{m^{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''
+the items, i.e. $\frac{Cm\log m}{m^{3/4}}$. So the revenue of the grand bundle
+mechanism is at most $\frac{1}{m^{3/4}}$ times the one of the ``good''
 mechanism.
 \end{proof}