Added stuff

1 files changed, 12 insertions, 3 deletions

diff --git a/final/main.tex b/final/main.tex
index b778e23..d3a1cc8 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -52,6 +52,8 @@
 \newtheorem*{definition}{Definition}
 \newtheorem*{goal}{Goal}
 
+\newenvironment{proofsketch}[1][Proof Sketch]{\proof[#1]\mbox{}\\*}{\endproof}
+
 \author{Thibaut Horel \and Paul Tylkin}
 \title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}}
 \date{}
@@ -363,7 +365,7 @@ 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
 whenever there exists $i$ such that $t_i^{min}>0$.
 
-This example shows that the approximation ratio in step 1. described above is
+This example shows that the approximation ratio in step 1, described above, is
 in fact unbounded.
 
 \section{$n$-to-1 Bidders Reductions}
@@ -391,10 +393,17 @@ We will step through his results in greater detail, and also improve the approxi
 $$ 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.
+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. This new distribution $F_\beta^+$, which has support $[\beta_1,\infty) \times \cdots \times [\beta_m,\infty)$, is then shifted, so that the distribution $F_\beta^+ - \beta$ has support $[0,\infty) \times \cdots \times [0,\infty) = [0,\infty)^k$.
 
 \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 \cdot \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).$$ \begin{proofsketch} Let $M$ be an IR-IC $\beta$-exclusive mechanism with allocation rule $x(t)$ and payment rule $p(t)$. The goal is to prove that $$ \Rev_\beta(F) \leq \E_{t \sim F}[(p(t)] \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta)$$.
+
+First, we establish that \begin{align*} \Rev_\beta(F) \leq \E_{t \sim F}[p(t)] &= \E_{t \sim F}[\beta\cdot x(t)] + \E_{t \sim F}[p(t) - \beta\cdot x(t)] \\ &= \beta \cdot \xi(F) + \E_{t \sim F}[p(t) - \beta \cdot x(t)]. \end{align*} The first inequality follows from the definition of $\beta$-exclusivity, namely that the revenue of a $\beta$-exclusive mechanism is upper-bounded by the revenue of a mechanism with the same type distribution, payment rule, allocation rule, but $\beta = (1,...,1)$.
+
+Next, we define another mechanism, $M'$, such that $M'$ is also IR-IC, and has allocation rule $\tilde{x}(\tilde{t})$ and payment rule $\tilde{p}(\tilde{t})$, with $\tilde{t} \sim F_\beta^+$, so that we have $$\E_{t \sim F}[p(t) - \beta \cdot x(t)] \leq \E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})].$$
+
+Finally, we show that $$\E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})] \leq \Rev(F_\beta^+ - \beta),$$ where the mechanism $M''$ that has revenue given by $\Rev(F_\beta^+ - \beta)$ is also shown to be IR-IC.
+ \end{proofsketch}\end{lemma}
 
 \bibliographystyle{abbrvnat}
 \bibliography{main}