diff options
| -rw-r--r-- | ps1/main.tex | 10 |
1 files changed, 9 insertions, 1 deletions
diff --git a/ps1/main.tex b/ps1/main.tex index 943d0f5..60ed947 100644 --- a/ps1/main.tex +++ b/ps1/main.tex @@ -180,7 +180,15 @@ We recall that the virtual value function for agent $i$ is defined as $$\phi_i(v \begin{enumerate}[(a)] -\item By the definition of virtual functions, we will maximize revenue when we maximize the virtual surplus (this follows from the definition $\E[p_i(v_i)] = \E[\phi_i(v_i)x_i(v_i)]$. Following Definition 3.5, we can do this via the VSM (VCG) mechanism. +\item By the definition of virtual functions, we will maximize revenue when we maximize the virtual surplus (this follows from the definition $\E[p_i(v_i)] = \E[\phi_i(v_i)x_i(v_i)]$. Following Definition 3.5, we can do this via the VSM (VCG) mechanism. So in particular, we are trying to solve the following maximization problem: + +$$\max \left[ \sum_i x_i\phi_i(v_i) - c({\mathbf x}) \right].$$ According to the given cost structure (either every agent is served or none of the agents are served), this means that we will only allocate to the agents (to maximize revenue) when $$\sum_{i=1}^n \phi_i (v_i) \geq 0,$$ because otherwise we can allocate to none of the agents and have revenue of $0$. So to summarize our mechanism is as follows: + +$$\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: + +$$\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}.$$ \end{enumerate} |