Connection between Yao and Babaioff in the unconstrained case

1 files changed, 90 insertions, 21 deletions

diff --git a/final/main.tex b/final/main.tex
index f5ad43f..a79a0bb 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -36,6 +36,10 @@
 \let\Pr\relax
 \DeclareMathOperator*{\Pr}{\mathbb{P}}
 \DeclareMathOperator*{\I}{\mathcal{I}}
+\DeclareMathOperator*{\TPRev}{\textsc{TPRev}}
+\DeclareMathOperator*{\Rev}{\textsc{Rev}}
+\DeclareMathOperator*{\BRev}{\textsc{BRev}}
+\DeclareMathOperator*{\SRev}{\textsc{SRev}}
 
 \newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
 \newcommand{\R}{\mathbb{R}}
@@ -114,11 +118,21 @@ Problem~\ref{eq:opt}:
     \E_{t\sim F}\big[x_i(t)] \leq \hat{x}_i,\quad\forall i\in[m]
 \end{equation}
 which expresses that the ex-ante allocation probability is upper-bounded by
-$\hat{x}$.
+$\hat{x}$. Note that when $\hat{x} = (1,\ldots,1)$, the ex-ante allocation
+constraint \eqref{eq:ea} does not further constrain the optimization problem
+given by Equation \ref{eq:opt}, i.e. the constraint is trivially satisfied.  In
+this case, as discussed above, the mechanism described in \citep{babaioff}
+provides a 6-approximation to $R((1,...,1))$.
 
 We use the notation from \citep{alaei}, where $R(\hat{x})$ denotes the revenue
 obtained by the optimal mechanism solution to Problem~\ref{eq:opt} with ex-ante
-allocation constraint $\hat{x}$ given by \eqref{eq:ea}. The main question
+allocation constraint $\hat{x}$ given by \eqref{eq:ea}. When we want to make
+the type distribution $F$ explicit we will write $R(\hat{x}, F)$. Finally, when
+the ex-ante allocation constraint \eqref{eq:ea} is not present, we use $\Rev(F)
+= R((1,\dots, 1), F)$ to denote the revenue of the revenue optimal IR-IC
+mechanism.
+
+The main question
 underlying this work can then be formulated as:
 
 \paragraph{Problem.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is
@@ -127,10 +141,7 @@ $\hat{x}$ and whose revenue is a constant approximation to $R(\hat{x})$?}
 
 \subsection{Examples and Motivations}
 
-\paragraph{}Note that when $\hat{x} = (1,\ldots,1)$, the ex-ante allocation constraint \eqref{eq:ea} does not further
-constrain the optimization problem given by Equation \ref{eq:opt}, i.e. the constraint is trivially satisfied.  In
-this case, as discussed above, the mechanism described in \citep{babaioff}
-provides a 6-approximation to $R((1,...,1))$.
+TODO: this section is mostly wrong, to be discussed.
 
 \paragraph{Single-item case.} 
 To make things more concrete, let us first look at the single-item case which
@@ -161,7 +172,6 @@ polynomial time a mechanism for the multi-agent problem which is
 a $\gamma\cdot\alpha$ approximation to the revenue-optimal mechanism where
 $\gamma$ is a constant which is at least $\frac{1}{2}$.
 
-
 \section{A Two-Part Tariff Mechanism}
 
 \subsection{Definition of the Mechanism}
@@ -174,19 +184,20 @@ unconstrained, regular case, no posted-price mechanism for the single-agent
 problem has an approximation ratio better than $\Omega(\log n)$.
 
 Instead, we consider the following candidate mechanism suggested by Jason
-Hartline: the buyer is charged a price $p_0$ to participate in the mechanism,
-and then is offered each item separately with posted prices $p_1,\ldots, p_m$.
-This is essentially the concept of a two-part tariff, as discussed in
-\citep{armstrong}.
+Hartline: the buyer is charged a price $\hat{v}_0$ to participate in the
+mechanism, and then is offered each item separately with posted prices
+$\hat{v}_1,\ldots, \hat{v}_m$.  This is essentially the concept of a two-part
+tariff, as discussed in \citep{armstrong}.
 
-Note that as written above, the candidate mechanism is not individually
-rational because the agent gets charged $p_0$ regardless of her type. To
+Note that as described above, the candidate mechanism is not individually
+rational because the agent gets charged $\hat{v}_0$ regardless of her type. To
 restore individual rationality, we need to have the agent pay only when
 \begin{displaymath}
-    \sum_{i=1}^m (t_i - p_i)^+ \geq p_0
+    \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
-above inequality could also be written as $$\sum_{i: t_i\geq p_i} (t_i- p_i)\geq p_0.$$
+above inequality could also be written as $$\sum_{i: t_i\geq \hat{v}_i} (t_i-
+\hat{v}_i)\geq \hat{v}_0.$$
 
 We can now formally describe the candidate mechanism.
 
@@ -199,21 +210,79 @@ We can now formally describe the candidate mechanism.
 \end{center}
     \begin{displaymath}
         \begin{cases}
-            x_i = \I[t_i \geq p_i],\; p = p_0 + \sum_i p_ix_i &\text{ if} \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 \\
-            x_i = 0\text{ for all $i$},\; p = 0&\text{ otherwise }
+            x_i(t) = \I[t_i \geq \hat{v}_i],\; p(t) = \hat{v}_0 + \sum_i
+            \hat{v}_ix_i &\text{ if} \sum_{i=1}^m (t_i - \hat{v}_i)^+ \geq
+            \hat{v}_0 \\
+            x_i(t) = 0\text{ for all $i$},\; p(t) = 0&\text{ otherwise }
         \end{cases}
     \end{displaymath}
     \vspace{1em}
 \end{minipage}
 }
 \end{center}
-
 where we use the notation $\I[\text{expression}]$ to denote the indicator
-variable for the expression, which takes on value 1 when the expression is true and 0 otherwise.
+variable for the expression, which takes on value 1 when the expression is true
+and 0 otherwise.
 
 We note that this mechanism is exactly the $\beta$-bundle mechanism from
-\citep{yao}, even though the interpretation in terms of entrance fee plus posted
-prices is not explicit in this paper.
+\citep{yao}, even though the interpretation as a two-part tariff is
+not explicit in this paper.
+
+For a choice $\hat{v} = (\hat{v}_0,\hat{v}_1,\dots,\hat{v}_m)$ of the entrance
+fee and the posted prices, let us denote by $x(t, \hat{v})$ and $p(t, \hat{v})$
+the allocation rule and payment rule of the two-part tariff mechanism. We will use
+$\TPRev(F)$ to denote the best expected revenue which can be obtained by the
+two-part tariff mechanism for an optimal choice of $\hat{v}$:
+\begin{displaymath}
+    \TPRev(F) = \sup_{\hat{v}\in\R_+^{m+1}} \E_{t\sim F}[p(t, \hat{v})]
+\end{displaymath}
+and by $\TPRev(\hat{x}, F)$ the best revenue which can be obtained by the
+two-part tariff mechanism with ex-ante allocation constraint $\hat{x}$:
+\begin{displaymath}
+    \begin{split}
+        \TPRev(\hat{x}, F) = \sup_{\hat{v}\in\R_+^{m+1}} &\E_{t\sim F}[p(t, \hat{v})]\\
+        \text{s.t.} &\, \E_{t\sim F}[x_i(t, \hat{v})]\leq \hat{x}_i,\quad \forall
+        i\in[m]\\
+\end{split}
+\end{displaymath}
+The problem we introduced in Section~\ref{sec:intro} can then be formulated for
+the two-part tariff mechanism: \emph{is $\TPRev(\hat{x}, F)$ a constant
+approximation to $\Rev(\hat{x}, F)$?}
+
+The following simple Lemma shows that at least in the unconstrained case, the
+answer to the previous question is positive. In fact, the proof shows that the
+two-part tariff mechanism is rich enough to simulate both bundle pricing and
+separate posted pricing. Using the notation from \citep{babaioff}, let us write
+$\BRev(F)$ the revenue obtained by the optimal grand bundle pricing and by
+$\SRev(F)$ the revenue obtained by selling each item at its monopoly reserve
+price, then we have:
+
+\begin{lemma} 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
+    thus only prove the first inequality. 
+
+    In the specific case where $\hat{v} = (0,\hat{v}_1,\dots,\hat{v}_m)$,
+    \emph{i.e} $\hat{v}_0 = 0$, there is no entrance fee and the two-part
+    tariff mechanism simply sells each item separately in a take-it-or-leave-it
+    manner. For the optimal choice of $(\hat{v}_1,\dots,\hat{v}_m)$, the
+    revenue of the mechanism reaches $\SRev(F)$. Since the supremum defining
+    $\TPRev(F)$ optimizes (in particular) over all $\hat{v}$ with $\hat{v}_0
+    = 0$ we have that $\TPRev(F)\geq \SRev(F)$.
+
+    When $\hat{v}_1=\dots=\hat{v}_m = 0$, the two part tariff mechanism then
+    simply sells all the item at price $\hat{v}_0$ whenever $\sum_{i=1}^m
+    t_i\geq \hat{v}_0$, \emph{i.e} is a grand bundle pricing mechanism. For the
+    optimal choice of $\hat{v}_0$, the revenue reaches $\BRev(F)$. As in the
+    previous paragraph, this implies that $\TPRev(F)\geq \BRev(F)$.
+\end{proof}
+
+\subsection{Computational Considerations}
 
 \subsection{$p$-exclusivity}