From 5f2f26abf7b9c74cdddd138410f12641c366ecf1 Mon Sep 17 00:00:00 2001
From: Paul <Paul@Pauls-MacBook-Air.local>
Date: Tue, 12 May 2015 13:53:45 -0400
Subject: R hat becomes REV and other changes

---
 final/main.tex | 49 ++++++++++++++++++++++++++-----------------------
 1 file changed, 26 insertions(+), 23 deletions(-)

(limited to 'final/main.tex')

diff --git a/final/main.tex b/final/main.tex
index 4eccb83..4bfff6e 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -108,7 +108,16 @@ 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
+Following \citep{hartline}, we use the notation $R(\hat{q})$ to denote the revenue obtained by the optimal mechanism as a function of equality constraint $\hat{q}$. 
+We slightly modify the notation from \citep{alaei} by replacing his $R$ with $\Rev$ and always making
+the type distribution $F$ explicit; so we will write $\Rev(\hat{x}, F)$, letting this denote 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}. Finally, when
+the ex-ante allocation constraint \eqref{eq:ea} is not present, we use $\Rev(F)
+\eqdef \Rev((1,\dots, 1), F)$ to denote the revenue of the revenue optimal IR-IC
+mechanism.
+
+We propose to extend the result of \citep{babaioff} by considering a more general version of
 Problem~\ref{eq:opt} where there is an additional \emph{ex-ante allocation
 constraint}. Formally, we are given a vector $\hat{x}
 = (\hat{x}_1,\ldots,\hat{x}_m)$ and we add the following constraint to
@@ -120,45 +129,39 @@ Problem~\ref{eq:opt}:
 which expresses that the ex-ante allocation probability is upper-bounded by
 $\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
+given by Problem \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))$.
-
-Following \citep{hartline}, we use the notation $R(x)$ to denote the revenue obtained by the optimal mechanism as a function of equality constraint $x$. 
-We slightly modify the notation from \citep{alaei} by replacing his $R$ with $\hat{R}$, and let $\hat{R}(\hat{x})$ denote 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}. When we want to make
-the type distribution $F$ explicit we will write $\hat{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.
+provides a 6-approximation to $\Rev((1,...,1),F)$.
 
 The main question
 underlying this work can then be formulated as:
 
-\paragraph{Question.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is
+\paragraph{Question.} \emph{Given an ex-ante allocation constraint $\hat{x}$ 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 $\hat{R}(\hat{x})$?}
+$\hat{x}$ and whose revenue is a constant approximation to $\Rev(\hat{x},F)$?}
 
 \subsection{Examples and Motivations}
 
 \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 make things more concrete, let us first look at the single-item case, which
+has already been studied extensively and is well-understood. In this setting, $\hat{x}$ is a real number and the
+function $\Rev(\hat{x},F)$ defined above is obtained by maximizing the revenue curve $R(\hat{x})$ subject to the allocation constraint, and turns out
 to be a very useful object to understand the revenue maximizing multiple-agent
 single-item auction (see \citep{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 the agent with ex-ante
-allocation probability $\hat{x}$ is a simple posted-price mechanism with price
-$p_{\hat{x}} = F^{-1}(1-\hat{x})$.
+distribution, the optimal mechanism which serves the agent with ex-ante
+allocation probability $\hat{x}$ has revenue $\Rev(\hat{x},F)$, given by solving \begin{align*}
+\max_{(x,p)} p(1-F(p)) \\
+\text{subject to }& 1 - F(p) \leq \hat{x} 
+\end{align*}
+
+which is a concave function.
 
 \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
+fully understood yet, but the revenue function $\Rev(\hat{x},F)$ defined above still
 seems to play an important role in understanding the revenue optimal auction.
-For example, it is noted in \citep{alaei} that $R(\hat{x})$ is a concave
+For example, it is noted in \citep{alaei} that $\Rev(\hat{x},F)$ is a concave
 function of $\hat{x}$. This allows us to define a convex optimization program
 (where the objective function is the sum of the revenue curves for all agents)
 whose optimal value is an upper bound on the expected value of the
-- 
cgit v1.2.3-70-g09d2

