Updates.

2 files changed, 33 insertions, 5 deletions

diff --git a/final/main.bib b/final/main.bib
index aaf7c97..a51a843 100644
--- a/final/main.bib
+++ b/final/main.bib
@@ -85,3 +85,23 @@
   pages     = {628--637},
   year      = {2013},
 }
+
+@article{liyao,
+  author    = {Xinye Li and Andrew Chi{-}Chih Yao},
+  title     = {On revenue maximization for selling multiple independently distributed items},
+  journal = {Proccedings of the National Academy of Sciences},
+  volume = {110},
+  number = {28},
+  pages     = {11232--11237},
+  year      = {2013},
+}
+
+@article{rubinstein,
+  author    = {Aviad Rubinstein and
+               S. Matthew Weinberg},
+  title     = {Simple Mechanisms for a Combinatorial Buyer and Applications to Revenue
+               Monotonicity},
+  journal   = {CoRR},
+  volume    = {abs/1501.07637},
+  year      = {2015}
+}
diff --git a/final/main.tex b/final/main.tex
index e5df90a..be71cd9 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -67,7 +67,7 @@
 for this project.}
 
 \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 $p$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints.
+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.
 \end{abstract}
 
 \section{Introduction}
@@ -214,7 +214,7 @@ restore individual rationality, we need to have the agent pay only when
 \begin{displaymath}
     \sum_{i=1}^m (t_i - \hat{v}_i)^+ \geq \hat{v}_0
 \end{displaymath}
-where we used the notation $(x)^+\eqdef\max(x, 0)$, so that the
+where we used the notation $(x)^+\eqdef\max\{x, 0\}$, so that the
 above inequality could also be written as $$\sum_{i: t_i\geq \hat{v}_i} (t_i-
 \hat{v}_i)\geq \hat{v}_0.$$
 
@@ -276,14 +276,14 @@ $\BRev(F)$ for the revenue obtained by the optimal grand bundle pricing and
 $\SRev(F)$ for the revenue obtained by selling each item at its monopoly reserve
 price. Then we have:
 
-\begin{lemma} For any product distribution $F$,
+\begin{lemma} \label{tprevlemma} For any product distribution $F$,
     \begin{displaymath}
         \TPRev(F)\geq \max\{\BRev(F), \SRev(F)\}\geq 6\cdot \Rev(F).
     \end{displaymath}
 \end{lemma}
 
 \begin{proof}
-    The second inequality is the main result from \citep{babaioff}; we will
+    The second inequality is the main result from \citep{babaioff} and we will discuss it in more detail as Lemma \ref{babaiofflemma}; we will
     thus only prove the first inequality, which holds even without the
     assumption that $F$ is a product distribution.
 
@@ -371,7 +371,7 @@ in fact unbounded.
 \section{$n$-to-1 Bidders Reductions}
 \label{sec:reduction}
 The goal of this section is to compare the two ways of constraining the single
-buyer problem that we discussed: namely $p$-exclusivity and ex-ante allocation
+buyer problem that we discussed: namely $\beta$-exclusivity and ex-ante allocation
 constraints and draw a parallel in how these two notions are used to construct
 $n$-to-1 bidders reductions in \citep{yao} and \citep{alaei} respectively.
 \subsection{\citep{alaei}'s Approach}
@@ -405,6 +405,14 @@ Next, we define another mechanism, $M'$, such that $M'$ is also IR-IC, and has a
 Finally, we show that $$\E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})] \leq \Rev(F_\beta^+ - \beta),$$ where the mechanism $M''$ that has revenue given by $\Rev(F_\beta^+ - \beta)$ is also shown to be IR-IC.
  \end{proofsketch}\end{lemma}
 
+Next, \citep{yao} quotes the following result from \citep{babaioff} (with the constant improved from $5 + \frac{3\sqrt{e}}{2} \approx 7.47$ to 6:
+
+\begin{lemma}[Theorem 2 in \citep{babaioff}; Lemma 6.2 in \citep{yao}] \label{babaiofflemma} Let $F =F_1\times\dots\times F_m$, let $\BRev(F)$ be the revenue obtained by the optimal grand bundle mechanism, treating the grand bundle as a single item, and let $\SRev(F)$ be the revenue obtained by selling each item separately at its monopoly reserve price. Then,
+$$\Rev(F) \leq 6 \cdot \max\{\SRev(F), \BRev(F)\}.$$ \begin{proofsketch} Following \citep{liyao}'s notion of a Core Decomposition, \citep{babaioff} decompose the optimal revenue into the contributions from items in the \emph{core} and \emph{tail}. \end{proofsketch}
+  \end{lemma}
+
+As a side note, a version of this lemma for more general distributions was recently proved by \citep{rubinstein}, in which the authors show that when a single buyer has subadditive utility and type drawn from distribution $F$, then the revenue of the optimal auction on $m$ items has the following constant-factor approximation: $$\Rev(F) \leq 314 \cdot \SRev(F) + 24 \cdot \BRev(F).$$ They do this by also using the Core Decomposition lemma from \citep{liyao}. Extensions to multiple buyers are not currently known. It may be possible to also relate this to our problem with allocation constraints, and prove an analogue of Lemma \ref{tprevlemma} for a buyer with subadditive utility.
+
 \section{Conclusion}
 
 \bibliographystyle{abbrvnat}