Update

1 files changed, 101 insertions, 0 deletions

diff --git a/final/main.tex b/final/main.tex
index 8f07ed1..13baefd 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -38,6 +38,7 @@
 \DeclareMathOperator*{\I}{\mathcal{I}}
 \DeclareMathOperator*{\TPRev}{\textsc{TPRev}}
 \DeclareMathOperator*{\Rev}{\textsc{Rev}}
+\DeclareMathOperator*{\Val}{\textsc{Val}}
 \DeclareMathOperator*{\BRev}{\textsc{BRev}}
 \DeclareMathOperator*{\SRev}{\textsc{SRev}}
 
@@ -49,6 +50,7 @@
 
 \newtheorem{theorem}{Theorem}
 \newtheorem{lemma}{Lemma}
+\newtheorem{corollary}{Corollary}
 \newtheorem*{definition}{Definition}
 \newtheorem*{goal}{Goal}
 
@@ -451,6 +453,105 @@ We have discussed the problem of selling $m$ heterogeneous items, with ex-ante a
 
 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.
 
+\appendix
+
+\section{Addendum: Answers to Jason's Questions}
+
+\subsection{Counter-example on $\beta$-exclusive mechanisms}
+
+We agree that the counter-example, by exploiting heavily the discreteness of the
+type distribution, is not satisfying in that it does not say anything about
+regular (or simply continuous) distributions.
+
+Yet, since the $\beta$-exclusive approach didn't seem as promising, and after
+a discussion with Aviad Rubinstein, we tried instead to adapt the approach of
+\cite{babaioff} to the ex-ante constrained problem: that is, showing that the
+maximum between (ex-ante constrained) grand bundling and separate posted
+pricing is a constant approximation to the optimal mechanism. Note that this
+would imply, similarly to Lemma~\ref{tprevlemma} that our candidate two-part
+tariff mechanism is also a constant approximation to the optimal mechanism.
+
+The ``core decomposition'' Lemma of \cite{babaioff}, which is a key ingredient
+in the proof of their main result, can be adapted to the case of ex-ante
+constraints, as we now show.
+
+\begin{lemma}[Marginal mechanism]\label{lemma:marginal}
+    Let $(D, D')$ be a joint distribution of types over two disjoint set of
+    items $S$ and $T$. Then:
+    \begin{displaymath}
+        \Rev\big(\hat{x}, (D, D')\big) \leq \Val(D) + \E_{t_S\sim
+        D}\left[\Rev\left(\frac{\hat{x}_T}{\Pr_{D}[t_S]}, D'|t_S\right)\right]
+    \end{displaymath}
+    where $\Val(D) \eqdef \sum_{i\in S} \E_{t\sim D}[t_i]$
+\end{lemma}
+
+\begin{proof}
+    This is an adaptation of Lemma 21 from \cite{hart-nisan}. The
+    main difference is that, starting from an optimal mechanism for $(D, D')$
+    satisfying the ex-ante constraint $\hat{x}$, fixing the value $t_S$ of the
+    items in $S$, the induced mechanism on $T$ for the distribution $(D'|t_S)$
+    allocates with probability at most $\frac{\hat{x}}{\Pr_{D}[t_S]}$.
+\end{proof}
+
+\begin{corollary}\label{cor}
+    For $D$ and $D'$, two distributions of types over disjoint set of items $S$
+    and $T$. Then:
+    \begin{displaymath}
+        \Rev(\hat{x}, D\times D') \leq \Val(D) + \Rev(\hat{x}_T, D')
+    \end{displaymath}
+\end{corollary}
+
+\begin{proof}
+    This follows from Lemma~\ref{lemma:marginal} by observing that $D'|t_S
+    = D'$ since we have a product distribution. We also have:
+    \begin{displaymath}
+        \E_{t_S\sim D}
+        \left[\Rev\left(\frac{\hat{x}_T}{\Pr_{D}[t_S]}, D'\right)\right]
+        \leq \Rev(\hat{x}_T, D')
+    \end{displaymath}
+    Indeed, the value of the left-hand side can be obtained by randomizing over
+    the mechanisms of value $\Rev\left(\frac{\hat{x}_T}{\Pr_{D}[t_S]},
+    D'\right)$ with probability $\Pr_D[t_S]$ for all values of $t_S$. Note that
+    the probability of allocation resulting from this randomization is then
+    bounded above by $\E_{t_S\sim D}\left[\frac{\hat{x}_T}{\Pr_D[t_S]}\right]
+    = \hat{x}_T$.
+\end{proof}
+
+Corollary~\ref{cor}, combined with Lemma~5 from \cite{babaoiff} (which can be
+extended \emph{mutatis mutandi} to the constrained case) as in the proof
+Lemma~6 from \cite{babaoiff} yields the following version of the core
+decomposition lemma:
+
+\begin{lemma}
+        $\Rev(\hat{x}, D)\leq \Val(D^C_\emptyset) + \sum_A p_A\Rev(\hat{x}_A,
+        D^T_A)$.
+\end{lemma}
+
+However, if we keep pushing in this direction, it seems that the approach fails
+when trying to obtain the following lemma:
+\begin{lemma}
+    $\Rev(\hat{x}, D) \leq m\SRev(\hat{x}, D)$.
+\end{lemma}
+
+This lemma 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
+Lemma~\ref{lemma:marginal} to ``split'' the set of items and reduce to the
+induction hypothesis. Unfortunately, the ex-ante constraint does not work well
+with this way of splitting. And we haven't been able to work around it and
+obtain a positive result as of now.
+
+\subsection{Answer to the second question, to be rewritten}
+
+We did not solve the ex ante pricing problem. We were hoping to find an
+approximately optimal mechanism for the ex-ante constrained single buyer,
+multiple-items setting. This was our stated goal, both in the abstract and the
+introduction, but we agree that the extent to which we solve it is not very
+clear and we apologize for that. The rest of the paper is an exposition of what
+we understood about the problem, and more precisely about the two-part tariff
+mechanism. The original problem is still open at this point.
+
 \bibliographystyle{abbrvnat}
 \bibliography{main}
 \end{document}