---
tags: inference
spellcheck: true
header-includes:
- \newcommand{\dd}{\mathrm{d}#1}
---

## Exercise 1

Prove that sincere bidding is an $\varepsilon$-dominant strategy for player $i$: no matter what strategies other players use, no unilateral deviation by $i$ can increase its payoff by more than $\varepsilon$.

---

**Given**

* We have $k$ available items, where each bidder can receive at most one item
* A set of bidders $I$
* A set of Active bidders for each timestep $t$
* $S_t$
* At the start of the auction $S_0 = I$
* A bid for each player $b_i$
* A starting price $p = 0$
* p rises at each timestep $t$ to $p = p + \varepsilon$
* At each timestep $t$ a player has 2 actions:
* The player stays in the auction $\qquad \quad x_{i1} = i \in S_{t}$
* The player drops out of the auction $\quad x_{i2} = i \notin S_{t}$
* The strategy decides which action the bidder will take
* $x_i = s_i(v_i)$
* $S : V \rightarrow X$
* The auction halts if $|S_t| <= k$
* All winners receive one item and pay $p$, when the auction terminates for $p + \varepsilon$
* If there are remaining items, these will be randomly sold to a subset of bidders $S_{t-1} \setminus S_t$ at price $p$

**Prove**

First, we need the formalize the different type of strategies.
Sincere Bidding will be represented as $s_s()$
All other possible strategies can be generalized as
* 'leave early' -> underbid: $s_u()$
* 'stay longer' -> overbid: $s_o()$

The reason for this is, that for underbidding it doesn't matter at which timestep you are exiting, you always pay nothing and receive nothing. For overbidding, we can say that there is only one outcome that matters, staying until the timestep where you win, which strategy that might be(possibly a lot).

To prove that $s_s()$ is dominant to $s_u()$ and $s_o()$, we have to look at 2 different situations.
Where player $i$ has an valuation, where sincere bidding lets him loose or win. In each of these situations we have to proof that player $i$ can't improve his payoff by deviating from $s_s()$.

What strategies other players are following, is nothing we have to reason about here, since the strategy of player $i$ could make a difference on possible outcomes we will look at. How these outcomes are exactly produced (strategies of other players) doesn't matter in this context.

First lets define the allocation rule $x_i$:

$$x_i(b_i, b_{-i}) = \begin{cases}
1 \qquad \text{if } b_i \in \max_k b \\
0 \qquad \text{if } b_i \notin \max_k b
\end{cases}$$

And also the payment Rule $p_i$:

$$p_i(b_i, b_{-i}) = \begin{cases}
p \qquad \text{if } b_i \in \max_k b \\
0 \qquad \text{if } b_i \notin \max_k b
\end{cases}$$

---

1. Player $i$ would loose

1.1 Payoff for sincere bidding:

$$u_i(s_s(v_i)) = v_i x_i(b_i, b_{-i}) - p_t$$

$$u_i(s_s(v_i)) = v_i \times 0 - 0 = 0$$

1.1 Payoff for overbidding:

Where $p + \varepsilon > v_i$ at $t$ for: $|S_t| <= k$
and $p > v_i$ at $t-1$ for: $|S_{t.1}| > k$
$$u_i(s_o(v_i)) = v_i x_i(b_i', b_{-i}) - p_t$$

$$u_i(s_o(v_i)) = v_i \times 1 - p = I\!R_- = \{x \in I\!R \; | \; x < 0\}$$

Negative utility!

Where $p + \varepsilon > v_i$ at $t$ for: $|S_t| <= k$
and $p <= v_i$ at $t-1$ for: $|S_{t-1}| > k$
and $i$ doesn't win by chance one of the leftovers.
$$u_i(s_o(v_i)) = v_i x_i(b_i', b_{-i}) - p_t$$

$$u_i(s_o(v_i)) = v_i \times 1 - p = I\!R_+ = \{x \in I\!R \; | \; 0 < x < \varepsilon\}$$

Payoff increased up to Epsilon

1.2 Payoff for underbidding:

Exactly the same as for sincere bidding!
$$u_i(s_s(v_i)) = v_i x_i(b_i, b_{-i}) - p_t$$

$$u_i(s_s(v_i)) = v_i \times 0 - 0 = 0$$

1.3 Special Case, Player $i$ doesn't win but could receive the item due to leftovers:

This does not change the utility of $i$, since the price $i$ has to pay stays the same.

---

2. Player $i$ would win

2.1 Payoff for sincere bidding

Where $p_t < v_i$ at $t$ for: $|S_t| <= k$

$u_i(s_s(v_i)) = v_ix_i(b_i, b_{-i}) - p_t$

$u_i(s_s(v_i)) = v_i \times 1 - p = I\!R_+ = \{x \in I\!R \; | \; x > 0\}$

2.3 Payoff for overbidding

This has no impact at all, since $i$ would win anyway, in the observed situation.

2.2 Payoff for underbidding

Here we have 2 different situations again:

2.2.1

The bid of player $i$ moves in between the set $\max_k b$ without leaving it.
Then the payoff wil be exactly the same as for sincere bidding.

2.2.2

player $i$ lowers the bid to an amount, where $b_i'$ drops out of the $k$ highest bids.
In this case the payoff would drop to $0$ :

$$u_i(s_s(v_i)) = v_i x_i(b_i', b_{-i}) - p_t$$

$$u_i(s_s(v_i)) = v_i \times 0 - 0 = 0$$

---

Therefore theres is, out of all possible outcomes, only one situtation where $i$ could improve his payoff. When $i$'s valuation $v_i$ lies between $p$ at $t-1$ for termination and $p + \varepsilon$ at $t$
Which concludes the proof that sincere bidding is an $\varepsilon$ dominant strategy.

**Additional example for clarity**

* no behavioural assumptions for other players, we just look at the point of termination
* 8 Bidders: $I = \{1, 2, 3, 4, 5, 6, 7, 8\}$
* $\varepsilon$ = 1
* 3 available items: $k = 3$
* $b_1 = 1$
* $b_2 = 2.1$
* $b_3 = 2.2$
* $b_4 = 2.3$
* $b_5 = 2.4$
* $b_6 = 2.5 \;$ $v_5 = 2.5 \;$ $b_5' = 3$
* $b_7 = 4$
* $b_8 = 5$

The auction would terminate at $t = 2$
Player 2 - 8 will be asked if they want the item at the price $p + \varepsilon = 3$
$|S_{t-1}| = $|S_1|$ = 7 > k$
Only player 4 and 5 will answer with yes and remain in the auction, which leads to $|S_t| = |S_2| = 2 < k$
player 7 and 8 would be in the set of winners, receive an item and pay $p = 2$
The leftover item will be sold randomly to one of the player from the set

$S_{t-1} \setminus S_t$
$S_{t-1} = \{2, 3, 4, 5, 6\}$

Assuming the item would have been sold to one of player 2, 3, 4 or 5 and we look at player 6.
In this situation, player 6 could improve his payoff by overbidding, specifically, saying Yes to $p + \varepsilon$ and therefore receving the item at price $p$.

$$u_5(s_o(v_5)) = v_5 \times x_i(b_5', b_{-5}) - p = 2.5 \times 1 - 2 = 0.5 < \varepsilon$$

$$u_5(s_s(v_5)) = v_5 \times x_i(b_5, b_{-5}) - p = 2.5 \times 0 - 0 = 0$$

---

**Exercise 2**

Consider again the English auction with k identical goods and unit-demand bidders. Prove that if every bidder bids sincerely, then the auction’s outcome has surplus within $k \varepsilon$ of the maximum possible.

---

The social surplus is defined by, the sum over all valuations, for all participants, for a given outcome:

$$ \sum_{i=1}^{n} v_i(a) $$

In this case, the outcome $a$ is defined by, the allocation for every participant $x_i$, therefore

$$ \sum_{i=1}^{n} v_i x_i $$

By definition $x_i$ can be either $1$ (winning) or $0$ (not winning)
$i$ wins, if they stays in the auction until it terminates.
The auction terminates if $|S_t| <= k$, therefore $i$ has to be in the set of winners $i \in S_t$
There is a special case where remaining items will be sold randomly to $S_{t-1}$
The amount of these leftovers will be denoted as $l$ with $l = |S_t| - k$
Therefore we can define the allocation rule as following:

$x_i = \begin{cases}
1 \qquad \text{if} \quad i \in S_t \; \lor \; i \in S_{t-1} \\
0
\end{cases}$

We know that, for sincere bidding, if $|S_t| = k$, the goods will be allocated to the $k$-highest bidders, with this to the $k$-highest private valuations. Which means that in the case of sincereness

$$\max \sum_{i=1}^{n} v_i x_i$$

Now there is the case where $|S_t| < k$, here $l$ items will be randomly sold to a Subset of $S_{t-1}$
What we are interested in, is what could be the worst possible, that can happen in this situation.
To find that out, we have to look at the worst case, which is specifically, the highest possible amount of random sells, where we loose our surplus maximization guarantee to an amount of $\varepsilon$ in each of these.
This happens when $|S_t| = 0$ , when $|S_{t-1}| > k$ and all of the players exiting the auction, in this case $l = k$

Now we have to think again about the worst case. We already maximized the number of random sells $l$. So lets maxmize the impact each of the $l$ sells has on the surplus(in the worse way).
Since each sell could lower the surplus, by the difference between the winner with the highest possible valuation(still lower than $p+\varepsilon$) and with the lowest, we can say that we need at least $|S_{t-1}| = 2l = 2k$ , where:

$S_{t-1,h} \subset S_{t-1}$
$v_{s_h} = p+\varepsilon \qquad s_h \in S_{t-1,h}$

$S_{t-1,l} \subset S_{t-1}$
$v_{s_l} = p \qquad s_l \in S_{t-1,l}$

$|S_{t-1,h}| = |S_{t-1,l}| = l / 2 = k / 2$

So now each of the random sells, could possible lower the social surplus up to $\varepsilon$

Where it is now allowed to say that in this scenario, the social surplus is: $\max \sum_{i=1}^{n} v_ix_i - \varepsilon$
and it also can not be worse.

With this we can state that, for sincere bidding

$$\sum_{i=1}^{n} v_ix_i \in [\max \sum_{i=1}^{n} v_ix_i - \varepsilon, \max \sum_{i=1}^{n} v_ix_i]$$

---

Exercise 3

---

Consider Scenario #2 from lecture: $m$ non-identical goods and bidders with additive valuations. Prove that sincere bidding in $m$ simultaneous English auctions is an ($m\varepsilon$)-ex post Nash equilibrium. That is: for every valuation profile $v$, if all bidders other than $i$ bid sincerely, then no strategy of bidder $i$ can ever improve over the payoff of sincere bidding by more than $m\varepsilon$.

---

In exercise 1 we already proved that...

$$\begin{equation} \begin{array}{c} \text{For one english auction, one player can improve their payoff} \\
\text{by deviating from sincere bidding, only up to }\varepsilon. \end{array} \end{equation}\tag{1}$$

Because we proved (1) is true for all possible strategies the other players could follow,
(1) also holds under the assumption that all other players bid sincerely.
If we have $m$ simultaneous english auctions, (1) applies to each of them in parallel, which concludes that a player can increase their payoff only up to $m\varepsilon$.
One more thing to consider, we proved (1) for $m$-identical goods, where the proof is also valid for $m=1$. So for $m$ parallel english auctions, where for each auction $m=1$, (1) holds.

**Mathematical formalization of the final statement:**

The valuation of a player is defined by:

$$v_i(S_i) := \sum_{j \in S_i} v_{ij}$$

where $S_i$ is the bundle of items $i$ receives: $S_i \subset U$

Now in the general notation, we do not have a predefined set that player $i$ wins. So we replace $S$ with the full set of items $U$ and pair the valuations with an allocation-function, that will have the bids as input:

$$v_i(b_i, b_{-i}) := \sum_{j \in U} v_{ij} x_{ij}(b_i, b_{ij})$$

The allocation for each player, is either $0$ or $1$ for each of the english auctions, depending on if they have the highest bid.

$$\forall j \in U \quad x_{ij}(b_{ij}, b_{-ij}) = \begin{cases}
1 \quad \text{if} \;\; b_{ij} = \max b_j\\
0 \quad \text{if} \;\; b_{ij} \neq \max b_j
\end{cases}$$

The payment for a player, will be defined as the sum of all payments, for each of the items:

$$p_i(b_i, b_{-i}) := \sum_{j \in U_i} p_{ij}(b_{ij}, b_{-ij})$$

The payment for each of the simultaneous english auctions, is defined as follows:

$$\forall j \in U \quad p_{ij}(b_{ij}, b_{-ij}) = \begin{cases}
p_j \;\; \text{if} \;\; b_{ij} = \max b_j\\
0 \quad \text{if} \;\; b_{ij} \neq \max b_j
\end{cases}$$

With this, we can define the utility of a bidder

$$u_i = v_ix_i - p_i$$

When we consider different strategies, that allows to model different outcomes in the same equation, the allocation and payment rule are going to have inputs based on these strategies:

$$x_i(b_i, b_{-i}) = x_i(s_i(v_i), s_{-i}(v_{-i}))$$

$$p_i(b_i, b_{-i}) = p_i(s_i(v_i), s_{-i}(v_{-i}))$$