diff options
Diffstat (limited to 'ps1')
| -rw-r--r-- | ps1/main.tex | 71 |
1 files changed, 51 insertions, 20 deletions
diff --git a/ps1/main.tex b/ps1/main.tex index 5dfca98..5ee2ece 100644 --- a/ps1/main.tex +++ b/ps1/main.tex @@ -315,40 +315,71 @@ And the payments can be computed using \cref{eq:pay} and the fact that $\phi^{-1 \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].$ +\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] + \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}: - +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}$. Hence: \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] +\E[\text{revenue}] += \E\left[ I_n\sum_{i=1}^n(2v_i-1)\right] += 2\E\left[I_n\sum_{i=1}^n v_i\right] - n\E[I_n] \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} +\begin{equation}\label{eq:prob} + \E[I_n] = \Pr\left[\sum_{i=1}^n v_i\geq\frac{n}{2}\right] = \frac{1}{2} +\end{equation} 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: +Now we have to compute $\E\left[I_n\sum_{i=1}^n 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. Let us define: +\begin{equation}\label{eq:xn} + X_n\eqdef \frac{1}{\sqrt{n}}\left(\sum_{i=1}^n v_i - \frac{n}{2}\right) +\end{equation} +By the central limit theorem, $X_n$ converges in distribution: \begin{displaymath} - \E\left[I_p\sum_i v_i\right] = \frac{n}{4} + O\left(\frac{1}{n\sqrt{n}}\right) + X_n\stackrel{d}{\rightarrow} X\sim\mathcal{N}\left(0,\frac{1}{12}\right) \end{displaymath} -Coming back to \cref{eq:rev} we get: +Note that: \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) + \E\left[I_nX_n] = \E\left[h(X_n)\right] \end{displaymath} -Asymptotically, we see that the revenue goes to zero and behaves like $\frac{1}{n\sqrt{n}}$. - - - +where $h(x) = \mathbf{1}_{x\geq 0}$ is the indicator function of $x$ being +non-negative. Using convergence in distribution: +\begin{equation}\label{eq:conv} + \E[h(X_n)] \rightarrow \E[h(X)] +\end{equation} +It is easy to compute $\E[h(X)]$ directly: +\begin{equation}\label{eq:lim} + \E[h(X)] = \sqrt{\frac{6}{\pi}}\int_0^{+\infty}x e^{-6x^2}dx + = \frac{1}{12}\sqrt{\frac{6}{\pi}}= \frac{1}{2\sqrt{6\pi}} \eqdef c +\end{equation} +\cref{eq:xn,eq:conv,eq:lim} together give: +\begin{displaymath} + \E[h(X_n)] = \frac{1}{\sqrt n} \E\left[I_n\sum_{i=1}^n v_i\right] + - \frac{1}{\sqrt{n}}\frac{n}{4}\rightarrow c +\end{displaymath} +Hence as $n$ goes to infinity: +\begin{equation}\label{eq:asymp} + \E\left[I_n\sum_{i=1}^n v_i\right] = \frac{n}{4} + c\sqrt{n} + o(\sqrt{n}) +\end{equation} +\cref{eq:rev,eq:prob,eq:asymp} together give: +\begin{displaymath} + \E[\text{revenue}] = \frac{n}{2} + 2c\sqrt{n} + o(\sqrt{n}) - \frac{n}{2} + = 2c\sqrt{n} + o(\sqrt{n}) +\end{displaymath} +As the number of agents goes to infinity, the revenue is $O(\sqrt{n})$. \end{enumerate} \end{document} |