From ee9252a6175d5333ae1ea9bb2bf0b8b1b3c69210 Mon Sep 17 00:00:00 2001 From: Paul Date: Tue, 12 May 2015 16:53:45 -0400 Subject: Added details on Yao's BGR approach --- final/main.tex | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'final') diff --git a/final/main.tex b/final/main.tex index 5508b59..ec3e253 100644 --- a/final/main.tex +++ b/final/main.tex @@ -298,7 +298,9 @@ 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\footnote{\citep{yao} actually uses the notation $\beta$-exclusive for the same thing, but we thought that $p$ was a more natural choice.} by \citep{yao} was crucial in his reduction -from the $k$-item $m$-buyer setting to the $k$-item single buyer setting. $p$-exclusivity +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}, by adding the following non-linear constraints: \begin{displaymath} -- cgit v1.2.3-70-g09d2