From d7e9fc9accc06f373793b3b6dae748387e865564 Mon Sep 17 00:00:00 2001
From: Paul <Paul@Pauls-MacBook-Air.local>
Date: Tue, 23 Sep 2014 15:41:57 -0400
Subject: Finished problem 4

---
 ps1/main.tex | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

(limited to 'ps1/main.tex')

diff --git a/ps1/main.tex b/ps1/main.tex
index d5290df..55c4971 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -217,10 +217,23 @@ $$\max \left[ \sum_i x_i\phi_i(v_i) -  c({\mathbf x}) \right].$$ According to th
 
 $$\begin{cases} \text {allocate to all agents if } &\sum_{i=1}^n \phi_i (v_i) \geq 0 \\ \text {allocate to none of the agents if } &\sum_{i=1}^n \phi_i (v_i) < 0\end{cases}$$
 
-\item If all of the agents' values are i.i.d. from U[0,1], then the agents' virtual functions are given by $$\phi_i(v_i) = (2v_i - 1),$$ and so we will allocate to all agents only if \begin{align*} &\sum_{i=1}^n (2v_i - 1) \geq 0 \\ &\implies \left(2\sum_{i=1}^n v_i \right)- n \geq 0 \\ &\implies \sum_{i=1}^n v_i \geq \frac{n}{2}. \end{align*} So to summarize, our mechanism is: 
+\item If all of the agents' values are i.i.d. from $U[0,1]$, then the agents' virtual functions are given by $$\phi_i(v_i) = (2v_i - 1),$$ and so we will allocate to all agents only if \begin{align*} &\sum_{i=1}^n (2v_i - 1) \geq 0 \\ &\implies \left(2\sum_{i=1}^n v_i \right)- n \geq 0 \\ &\implies \sum_{i=1}^n v_i \geq \frac{n}{2}. \end{align*} So to summarize, our mechanism is: 
 
 $$\begin{cases} \text {allocate to all agents if } &\sum_{i=1}^n v_i \geq \frac{n}{2} \\ \text {allocate to none of the agents if } &\sum_{i=1}^n v_i < \frac{n}{2}\end{cases}.$$
 
+\item Finally, we want to give an asymptotic expression for the expected revenue for the revenue-optimal mechanism, with all of the agents' values i.i.d. from $U[0,1].$ The key idea here is that if we want to consider the revenue for a single agent, then we can give a bound for that using the values of all of the other agents. So in particular, for $n$ agents,
+
+\begin{align}
+\E[\text{revenue}] &= \E\left[\sum_i p_i\right] \\
+&= \E\left[ \sum_i\left( \frac{n}{2} - \sum_{j \neq i} v_j \right) \right] \\
+&= \E\left[ \frac{n^2}{2} - \sum_i\sum_{j \neq i} v_j \right] \\
+&= \E\left[\frac{n^2}{2} - (n-1)\sum_i v_i\right] \label{eq:doublesum}\\
+&= \frac{n^2}{2} - (n-1)\frac{n}{2}\\
+&= \frac{n}{2}.
+\end{align}
+
+Note that \cref{eq:doublesum} follows from the previous step because each value is obtained exactly $n-1$ times in the double sum, and hence can be simplified to $(n-1)\sum_i v_i$.
+
 \end{enumerate}
 
 \end{document}
-- 
cgit v1.2.3-70-g09d2

