# Meeting 01.12.2023
---

## Exercise 5

Consider a single-item auction with at least three bidders. Prove that awarding the item to the highest bidder, at a price equal to the third-highest bid, yields an auction that is not dominant-strategy incentive compatible (DSIC).

---

To prove that something is or is not dominant strategy incentive compatible, we first have to define what DSIC is:

A mechanism is DSIC, if both conditions hold:

- every bidder has a dominant strategy (regardless of other bidder actions, every bidder maximizes own utility by setting their bid to their own valuation)
- every truth-telling bidder is guaranteed non-negative utility

Incentive Compatibleness means, the utility $u_i$ a player receives from the mechanism, if he declares $v_i$ , his true valuation, is not lower that declaring $v'_i$ .

$$ u_i(v_i, v_{-1}) \geq u_i(v'_i, v_{-i})$$

$$ v_i(a) − p_i(v_i, v_{−i}) ≥ v_i(a') − p_i(v'_i , v_{−i} ) $$

Now we introduce $b_i$ as the notation for the bid of a player, since the payment will be caclulated over bids and not over valuations

$$ v_i(a) − p_i(b_i, b_{−i}) ≥ v_i(a') − p_i(b'_i , b_{−i} ) $$

$$ u_i(v_i, b_{-i}) = v_i(f(b_i, b_{-i})) - p_i(b_i, b_{-i})$$

So the strategy to tell the truth is a weakly dominant strategy -> DSIC
Weakly Dominant means you could receive $u_i = 0$ , but never $u_i < 0$ .

In the further solution, telling the truth is expressed with $b_i = v_i$, and lying with $b'_i \neq v_i$

As mentioned our payment rule $p_i$ is defined as follows

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

$v_i(a)$ declares a valuation we have for a given outcome of the auction, that is formally described by a social choice function $f(b_i, b_{-i}) = a$ . Here we also have two different cases:

$v_i(a) = \begin{cases}
0 \quad \text{ if } \max b \neq b_i\\
v_i \quad \text{ if } \max b = b_i
\end{cases}$

To discover if the mechanism is incentive compatible, we look at the options different players have, starting with the winner of the auction

Fix $v_1, v_2$ and $v_3$ without loss of generality, where $v_1 > v_2 > v_3$

$u_1 = v_1(a_1) - p_1(b_1, b_{-1})$
$u_1 = v_1(a_1) - v_3$

As we can see the utility for player 1 is postive, since $v_1 > v_3$

Now we look if player 1 can improve his utility by declaring a bid $b_i'$ which is different than his true valuation.

**Player 1/ Case 1 overbidding**
The social choice function $f$ would still choose player 1 as the winner of the auction $f(b_1', b_{-1}) = a_1$

$u_1 = v_1(a_1) - p(b_1', b_{-1})$
$u_1 = v_1(a_1) - v_3$

Therefore our DSIC property still holds in this case:

$$ v_i(a) − p_i(b_i, b_{−i}) ≥ v_i(a') − p_i(b'_i , b_{−i} ) $$

**Player 1/ Case 2 underbidding**
Depending on how much player 1 is underbidding, we can have two different cases:

**Case 2.1 his bid is still the highest bid**
See case 1

**Case 2.2 his bid is not the highest bid anymore**
The social choice function $f$ would now choose player 2 as the winner of the auction $f(b_1', b_{-1}) = a_2$

$u_1 = v_1(a_2) - p(b_1', b_{-1})$
$u_1 = 0 - 0 = 0$

Player one would receive a lower utility, in the case he underbids the second highest bid, so the DSIC property still hold.

$$ v_i(a) − p_i(b_i, b_{−i}) ≥ v_i(a') − p_i(b'_i , b_{−i} ) $$

---

If the second player 2 declares his true valuation $b_2 = v_2$ he would receive $0$ utility
$f(b_2, b_{-2}) = a_1$

$u_2 = v_2(a_1) - p(b_2, b_{-2})$
$u_1 = 0 - 0 = 0$

Now we look if player 2 can improve his utility by declaring a bid $b_i'$ which is different than his true valuation.

**Player 2/ Case 1 overbidding**
The social choice function $f$ would choose player 2 as the winner of the auction $f(b_2', b_{-2}) = a_2$

$u_2 = v_2(a_2) - p(b_2', b_{-2})$
$u_2 = v_2 - v_3$

Since $v_2 > v_3$, the utility for player 2 would be positive and therefore higher than declaring his true valuation, **which breaks our DSIC property**.

---
If we know look back at player 1, considering the auction is open and the players know the bids of the other players

---
Questions for discussion:
- we assume that all players on with a valuation on position 1 or 2 have an incentive to overbid, that's why the mechanism is not DSIC (what's the right generalized notation?)
- DSIC breaks in this type of auction where bidders can see/know each others' bids, would DSIC also break in a sealed bid auction? (for reference: single-item auction with at least three bidders)