diff options
Diffstat (limited to 'final')
| -rw-r--r-- | final/main.tex | 12 |
1 files changed, 8 insertions, 4 deletions
diff --git a/final/main.tex b/final/main.tex index bf8e6c8..5508b59 100644 --- a/final/main.tex +++ b/final/main.tex @@ -60,6 +60,10 @@ \blfootnote{We are grateful to Jason Hartline who provided the original idea for this project.} +\begin{abstract} +In this paper, given the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$, we focus on finding a simple mechanism obeying the allocation constraint whose revenue is a constant approximation to the revenue of the optimal mechanism with this constraint. In particular, following a suggestion by J.D. Hartline, we define a mechanism based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then draw a connection with a technique from \citep{yao}, in which we relate this mechanism to a $p$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints. +\end{abstract} + \section{Introduction} \label{sec:intro} @@ -228,7 +232,7 @@ and 0 otherwise. We note that this mechanism is exactly the $\beta$-bundle mechanism from \citep{yao}, even though the interpretation as a two-part tariff is -not explicit in this paper. +not explicit in his paper. For a choice $\hat{v} = (\hat{v}_0,\hat{v}_1,\dots,\hat{v}_m)$ of the entrance fee and the posted prices, let us denote by $x(t, \hat{v})$ and $p(t, \hat{v})$ @@ -277,7 +281,7 @@ price. Then we have: $\TPRev(F)$ optimizes (in particular) over all $\hat{v}$, with $\hat{v}_0 = 0$, we have that $\TPRev(F)\geq \SRev(F)$. - When $\hat{v}_1=\dots=\hat{v}_m = 0$, the two part tariff mechanism then + When $\hat{v}_1=\dots=\hat{v}_m = 0$, the two-part tariff mechanism then simply sells all the items at price $\hat{v}_0$ whenever $\sum_{i=1}^m t_i\geq \hat{v}_0$, \emph{i.e} is a grand bundle pricing mechanism. For the optimal choice of $\hat{v}_0$, the revenue reaches $\BRev(F)$. As in the @@ -288,13 +292,13 @@ price. Then we have: \subsection{$p$-exclusivity} -As noted by \citep{yao}, the above mechanism has the additional property of being +As noted by \citep{yao}, the above mechanism $\M$ has the additional property of being $p$-exclusive, where $p$-exclusivity is defined as follows: 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\footnote{\citep{yao} actually uses the notation $\beta$-exclusive for the same thing, but we thought that $p$ was a more natural choice.} by \citep{yao} was crucial in his reduction -from the $k$-item n-buyer setting to the $k$-item single buyer setting. $p$-exclusivity +from the $k$-item $m$-buyer setting to the $k$-item single buyer setting. $p$-exclusivity can easily be enforced in the optimization we formulated in Section~\ref{sec:intro}, by adding the following non-linear constraints: \begin{displaymath} |