diff options
Diffstat (limited to 'ps1/main.tex')
| -rw-r--r-- | ps1/main.tex | 94 |
1 files changed, 85 insertions, 9 deletions
diff --git a/ps1/main.tex b/ps1/main.tex index a503471..5fd6d6a 100644 --- a/ps1/main.tex +++ b/ps1/main.tex @@ -184,6 +184,8 @@ We recall that the virtual value function for agent $i$ is defined as $$\phi_i(v \begin{equation}\label{eq:virt} \E[p_i(v_i)] = \E[\phi_i(v_i)x_i(v_i)]. \end{equation} + +\paragraph{Virtual value function} If the residual surplus is $$\sum_i \left(v_ix_i - p_i\right) - c({\mathbf x}),$$ where $x_i$ is the probability that agent $i$ will be allocated the item and $c({\mathbf x})$ is the service cost, and so if we want to maximize this, we are maximizing \begin{align*} @@ -195,24 +197,98 @@ Using \cref{eq:virt}, this is equal to: \sum_i\E\big[x_i(v_i)(v_i-\phi_i(v_i))\big] = \sum_i\E\big[x_i(v_i)h_i(v_i)\big] \end{displaymath} -where we defined $h_i(v_i)$ to be the inverse of the hazard rate function: +where we defined $h_i(v_i)$, our virtual value function for residual surplus to +be the inverse of the hazard rate function: \begin{displaymath} h_i(v_i) \eqdef \frac{1-F_i(v_i)}{f_i(v_i)} \end{displaymath} +\paragraph{Ironing} 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 function obtained -by ironing $h_i$. Since $h_i$ is non-increasing, we have to apply the ironing +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 -function $\bar{h}_i = c_i$. +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: +\begin{displaymath} + \int_0^1 h_i\big(F_i^{-1}(1-q)\big)dq = + \int_0^1 \bar{h}_i\big(F_i^{-1}(1-q)\big)dq = a_i +\end{displaymath} +We substitute $v$ for $F_i^{-1}(1-q)$ in the integration: +\begin{displaymath} +\int_{\R^+} h_i(v)f_i(v)dv = a_i +\end{displaymath} +By definition of $h_i$, we obtain: +\begin{displaymath} + a_i = \int_{\R^+} (1-F_i(v))dv = \E_{v\sim F_i}[v] +\end{displaymath} +\emph{The constant ironed virtual value functions are simply the expected +values.} + +\paragraph{Residual surplus maximizing mechanism} +By Theorem 3.20, the residual maximizing mechanism is simply the VSM mechanism +applied to the constants $(a_1,\ldots,a_n)$. In particular, the allocation rule +is obtained by maximizing $\sum_i x_i a_i - c(\mathbf{x})$. There are several +things to note about this mechanism: +\begin{itemize} + \item the bids of the agents are completely ignored. The allocation only + depends on the expected values of the agents and not on the reported + bids. + \item as a consequence, it is easy to see that truth telling is a dominant + strategy: since your bid is ignored by the mechanism, you might as well + report your true value. + \item the allocation rule is monotone, in fact it is constant since it does + not depend on the bids. + \item the payments are always zero. This follows from the fact if an agent + is allocated, he will be allocated no matter what he bids, hence his + threshold bid is zero. This also follows from the fact that the inverse + of the (constant) ironed virtual value functions are zero (using the + pseudo-inverse definition page 65 of the manuscript). Intuitively, it + is natural to have zero payments: since we are maximizing residual + surplus, we are only maximizing the utility of the bidders, which is + always higher when they don't have to pay. +\end{itemize} -By construction, the mechanism maximizing residual surplus is the VSM mechanism -where we use the $(c_1,\ldots,c_n)$ as virtual functions. Note that it is easy -to see in this case that truth telling is a dominant strategy equilibrium: the -mechanism ignores the bids of the players and only allocates based on the -ironed constants +\paragraph{Specific environments} We now consider three specific environments +in which the residual surplus maximizing mechanism defined above takes +a simpler form. +\begin{enumerate}[(a)] + \item For a single-item auction with i.i.d values. The expected values of + the agent are all equal. Let us denote by $V$ this common expected + value (that is, we have $a_i = V$ for all $i$). Since we can only + allocate to one agent $\sum_i a_ix_i - c(\mathbf{x})$ will always be + equal to $V$ no matter which agent we choose. As usual we break ties at + random. The mechanism in this case is simply a lottery: allocate to an + agent chosen uniformly at random (each agent has a probability + $\frac{1}{n}$ of being allocated) and charge her nothing. The residual + surplus in this case is $V$ which is clearly optimal. + \item For a single-item auction with non-identical values, the quantity + $\sum_i a_ix_i - c(\mathbf{x})$ is maximized when allocating to agent + $i$ with the largest $a_i$, that is the largest expected value. The + mechanism in this case has a simple form: allocate to the agent with + the largest expected value (break ties uniformly at random) and charge + her nothing. The residual surplus in this case is the largest expected + value which is clearly optimal. + + \item For non-identical values and a general cost $c$, we have to maximize + $\sum_i a_ix_i - c(\mathbf{x})$. The exact nature of this optimization + problem strongly depends on the cost function $c$. + + For example, if we think of $c$ as enforcing a budget constraint: + \begin{displaymath} + c(x)=\begin{cases} + 0& \mathrm{if} \sum_i x_i\leq B\\ + \infty&\mathrm{otherwise} + \end{cases} + \end{displaymath} + then our optimization problem becomes a fractional Knapsack problem for + which the optimal solution is easy to compute: order agents by + decreasing order of expected values and allocate to them in this order + until the budget is exhausted. +\end{enumerate} \section*{Exercise 3.4} |