\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{\R}{\mathbb{R}}
\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} \frac{1}{2}\big(v_1+\frac{1}{2}\big) &\text{ if } v_1 > \frac{1}{2} \\ 0 &\text{ if } v_1  \leq \frac{1}{2} \end{cases}$$
Indeed, in expectation a uniform random variable evenly divides the interval it is over, and conditioned on $v_1\geq v_2$, $v_2$ is $U\big[\frac{1}{2},v_1\big]$. Thus, 
$$s_1(v_1) =  \begin{cases} \frac{1}{2}\big(v_1+\frac{1}{2}\big) &\text{ if } v_1 > \frac{1}{2} \\ 0 &\text{ if } v_1  \leq \frac{1}{2} \end{cases}.$$

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]  = \frac{v_2}{2}$$
since conditioned on $v_2\geq v_1$, $v_1$ is $U\big[0,v_2\big]$.

So $$s_2(v_2) = \frac{v_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{1}{2}$ and let $v_2 = \frac{3}{4}$. Then, $$s_1(v_1) = \frac{1}{2}\left(\frac{1}{2}+\frac{1}{2}\right) = \frac{1}{2}$$ but $$s_2(v_2) = \frac{3}{8}<\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}
By assumption, $s$ is strictly increasing. 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 the 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{equation}\label{eq:parts}
    \int_0^{v_i} F(z)dz = v_iF(v_i) - \int_0^{v_i}zf(z)d(z)
\end{equation}
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\footnote{The quantity $\int_{0}^{v_i}zf(z)dz$ can be naturally
    interpreted as the expected value of the other agent conditioned on the
    fact that is has value less than $v_i$, which is the payment in a second
    price auction. In fact, an alternative way to derive our candidate strategy
    would be to use revenue equivalence and equate the payments of our
    first-price mechanism for the position auction to the payments of the VCG
mechanism.}:
\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 increasing. 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 because the denominator is always
positive. Rearranging the terms, the numerator 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
rightmost parentheses is equal to $\int_0^{v_i}F(z)dz$ using the integration by
parts of \cref{eq:parts}.

As noted above, $s$ being increasing implies that the allocation rule of
the position auction with strategy $s$ is also increasing. By design, $s$
satisfies the payment identity of Theorem 2.10. 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 attained by $s$ are dominated. Since $s$ is
non-decreasing, its maximum value is:
\begin{displaymath}
s^* = \frac{w_1-w_2}{w_1}\int_{\R^+} zf(z)dz}
\end{displaymath}
Let us show that bids above $s^*$ are dominated by $s^*$. The utility of an
agent with value $v$ when bidding $s^*$ is $u = w_1\big(v-s^*\big)$ since he
will be allocated to the first position in this case. Then consider a bid
$b>s^*$; the utility in this case will be $u' = w_1(v-b)$ which is less than
$u$.

We have now established the uniqueness of a symmetric Bayes-Nash equilibrium.
Furthermore we can rule out the possibility of asymmetric strategy profiles by
applying verbatim the proof of Theorem 2.10.

\section*{Exercise 3.1}

We recall that the virtual value function for agent $i$ is defined as $$\phi_i(v_i) = v_i - \frac{1 - F_i(v_i)}{f_i(v_i)}$$ for a cumulative density function $F_i(v_i)$ and density function $f_i(v_i)$, with $F_i'(v_i) \stackrel{\text{def}}{=} f_i(v_i)$. The virtual function satisfies the following relationship:
\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*}
    \E\left[\sum_i \left(v_ix_i(v_i) - p_i(v_i)\right)\right] =  
    \sum_i\E\big[v_ix_i(v_i)-p_i(v_i)\big]
\end{align*}
Using \cref{eq:virt}, this is equal to:
\begin{displaymath}
    \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)$, 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 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 = 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}

\begin{enumerate}[(a)]

\item By the definition of virtual functions, we will maximize revenue when we maximize the virtual surplus (this follows from the definition $\E[p_i(v_i)] = \E[\phi_i(v_i)x_i(v_i)]$. Following Definition 3.5, we can do this via the VSM (VCG) mechanism. So in particular, we are trying to solve the following maximization problem:

$$\max \left[ \sum_i x_i\phi_i(v_i) -  c({\mathbf x}) \right].$$ According to the given cost structure (either every agent is served or none of the agents are served), this means that we will only allocate to the agents (to maximize revenue) when $$\sum_{i=1}^n \phi_i (v_i) \geq 0,$$ because otherwise we can allocate to none of the agents and have revenue of $0$. So to summarize our mechanism is as follows:

$$\begin{cases} \text {allocate to all agents if } &\sum_{i=1}^n \phi_i (v_i) \geq 0 \\ \text {allocate to none of the agents if } &\sum_{i=1}^n \phi_i (v_i) < 0\end{cases}$$

\item If all of the agents' values are i.i.d. from $U[0,1]$, then the agents' virtual functions are given by $$\phi_i(v_i) = (2v_i - 1),$$ and so we will allocate to all agents only if \begin{align*} &\sum_{i=1}^n (2v_i - 1) \geq 0 \\ &\implies \left(2\sum_{i=1}^n v_i \right)- n \geq 0 \\ &\implies \sum_{i=1}^n v_i \geq \frac{n}{2}. \end{align*} So to summarize, our mechanism is: 

$$\begin{cases} \text {allocate to all agents if } &\sum_{i=1}^n v_i \geq \frac{n}{2} \\ \text {allocate to none of the agents if } &\sum_{i=1}^n v_i < \frac{n}{2}\end{cases}.$$

\item Finally, we want to give an asymptotic expression for the expected revenue for the revenue-optimal mechanism, with all of the agents' values i.i.d. from $U[0,1].$ The key idea here is that if we want to consider the revenue for a single agent, then we can give a bound for that using the values of all of the other agents. So in particular, for $n$ agents,

\begin{align}
\E[\text{revenue}] &= \E\left[\sum_i p_i\right] \\
&= \E\left[ \sum_i\left( \frac{n}{2} - \sum_{j \neq i} v_j \right) \right] \\
&= \E\left[ \frac{n^2}{2} - \sum_i\sum_{j \neq i} v_j \right] \\
&= \E\left[\frac{n^2}{2} - (n-1)\sum_i v_i\right] \label{eq:doublesum}\\
&= \frac{n^2}{2} - (n-1)\frac{n}{2}\\
&= \frac{n}{2}.
\end{align}

Note that \cref{eq:doublesum} follows from the previous step because each value is obtained exactly $n-1$ times in the double sum, and hence can be simplified to $(n-1)\sum_i v_i$.

\end{enumerate}

\end{document}