diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 29 |
1 files changed, 14 insertions, 15 deletions
diff --git a/final/main.tex b/final/main.tex index 4ff3c12..57a3645 100644 --- a/final/main.tex +++ b/final/main.tex @@ -112,15 +112,6 @@ 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. -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} @@ -132,13 +123,21 @@ Problem~\ref{eq:opt}: \end{equation} 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 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 $\Rev((1,...,1),F)$. -The main question -underlying this work can then be formulated as: +Following \citep{hartline}, we use the notation $R(\hat{q})$ to denote the +revenue obtained by the optimal mechanism which serves with ex-ante allocation +probability equal to $\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. In this case, this case, as +discussed above, the mechanism described in \citep{babaioff} 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}$ and a type distribution $F$, is there a simple mechanism whose ex-ante allocation rule is upper-bounded by |