From 49d9bce73c857415619a6d73b9336b6b649f466a Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 20 Dec 2014 00:30:44 +0100
Subject: Include Jason's feedback + roadmap

---
 project2/main.tex | 64 ++++++++++++++++++++++++++++++-------------------------
 1 file changed, 35 insertions(+), 29 deletions(-)

(limited to 'project2/main.tex')

diff --git a/project2/main.tex b/project2/main.tex
index c3bb706..1e02d78 100644
--- a/project2/main.tex
+++ b/project2/main.tex
@@ -48,8 +48,6 @@
 
 \maketitle
 
-
-
 \section{Introduction to the Problem}
 
 \blfootnote{We are grateful to Jason Hartline who provided the original idea
@@ -83,17 +81,16 @@ obtained as the solution to the following optimization problem:
 where the first constraint expresses incentive compatibility and the second
 constraint expresses individual rationality.
 
-Unfortunately, it has been shown in \cite{hart} that even in this simple case
-and as soon as $m\geq 2$, the optimal mechanism can have a menu size which is
-exponential in $m$. Therefore it is important to understand to which extent
-simple mechanisms can approximate the revenue-optimal mechanism.
+If the distribution $F$ is correlated, a result from \cite{hart} shows that
+the gap between the revenue of auctions with finite menu size and
+a revenue-maximizing auction can be arbitrarily large.
 
-A remarkable result of \cite{babaioff} proves that a simple mechanism provides
-a constant approximation to Problem~\ref{eq:opt}. More precisely, it is shown
-that the maximum of \emph{item pricing} where each item is priced separately at
-its monopoly reserve price and \emph{bundle pricing} where the grand bundle of
-all items is priced and sold together achieves a 6-approximation to the optimal
-mechanism.
+When $F$ is a product distribution however, there is a hope to obtain simple
+auctions with constant approximation ratios to the optimal revenue. In fact,
+a result from \cite{babaioff} shows that the maximum of \emph{item pricing}
+where each item is priced separately at its monopoly reserve price and
+\emph{bundle pricing} where the grand bundle of all items is priced and sold
+as a single item achieves a 6-approximation to the optimal revenue.
 
 We propose to extend this result by considering a more general version of
 Problem~\ref{eq:opt} where there is an additional \emph{ex-ante allocation
@@ -115,7 +112,13 @@ allocation constraint $\hat{x}$ given by \eqref{eq:ea}.
 there a simple mechanism whose ex-ante allocation rule is upper-bounded by
 $\hat{x}$ and whose revenue is a constant approximation to $R(\hat{x})$?}
 
+Note that when $\hat{x} = (1,\ldots,1)$, \eqref{eq:ea} does not further
+constrain Problem~\ref{eq:opt}, i.e. the constraint is trivially satisfied.  In
+this case, as discussed above, the mechanism described in \cite{babaioff}
+provides a 6-approximation to $R((1,...,1))$.
+
 \section{Importance of the Problem and Possible Approach}
+
 \paragraph{} One reason why one might want to consider this problem is that it
 can be used as a building block for more general mechanisms. Indeed, in
 \cite{alaei}, Alaei shows that under fairly general assumptions, given an
@@ -125,20 +128,6 @@ 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}$.
 
-It is interesting to consider two specific cases for which we already have an
-answer to our problem:
-\begin{itemize}
-    \item when $\hat{x} = (1,\ldots,1)$, \eqref{eq:ea} does not further
-        constrain Problem~\ref{eq:opt}, i.e. the constraint is trivially satisfied. 
-        In this case, as discussed above, the
-        mechanism described in \cite{babaioff} provides a 6-approximation to $R((1,...,1))$.
-    \item when $\hat{x} = \left(\frac{1}{m},\ldots,\frac{1}{m}\right)$, by
-        summing the constraint \eqref{eq:ea} for all $i\in[m]$, we see that the
-        ex-ante allocation constraint implies that in expectation, no more than
-        one item is sold to the agent. This is exactly the ex-ante relaxation
-        of the unit-demand case for which a 2-approximation to $R\left(
-        \left(\frac{1}{m},\ldots,\frac{1}{m}\right)\right)$ is already known.
-\end{itemize}
 
 In the general case, a candidate simple mechanism suggested by Jason Hartline
 is the following: the buyer is charged a price $p_0$ to participate in the
@@ -148,9 +137,26 @@ discussed in \cite{armstrong}. Our problem is then to understand how to set
 $p_0$ and the posted prices $p_1,\ldots, p_m$ such that in expectation over the
 agent's type, item $i$ is sold with probability $x_i\leq \hat{x}_i$.
 
-\section{Two-Part Tariffs and Optimal Pricing}
-
-\section{The Core Decomposition Lemma}
+\section{Roadmap}
+
+Here are the steps we plan to execute before the completion of our project.
+
+\begin{enumerate}
+    \item work out simple examples for which we will be able to do exact
+        computation on the proposed two-part mechanism. The goal is to obtain
+        a ``proof-of-concept'' that this mechanism can yield, at least in some
+        cases, a constant approximation to the optimal revenue.
+    \item prove (or disprove) that this two-part mechanism achieves
+        a constant-approximation for any product distribution $F$.
+    \item by then, we should have a better understanding of two-part tariff
+        ideas. Use this understanding to re-interpret the results from
+        \cite{yao} as two-part tariff mechanisms. Indeed, it seems that many
+        mechanisms in this paper have a ``two-part'' structure (entrance fee
+        plus separate prices) and could benefit from this re-interpretation.
+\end{enumerate}
+
+In terms of timeline, we estimate that these steps will take us until beginning
+of January 2015.
 
 \bibliographystyle{abbrv}
 \bibliography{main}
-- 
cgit v1.2.3-70-g09d2

