From a8a2bcf92070104e41a5b1f285ee88bbc04fd678 Mon Sep 17 00:00:00 2001
From: Paul <Paul@Pauls-MacBook-Air.local>
Date: Mon, 20 Oct 2014 11:57:41 -0400
Subject: [ps2] fixing 4.19 even more

---
 ps2/main.tex | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

(limited to 'ps2/main.tex')

diff --git a/ps2/main.tex b/ps2/main.tex
index 692654c..d7c0a91 100644
--- a/ps2/main.tex
+++ b/ps2/main.tex
@@ -51,7 +51,7 @@
 
 \begin{proof} Let REF denote the optimal mechanism and its expected revenue and let APX denote the surplus maximization mechanism with monopoly reserves and its expected revenue. Similarly to the single-item case, we know that REF $\geq$ APX and want to show that REF $\leq$ 2APX. Let $I$ denote the set of agents allocated by the optimal mechanism and let $J$ denote the set of agents allocated by the surplus maximization mechanism with monopoly reserves. Then, $$REF = \E\left[\sum_{i \in I}\phi_i(v_i)\right]$$ and $$APX =  \E\left[\sum_{j \in J}\phi_j(v_j)\right].$$ By linearity of expectation, we can write this as $$REF = \sum_{i \in I}\E\left[\phi_i(v_i)\right]$$ and $$APX =  \sum_{j \in J}\E\left[\phi_j(v_j)\right].$$ 
 
-Now, let $\psi: I \rightarrow J$ be the map (bijection) with the following property: $I \backslash \{i\} \cup \{\psi(i)\}\text{ is feasible.}$ This is known as the \textit{matroid basis exchange property} - and says basically that $\psi(i) \in J$ is a possible replacement for $i \in I$.
+Now, let $\psi: I \rightarrow J$ be a map (bijection) with the following property: $I \backslash \{i\} \cup \{\psi(i)\}\text{ is feasible.}$ The existence of such a map is guaranteed by the \textit{matroid basis exchange property} - and says basically that $\psi(i) \in J$ is a possible replacement for $i \in I$.
 
 Now, we can write the expected revenue of the optimal mechanism by conditioning on whether $i = \psi(i)$ for $i \in I$, $\psi(i) \in J$. (i.e. whether agent $i$ is allocated the same item by the optimal mechanism as agent $\psi(i)$ is by the surplus maximization mechanism). So we can write $$REF = \underbrace{\sum_{\substack{i \in I}}\E[\phi_i(v_i) | i = \psi(i)] \Pr[i=\psi(i)]}_{REF_=} + \underbrace{\sum_{\substack{i \in I}}\E[\phi_i(v_i) | i \neq\psi(i)] \Pr[i\neq \psi(i)]}_{REF_{\neq}}.$$ We will prove the desired result by showing both $REF_=$ and $REF_{\neq}$ are bounded from above by APX. 
 
@@ -60,10 +60,11 @@ REF_= &= \sum_{\substack{i \in I}}\E[\phi_i(v_i) | i = {\psi(i)}] \Pr[i={\psi(i)
 &= \sum_{\substack{i \in I}}\E[\phi_{\psi(i)}(v_{\psi(i)}) | i = {\psi(i)}] \Pr[i={\psi(i)}] \\
 &\leq  \sum_{\substack{i \in I}}\E[\phi_{\psi(i)}(v_{\psi(i)}) | i = {\psi(i)}] \Pr[i={\psi(i)}] +  \sum_{\substack{i \in I}}\E[\phi_{\psi(i)}(v_{\psi(i)}) | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \label{42}\\
 &= \sum_{i\in I}\E\left[\phi_{\psi(i)}(v_{\psi(i)})\right] \\
+&= \sum_{j\in J}\E\left[\phi_{j}(v_{j})\right] \label{bijection1}\\
 &= APX.
 \end{align}
 
-Note that Equation $\ref{42}$ follows from Lemma 4.2 (i.e. from the monotonicity of virtual value functions).
+Note that Equation $\ref{42}$ follows from Lemma 4.2 (i.e. from the monotonicity of virtual value functions).  Equation $\ref{bijection1}$ follows because $\Psi$ is a bijection.
 
 Next, we consider $REF_{\neq}$.
 
@@ -73,10 +74,11 @@ REF_{\neq} &= \sum_{\substack{i \in I}}\E[\phi_i(v_i) | i \neq {\psi(i)}] \Pr[i\
 &\leq \sum_{\substack{i \in I}}\E[p_{\psi(i)}({\mathbf v}) | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \label{428} \\
 &\leq \sum_{\substack{i \in I}}\E[p_{\psi(i)}({\mathbf v}) | i = {\psi(i)}] \Pr[i={\psi(i)}] +  \sum_{\substack{i \in I}}\E[p_{\psi(i)}({\mathbf v}) | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \label{429} \\
 &= \sum_{i \in I} \E[p_{\psi(i)}({\mathbf v})] \\
+&= \sum_{j \in J}\E[p_j({\mathbf v})] \label{bijection2}\\
 &= APX.
 \end{align}
 
-Note that Equation $\ref{428}$ follows from Lemma 4.28 and Equation $\ref{429}$ follows from Theorem 4.29.
+Note that Equation $\ref{428}$ follows from Lemma 4.28 and Equation $\ref{429}$ follows from Theorem 4.29. Equation $\ref{bijection2}$ follows because $\Psi$ is a bijection.
 
 \end{proof}
 
-- 
cgit v1.2.3-70-g09d2

