Writing Section 3.2

1 files changed, 8 insertions, 3 deletions

diff --git a/final/main.tex b/final/main.tex
index b49e959..b778e23 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -196,7 +196,7 @@ $\gamma$ is a constant which is at least $\frac{1}{2}$.
 Given the simplicity of posted-price mechanisms and the fact that they are
 optimal in the single-agent single-item setting (for a regular distribution
 $F$), it would be desirable to obtain a mechanism as close as possible to posted-price.
-Unfortunately, \citep{hart-nisan} showed that even in the
+However, \citep{hart-nisan} showed that even in the
 unconstrained, regular case, no posted-price mechanism for the single-agent
 problem has an approximation ratio better than $\Omega(\log n)$.
 
@@ -387,9 +387,14 @@ 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 begin with a definition and a key lemma:
-\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] \end{definition}
+\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] Let $F =F_1\times\dots\times F_m$, and let $t_i \sim F_i$. Let $$\Xi \sim \left(\text{Bernoulli}(t_1 > \beta_1),...,\text{Bernoulli}(t_m>\beta_m)\right),$$ i.e. $\xi_i$, which is defined to be the $i^{th}$ coordinate of a random variable with distribution $\Xi$, is 1 with probability $t_i>\beta_i$ and 0 otherwise. Then, let $F^+_\beta$ be defined as follows: the $i^{th}$ coordinate in $F^+_\beta$ is: 
+$$ F^+_{\beta,i} = \begin{cases}  F_i | (F_i > \beta_i) &\text{if } \xi_i = 1 \\ \beta_i &\text{otherwise}\end{cases}$$
+ \end{definition}
+
+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.
+
 \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}
+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).$$ \end{lemma}
 
 \bibliographystyle{abbrvnat}
 \bibliography{main}