Last minute changes, hope I didn't introduce additional mistakes

1 files changed, 43 insertions, 11 deletions

diff --git a/ps1/main.tex b/ps1/main.tex
index 84a6e7a..5dfca98 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -207,7 +207,7 @@ be the inverse of the hazard rate function:
 Note that by assumption, $h_i$ is non-increasing (since the harzard rate function
 is non-decreasing). Hence, we need to consider $\bar{h}_i$, the ironed virtual
 value function. Since $h_i$ is non-increasing, we have to apply the ironing
-procedure to the whole interval of values, leading to a constant ironed
+procedure to the whole interval of values\footnote{Indeed, in quantile space the virtual function will be non-decreasing, hence the cumulative virtual function will be convex. Taking the concave hull of this convex function will lead to joining by a line the values of the cumulative at the end points of the interval.}, leading to a constant ironed
 function $\bar{h}_i = a_i$. By construction of the ironing procedure, the
 integral of the virtual value function in quantile space must be maintained in
 quantile space:
@@ -300,22 +300,54 @@ $$\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}$$
 
+If the virtual functions are not monotone, we can apply the same mechanism by replacing the virtual functions by the ironed virtual functions. Finally, the payments of the mechanism are obtained by applying the inverse virtual function to the threshold virtual payments:
+\begin{equation}\label{eq:pay}
+    p_i = \phi^{-1}\big(-\sum_{j\neq i}\phi_j(0)\big)
+\end{equation}
+
 \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,
+And the payments can be computed using \cref{eq:pay} and the fact that $\phi^{-1}(v) = \frac{v+1}{2}$:
+\begin{equation}\label{eq:pay2}
+    p_i = \frac{n}{2} - \sum_{j\neq i} v_j
+\end{equation}
+
+
+\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].$
+\begin{displaymath}
+    \E[\text{revenue}] &= \E\left[\sum_i p_i\right] = \E\left[\sum_i\phi_i(v_i)x_i(v_i)\right]
+= \E\left[I_p\sum_i\phi_i(v_i)\right]
+\end{displaymath}
+where $I_p$ is the random indicator variable of the auction being allocated, that is, $I_p=1$ iff $\sum_i v_i\geq \frac{n}{2}$. Using \cref{eq:pay2}:
+
+\begin{equation}\label{eq:rev}
+\E[\text{revenue}] = \E\left[I_p\sum_i p_i\right] 
+    = \E\left[ I_p\sum_i(2v_i-1)\right]
+    = 2\E\left[I_p\sum_i v_i\right] - n\E[I_p]
+\end{equation}
+
+Now observe that:
+\begin{displaymath}
+    \E[I_p] = \Pr\left[\sum_i v_i\geq\frac{n}{2}\right] = \frac{1}{2}
+\end{displaymath}
+Since $\sum_i v_i$ is a symmetric random variable centered at $\frac{n}{2}$.
+
+Now we have to compute $\E\left[I_p\sum_i v_i\right]$. It is hard to obtain a closed-form formula, but we can obtain an asymptotic approximation when $n$ goes to infinity by observing that the sum of iid variables behaves like a normal distribution in the limit. This can be made formal by applying the central limit theorem: if we substract the mean and multiply by $n\sqrt{n}$ we should obtain a constant in the limit. We obtain:
+\begin{displaymath}
+    \E\left[I_p\sum_i v_i\right] = \frac{n}{4} + O\left(\frac{1}{n\sqrt{n}}\right)
+\end{displaymath}
+Coming back to \cref{eq:rev} we get:
+\begin{displaymath}
+    \E[\text{revenue}] = \frac{n}{2} -\frac{n}{2} +O\left(\frac{1}{n\sqrt{n}}\right) = 
+O\left(\frac{1}{n\sqrt{n}}\right)
+\end{displaymath}
+Asymptotically, we see that the revenue goes to zero and behaves like $\frac{1}{n\sqrt{n}}$.
+
+
 
-\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}