From d6f37b602c4ff199159da2862d31de2e8a8710b4 Mon Sep 17 00:00:00 2001
From: Paul <Paul@Pauls-MacBook-Air.local>
Date: Mon, 22 Sep 2014 22:57:41 -0400
Subject: Finished first problem.

---
 ps1/main.tex | 25 +++++++++++++++++++++----
 1 file changed, 21 insertions(+), 4 deletions(-)

(limited to 'ps1/main.tex')

diff --git a/ps1/main.tex b/ps1/main.tex
index 23f5fb7..7b595c1 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -51,13 +51,13 @@ For agent 1, $$\Pr[v_1 \geq v_2] = \begin{cases} 1 &\text{ if } v_1 > \frac{1}{2
 
 $$P_1^{FP}(v_1) = s_1(v_1)\cdot \Pr[v_1 \geq v_2] = s_1(v_1) \cdot  \begin{cases} 1 &\text{ if } v_1 > \frac{1}{2} \\ v_1 &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$
 
-For agent 1, $P_1^{SP}(v_1)$ equals $\E[v_2|v1\geq v2]\cdot \Pr[v_1 \geq v_2]$. By Revenue Equivalence (Corollary 2.5), for $i \in \{1,2\}$, $P_i^{SP}(v_i) = P_i^{FP}(v_i)$. 
+For agent 1, $P_1^{SP}(v_1)$ equals $\E[v_2|v_1\geq v_2]\cdot \Pr[v_1 \geq v_2]$. By Revenue Equivalence (Corollary 2.5), for $i \in \{1,2\}$, $P_i^{SP}(v_i) = P_i^{FP}(v_i)$. 
 
-We directly compute $$\E[v_2|v1\geq v2] =  \begin{cases} \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ \frac{v_1}{2} &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$
+We directly compute $$\E[v_2|v_1\geq v_2] =  \begin{cases} \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ \frac{v_1}{2} &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$
 
 Combining this, we get
 
-$$P_1^{SP}(v_1) = \E[v_2|v1\geq v2]\cdot \Pr[v_1 \geq v_2] = \begin{cases} \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ \frac{v_1^2}{2} &\text{ if } v_1  \leq \frac{1}{2} \end{cases}.$$ So we get $$s_1(v_1) = \begin{cases} \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ \frac{v_1}{2} &\text{ if } v_1  \leq \frac{1}{2} \end{cases}.$$ For agent 2, the only case to consider is $v_1 \leq \frac{1}{2}$ (since otherwise agent 2's probability of winning is 0). This case is exactly the same as for agent 1, conditioned on $v1 \leq \frac{1}{2}$. This leads to $$s_2(v_2) = \frac{v_2}{2}.$$ We need to show two more things: that the strategies we obtain satisfy the restriction that the item is allocated to the agent with the highest value, and that there are no other strategies that dominate the strategy profile described above.
+$$P_1^{SP}(v_1) = \E[v_2|v_1\geq v_2]\cdot \Pr[v_1 \geq v_2] = \begin{cases} \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ \frac{v_1^2}{2} &\text{ if } v_1  \leq \frac{1}{2} \end{cases}.$$ So we get $$s_1(v_1) = \begin{cases} \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ \frac{v_1}{2} &\text{ if } v_1  \leq \frac{1}{2} \end{cases}.$$ For agent 2, the only case to consider is $v_1 \leq \frac{1}{2}$ (since otherwise agent 2's probability of winning is 0). This case is exactly the same as for agent 1, conditioned on $v_1 \leq \frac{1}{2}$. This leads to $$s_2(v_2) = \frac{v_2}{2}.$$ We need to show two more things: that the strategies we obtain satisfy the restriction that the item is allocated to the agent with the highest value, and that there are no other strategies that dominate the strategy profile described above.
 
 If $v_1 > \frac{1}{2}$, then $v_1$ will bid $\frac{1}{4}$ which is greater than or equal to any bid that agent 2 may have, so agent 1 will be allocated the item. If $v_1 \leq \frac{1}{2}$ and $v_1 > v_2$ then $\frac{v_1}{2} > \frac{v_2}{2}$ and he will again be allocated the item. If $v_1 \leq \frac{1}{2}$ and $v_1 < v_2$ then $\frac{v_1}{2} < \frac{v_2}{2}$ and agent 2 will be allocated the item, as desired. 
 
@@ -65,7 +65,24 @@ Suppose that agent 1 bids greater than $\frac{1}{4}$. Then, his probability of w
 
 So we have demonstrated that there is a Bayes-Nash Equilibrium.
 
-\item NO...
+\item We are analyzing the scenario when agent 1 has values in $U[0,1]$ and agent 2 has values in $U[\frac{1}{2},1]$. There are again two scenarios to consider: one in which agent 1's value exceeds $\frac{1}{2}$, and one in which his value is less than $\frac{1}{2}$. In the first scenario, agent 1 will always lose (i.e. agent 2 will always win).
+
+For agent 1,$$\Pr[v_1 \geq v_2] = \begin{cases} \int_{\frac{1}{2}}^{v_1} 2\,dx = 2v_1 -1 &\text{ if } v_1 > \frac{1}{2} \\ 0 &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$ $$P_1^{FP}(v_1) = s_1(v_1)\cdot \Pr[v_1 \geq v_2] = s_1(v_1) \cdot  \begin{cases} 2v_1 - 1 &\text{ if } v_1 > \frac{1}{2} \\ 0 &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$
+
+For agent 1, $P_1^{SP}(v_1)$ equals $\E[v_2|v_1\geq v_2]\cdot \Pr[v_1 \geq v_2]$. By Revenue Equivalence (Corollary 2.5), for $i \in \{1,2\}$, $P_i^{SP}(v_i) = P_i^{FP}(v_i)$. 
+
+We directly compute $$\E[v_2|v_1\geq v_2] =  \begin{cases} \int_{\frac{1}{2}}^{v_1} 2x\,dx = v_1^2 - \frac{1}{4} &\text{ if } v_1 > \frac{1}{2} \\ 0 &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$
+
+Thus, 
+$$s_1(v_1) = v_1^2-\frac{1}{4} \text{ if } v_1 > \frac{1}{2}.$$
+
+For agent 2,  $$\Pr[v_2 \geq v_1] =  \int_{0}^{v_2}\,dx = v_2$$
+
+Computing $$\E[v_1|v_2\geq v_1] =  \int_0^{v_2} x\,dx = \frac{v_2^2}{2}$$
+
+So $$s_2(v_2) = \frac{v_2^2}{2}.$$
+
+We will show a counterexample to the requirement that the item it always allocated to the agent with the highest value. Specifically, we will exhibit a scenario where $v_1 < v_2$ but $s_1(v_1) > s_2(v_2)$ and so agent 1 will be allocated the item despite having a lower valuation. Let $v_1 = \frac{7}{8}$ and let $v_2 = 1$. Then, $$s_1(v_1) = \frac{49}{64} - \frac{16}{64} = \frac{33}{64}$$ but $$s_2(v_2) = \frac{1}{2.}$$ Therefore, no Bayes-Nash Equilibrium with the desired properties can exist.
 
 \end{enumerate}
 
-- 
cgit v1.2.3-70-g09d2

