---
tags: inference
spellcheck: true
header-includes:
- \newcommand{\argmax}{\mathrm{argmax}}
---
# Exercise Set 1

## Exercise 1
Give at least two suggestions for how to modify the Olympic badminton tournament format to reduce or eliminate the incentive for teams to intentionally lose a match.

The incentive to intentionally lose match was mainly induced by the existing of the group stage.

**Example:**
Knockout round:
1st of A **vs** 2nd of D
2nd of A **vs** 1st of D
In Group D, Team PJ upsetted by winning over the favorite QW. With this the favorite ended the group stage in the 2nd place.
In Group A, Team XY plays Team KH, both would win the group if they win the game, which means they have to face team QW in the knockout stage.
Both would not face the best team upon the final, which means at least a silver medal could be reached without facing the strongest opponent.

**suggestion 1, eliminate group stage**
(In the lecture mentioned)
There is never an competitional incentive to lose a Knockout game. Eliminating the Group-Phase would remove the incentive to intentionally loose a game.

**suggestion 2, eliminate knockout stage**
(maybe not feasible in respect to the time available)
Eliminate the Knockout round. If all teams play once against each other(league-system), and the podium places will be defined by the final places in the table, there will be no incentive to intentionally lose a game.

**suggestion 3, knockout draws 1**
(champions league draw)
A draw of matches for the knockout stage, where all 1st places and all 2nd stages are seperated to pools. This would only reduce the possibility of creating the mentioned incentive during the tournament, explained as following.
Since a draw in respect to the finishing places of the group stage, could still incentivice intentional losing, if more than the half of the groups has upsets in the finishing positions.

**suggestion 4, knockout draws 2, BEST SOLUTION**
(In reference to the champions league draw)
A draw of matches for the knockout stage(between all advancing teams, no matter which place), would eliminate all possible incentives, to intentionally lose a group-stage game.

## Exercise 2

A pure strategy Nash equilibirum is formally defined by:

$$ u_i(s_i, s_{-i}) \geq u_i(s'_i, s_{-i}) $$

Which means that no player can improve his utility by changing his strategy, while all other players stick to their strategy.

For the example given in the scene, we have that all players(the mens) prefer the same alternative(women) over the others. A preference order for the other alternatives is not provided.
There are two given strategys the players could follow

$s_1$ which leads to action $x_1$ , $x_1$ is defined as "dance with woman 1(blonde)"

$s_2$ leads to action $x_{(2/3/4/5)}$ , $x_{(2/3/4/5)}$ is defined as "dance with woman (2/3/4/5)"

Since in the scene every men dances with another woman if everyone uses $s_2$ , lets assume that all players have different types $t_i$ except for alternative 1.
Which results in an outcome where every player takes a different action $x_i$ except $x_1$, if everyone follows $s_2$.

The utilitys are defined as following:

If everyone plays $s_1$
$$ u_i(s_i, s_{-i}) = 0 $$

If everyone plays $s_2$
$$ u_i(s_i, s_{-i}) > 0 $$

If one player($i$) only plays $s_1$
$$ u_i(s_i, s_{-i}) > u_{-i} $$

Where we have to note that, if everyone else in the vector $s_{-i}$ choose $s_2$, but $i$ chooses $s_1$ than for $s'_i = s_1$

$$u_i(s_i, s_{-i}) < u_i(s'_i, s_{-i})$$

### a)
Explain why the solution proposed by the John Nash character (i.e., Russell Crowe) is not a Nash equilibrium

In the solution proposed in the scene, every player should follow $s_2$ , where every player will have their utility $u_i$ higher, as when everyone would follow $s_1$.

This is not a pure strategy nash equilibrium, since a single player could improve his payoff($u_i$), by changing their strategy to $s_1$(dance with w1), when everyone else sticks to strategy $s_2$(dance with w(2/3/4/5)). Which is against the definition

$$ u_i(s_i, s_{-i}) \geq u_i(s'_i, s_{-i}) $$

where $s'_i$ would be $s_1$

### b)

## Exercise 3

Prove that there is a unique (mixed-strategy) Nash equilibrium in the Rock-Paper-Scissors game described in class.

A mixed strategy for a player, is defined by a probalility distribution $p_i$ over his set of actions.

The game described in the class has a given payoff matrix for each of the players

$$ A_r = \begin{pmatrix}
0 & -1 & 1\\
1 & 0 & -1\\
-1 & 1 & 0
\end{pmatrix} $$

$$ A_c = \begin{pmatrix}
0 & 1 & -1\\
-1 & 0 & 1\\
1 & -1 & 0
\end{pmatrix} $$

where $A_r^T=A_c$

As we can see, this is a 2-Player Zero-Sum Game, which means that for every choice of the players, the sum of both payoffs is 0.
The probability distribution vector $p_i$ is unknown at this point.
$$ p_i = \begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}$$

To find a mixed strategy Nash Equilibrium for both players, we have to define which probability distribution over the possible actions would be a best response, to the public known strategy of the other player. Since we don't know either of these public strategies, we have to define one of these, in respect to the mixed strategy with unknown values from the other player. To do this, we will observe the payoffs for one player.

The expected payoffs for player column, are defined by $p_c \times A_c$

$$ \begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix} \times \begin{pmatrix}
0 & 1 & -1\\
-1 & 0 & 1\\
1 & -1 & 0
\end{pmatrix} = \begin{pmatrix}
0 & x_2 & -x_3\\
-x_1 & 0 & x_3\\
x_1 & -x_2 & 0
\end{pmatrix}$$

If $p_c$ would be known, player column would choose a strategy that minimizes his loss, a best response strategy from player row in this case, would be a maximization over this.
As stated in the AGT-Book(page 17) this can be found by solving following linear program:

1. $v_r = max$ $v$
2. $p \geq 0$
3. $\sum_{i}p_i = 1$
4. $(p_c\times A_c)_j \geq v$

Point 4 means, that for every entry $j$ in the payoff matrix, the value has to be greater or equal to $v$

We can reformulate 4. to:

1. $x_2 - x_3 \geq v$
2. $-x_1 + x_3 \geq v$
3. $x_1 - x_2 \geq v$

A combination of these, concludes to $0 \geq 3v$ . This tells us that $v$ has to be either $0$ or negative.
With this, in respect to point 1-3, we can say that:

$$ x_3 \geq x_2 \geq x_1 \geq x_3$$

And this can only hold if all values are equal to each other, in respect to $\sum_{i}p_i = 1$ , we can now state that:

$$ x_ 1 = x_ 2 = x_ 3 = \frac{1}{3}$$

Since this is a Two player Zero-Sum Game the strong duality theorem holds, which means that we would get the exact same result if we repeat this process for player column.

Which results in a mixed strategy Nash equilibrium where both players play strategy:

$p = \begin{pmatrix}
\frac{1}{3}\\
\frac{1}{3}\\
\frac{1}{3}
\end{pmatrix}$

This is also a unique equilibrium, because for no other values in the vector $p$ we could fulfill the requirement that:

$$ x_3 \geq x_2 \geq x_1 \geq x_3 $$

## Exercise 4

Compare and contrast an eBay auction with the sealed-bid second-price auction described in class. Should you bid differently in the two auctions?

---

| | Sealed-Bid Second-Price | Ebay-Auction |
| ------------ | ----------------------- | -------------- |
| Bid Model | Single-Shot(once) | Sequential(multiple times)|
| Public-Values| No | Yes
| IC | Yes | Yes |

First we have to answer why the Ebay auction is Incentive Compatible.
A short answer is, that it is an anlog to the second price auction, which is also IC, and therefore the property is preserved.

It differs in how the auction is executed, but essentially you will submit your true valuation and pay the second highest valuation + 1.

Also no player can improve his payoff, assuming that everyone else plays their ominant strategy.

## 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} ) $$

$$ 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)

## Exercise 6

Suppose there are $k$ identical copies of a good and $n > k$ bidders. Suppose also that each bidder can receive at most one good. What is the analog of the second-price auction? Prove that your auction is DSIC.

---

To create an analog of a second price auction, lets recap the properties and adjust them to the current situation:

First we have a social choice function $f$ that select the player with the highest bid $b_i$ as the winner of the auction.

$f(b_i, b_{-i}) = a$

Now we have $k$ items and therefore we need to have $k$ winners. So $f$ has to select a set $A_w$ with winners, wich needs to has the size $k$ . $A_w$ has to include the $k$ highest bids.

$f(b_i, b_{-i}) = A_w$
$|A_w| = k$
$A_w \in \max_k A$

In the Vickrey Auction every player had a valuation for a given outcome, defined as follows:

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

Then we had the payment function $p$ which was defined as follows:

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

To create an analog payment function, we have to treat the set of winners $A_w$ in the same way we treated the winner $a$ in the second price auction.
As an additional reason to do this, we can argue that different prices for the same good would incentivice strategical bidding, which would break the IC property.
The logical conclusion is that all players that are part of the set $A_w$ receive an item and have to pay the bid $b_{k+1}$ , where $b_{k+1}$ is the $k+1$ highest bid. The bid from the player with the highest private valuation $v_i$ , assuming all bidders id truthfully $b_i = v_i$ .
Formally, $max_{k+1} b$ is the $k+1$ highest $b$ .
Furhtermore, the $k$-highest bids will eb represented by $B_{\max_k}$

$v_i(A_w) = \begin{cases}
0 \quad \text{ if } b_i \notin B_{\max_k}\\
v_i \quad \text{ if } b_i \in B_{\max_k}
\end{cases}$

$p_i = \begin{cases}
0 \qquad \qquad \text{ if } b_i \notin B_{\max_k}\\
\max_{k+1} b \quad \text{ if } b_i \in B_{\max_k}
\end{cases}$

Now that we have defined the necessary components for the new auction mechanism, lets proof that it is incentive compatible. For the proof we are going to use general utility function for auction mechanisms:

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

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

First it is necessary to state, that every winners of the set $A_W$ can, w. l. o. g. , be representative for the while set, because the position in the set does not matter, you pay the same and receive the same.

First lets look at the strategies for winning players:

1. Telling the truth $b_i = v_i \quad \rightarrow \quad$ guarantees positive utility:
$\forall a_i \in A_w \quad u_i(b_i, b_{-i}) = v_i - \max_{k+1} b > 0$

2. Overbidding $b_i' \neq v_i \quad \rightarrow \quad$ results in the exact same utility function, since you can't change your payment or allocation depending on your position in the set.
$\forall a_i \in A_w \quad u_i(b_i', b_{-i}) = v_i - \max_{k+1} b > 0$

3. Underbidding $b_i' \neq v_i \quad \rightarrow \quad$ provides the same outcomes with an additional chance for zero utility:
$\forall a_i \in A_w \quad u_i(b_i', b_{-i}) = \begin{cases}
0 - 0 \qquad \qquad = 0 \quad \text{ if } b_i' \notin B_{\max_k}\\
v_i - \max_{k+1} b > 0\end{cases}$

With these observations, we can conclude three statements, that prove that our mechanism is at least DSIC fo the winners of the auction:

* $\forall a_i \in A_w \quad u_i(b_i, b_{-i}) > 0$
* $\forall a_i \in A_w \quad u_i(b_i', b_{-i}) \geq 0$
* $\forall a_i \in A_w \quad u_i(b_i, b_{-i}) \geq u_i(b_i', b_{-i})$

Now lets look if the same holds for the loosers of the auction, lets look again at the different strategies:

1. Telling the truth $b_i = v_i \quad \rightarrow \quad$ guarantees zero utility:
$\forall a_i \notin A_w \quad u_i(b_i, b_{-i}) = 0 - 0 = 0$

3. Underbidding $b_i' = v_i \quad \rightarrow \quad$ results in the exact same utility, because you can't change your allocation or payment if you are not included in the set:
$\forall a_i \notin A_w \quad u_i(b_i', b_{-i}) = 0 - 0 = 0$

3. Overbidding $b_i' \neq v_i \quad \rightarrow \quad$ additionally enables negative utility:
$\forall a_i \notin A_w \quad u_i(b_i', b_{-i}) = \begin{cases}
0 - 0 \qquad \qquad = 0 \quad \text{ if } b_i' \notin B_{\max_k}\\
v_i - \max_{k+1} b < 0 \quad \text{ if } b_i' \in B_{\max_k}
\end{cases}$

With these observations, we can conclude three statements, that prove that our mechanism is additionally DSIC fo the loosers of the auction:

* $\forall a_i \notin A_w \quad u_i(b_i, b_{-i}) = 0$
* $\forall a_i \notin A_w \quad u_i(b_i', b_{-i}) \leq 0$
* $\forall a_i \notin A_w \quad u_i(b_i, b_{-i}) \geq u_i(b_i', b_{-i})$

Which concludes the proof that for all participants, our mechanism is DSIC:

$$ u_i(b_i, b_{-i}) \geq u_i(b_i', b_ {-i})$$

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

## Exercise 7

Suppose you want to hire a contractor to perform some task, like remodeling a house. Each contractor has a private cost for performing the task. Give an analog of the Vickrey auction in which contractors report their costs and the auction chooses a contractor and a payment. Truthful reporting should be a dominant strategy in your auction and, assuming truthful bids, your auction should select the contractor with the smallest private cost. [Aside: auctions of this type are called procurement or reverse auctions.]

---

The social choice function of a VCG-mechanism for auctions is defined by:
$f(b_1, ..., b_n) \in \text{arg}\max_{a \in A} \sum_i v_i(a)$
Which means it chooses the alternative that submitted the highest $v_i$

Now that all bids are representing a cost(negative) rather than a valuation(positive), choosing the lowest bid $b_i$(closest to zero in a negative interpretation), is a maximization of social surplus. This happens because we minimize the overall cost instead of maximizing the overall valuation.

In the context of this auction $f$ receives $b_1, ..., b_n$ and chooses the bidder $a$ that submitted the lowest $b$ as the winner of the auction and therefore the contract.
$f(b_1, ..., b_n) \in \text{arg}\min_{a \in A} \sum_i v_i(a)$

The allocation rule would therefore also swap from a maximization condition to a minimization condition

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

To define a payment rule analog to the vickrey auction, we have to do the same thing again:

$p_i = \begin{cases}
0 \qquad \qquad \text{ if } b_i \neq \min b \\
\min b_{-i} \quad \text{ if } b_i = \min b
\end{cases}$

where $\min b_{-i}$ is the second lowest bid $b$ (price for the task).

With the swap from a maximization to a minimization over the bids, we can preserve DSIC, if the cost is submitted as a positive bid $b$ .

## Exercise 8

Recall the sponsored search setting, in which bidder $i$ has a valuation $v_i$ per click. There are $k$ slots with click-through-rates (CTRs) $α_1 ≥ α_2 ≥ · · · ≥ α_k$. Recall that the social surplus of an assignment of bidders to slots is $∑_{i=1}^n v_ix_i$, where $x_i$ equals the CTR of the slot to which $i$ is assigned (or $0$ if bidder $i$ is not assigned to any slot).
**Prove** that the social surplus is maximized by **assigning the bidder with the jth highest valuation to the jth slot** for $j = 1, 2, . . . , k$

---

To do this, lets first recall the previous definition of social surplus for single item auctions:

$\sum_i^n v_i(a)$

Previously we have also stated, that a social choice function $f$ maxmizes social surplus if:

$f(b_1, ..., b_n) \in \text{arg}\max_{a \in A} \sum_i v_i(a)$

In the context of sponsored search auctions, the valuation over the outcome will not depend on a single candidate $a$ that is chosen by the social choice function, instead it depends on the slot $j$ that is assigned to him. Where $j$ has an associated CTR $α_j$ , which will be represented by $x_i$.

In this new setup, the valuation of a player over the outcome, will be represented by the product of his valuation $v_i$ and the CTR of the assigned slot $x_i$ , becauce it is the probability with which he will achieve his valuation. Therefore, the definition of social surplus for a SSA is:

$\sum_i^n v_ix_i$

While in the previously defined social surplus, all players had valuations over the same outcome $v_i(a)$ , now all players have valuations for the part of the outcome that is associated to them $v_ix_i$ .

So $f$ has a more sophisticated task. Instead of choosing one ouctome $a$
$f$ has to pair an input set of valuations $V, |V| = n$ with a set $K$ of slots , $(v, k) \in V \times K$
$f$ also has access to a set of CTR-Values $X$ , where $|X| = k$

This pairing has to be maximized, since the pairing indicates which $x$ will be assigned to which $v$ .
So we can say the task of $f$ is to maximize the pairings, because a higher $k$ indicates a higher $x$ that will be assigned. This can be expressed as follows: $\max_{(v, k) \in V \times K}$

With this plugged in the previous formula, $f$ maximizes social surplus if:

$$f(b_1, ..., b_n) \in \text{arg}\max_{(v, k) \in V \times K} \sum_i^n v_ix_i$$

And that is exactly achieved if **the bidder with the jth highest valuation is assigned to the jth slot** , which concludes the proof.