diff options
| -rw-r--r-- | final/main.tex | 49 |
1 files changed, 26 insertions, 23 deletions
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 |