1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage[capitalize, noabbrev]{cleveref}
\usepackage{paralist}
% these are compressed lists to help fit into a 1 page limit
\newenvironment{enumerate*}%
{\vspace{-2ex} \begin{enumerate} %
\setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
{\end{enumerate}}
\newenvironment{itemize*}%
{\vspace{-2ex} \begin{itemize} %
\setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
{\end{itemize}}
\newenvironment{description*}%
{\vspace{-2ex} \begin{description} %
\setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
{\end{description}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbb{P}}
\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
\newcommand{\llbracket}{[\![}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\author{Thibaut Horel \& Paul Tylkin}
\title{Economics 2099 Problem Set 1 -- Solutions}
\begin{document}
\maketitle
\section{Exercise 2.5}
\begin{enumerate}[(a)]
\item We are analyzing the scenario when agent 1 has values in $U[0,1]$ and agent $U[0,\frac{1}{2}]$. Informally, we are considering two different scenarios: 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 win.
We formalize this as follows. We first calculate the strategies for each agent.
Because we are looking for a Bayes-Nash equilibrium in which the item is always allocated to the agent with the highest value, we can consider $\Pr[v_1 \geq v_2]$ as the probability that the item is allocated to agent 1.
For agent 1, $$\Pr[v_1 \geq v_2] = \begin{cases} 1 &\text{ if } v_1 > \frac{1}{2} \\ v_1 &\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} 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|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} \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|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.
Suppose that agent 1 bids greater than $\frac{1}{4}$. Then, his probability of winning does not increase (it is 1 at a bid of $\frac{1}{4}$, and so he pays more without increasing the probability of winning (his utility strictly decreases with a higher bid). Suppose that agent 2 bids greater than $\frac{1}{4}$. Since the largest possible value that agent 2 can have is $\frac{1}{4}$, for any bid greater than $\frac{1}{4}$, he pays more than his value and hence his utility is negative.
So we have demonstrated that there is a Bayes-Nash Equilibrium.
\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}
\section{Exercise 2.10}
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}
|
