diff options
Diffstat (limited to 'ps2')
| -rw-r--r-- | ps2/main.tex | 8 |
1 files changed, 5 insertions, 3 deletions
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} |