From 75b0620a2cfcad75ae1d87094bee3dadb9b0a4af Mon Sep 17 00:00:00 2001
From: Paul <Paul@Pauls-MacBook-Air.local>
Date: Wed, 13 May 2015 14:00:18 -0400
Subject: Updates, including an additional reference

---
 final/main.tex | 37 ++++++++++++++++++++++---------------
 1 file changed, 22 insertions(+), 15 deletions(-)

(limited to 'final/main.tex')

diff --git a/final/main.tex b/final/main.tex
index ce27f47..b49e959 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -31,9 +31,10 @@
   \endgroup
 }
 
-\DeclareMathOperator*{\E}{\mathbb{E}}
+
+\DeclareMathOperator*{\E}{\mathbf{E}}
 \let\Pr\relax
-\DeclareMathOperator*{\Pr}{\mathbb{P}}
+\DeclareMathOperator*{\Pr}{\mathbf{P}}
 \DeclareMathOperator*{\I}{\mathcal{I}}
 \DeclareMathOperator*{\TPRev}{\textsc{TPRev}}
 \DeclareMathOperator*{\Rev}{\textsc{Rev}}
@@ -48,12 +49,15 @@
 
 \newtheorem{theorem}{Theorem}
 \newtheorem{lemma}{Lemma}
+\newtheorem*{definition}{Definition}
 \newtheorem*{goal}{Goal}
 
 \author{Thibaut Horel \and Paul Tylkin}
 \title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}}
 \date{}
 \begin{document}
+%include all references
+\nocite{*}
 
 \maketitle
 
@@ -306,10 +310,9 @@ essentially saying that there is a reserve price for each item.
 
 Theorem 6.1 from \citep{yao} shows that for an optimal choice of
 $\hat{v}_{-1}\geq \beta$ and $\hat{v}_0$, mechanism $\M$ described above is
-a constant $7$-approximation to the optimal $\beta$-exclusive mechanism.
+a constant $7$-approximation to the optimal $\beta$-exclusive mechanism. We will discuss this in greater detail in Section \ref{sec:reduction}.
 
-There is an easy one-way reduction from $\hat{x}$ ex-ante constrained
-mechanisms to $\beta$-exclusive mechanisms captured by the following Lemma.
+There is a one-way reduction from mechanisms with ex-ante constraint $\hat{x}$ to $\beta$-exclusive mechanisms captured by the following Lemma.
 
 \begin{lemma}
     If a mechanism is $\beta$-exclusive with $\beta\geq F^{-1}(1-\hat{x})$, then
@@ -331,11 +334,12 @@ This is true for all $i\in[m]$ so the mechanism satisfies the ex-ante
 allocation constraint $\hat{x}$.
 \end{proof}
 
+Let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. 
 One could hope to use this reduction to show that $\TPRev(\hat{x}, F)$ is
 a constant approximation to $\Rev(\hat{x}, F)$ by:
 \begin{enumerate}
     \item showing that the revenue of the optimal $\beta$-exclusive
-        mechanism with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation
+        mechanism, $\Rev_\beta(F)$, with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation
         to $\Rev(\hat{x}, F)$.
     \item using that $\M$ is a constant approximation to the optimal
         $\beta$-exclusive mechanism (Theorem 6.1 in \citep{yao}).
@@ -352,29 +356,29 @@ allocate any item and hence will have a revenue of $0$. Hence the optimal
 $\beta$-exclusive mechanism for $\beta = F^{-1}(1-\hat{x})$ will have revenue
 $0$.
 
-However, there is a very simple mechanism which satisfies the $\hat{x}$ ex-ante
-allocation constraint: regardless of the type, allocate each item $i\in [m]$
-with probability $\hat{x}_i$ at price $t_i^{min}\eqdef\min_{t_i\in T_i} t_i$.
+However, there is a very simple mechanism which satisfies the ex-ante
+allocation constraint $\hat{x}$: regardless of the type, allocate each item $i\in [m]$
+with probability $\hat{x}_i$ at price $$t_i^{min}\eqdef\min_{t_i\in T_i} t_i.$$
 This mechanism is clearly IR and IC, satisfies the constraint $\hat{x}$ and has
-expected revenue $\sum_{i\in [m]} \hat{x}_i t_i^{min}$. The revenue is positive
+expected revenue $$\sum_{i\in [m]} \hat{x}_i t_i^{min}.$$ The revenue is positive
 whenever there exists $i$ such that $t_i^{min}>0$.
 
 This example shows that the approximation ratio in step 1. described above is
 in fact unbounded.
 
 \section{$n$-to-1 Bidders Reductions}
-
+\label{sec:reduction}
 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.
 \subsection{\citep{alaei}'s Approach}
 \subsection{\citep{yao}'s Approach}
-The notion of $p$-exclusivity introduced by \citep{yao} was crucial in his
+The notion of $\beta$-exclusivity introduced by \citep{yao} was crucial in his
 reduction from the $m$-item $n$-buyer setting to the $m$-item single buyer
 setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which
-conducts $n$ single-buyer $m$-item auctions, using an IR-IC $p$-exclusive
-mechanism, for a particular value of $p$ drawn from the joint bid distribution
+conducts $n$ single-buyer $m$-item auctions, using an IR-IC $\beta$-exclusive
+mechanism, for a particular value of $\beta$ 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 $m$-item, $n$-buyer
@@ -382,7 +386,10 @@ 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.
 
-We will step through his results in greater detail, and also improve the approximation ratio in one of his lemmas, using the result from the published version of \citep{babaioff}.
+We will step through his results in greater detail, and also improve the approximation ratio in one of his lemmas, using the result from the published version of \citep{babaioff}. We begin with a definition and a key lemma:
+\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] \end{definition}
+\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 \xi(F) + \Rev(F_\beta^+ - \beta).$$ \end{lemma}
 
 \bibliographystyle{abbrvnat}
 \bibliography{main}
-- 
cgit v1.2.3-70-g09d2

