Problem 2

1 files changed, 75 insertions, 1 deletions

diff --git a/ps1/main.tex b/ps1/main.tex
index 7b595c1..e45246d 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -88,5 +88,79 @@ We will show a counterexample to the requirement that the item it always allocat
 
 \section{Exercise 2.10}
 
-Characterization by Theorem 2.2. By Theorem 2.10, there are no asymmetric strategy profiles (there is a unique symmetric Bayes-Nash equilibrium).
+We first try to find a symmetric Bayes-Nash equilibrium. Let us assume that
+such a symmetric equilibrium exists and let us denote by $s$ the common
+strategy of the agents. Using the payment identity of Theorem 2.10, we have:
+\begin{displaymath}
+    p_i(v_i) = v_ix_i(v_i) - \int_0^{v_i} x_i(z)dz,\quad i\in\{1,2\}
+\end{displaymath}
+Since bidders pay their bids when they are served, we can write $p_i(v_i)
+= s(v_i)x_i(v_i)$ and obtain:
+\begin{equation}\label{eq:strag}
+    s(v_i) = v_i - \frac{\int_0^{v_i} x_i(z)dz}{x_i(v_i)},\quad i\in\{1,2\}
+\end{equation}
+
+We now compute $x_1(v_1)$; the situation being symmetric, $x_2(v_2)$ can be
+computed by replacing $1$ by $2$ and vice versa in what follows. By
+conditioning on whether agent $1$ wins, we get:
+\begin{displaymath}
+    x_1(v_1) = w_1 \Pr[s(v_1)\geq s(v_2)] + w_2\Pr[s(v_1)\leq s(v_2)]
+\end{displaymath}
+But note that if $s$ exists, it has to be non-decreasing (otherwise, this would
+contradict the fact that the allocation rule is non-decreasing by Theorem
+2.10). Hence, $\Pr[s(v_1)\geq s(v_2)] = \Pr[v_1 \geq v_2]$ and similarly,
+$\Pr[s(v_1) \leq s(v_2)] = \Pr[v_1\leq v_2]$. Now, denoting by $F$ the
+distribution of agent's values, we can rewrite:
+\begin{displaymath}
+    x_1(v_1) = w_1F(v_1) + w_2\big(1-F(v_1)\big) = w_2 + (w_1-w_2)F(v_1)
+\end{displaymath}
+Combining this with \cref{eq:strag} yields:
+\begin{displaymath}
+    s(v_i) = v_i - \frac{w_2v_i + (w_1 - w_2)\int_0^{v_i} F(z)dz}{w_2 + (w_1
+    - w_2)F(v_i)}
+\end{displaymath}
+Rearranging the right hand side, we get:
+\begin{equation}\label{eq:strag2}
+    s(v_i) = \frac{(w_1 - w_2)\big(v_iF(v_i) - \int_0^{v_i} F(z)dz\big)}{w_2 + (w_1
+    - w_2)F(v_i)}
+\end{equation}
+Finally, using integration by parts, we see that:
+\begin{displaymath}
+    \int_0^{v_i} F(z)dz = v_iF(v_i) - \int_0^{v_i}zf(z)d(z)
+\end{displaymath}
+where $f(z) = F'(z)$ denotes the density function of $F$. This, in addition to
+\cref{eq:strag2} leads to the following expression for our candidate strategy:
+\begin{displaymath}
+    \boxed{
+    s(v_i) = \frac{(w_1 - w_2)\big(\int_0^{v_i} zf(z)dz\big)}{w_2 + (w_1
+    - w_2)F(v_i)}
+}
+\end{displaymath}
+
+Let us now verify that $s$ is indeed non-decreasing. We compute:
+\begin{displaymath}
+    s'(v_i) = \frac{(w_1-w_2)v_if(v_i)\big(w_2 + (w_1-w_2)F(v_i)\big)
+    - (w_1-w_2)\big(\int_0^{v_i}zf(z)dz\big)(w_1-w_2)f(v_i)}{\big(w_2+(w_1-w_2)F(v_i)\big)^2}
+\end{displaymath}
+We only care about the sign of the numerator. Rearranging the terms, it is
+equal to:
+\begin{displaymath}
+    (w_1-w_2)w_2v_if(v_i) + (w_1-w_2)^2f(v_i)\left(v_iF(v_i)
+    - \int_0^{v_i}zf(z)dz\right)
+\end{displaymath}
+It is easy to see that this quantity is non-negative since the term inside the
+paranthesis is equal to $\int_0^{v_i}F(z)dz$ using the same integration by
+parts as above.
+
+As noted above, $s$ being non-decreasing implies that the allocation rule of
+the position auction with strategy $s$ is non-decreasing. By design, $s$
+satisfies the payment identity of Theorem 2.10. But we cannot conclude that $s$
+is a Bayes-Nash equilibrium yet because it is not onto. However, we can show
+that bids which are not in the image of $s$ are dominated. Since $s$ is
+non-decreasing, its maximum value is:
+\begin{displaymath}
+    s(1) = \frac{(w_1-w_2)\int_0^1 zf(z)dz}{w_1}
+\end{displaymath}
+
+By Theorem 2.10, there are no asymmetric strategy profiles (there is a unique symmetric Bayes-Nash equilibrium).
 \end{document}