[ps2] fixing 4.19 with basis exchange

1 files changed, 14 insertions, 10 deletions

diff --git a/ps2/main.tex b/ps2/main.tex
index 3321930..765c399 100644
--- a/ps2/main.tex
+++ b/ps2/main.tex
@@ -49,13 +49,17 @@
 \section*{Exercise 4.19}
 \begin{claim} In regular, matroid environments, the revenue of the surplus maximization mechanism with monopoly reserves is a 2-approximation to the optimal mechanism revenue.
 
-\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, we can write the expected revenue of the optimal mechanism by conditioning on whether $i = j$ for $i \in I$, $j \in J$. (i.e. whether agent $i$ is allocated the same item by the optimal mechanism as agent $j$ is by the surplus maximization mechanism; an alternate way of phrasing this is that the map $I \rightarrow J$ is an injection). So we can write $$REF = \underbrace{\sum_{\substack{i \in I \\ j \in J}}\E[\phi_i(v_i) | i = j] \Pr[i=j]}_{REF_=} + \underbrace{\sum_{\substack{i \in I \\ j \in J}}\E[\phi_i(v_i) | i \neq j] \Pr[i\neq j]}_{REF_{\neq}}.$$ We will prove the desired result by showing both $REF_=$ and $REF_{\neq}$ are bounded from above by APX. 
+\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, 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. 
 
 \begin{align}
-REF_= &= \sum_{\substack{i \in I \\ j \in J}}\E[\phi_i(v_i) | i = j] \Pr[i=j] \\
-&= \sum_{\substack{i \in I \\ j \in J}}\E[\phi_j(v_j) | i = j] \Pr[i=j] \\
-&\leq  \sum_{\substack{i \in I \\ j \in J}}\E[\phi_j(v_j) | i = j] \Pr[i=j] +  \sum_{\substack{i \in I \\ j \in J}}\E[\phi_j(v_j) | i \neq j] \Pr[i\neq j] \label{42}\\
-&= \sum_{j \in J}\E\left[\phi_j(v_j)\right] \\
+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] \\
 &= APX.
 \end{align}
 
@@ -64,11 +68,11 @@ Note that Equation $\ref{42}$ follows from Lemma 4.2 (i.e. from the monotonicity
 Next, we consider $REF_{\neq}$.
 
 \begin{align}
-REF_{\neq} &= \sum_{\substack{i \in I \\ j \in J}}\E[\phi_i(v_i) | i \neq j] \Pr[i\neq j] \\
-&\leq \sum_{\substack{i \in I \\ j \in J}}\E[v_i | i \neq j] \Pr[i\neq j] \\
-&\leq \sum_{\substack{i \in I \\ j \in J}}\E[\hat{v}_i | i \neq j] \Pr[i\neq j]  \\
-&= \sum_{\substack{i \in I \\ j \in J}}\E[v_j | i \neq j] \Pr[i\neq j] \label{428} \\
-&\leq \sum_{\substack{i \in I \\ j \in J}}\E[v_j | i = j] \Pr[i=j] +  \sum_{\substack{i \in I \\ j \in J}}\E[v_j | i \neq j] \Pr[i\neq j] \label{429} \\
+REF_{\neq} &= \sum_{\substack{i \in I}}\E[\phi_i(v_i) | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \\
+&\leq \sum_{\substack{i \in I}}\E[v_i | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \\
+&\leq \sum_{\substack{i \in I}}\E[\hat{v}_i | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}]  \\
+&= \sum_{\substack{i \in I}}\E[v_{\psi(i)} | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \label{428} \\
+&\leq \sum_{\substack{i \in I}}\E[v_{\psi(i)} | i = {\psi(i)}] \Pr[i={\psi(i)}] +  \sum_{\substack{i \in I}}\E[v_{\psi(i)} | i \neq {\psi(i)}] \Pr[i\neq {\psi(i)}] \label{429} \\
 &= APX.
 \end{align}