diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 23 |
1 files changed, 11 insertions, 12 deletions
diff --git a/final/main.tex b/final/main.tex index a79a0bb..4eccb83 100644 --- a/final/main.tex +++ b/final/main.tex @@ -124,10 +124,11 @@ given by Equation \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))$. -We use the notation from \citep{alaei}, where $R(\hat{x})$ denotes the revenue +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 $R(\hat{x}, F)$. Finally, when +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. @@ -135,14 +136,12 @@ mechanism. The main question underlying this work can then be formulated as: -\paragraph{Problem.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is +\paragraph{Question.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is 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})$?} +$\hat{x}$ and whose revenue is a constant approximation to $\hat{R}(\hat{x})$?} \subsection{Examples and Motivations} -TODO: this section is mostly wrong, to be discussed. - \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 @@ -236,7 +235,7 @@ two-part tariff mechanism for an optimal choice of $\hat{v}$: \begin{displaymath} \TPRev(F) = \sup_{\hat{v}\in\R_+^{m+1}} \E_{t\sim F}[p(t, \hat{v})] \end{displaymath} -and by $\TPRev(\hat{x}, F)$ the best revenue which can be obtained by the +and by $\TPRev(\hat{x}, F)$ the best revenue which can be obtained by the two-part tariff mechanism with ex-ante allocation constraint $\hat{x}$: \begin{displaymath} \begin{split} @@ -245,7 +244,7 @@ two-part tariff mechanism with ex-ante allocation constraint $\hat{x}$: i\in[m]\\ \end{split} \end{displaymath} -The problem we introduced in Section~\ref{sec:intro} can then be formulated for +The question we introduced in Section~\ref{sec:intro} can then be formulated for the two-part tariff mechanism: \emph{is $\TPRev(\hat{x}, F)$ a constant approximation to $\Rev(\hat{x}, F)$?} @@ -253,9 +252,9 @@ The following simple Lemma shows that at least in the unconstrained case, the answer to the previous question is positive. In fact, the proof shows that the two-part tariff mechanism is rich enough to simulate both bundle pricing and separate posted pricing. Using the notation from \citep{babaioff}, let us write -$\BRev(F)$ the revenue obtained by the optimal grand bundle pricing and by -$\SRev(F)$ the revenue obtained by selling each item at its monopoly reserve -price, then we have: +$\BRev(F)$ for the revenue obtained by the optimal grand bundle pricing and +$\SRev(F)$ for the revenue obtained by selling each item at its monopoly reserve +price. Then we have: \begin{lemma} For any product distribution $F$, \begin{displaymath} @@ -264,7 +263,7 @@ price, then we have: \end{lemma} \begin{proof} - The second inequality is the main result from \citep{babaioff}, we will + The second inequality is the main result from \citep{babaioff}; we will thus only prove the first inequality. In the specific case where $\hat{v} = (0,\hat{v}_1,\dots,\hat{v}_m)$, |