Updates, including an additional reference

2 files changed, 38 insertions, 38 deletions

diff --git a/final/main.bib b/final/main.bib
index a50107a..aaf7c97 100644
--- a/final/main.bib
+++ b/final/main.bib
@@ -5,7 +5,7 @@
                S. Matthew Weinberg},
   title     = {A Simple and Approximately Optimal Mechanism for an Additive Buyer},
   journal   = {FOCS},
-  year      = {2014},
+  year      = {2014}
 }
 
 @article{yao,
@@ -13,11 +13,7 @@
   title     = {An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications},
   journal   = {CoRR},
   volume    = {abs/1406.3278},
-  year      = {2014},
-  url       = {http://arxiv.org/abs/1406.3278},
-  timestamp = {Tue, 01 Jul 2014 11:58:08 +0200},
-  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/Yao14},
-  bibsource = {dblp computer science bibliography, http://dblp.org}
+  year      = {2014}
 }
 
 @inproceedings{hart,
@@ -27,12 +23,7 @@
   booktitle = {{ACM} Conference on Electronic Commerce, {EC} '13, Philadelphia, PA,
                USA, June 16-20, 2013},
   pages     = {565--566},
-  year      = {2013},
-  url       = {http://doi.acm.org/10.1145/2482540.2482544},
-  doi       = {10.1145/2482540.2482544},
-  timestamp = {Mon, 24 Feb 2014 16:09:47 +0100},
-  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/HartN13},
-  bibsource = {dblp computer science bibliography, http://dblp.org}
+  year      = {2013}
 }
 
 @book{hartline,
@@ -51,11 +42,6 @@
   number    = {3},
   pages     = {143--263},
   year      = {2013},
-  url       = {http://dx.doi.org/10.1561/0400000045},
-  doi       = {10.1561/0400000045},
-  timestamp = {Wed, 23 Oct 2013 15:47:35 +0200},
-  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/fttcs/Hartline13},
-  bibsource = {dblp computer science bibliography, http://dblp.org}
 }
 
 @article{armstrong,
@@ -85,10 +71,17 @@
   booktitle = {{ACM} Conference on Electronic Commerce, {EC} '12, Valencia, Spain,
                June 4-8, 2012},
   pages     = {656},
-  year      = {2012},
-  url       = {http://doi.acm.org/10.1145/2229012.2229061},
-  doi       = {10.1145/2229012.2229061},
-  timestamp = {Mon, 24 Feb 2014 16:09:47 +0100},
-  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/HartN12},
-  bibsource = {dblp computer science bibliography, http://dblp.org}
+  year      = {2012}
+}
+
+@inproceedings{alaeietal,
+  author    = {Saeed Alaei and
+               Hu Fu and
+               Nima Haghpanah and
+               Jason D. Hartline},
+  title     = {The Simple Economics of Approximately Optimal Auctions},
+  booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
+               2013, 26-29 October, 2013, Berkeley, CA, {USA}},
+  pages     = {628--637},
+  year      = {2013},
 }
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}