Create new section on reductions and move the stuff on BGR there

1 files changed, 19 insertions, 2 deletions

diff --git a/final/main.tex b/final/main.tex
index adde64f..36f0b04 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -305,8 +305,6 @@ consistent notations.} is defined as follows: for a vector $p = (p_1,\dots,p_m)$
 a mechanism is said to be $p$-exclusive if $x_i = 0$ whenever $p_i > t_i$. This
 is essentially saying that there is a reserve price for each item.
 
-The notion of $p$-exclusivity introduced by \citep{yao} was crucial in his reduction
-from the $k$-item $m$-buyer setting to the $k$-item single buyer setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which conducts $m$ single-buyer $k$-item auctions, using an IR-IC $p$-exclusive mechanism, for a particular value of $p$ drawn from the joint bid distribution 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 $k$-item, $m$-buyer 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.
 
 $p$-exclusivity
 can easily be enforced in the optimization we formulated in Section~\ref{sec:intro},
@@ -324,6 +322,25 @@ Lemma.
     = \big(F^{-1}(1-p_1), \dots, F^{-1}(1-p_m)\big).$$
 \end{lemma}
 
+\section{$n$-to-1 Bidders Reductions}
+
+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
+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.
+
+
+The notion of $p$-exclusivity introduced by \citep{yao} was crucial in his
+reduction from the $k$-item $m$-buyer setting to the $k$-item single buyer
+setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which
+conducts $m$ single-buyer $k$-item auctions, using an IR-IC $p$-exclusive
+mechanism, for a particular value of $p$ drawn from the joint bid distribution
+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 $k$-item, $m$-buyer
+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.
 
 \bibliographystyle{abbrvnat}
 \bibliography{main}