Updates

2 files changed, 35 insertions, 34 deletions

diff --git a/final/main.bib b/final/main.bib
index a51a843..8e528b0 100644
--- a/final/main.bib
+++ b/final/main.bib
@@ -105,3 +105,10 @@
   volume    = {abs/1501.07637},
   year      = {2015}
 }
+
+@article{rubinstein2,
+  author    = {Aviad Rubinstein},
+  title     = {On the Computational Complexity of Optimal Simple Mechanisms},
+  journal   = {Preprint},
+  year      = {2015}
+}
diff --git a/final/main.tex b/final/main.tex
index 13baefd..9e2f3f3 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -51,8 +51,10 @@
 \newtheorem{theorem}{Theorem}
 \newtheorem{lemma}{Lemma}
 \newtheorem{corollary}{Corollary}
+\newtheorem{conjecture}{Conjecture}
 \newtheorem*{definition}{Definition}
 \newtheorem*{goal}{Goal}
+\newtheorem*{counterexample}{Counterexample}
 
 \newenvironment{proofsketch}[1][Proof Sketch]{\proof[#1]\mbox{}\\*}{\endproof}
 
@@ -69,7 +71,11 @@
 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 $\beta$-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.
+
+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.
 \end{abstract}
 
 \section{Introduction}
@@ -152,6 +158,8 @@ 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.
+
 \subsection{Examples and Motivations}
 
 \paragraph{Single-item case.} 
@@ -349,7 +357,7 @@ a constant approximation to $\Rev(\hat{x}, F)$ by:
         $\beta$-exclusive mechanism (Theorem 6.1 in \citep{yao}).
 \end{enumerate}
 
-Unfortunately, this approach breaks at step 1. To see why, consider for
+There is a counterexample to step 1 for discrete, non-regular distributions. Consider for
 simplicity a discrete type space $T\subset \R_+^m$ and assume that the support
 of $F$ is exactly $T$. Writing $T = T_1\times\dots\times T_m$ and $F
 = F_1\times\dots\times F_m$, consider an ex-ante constraint $\hat{x}$ such that
@@ -367,8 +375,8 @@ This mechanism is clearly IR and IC, satisfies the constraint $\hat{x}$ and has
 expected revenue $$\sum_{i\in [m]} \hat{x}_i t_i^{min}.$$ The revenue is positive
 whenever there exists $i$ such that $t_i^{min}>0$.
 
-This example shows that the approximation ratio in step 1, described above, is
-in fact unbounded.
+This example shows that for discrete non-regular distributions, the approximation ratio in step 1, described above, is
+in fact unbounded. However, this relies on the discreteness of the type distribution, and, we have not identified a counterexample for regular, continuous type distributions.
 
 \section{$n$-to-1 Bidders Reductions}
 \label{sec:reduction}
@@ -455,20 +463,13 @@ Our proposed mechanism $\M$ can be viewed as a generalization of the work of \ci
 
 \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.
+\section{Addendum: An Alternative Mechanism}
 
-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
+We also 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
+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
@@ -517,40 +518,33 @@ constraints, as we now show.
     = \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
+Corollary~\ref{cor}, combined with Lemma~5 from \cite{babaioff} (which can be
+extended, having made the appropriate changes, to the constrained case) as in the proof
+Lemma~6 from \cite{babaioff} yields the following version of the core
 decomposition lemma:
 
-\begin{lemma}
+\begin{conjecture}
         $\Rev(\hat{x}, D)\leq \Val(D^C_\emptyset) + \sum_A p_A\Rev(\hat{x}_A,
         D^T_A)$.
-\end{lemma}
+\end{conjecture}
 
 However, if we keep pushing in this direction, it seems that the approach fails
-when trying to obtain the following lemma:
-\begin{lemma}
+when trying to obtain the following:
+\begin{conjecture}
     $\Rev(\hat{x}, D) \leq m\SRev(\hat{x}, D)$.
-\end{lemma}
+\end{conjecture}
 
-This lemma would be required if we wanted to apply the same proof technique as
+This conjecture 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.
+induction hypothesis.
 
-\subsection{Answer to the second question, to be rewritten}
+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}
 
-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}