## Exercise 9

Use Myerson’s Lemma to prove that the Vickrey auction is the unique single-item auction that is DSIC, always awards the good to the highest bidder, and charges losers $0$

---

**Myersons Lemma**

Myersons Lemma for a single parameter environment consists of 3 Statements:

1. An allocation rule $x$ is implementable if and only if it is monotone.
2. If $x$ is monotone, then there is a unique payment rule such that the sealed-bid mecha-
nism $(x, p)$ is DSIC [assuming the normalization that: $bi = 0 \quad \text{implies} \quad pi(b) = 0$].
3. The payment rule in (b) is given by an explicit formula (see (6), below).

**Allocation Rule**
Myersons lemma states, that we need a monotone allocation rule $x$ , otherwise the allocation rule would not be implementable.

By definition for a monotone allocation rule, the more you bid, the more you get.
Since it is a single item auction, this yields a rule where the item is allocated to the highest bidder.

$$ x_i = \begin{cases}
0 \quad \text{if} \max b \neq b_i\\
1 \quad \text{if} \max b = b_i
\end{cases}$$

**Payment Rule**

In the lecture we derived from the payment sandwich that, $p_i (b_i) = b_i x_i (b_i) − ∫_0^{b_i} x_i(z) dz$ guarantees DSIC, if its combined with a monotone allocation rule. Additionally this is the only payment rule that can be DSIC.

This rule can also be rewritten as:

$$ p_i(b_i, b−i) = ∑_{j=1}^{b_i} z_j · \text{jump in } x_i(·, b−i) \text{at } z_j$$

Informally speaking, all allocation jumps will be mulitplied with the bidding value($z_j$ in our case $b_j$) associated to that point, and all of these are summed together.

If we now look at the concrete case of the Vickrey Auction, the only jump occuring in the allocation function $x$, is exactly the breakpoint between being the highest or the seocnd highest bidder, which is the second highest bid ($\max b_{-i} \quad$ assuming w.l.o.g. $\quad \max b = b_i$).

As already stated, by extracting this from the formula, the bidding value at the breakpoint, has to be multiplicated with the upper end of the allocation jump. Which is $1$ in our case, because the winner will reach his full valuation, by receiving the item.

To bring the formula above in a desired notation, we can first get rid of the sum sign, because we only have one jump. Additionally, the point $z_j$ for the jump is, as stated before, at $\max b_{-i}$. The last variable needed to be replaced, is the $x_i$ at this point, which would be exactly $1$.

$$ p_i(b_i, b−i) = \max b_{-i} · 1$$

This also implies there are just two cases, you win or not, we can integrate thi sin the formula:

$$ p_i(b_i, b−i) = \begin{cases}
0 \qquad \quad \quad \text{if} \max b \neq b_i\\
\max b_{-i} \quad \text{if} \max b = b_i
\end{cases}$$

Which cooncludes the proof, that the correct interpretation of Myersons Lemma for a single item auction, is exactly the allocation and payment rule given by the Vickrey Auction.

---

## Exercise 10

Use the “payment difference sandwich” in the proof of Myerson’s Lemma to prove that if an allocation rule is not monotone, then it is not implementable

---

The "payment difference sandwich" is defined as follows:

$$ z · [x(y) − x(z)] ≤ p(y) − p(z) ≤ y · [x(y) − x(z)] $$

Where $z > y$

For the proof we do not need the part in the middle, so we can rewrite the "sandwich" as follows:

$$ z · [x(y) − x(z)] ≤ y · [x(y) − x(z)] $$

If the allocation rule $x$ is not monotone we have two possible cases:

1. $x(y) > x(z)$
2. $x(y) = x(z)$

Therefore we can say that: $x(y) \geq x(z)$ , which concludes that $x(y) - x(z)$ is $0$ or positive:

$$x(y) - x(z) \geq 0$$

Now if:

* $z > y$
* $x(y) - x(z) \geq 0$

It is impossible that:

* $z · [x(y) − x(z)] ≤ y · [x(y) − x(z)]$

Which concludes the proof that there is no allocation rule $x$ , that is not monotone and implementable

---

## Exercise 11

We concluded the proof of Myerson’s Lemma by giving a “proof by picture” that coupling a monotone and piecewise constant allocation rule x with the payment formula
$$ p_i(b_i, b−i) = ∑_{j=1}^{b_i} z_j · \text{jump in } x_i(·, b−i) \text{at } z_j$$

(1) where $z_1, . . . , z^b$ are the breakpoints of the allocation function $x_i(·, b_{−i})$ in the range $[0, bi]$, yields a DSIC mechanism.
Where does the proof-by-picture break down if the piecewise constant allocation rule $x$ is not monotone?

---

Thats what we have with an monotone allocation rule:


Thats what we have for a non monotone allocation rule, that is not constant: