From 6dc05314e2b6d6caef4a69634cb8e472cc4f6708 Mon Sep 17 00:00:00 2001 From: Paul Date: Fri, 15 May 2015 02:09:48 -0400 Subject: Adding more stuff --- final/main.tex | 29 +++++++++++++++++++++++++---- 1 file changed, 25 insertions(+), 4 deletions(-) diff --git a/final/main.tex b/final/main.tex index bc8917b..6d5b6b6 100644 --- a/final/main.tex +++ b/final/main.tex @@ -384,7 +384,7 @@ mechanism, for a particular value of $\beta$ drawn from the joint bid distributi over all buyers conditioned on the bids of all other buyers, and then combines this with the Vickrey second-price auction, showing that this mechanism has revenue that is a constant approximation to the optimal $m$-item, $n$-buyer -mechanism. He then defines another mechanism, \emph{Second-Price Bundling}, +mechanism. He also defines a mechanism known as \emph{Deterministic Best-Guess Reduction}, in which the $\beta$-exclusive mechanism from \emph{Best-Guess Reduction} is replaced with a $\beta$-bundling mechanism. He then defines another mechanism, \emph{Second-Price Bundling}, which is meant to heuristically approximate this combined mechanism, and shows that its revenue is also a constant approximation to the optimal mechanism. @@ -396,7 +396,8 @@ $$ F^+_{\beta,i} = \begin{cases} F_i | (F_i > \beta_i) &\text{if } \xi_i = 1 \\ Intuitively, this defines a transformation of the distribution $F$ using $\beta$ which can then be used in the following lemma to relate the revenue of the optimal $\beta$-exclusive mechanism to the revenue of the optimal mechanism. This new distribution $F_\beta^+$, which has support $[\beta_1,\infty) \times \cdots \times [\beta_m,\infty)$, is then shifted, so that the distribution $F_\beta^+ - \beta$ has support $[0,\infty) \times \cdots \times [0,\infty) = [0,\infty)^k$. \begin{lemma}[Lemma 6.1 in \citep{yao}] -Let $F =F_1\times\dots\times F_m$, and let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. Let $$\xi(F) = (\Pr[t_1> \beta_1],...,\Pr[t_m > \beta_m]).$$ Then, $$Rev_\beta(F) \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ \begin{proofsketch} Let $M$ be an IR-IC $\beta$-exclusive mechanism with allocation rule $x(t)$ and payment rule $p(t)$. The goal is to prove that $$ \Rev_\beta(F) \leq \E_{t \sim F}[(p(t)] \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta)$$. +\label{xilemma} +Let $F =F_1\times\dots\times F_m$, and let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. Let $$\xi(F) = (\Pr[t_1> \beta_1],...,\Pr[t_m > \beta_m]).$$ Then, $$Rev_\beta(F) \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ \begin{proofsketch} Let $M$ be an IR-IC $\beta$-exclusive mechanism with allocation rule $x(t)$ and payment rule $p(t)$. The goal is to prove that $$ \Rev_\beta(F) \leq \E_{t \sim F}[(p(t)] \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ First, we establish that \begin{align*} \Rev_\beta(F) \leq \E_{t \sim F}[p(t)] &= \E_{t \sim F}[\beta\cdot x(t)] + \E_{t \sim F}[p(t) - \beta\cdot x(t)] \\ &= \beta \cdot \xi(F) + \E_{t \sim F}[p(t) - \beta \cdot x(t)]. \end{align*} The first inequality follows from the definition of $\beta$-exclusivity, namely that the revenue of a $\beta$-exclusive mechanism is upper-bounded by the revenue of a mechanism with the same type distribution, payment rule, allocation rule, but $\beta = (1,...,1)$. @@ -405,7 +406,7 @@ 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: +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 since \citep{yao}): \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}; 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} @@ -417,7 +418,27 @@ Now, let $\BRev_\beta(F)$ denote the revenue of the $\beta$-bundling mechanism i \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} -Now, to summarize the results of these lemmas, we have shown that there is a constant approximation to the r +Now, to summarize the results of these lemmas, we have shown that the revenue of the optimal $\beta$-exclusive mechanism is a constant approximation to the revenue of the $\beta$-bundling mechanism, which is related to the optimal revenue via the transformation of $F$ described in Lemma \ref{xilemma}. + +Next, we define the Best-Guess Reduction mechanism (BGR for short), and let $\Rev_{BGR}(F)$ denote its revenue. Let $B_{(-i,j)}$ denote the maximum bid by all buyers except for buyer $i$ for item $j \in [m]$. Then, the vector of these is denoted by $$B_{-i} \eqdef \left(B_{(-i,1)},..,B_{(-i,m)}\right).$$ In this mechanism, the goal of selling $m$ heterogeneous buyers goods to $n$ bidders is achieved by running, for each $i \in [n]$, a single-bidder, $m$-unit $B_{-i}$-exclusive mechanism\footnote{Using the bids of everyone else to set the mechanism for a bidder has the flavor of peer prediction with proper scoring rules.}. Let $p_{2nd}(t)$, $t \sim F$ denote the payment rule under the Vickrey second-price mechanism, and let $$\Rev_{2nd}(F) \eqdef \E_{t \sim F} p_{2nd}(t).$$ Then, the following mechanism, which we call $\text{BGR}^+$ (\citep{yao} calls it \emph{BG}) is defined as follows: + +$$\text{BGR}^+ \eqdef \begin{cases} \text {if } \Rev_{BGR}(F) \geq \Rev_{2nd}(F) \text{ use BGR} \\ \text{if } \Rev_{BGR}(F) < \Rev_{2nd}(F) \text{ use Vickrey 2nd price mechanism} \end{cases}$$ + +The revenue of this mechanism, $\Rev_{\text{BGR}^+}$ is related to the revenue of the revenue of the optimal mechanism via the following lemma: + +\begin{lemma}[\citep{yao}, combination of Theorem 2 and Theorem 5.2, with improved constant based on \citep{babaioff}] +\ \\ +Let $F =F_1\times\dots\times F_m$. Then, $$\Rev(F) \leq 8\cdot \Rev_{\text{BGR}^+}(F)$$\end{lemma} + +The deterministic version of the BGR mechanism, which we call DBGR, can be defined by using the $B_{-i}$-bundling mechanism instead of the $B_{-i}$-exclusive mechanism, as in BGR (\citep{yao}, Section 3). Then, define the following mechanism, analogously to $\text{BGR}^+$: + +$$\text{DBGR}^+ \eqdef \begin{cases} \text {if } \Rev_{DBGR}(F) \geq \Rev_{2nd}(F) \text{ use DBGR} \\ \text{if } \Rev_{DBGR}(F) < \Rev_{2nd}(F) \text{ use Vickrey 2nd price mechanism} \end{cases}$$ + +If we denote the revenue from this mechanism by $\Rev_{\text{DBGR}^+}(F)$, then it is also a constant approximation of the optimal revenue: + +\begin{lemma}[\citep{yao}, combination of Theorem 3 and Corollary to Theorem 2] \ \\ Let $F =F_1\times\dots\times F_m$. Then, $$\Rev(F) \leq 69 \cdot \Rev_{\text{DBGR}^+}(F)$$ \end{lemma} + +While this mechanism \section{Conclusion} -- cgit v1.2.3-70-g09d2