From df195b05cf9349bb0813f8d5c7e89b8e4dcc0e77 Mon Sep 17 00:00:00 2001 From: Paul Date: Thu, 14 May 2015 19:26:55 -0400 Subject: Updates. --- final/main.bib | 20 ++++++++++++++++++++ final/main.tex | 18 +++++++++++++----- 2 files changed, 33 insertions(+), 5 deletions(-) diff --git a/final/main.bib b/final/main.bib index aaf7c97..a51a843 100644 --- a/final/main.bib +++ b/final/main.bib @@ -85,3 +85,23 @@ pages = {628--637}, year = {2013}, } + +@article{liyao, + author = {Xinye Li and Andrew Chi{-}Chih Yao}, + title = {On revenue maximization for selling multiple independently distributed items}, + journal = {Proccedings of the National Academy of Sciences}, + volume = {110}, + number = {28}, + pages = {11232--11237}, + year = {2013}, +} + +@article{rubinstein, + author = {Aviad Rubinstein and + S. Matthew Weinberg}, + title = {Simple Mechanisms for a Combinatorial Buyer and Applications to Revenue + Monotonicity}, + journal = {CoRR}, + volume = {abs/1501.07637}, + year = {2015} +} diff --git a/final/main.tex b/final/main.tex index e5df90a..be71cd9 100644 --- a/final/main.tex +++ b/final/main.tex @@ -67,7 +67,7 @@ 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. +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 $\beta$-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} @@ -214,7 +214,7 @@ restore individual rationality, we need to have the agent pay only when \begin{displaymath} \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 +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 \hat{v}_i} (t_i- \hat{v}_i)\geq \hat{v}_0.$$ @@ -276,14 +276,14 @@ $\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{lemma} \label{tprevlemma} 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 + The second inequality is the main result from \citep{babaioff} and we will discuss it in more detail as Lemma \ref{babaiofflemma}; we will thus only prove the first inequality, which holds even without the assumption that $F$ is a product distribution. @@ -371,7 +371,7 @@ in fact unbounded. \section{$n$-to-1 Bidders Reductions} \label{sec:reduction} The goal of this section is to compare the two ways of constraining the single -buyer problem that we discussed: namely $p$-exclusivity and ex-ante allocation +buyer problem that we discussed: namely $\beta$-exclusivity and ex-ante allocation constraints and draw a parallel in how these two notions are used to construct $n$-to-1 bidders reductions in \citep{yao} and \citep{alaei} respectively. \subsection{\citep{alaei}'s Approach} @@ -405,6 +405,14 @@ Next, we define another mechanism, $M'$, such that $M'$ is also IR-IC, and has a Finally, we show that $$\E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})] \leq \Rev(F_\beta^+ - \beta),$$ where the mechanism $M''$ that has revenue given by $\Rev(F_\beta^+ - \beta)$ is also shown to be IR-IC. \end{proofsketch}\end{lemma} +Next, \citep{yao} quotes the following result from \citep{babaioff} (with the constant improved from $5 + \frac{3\sqrt{e}}{2} \approx 7.47$ to 6: + +\begin{lemma}[Theorem 2 in \citep{babaioff}; Lemma 6.2 in \citep{yao}] \label{babaiofflemma} Let $F =F_1\times\dots\times F_m$, let $\BRev(F)$ be the revenue obtained by the optimal grand bundle mechanism, treating the grand bundle as a single item, and let $\SRev(F)$ be the revenue obtained by selling each item separately at its monopoly reserve price. Then, +$$\Rev(F) \leq 6 \cdot \max\{\SRev(F), \BRev(F)\}.$$ \begin{proofsketch} Following \citep{liyao}'s notion of a Core Decomposition, \citep{babaioff} decompose the optimal revenue into the contributions from items in the \emph{core} and \emph{tail}. \end{proofsketch} + \end{lemma} + +As a side note, a version of this lemma for more general distributions was recently proved by \citep{rubinstein}, in which the authors show that when a single buyer has subadditive utility and type drawn from distribution $F$, then the revenue of the optimal auction on $m$ items has the following constant-factor approximation: $$\Rev(F) \leq 314 \cdot \SRev(F) + 24 \cdot \BRev(F).$$ They do this by also using the Core Decomposition lemma from \citep{liyao}. Extensions to multiple buyers are not currently known. It may be possible to also relate this to our problem with allocation constraints, and prove an analogue of Lemma \ref{tprevlemma} for a buyer with subadditive utility. + \section{Conclusion} \bibliographystyle{abbrvnat} -- cgit v1.2.3-70-g09d2