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