More things

1 files changed, 107 insertions, 36 deletions

diff --git a/final/main.tex b/final/main.tex
index 32d514d..ac8f87d 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -48,11 +48,14 @@
 
 \maketitle
 
-\section{Introduction}
-
 \blfootnote{We are grateful to Jason Hartline who provided the original idea
 for this project.}
 
+\section{Introduction}
+\label{sec:intro}
+
+\subsection{Problem}
+
 The exposition in this section draws from \cite{hartlinebayes}. We consider the
 problem of selling $m$ heterogeneous items to a single agent with additive
 utility. The type $t$ of the agent is drawn from a distribution $F$ over
@@ -117,51 +120,119 @@ underlying this work can then be formulated as:
 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
+\subsection{Examples and Motivations}
+
+\paragraph{}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{Single-item case.} 
+To make things more concrete, let us first look at the single-item case which
+is well understood. In this setting, $\hat{x}$ is a real number and the
+function $R(\hat{x})$ defined above is simply the revenue curve and turns out
+to be a very useful object to understand the revenue maximizing multiple-agent
+single-item auction (see \cite{hartline}, Chapter 3).
+
+In particular, if the type of the agent (her value) is drawn from a regular
+distribution, the posted price revenue curve is concave and equal to the
+revenue curve. In this case, the optimal mechanism which serves with ex-ante
+allocation probability $\hat{x}$ is a simple posted-price mechanism with price
+$p_{\hat{x}} = F^{-1}(1-\hat{x})$.
+
+\paragraph{Multiple-item case.} The multiple-agent multiple-item setting is not
+fully understood yet, but the revenue function $R(\hat{x})$ defined above still
+seems to play an important role in understanding the revenue optimal auction.
+For example, it is noted in \cite{alaei} that $R(\hat{x})$ is a concave
+function of $\hat{x}$. This allows to define a convex optimization program
+(where the objective function is the sum of the revenue curve for all agents)
+whose optimal value is an upper bound on the expected value of the
+multiple-agent revenue optimal mechanism.
+
+Furthermore, in the same paper, Alaei shows that under fairly general
+assumptions, given an $\alpha$-approximate mechanism for the single-agent,
+ex-ante allocation constrained problem it is possible to construct in
+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}
 
-\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
-$\alpha$-approximate mechanism for the single-agent, ex-ante allocation
-constrained problem it is possible to construct in 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}$.
+\subsection{Definition of the Mechanism}
 
+Given the simplicity of posted-price mechanisms and the fact that they are
+optimal in the single-agent single-item setting (for a regular distribution
+$F$), we would like a mechanism as close as possible to posted-price.
+Unfortunately, Hart and Nisan \cite{hart-nisan} showed that even in the
+unconstrained, regular case, no posted-price mechanism for the single-agent
+problem has an approximation ratio better than $\Omega(\log n)$.
 
-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
-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 \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$.
+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
+\cite{armstrong}.
 
-\section{Roadmap}
+Note that as written above, the candidate mechanism is not individually
+rational because the agent gets charged $p_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
+\end{displaymath}
+where we used the notation $(x)^+\eqdef\max\{x, 0\}$, so that the sum in the
+above inequality could also be written $\sum_{i: t_i\geq p_i} (t_i- p_i)$.
+
+We can now formally describe the candidate mechanism.
+
+\begin{center}
+\fbox{
+\begin{minipage}{0.9\textwidth}
+    \vspace{1em}
+\begin{center}
+    \textbf{Candidate mechanism for the single-agent problem}
+\end{center}
+    \begin{displaymath}
+        \begin{cases}
+            x_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 }
+        \end{cases}
+    \end{displaymath}
+    \vspace{1em}
+\end{minipage}
+}
+\end{center}
+where we used the Iverson bracket notation $[P]$ to denote the indicator
+variable of predicate $P$.
+
+We note that this mechanism is exactly the $\beta$-bundle mechanism from
+\cite{yao}, even though the interpretation in terms of entrance fee plus posted
+prices is not explicit in this paper.
+
+\subsection{$p$-exclusivity}
+
+As noted by Yao, the above mechanism has the additional property of being
+$p$-exclusive in the following sense: for a vector $p = (p_1,\dots,p_m)$
+a mechanism is said to be $p$-exclusive if $x_i = 0$ whenever $p_i > t_i$. This
+is essentially saying that there is a reserve price for each item.
+
+The notion of $p$-exclusivity introduced by Yao was crucial in his reduction
+from the multiple-buyer setting to the single buyer setting. $p$-exclusivity
+can easily be enforced in the problem we formulated in Section~\ref{sec:intro},
+by adding the following non-linear constraints:
+\begin{displaymath}
+    x_i(t_i - p_i)\geq 0,\quad \forall i\in[m] 
+\end{displaymath}
 
-Here are the steps we plan to execute before the completion of our project:
+$p$-exclusivity relates to ex-ante allocation constraints through the following
+Lemma.
 
-\begin{enumerate}
-    \item work out simple, illustrative 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}
+\begin{lemma}
+    If a mechanism is $p$-exclusive for some vector $p=(p_1,\dots, p_m)$, then
+    it satisfies the ex-ante allocation constraint defined by $\hat{x}
+    = \big(F^{-1}(1-p_1), \dots, F^{-1}(1-p_m)\big)$.
+\end{lemma}
 
-In terms of timeline, we estimate that these steps will take us until beginning
-of January 2015.
 
 \bibliographystyle{abbrv}
 \bibliography{main}