From 20a34e518d8769e656e14fe7c9db8393fe2e959c Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 23 Sep 2014 21:52:04 -0400
Subject: End of 3.1

---
 ps1/main.tex | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 87 insertions(+), 11 deletions(-)

(limited to 'ps1/main.tex')

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$. 
-
-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
-
+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}
+
+\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}
 
-- 
cgit v1.2.3-70-g09d2

