## Problem 1
Identify a real-world system in which the goals of some of the participants and the designer are fundamentally misaligned, leading to non-trivial strategic behavior by the participants. You should also give proposals for how the system could be improved to mitigate the incentive problems. You should include:
* A description of the system, detailed enough that you can express clearly the incentive problems and your solutions for them.
* **Source: https://www.youtube.com/watch?v=nUYUJ0r5Y2M&list=WL&index=8&t=876s (14:10min)**
* Between 1940 and 1950 the provincial government of Union Nationale(Quebec) Premier Maurice Duplessis received 1.25$ per orphan and 2.75$ per psychiatric patient from the federal government.
* These condition provided a strong financial incentive for wrong classifications, to improve the financial situtation of the province
* Financial support for double classification should not be allowed. Additionally, the amount received per orphan or mentally ill person, should be equal.
* Evidence that participants are gaming the system in undesirable ways. This could be anecdotal evidence, something that has or can be measured, or something that you demonstrate yourself. (Feel free to include screen shots or pictures.)
* **Source: https://en.wikipedia.org/wiki/Duplessis_Orphans**
* 

* A convincing argument why your proposed changes would reduce or eliminate the strategic behavior that you identified. We emphasize that a “system” could be any number of things — a Web site, a competition, a political process, etc
* If we prohibit that one citizen can be included in both classifications, the resulting payment would make much more sense. This is because a citizen can either live in an orphanage or in an psychatrie, and the provincial government could not have a pure financial surplus by doing double classifications.
* Anyhow, since a psychatric patient still means more financial support for the state, an equal payment for each person, no matter in which group, would eliminate all incentives for wrong classifications. How feasible this is in terms of operating costs is not taken into account, because of lack of information.

---

**Mathematical representation:**

---

## Problem 2

### a)
Prove that for every false bid $b_i \neq v_i$ by a bidder in a Vickrey auction, there exist bids $b_{−i}$ by the other bidders such that $i$’s payoff when bidding $b_i$ is strictly less than when bidding $v_i$

---

To do this, we first have to recall the definition of the Vickrey auction

We have a social choice function $f(b_i, b_{-i}) \in \text{arg} \max_{a \in A} \sum_i v_i(a)$

And we have payment function $p_i(v_i, v_{-i}) = \begin{cases}
0 \qquad \qquad \text{ if } \max b \neq b_i\\
\max b_{-i} \quad \text{ if } \max b = b_i
\end{cases}$

For the proof, we have to look at two possible situation, $b_i < v_i$ and $b_i > v_i$
To simplify further explanations,
$b_i < v_i$ will be expressed as $b'_i$ and
$b_i > v_i$ will be expressed as $b''_i$

To prove that something is strictly less, we first have to give an initial situation:
Fix $v_i$ , $b_i$ , $b_j$ and $b_{-ij}$ , where $v_i = b_i > b_j > b_{-ij}$
The social choice function now chooses $i$ as the winner: $f(b_i, b_{-i}) = a_i$
This means $i$ has a positive valuation for outcome $a_i$ : $v_i(a_i) = v_i$
The payment rule defines $\max b_{-i} = b_j$ as a payment
Which leads to a positive utility for player $i$ : $u_i = v_i - b_j$

1. Lets look at the first case $b'_i$ :
The fixed values remain the same, except for $b_i$ which changes to $b'_i$
Now we have that $v_i > b_j > b'_i > b_{-ij}$
The social choice function now chooses player $j$ as the winner: $f(b_i, b_{-i}) = a_j$
This means $i$ has $0$ utility $v_i(a_j) = 0$
And also $0$ as payment
Which leadds to $0$ utility, and is therefore strictly less: $u'_i = 0 - 0 = 0 < u_i$

So we have proofen that for every bid $b_i \neq v_i$ , where $b_i < v_i$ , there exists a set of bids $b_{-i}$, that guarantees a lower payoff.

To proof that is also holds when $b_i > v_i$ we are allowed to change $b_{-i}$ and we also define a new initial situation:

Fix $v_i$ , $b_i$ , $b_j$ and $b_{-ij}$ , where $b_j > v_i = b_i > b_{-ij}$
The social choice function now chooses $i$ as the winner: $f(b_i, b_{-i}) = a_j$
Which leadds to $0$ utility for player $i$ (compare 1.) : $u_i = 0 - 0 = 0$

2. Lets look at the second case $b''_i$ :
The fixed values remain the same, except for $b_i$ which changes to $b'_i$
Now we have that $b''_i > b_j > v_i > b_{-ij}$
The social choice function now chooses player $i$ as the winner: $f(b_i, b_{-i}) = a_i$
This means $i$ has a positive valuation for outcome $a_i$ : $v_i(a_i) = v_i$
The payment rule defines $\max b_{-i} = b_j$ as a payment
Which leads to a negative utility for player $i$ : $u''_i = v_i - b_j < 0 = u_i$

Now it is proven, that for every $b_i \neq v_i$ there exists a set $b_{-i}$ , so that the payoff for player $i$ would be strictly less.

---

### b)

Consider a Vickrey auction with $n$ bidders and suppose a subset $S$ of the bidders decide to collude, meaning that they submit false bids in a coordinated way to maximize the sum of their payoffs. Prove necessary and sufficient conditions on the set $S$ (in terms of the private valuations of the bidders) such that the bidders of $S$ can increase their collective payoff via non-truthful bidding.

---

**First lets make some formal definitions for the proof:**
The set of participating bidders $A$
Subset of colluding bidders $S$
Where every player can possibly collude $S \subseteq A$
Player is in colluding subset $a_i = s_x \in S$ , where $_x$ denotes an unknown position in $S$
Bids of Subset $S$ , $b_s$
Bids of subset $S$ without player $i$ , $b_{s-i}$
Bids of all other players $b_o$
A non-truthful bid $b'$
The count of colluders: $k = |S|$
The utility for any of the colluders, where $_x$ denotes a position in the set $S$: $u_{sx}$
The collective payoff for all colluders: $\sum_x u_{sx}$

For the following proof, fix $a_j$ as the winner of the auction.
This concludes to the following statements:

$f(b_1, ..., b_n) \in \text{arg}\max_{a \in A} \sum_i v_i(a) = a_j$
$\max b = b_j$

$v_i(a) = \begin{cases}
0 \quad \text{if } s \neq a_j\\
v_i \quad \text{if } s = a_j\end{cases}$

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

**Now we can look at two possible cases:**
Subset $S$ includes the player with the highest valuation $a_j$ or not.

1. Not included, $a_j \neq s \in S$

$S = \{ s | s \neq a_{max} \}$

Every colluder would receive $0$ utility for truthful bidding

$\forall s \in S \quad u_i(b_i, b_{-i}) = v_i(a) - p_i(b_i, b_{-i}) = 0 - 0 = 0$

If one colluder $i$ would overbid to win, the payment rule would flip to the following:

$p_i(b'_i, b_{-i}) = \begin{cases}
0 \qquad \qquad \qquad \text{if } s \neq a_j\\
\max b_{-i} = b_j \quad \text{if } s = a_j\end{cases}$

Therefore, he and with this all colluders, would receive a negative utility, because $b_j > v_i$

$\forall s \in S \quad u'_i(b'_i, b_{-i}) = v_i(a') - p_i(b'_i, b_{-i}) = v_i - b_j < 0$

Now if a second colluder overbid $b_j$ , $i$ would have to pay his bid, which would result in an even more negative utility:

$0 = u_i(b_i, b_{-i}) > u'_i(b'_i, b_{-i}) > u'_i(b'_i, b'_{s-i}, b_o)$

This leads to the first condition, the player with the highest private valuation has to collude, that a gropu of colluders can improve their overall utility

2. Included, $a_j = s_j \in S$
In this case, the player $s_j$ could improve his payoff, and therefore the payoff of all colluders summed, only if he pays less: $\min p_j$

$$\sum_x u_{sx} = u_j(b_j, b_{-j}) = v_j(a_j) - p_j(b_j, b_{-j}) $$

$$\max \sum_x u_{sx} = v_j(a_j) - \min p_j$$

**Which also gives us the first condition, that we need to have the player with the highest private valuation as a colluder:**

$$S = \{s_1, ..., s_k | \max v_s = \max v\}$$

2.1. Minimizing $p_j$ means we need to minimize the second highest bid $b_{-j}$, which is only possible if we have the player with second highest true valuation included in $S$.

**Therefore our second condition is:**
$$S = \{s_1, ..., s_k | \max v_s = \max v\land \max_{k-1}v_s = \max_{n-1}v\ \land k \geq 1\}$$

To simplify this, lets denote the m-highest valuations from colluders of set $v_s$ , as $\max_m v_s$

$$S = \{s_1, ..., s_k | \max_m v_s = \max_m v \land (k, m) \geq 1\}$$

2.2 Because the Vickrey Auction is a sealed bid auction, we can minimize only to the lowest bound of bids we know, to not loose the auction at all:

$$ \min p_j > \min_{b \in b_s} b_{-j}$$

2.2 For $\min p_j < \max b_{-j}$ , we need to have at least the third highest true valuation included in $S$ , assuming that all not colluding players bid truthfully, what we are allowed to do, because the Vickrey-Auction is DSIC.

**This gives us our third condition, that we need at least the three participants with the three highest private valuations:**

$$S = \{s_1, ..., s_k | \max_m v_s = \max_m v \land (k, m) \geq 3\}$$

Which completes the set of neccessary and sufficient conditions.

---

### c)

We proved that the Vickrey auction is truthful under the assumption that every bidder’s utility function is quasi-linear — of the form $u_i(v_i, p_i) = v_i x_i − p_i$ (where $x_i$ is $1$ if $i$ wins and $0$ otherwise). State some significantly weaker assumptions on the utility functions $u_i(v_i, p_i)$ under which truthful bidding is a dominant strategy for every bidder.

---

By definition, weakly assumption means that it is very reasonable and close to the given circumstances.

Weakly Assumptions:

1. Monotonicity for the allocation function $x_i(b)$ $\rightarrow$ The higher the bid, the more you get
2. Normalization for a payment function $p_i(b) \in [0, b_i x_i(b)]$ $\rightarrow$ seller never pays bidder
3. Given 1. we will be able to create a unique payment function $p_i(b)$ under the condition of 2. such that:
$$ v_i' \cdot [x(b_i) - x(b_i')] \leq p(b_i) - p(b_i') \leq v_i \cdot [x(b_i) - x(b_i')] $$

Explanation:

To be DSIC, for both players it has to be true that, truthtelling yields in a higher utility than submitting a wrong(higher/lower) bid. We can utilise two perspectives with shared fixed values, to couple a context:

Player 1 has private valuation $v_i$ and bids $b_i$, he could also bid $b_i'$ which is lower $\quad v_i = b_i \quad, b_i > b_i'$

Player 2 has private valutation $v_i'$ and bids $b_i'$, he could also bid $b_i$ which is higher $\quad v_i' = b_i' \quad, v_i > v_i'$

* $v_i \cdot x_i(b_i) - p_i(b_i) \geq v_i \cdot x_i(b_i') - p_i(b_i')$
* $v_i' \cdot x_i(b_i') - p_i(b_i') \geq v_i' \cdot x_i(b_i) - p_i(b_i)$

Now we can rearrange the equations:

1.
$$ v_i \cdot x_i(b_i) - v_i \cdot x_i(b_i') \geq p_i(b_i) - p_i(b_i') $$

$$ v_i \cdot [x_i(b_i) - x_i(b_i')] \geq p_i(b_i) - p_i(b_i') $$

2.
$$v_i' \cdot x_i(b_i') - v_i' \cdot x_i(b_i) \geq p_i(b_i') - p_i(b_i)$$

$$-v_i' \cdot x_i(b_i') + v_i' \cdot x_i(b_i) \leq -p_i(b_i') + p_i(b_i)$$

$$v_i' \cdot [-x_i(b_i') + x_i(b_i)] \leq -p_i(b_i') + p_i(b_i)$$

$$v_i' \cdot [x_i(b_i) - x_i(b_i')] \leq p_i(b_i) - p_i(b_i')$$

Where we can bound on $p_i(b_i) - p_i(b_i')$ to get the constraint:

$$ v_i' \cdot [x(b_i) - x(b_i')] \leq p(b_i) - p(b_i') \leq v_i \cdot [x(b_i) - x(b_i')] $$