diff options
| -rw-r--r-- | final/main.tex | 111 |
1 files changed, 90 insertions, 21 deletions
diff --git a/final/main.tex b/final/main.tex index f5ad43f..a79a0bb 100644 --- a/final/main.tex +++ b/final/main.tex @@ -36,6 +36,10 @@ \let\Pr\relax \DeclareMathOperator*{\Pr}{\mathbb{P}} \DeclareMathOperator*{\I}{\mathcal{I}} +\DeclareMathOperator*{\TPRev}{\textsc{TPRev}} +\DeclareMathOperator*{\Rev}{\textsc{Rev}} +\DeclareMathOperator*{\BRev}{\textsc{BRev}} +\DeclareMathOperator*{\SRev}{\textsc{SRev}} \newcommand{\inprod}[1]{\left\langle #1 \right\rangle} \newcommand{\R}{\mathbb{R}} @@ -114,11 +118,21 @@ Problem~\ref{eq:opt}: \E_{t\sim F}\big[x_i(t)] \leq \hat{x}_i,\quad\forall i\in[m] \end{equation} which expresses that the ex-ante allocation probability is upper-bounded by -$\hat{x}$. +$\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 +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 obtained by the optimal mechanism solution to Problem~\ref{eq:opt} with ex-ante -allocation constraint $\hat{x}$ given by \eqref{eq:ea}. The main question +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 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. + +The main question underlying this work can then be formulated as: \paragraph{Problem.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is @@ -127,10 +141,7 @@ $\hat{x}$ and whose revenue is a constant approximation to $R(\hat{x})$?} \subsection{Examples and Motivations} -\paragraph{}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 -this case, as discussed above, the mechanism described in \citep{babaioff} -provides a 6-approximation to $R((1,...,1))$. +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 @@ -161,7 +172,6 @@ polynomial time a mechanism for the multi-agent problem which is a $\gamma\cdot\alpha$ approximation to the revenue-optimal mechanism where $\gamma$ is a constant which is at least $\frac{1}{2}$. - \section{A Two-Part Tariff Mechanism} \subsection{Definition of the Mechanism} @@ -174,19 +184,20 @@ unconstrained, regular case, no posted-price mechanism for the single-agent problem has an approximation ratio better than $\Omega(\log n)$. Instead, we consider the following candidate mechanism suggested by Jason -Hartline: the buyer is charged a price $p_0$ to participate in the mechanism, -and then is offered each item separately with posted prices $p_1,\ldots, p_m$. -This is essentially the concept of a two-part tariff, as discussed in -\citep{armstrong}. +Hartline: the buyer is charged a price $\hat{v}_0$ to participate in the +mechanism, and then is offered each item separately with posted prices +$\hat{v}_1,\ldots, \hat{v}_m$. This is essentially the concept of a two-part +tariff, as discussed in \citep{armstrong}. -Note that as written above, the candidate mechanism is not individually -rational because the agent gets charged $p_0$ regardless of her type. To +Note that as described above, the candidate mechanism is not individually +rational because the agent gets charged $\hat{v}_0$ regardless of her type. To restore individual rationality, we need to have the agent pay only when \begin{displaymath} - \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 + \sum_{i=1}^m (t_i - \hat{v}_i)^+ \geq \hat{v}_0 \end{displaymath} where we used the notation $(x)^+\eqdef\max(x, 0)$, so that the -above inequality could also be written as $$\sum_{i: t_i\geq p_i} (t_i- p_i)\geq p_0.$$ +above inequality could also be written as $$\sum_{i: t_i\geq \hat{v}_i} (t_i- +\hat{v}_i)\geq \hat{v}_0.$$ We can now formally describe the candidate mechanism. @@ -199,21 +210,79 @@ We can now formally describe the candidate mechanism. \end{center} \begin{displaymath} \begin{cases} - x_i = \I[t_i \geq p_i],\; p = p_0 + \sum_i p_ix_i &\text{ if} \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 \\ - x_i = 0\text{ for all $i$},\; p = 0&\text{ otherwise } + x_i(t) = \I[t_i \geq \hat{v}_i],\; p(t) = \hat{v}_0 + \sum_i + \hat{v}_ix_i &\text{ if} \sum_{i=1}^m (t_i - \hat{v}_i)^+ \geq + \hat{v}_0 \\ + x_i(t) = 0\text{ for all $i$},\; p(t) = 0&\text{ otherwise } \end{cases} \end{displaymath} \vspace{1em} \end{minipage} } \end{center} - where we use the notation $\I[\text{expression}]$ to denote the indicator -variable for the expression, which takes on value 1 when the expression is true and 0 otherwise. +variable for the expression, which takes on value 1 when the expression is true +and 0 otherwise. We note that this mechanism is exactly the $\beta$-bundle mechanism from -\citep{yao}, even though the interpretation in terms of entrance fee plus posted -prices is not explicit in this paper. +\citep{yao}, even though the interpretation as a two-part tariff is +not explicit in this 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})$ +the allocation rule and payment rule of the two-part tariff mechanism. We will use +$\TPRev(F)$ to denote the best expected revenue which can be obtained by the +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 +two-part tariff mechanism with ex-ante allocation constraint $\hat{x}$: +\begin{displaymath} + \begin{split} + \TPRev(\hat{x}, F) = \sup_{\hat{v}\in\R_+^{m+1}} &\E_{t\sim F}[p(t, \hat{v})]\\ + \text{s.t.} &\, \E_{t\sim F}[x_i(t, \hat{v})]\leq \hat{x}_i,\quad \forall + i\in[m]\\ +\end{split} +\end{displaymath} +The problem 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)$?} + +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: + +\begin{lemma} For any product distribution $F$, + \begin{displaymath} + \TPRev(F)\geq \max\{\BRev(F), \SRev(F)\}\geq 6\cdot \Rev(F). + \end{displaymath} +\end{lemma} + +\begin{proof} + 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)$, + \emph{i.e} $\hat{v}_0 = 0$, there is no entrance fee and the two-part + tariff mechanism simply sells each item separately in a take-it-or-leave-it + manner. For the optimal choice of $(\hat{v}_1,\dots,\hat{v}_m)$, the + revenue of the mechanism reaches $\SRev(F)$. Since the supremum defining + $\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 + simply sells all the item 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 + previous paragraph, this implies that $\TPRev(F)\geq \BRev(F)$. +\end{proof} + +\subsection{Computational Considerations} \subsection{$p$-exclusivity} |