Adding more stuff

1 files 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}