diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 8 |
1 files changed, 6 insertions, 2 deletions
diff --git a/final/main.tex b/final/main.tex index be71cd9..6678f08 100644 --- a/final/main.tex +++ b/final/main.tex @@ -194,7 +194,7 @@ $\gamma$ is a constant which is at least $\frac{1}{2}$. \section{A Two-Part Tariff Mechanism} \subsection{Definition of the Mechanism} - +\label{subsec:mechanism} Given the simplicity of posted-price mechanisms and the fact that they are optimal in the single-agent single-item setting (for a regular distribution $F$), it would be desirable to obtain a mechanism as close as possible to posted-price. @@ -408,11 +408,15 @@ Finally, we show that $$\E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \ 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} +$$\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}; although their definitions are slightly different, the tail is meant to represent items that the buyer has a very high value for and the core consists of the tail's complement. In particular, \citep{babaioff} define the core for each $F_i$ as $t^*_i > k_i$, where $t^*_i$ is the highest value that the buyer places on item $i$, and $k_i$ is chosen to appropriately separate the core and tail. This is done, as explained in \citep{babaioff}, Propostion 3, by setting $k_i = \SRev(F)$. This allows the revenue from the core and tail to be separately bounded, and leads to the desired constant approximation (with which of $\SRev(F)$ or $\BRev(F)$ is greater depending on the ratio of the welfare of the core to $\SRev(F)$). \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. +Now, let $\BRev_\beta(F)$ denote the revenue of the $\beta$-bundling mechanism introduced by \citep{yao}. We have already met this mechanism in Section \ref{subsec:mechanism}, as $\M$. The following lemma provides the relationship between the revenue of this mechanism and the revenue of the $\beta$-exclusive mechanism. + +\begin{lemma}[Theorem 6.1 in \citep{yao}, with a constant of 7 instead of 8.5] Let $F =F_1\times\dots\times F_m$, let $\BRev_\beta(F)$ denote the revenue of the $\beta$-bundling mechanism, and let $\Rev_\beta(F)$ denote the revenue of the optimal $\beta$-exclusive mechanism. Then, $$\Rev_\beta(F) \leq 7\cdot \BRev_\beta(F).$$ \end{lemma} + \section{Conclusion} \bibliographystyle{abbrvnat} |