# COMP553 ASSN 3
### Q1 Zero-Sum game
**(a) Consider a 2-player zero-sum game with Nash equilibria {x1,y1} and {x2,y2}.
Show that {x1, y2} and {x2, y1} must also be Nash equilibria.**

Suppose {x1, y1} is the Nash equilibrium for player 1 and {x2, y2} is the Nash equilibrium for player 2.
Given {x1, y1} is a Nash equilibria, for player 1 who tries to maximises his payoff, we may have payoff $\pi$(x1, y1) $\ge$ $\pi$ (x2, y1).
However, since (x2, y2) is a Nash equilibrium as well, for the second player plays to minimises the payoff of player 1, we have $\pi$(x2, y1) $\ge$ $\pi$ (x2, y2).

Combining these 2 inequalities, we may have
$$\pi (x1, y1) \ge \pi (x2, y1) \ge \pi(x2, y2) $$

And Similarly,
$$\pi (x1, y1) \le \pi (x1, y2) \le \pi(x2, y2) $$

Thus
$$ \pi (x1, y1) = \pi (x2, y1) =\pi (x1, y2) = \pi(x2, y2) $$

Since (x2, y2) is a Nash equilibrium for player 2,
for all strategy s2 in all strategies of player 2 , $$ \pi(x2, s2) \ge \pi(x2, y2) = \pi(x2, y1)$$ as proved above; similarly since (x1, y1) is a Nash equilibrium of for player 1, for all strategy s1 in all strategies of player 1,
$$ \pi (s1, y1) \le \pi (x1, y1) =\pi (x2, y1) $$

Similarly for (x1, y2). ■

**(b) In a 3-player zero-sum game, the payoffs of the three players in any outcome always sum to zero. Show that finding a Nash equilibrium in a 3-player zero-sum game is at least as hard as finding one in a general
two-player game.**
Want to show a reduction from finding a Nash equilibirum in a general 2-player game to finding one in a zero-sum 3-player game.

<!--Suppose that we know the equilibrium strategy of the 3rd player, given this context, we want to find the corresponding equilibrium strategies of the other 2 players. This remaining problem is a general two-player game, as their payoffs might not sum to 0.--->

Suppose we have a 2-player general game, whose payoffs may not sum to 0. Since any 2-player general game must have at least one Nash equilibrium, we suppose that for a Nash equilibrium $(m1, m2)$; $a(m1, m2)$ is the player1's playoff by playing $m1$ and $b(m1, m2)$ is the playoff of player 2 for her playing $m2$.

In this case, since this is a general 2-player game, the sum of payoffs $$a(m1, m2) + b(m1, m2) $$ in this case might not sum to 0.

Then, with player 1 and 2 still, suppose we have 3-player game consisting of players {p1, p2, p3}. Knowing that the 3rd player plays $m3$ as a equilibrium strategy, what is left to do is to find the Nash equilibrium strategies of the rest 2 players, whose two payoffs sum as
$$a(m1, m2, m3) + b(m1, m2, m3)$$ which might not sum to 0. And this is exactly a 2-player general game by knowing m3.

Moreover, by adopting our former comments on 2-player general game, we may have $$a(m1, m2, m3) + b(m1, m2, m3) + c(m1, m2, m3) = 0$$ by definition of 3-player zero-sum game.

Thus, a 2-player general game may be used to construct a 3-player zero-sum game. There is a reduction from finding a Nash equilibirum in a general 2-player game to finding one in a zero-sum 3-player game and thus finding a Nash equilibrium in a 3-player zero-sum game is at least as hard as finding one in a general two-player game. ■

### Q2 Zero-Sum game part 2
**Auction: Seller is trying to sell {$i_1$, $i_2$}. Buyers are {$p_1$, $p_2$}.
Buyer 1's payoff is the sum of her values for the item she wins - the sum of the prices of the items. Note that player 1 values both item at $1 and player 2 values the 2 items as 0, whose payoff = $-$player1 payoff.**

**Buyer 2 plays a threat strategy that minimises the max payoff of buyer 1. Their payoffs adding up and have a sum of 0 and this is a zero-sum game.
First round, the buyers place bids on 1 item i1, highest bidder wins and and they pay exactly their bids. Similarly i₂ is sold in the same fashion.**
**Suppose buyer 2 enters with $m to spend and** $$0 \le m \le 2$$. **Buyer 2 bids with restriction since if she uses up all $m on the first item, she can only spend the rest of her money on the second item.**

To find the value of this 0-sum game as a function of m, we want to find the payoff of Nash equilibrium of player 1 under the assumption that they bid simultaneously, not over-bidding and knowing each other's bids.

As introduced in class, with both players playing a Safe Strategy, we may have a Nash equilibrium. Player 1's safe strategy is to bid exactly as her value on the item, namely, $1 for each i₁ and i₂; meanwhile player 2 plays a "safe" strategy by bidding higher than player 1's bid.

Suppose $b_i$ belongs to player i.
For $i_1$, $b_{1,1}$ = $1$, $b_{2,1} \ge 1$; for $i_2$, $b_{1,2}$ = $$1$, $b_{2,2} = m-1$.
Value of the game = payoff of player 1 at Nash equilibirum.

The value of the game mainly depends on $m$.
**Case 1**: suppose $m < 1$
For the 1st round, player bid 1, and player 2 at most will only bid less than 1; in the 2nd round, player 1 bid for 1 and player 2 will only bid less than 1 or 0. In both round, player 1 gets the items.
Value $= 1 + 1 -1 -1 = 0$

**Case 2**: suppose $2\ge m > 1$
For the 1st round, player 1 bid for 1 and player 2 bid larger than player 1; thus in the second round, as player 1 bid for 1, player 2 does not have the ability to bid strictly higher than player 1. Player 1 only gets item 2.
Value $= 1 - 1 = 0$

**Case 3**: suppose $m=1$
Since the tie-breaker favors player 1, in any round player 2 will not get the item.
Value $1+1-1-1 = 0$

**Case 4**: suppose $m > 2$
In both round, player 2 has the ability to out-bit player 1, and thus player 1 gets nothing.
Value $= 0$
■

### Q3 The Lemke-Howson Algorithm
$$A=\left(\begin{array}{cc}
3&5&0\\
4&4&2\\
1&1&6
\end{array}\right)$$
List all symmetric Nash equilibrium of this game that can be found by the Lemke-Howson algorithm via the 3 possible walks starting from the origin.

We know that the polytype generated by A would be
$$ Ax \le 1 \\
x \ge 0$$

Such that
$$ 3x_1 + 5x_2 \le 1 \\
4x_1 + 4x_2 + 2x_3 \le 1 \\
x_1 + x_2 + 6x_3 \le 1 \\
x_1 \ge 0 \\
x_2 \ge 0 \\
x_3 \ge 0$$

The polytype generated is

### Q4 The Service Provider Game
**(a) In the corresponding game, each firm f selects a strategy (i.e. location) sf , and wants to maximize their profits. So given a set of strategies {s1 , s2 , . . . , sk }, what is the profit of firm f?**

By question, let price that customer $j$ pays to the firm f at stategy(location) $s_f$.

Supposed that for a firm f, the second smallest marginal cost to j at the location of another firm is denoted as
$min_{f' != f}C_{s_f, j}^{f'}$.

Also, denote the set of customers of firm $f$ in location $s_j$ as: $C_{s_f, j}^{f}$

Thus, we have profit of firm $f$ to be:
$$ \sum_{j \in C(s_f)} \{ min\{\pi_j, min_{f' != f}C_{s_f, j}^{f'}\} - C_{s_f, j}^{f} \}$$

Namely, the profit of firm $f$ is the sum of, all customers who accepted offer from firm $f$ in the location $s_f$, price depending on the min condition, subtracting the marginal cost of this firm.

**(b) What is the social welfare of a set of strategies {s1, s2, . . . , sk}?**

Social welfare = customer surplus + profits

Consumer Surplus = their value - what they actually charged
$= \pi_j- \{ min\{\pi_j, min_{f' != f}C_{s_f, j}^{f'}\}$

Social welfare of this set of strategies:
$$\sum_{j \in C(s_f)} \{ \pi_j- \{ min\{\pi_j, min_{f' != f}C_{s_f, j}^{f'}\}+min\{\pi_j, min_{f' != f}C_{s_f, j}^{f'}\} - C_{s_f, j}^{f} \} $$
$$= \sum_{j \in C(s_f)} \{ \pi_j-C_{s_f, j}^{f} \}$$

**(c ) Show by a potential function argument that this game has a Pure-strategy Nash
equilibrium.**

Potential function here is the sum of all marginal costs of a firm in s_j for each customer j;
to show a PSNE, we can show that minimising the potential function gives out maximization on social welfare.

### Q5 TTC part 1
**Use TTC to find a sore solution of trading game.**
p1: H4 ≻H5 ≻H8 ≻H2 ≻H1 ≻H7 ≻H3 ≻H6
p2: H8 ≻H6 ≻H2 ≻H1 ≻H4 ≻H3 ≻H7 ≻H5
p3: H4 ≻H1 ≻H8 ≻H2 ≻H5 ≻H6 ≻H3 ≻H7
p4: H4 ≻H1 ≻H2 ≻H3 ≻H5 ≻H6 ≻H8 ≻H7
p5: H8 ≻H7 ≻H6 ≻H4 ≻H5 ≻H3 ≻H1 ≻H2
p6: H2 ≻H1 ≻H4 ≻H3 ≻H6 ≻H5 ≻H8 ≻H7
p7: H2 ≻H1 ≻H4 ≻H8 ≻H6 ≻H5 ≻H7 ≻H3
p8: H3 ≻H8 ≻H4 ≻H7 ≻H1 ≻H2 ≻H6 ≻H5

C1: p1->p4 p2->p8 p3->p4 p4->p4 p5->p8 p6->p2 p7->p2 p8->p3
The cycle here is **p4->p4 to itself loop**.

Now it is left with:
p1: ~~H4~~ ≻H5 ≻H8 ≻H2 ≻H1 ≻H7 ≻H3 ≻H6
p2: H8 ≻H6 ≻H2 ≻H1 ≻~~H4~~ ≻H3 ≻H7 ≻H5
p3: ~~H4~~ ≻H1 ≻H8 ≻H2 ≻H5 ≻H6 ≻H3 ≻H7

p5: H8 ≻H7 ≻H6 ≻~~H4~~ ≻H5 ≻H3 ≻H1 ≻H2
p6: H2 ≻H1 ≻~~H4~~ ≻H3 ≻H6 ≻H5 ≻H8 ≻H7
p7: H2 ≻H1 ≻~~H4~~ ≻H8 ≻H6 ≻H5 ≻H7 ≻H3
p8: H3 ≻H8 ≻~~H4~~ ≻H7 ≻H1 ≻H2 ≻H6 ≻H5

C2: p1->p5 p2->p8 p3->p1 p5->p8 p6->p2 p7->p2 p8->p3
The cycle here is **p1->p5->p8->p3->p1**

Now we are left with:
p2: ~~H8~~ ≻H6 ≻H2 ≻~~H1 ~~≻~~H4~~ ≻~~H3~~ ≻H7 ≻~~H5
p6: H2 ≻~~H1~~≻~~H4~~ ≻~~H3~~ ≻H6 ≻~~H5~~ ≻~~H8~~ ≻H7
p7: H2 ≻~~H1~~ ≻~~H4~~ ≻~~H8~~ ≻H6 ≻~~H5~~ ≻H7 ≻~~H3~~

C3: p2->p6 p6->p2 p7->p2
The cycle here is **p2->p6->p2**

Lastly, we have:
p7: ~~H2~~ ≻~~H1~~ ≻~~H4~~ ≻~~H8~~ ≻~~H6~~ ≻~~H5~~ ≻H7 ≻~~H3~~
C4: **p7->p7** loop to itself.

Overall, the core solution is: p4 gets her own house, p1 gets the house of p5, p5 gets the house of p8, p8 gets the house of p3, p3 gets the house of p1; and finally p7 gets her own house.

### Q6 TTC Part 2
**(a) Give an example to show that, when ties are allowed, the top-trading cycle
algorithm does not always output a core solution.**

p1: H1 = H2 ≻ H3 = H4
p2: H4 = H1 ≻ H2 = H3
p3: H2 ≻ H3 = H4 ≻ H1
p4: H4 ≻ H3 ≻ H2 ≻ H1

Perform TTC algorithms following the given prefernece lists, we have:

C1: **p1->p1, p4->p4**
p1 and p4 get their own houses respectively.

Now left with:
p2: ~~H4 = H1~~ ≻ H2 = H3
p3: H2 ≻ H3 ~~= H4 ≻ H1~~

C2: **p2->p2**, p3->p2
Then we have p2 allocated her own house sincd it is a self loop.

Finally, we are left with only
p3: ~~H2 ≻~~ H3 ~~= H4 ≻ H1~~

C3: **p3-> p3**
P3 gets its own house too.

Thus the solution we get on this preference lists following TTC is that, every agent (p1, p2, p3, p4) gets their own house. But this is apparently not a core solution since there can be a blocking coalition formed by s = {p2, p3} $\subseteq$ {p1, p2, p3, p4}. Where p2 and p3 can simly switch their houses and resulting subset solution will be: **p2 getting H3 and p3 getting H2**.

This is a *pareto improved* outcome since p2 and p3 both get a house they like at least as much as the house they get in the solution produced by TTC, since for p2, she likes H2 just as much as H3 (H2 = H3); and for p3, her preference is H2 ≻ H3, which means that getting p2 later in the coalition makes her even better off. ■

**(b) We say that a coalition S strongly blocks an outcome O if by deviating every member of the coalition is strictly better off. Then, an outcome is in the weak core if no coalition strongly blocks it. Show that, in the house-trading game with ties allowed, the top-trading cycle algorithm outputs an allocation in the weak core.**

Prove by contradiction, let O be the outcome produced by the TTC algoritghm performed in the house-trading game with ties allowed, and suppose this O is NOT in the weak core. And such that, some subsets of agents S gets better house allocation than the one in O.
Let such S = {1,2,3,...,n}. And assume the pareto-improved reallocation is that agent 1 gets H2, agent 2 gets H3, agent 3 gets H4,... and agent n-1 gets Hn and finally agent n gets 1 forming a cycle. The reallocation shows that agent 1 strictly prefers H2 than what he was allocated in O which we here denoted as O(1) and by the context "strict" we know that H2 ≻ O(1).

This means that in TTC allocation, H2 is not in the available preference lists, which further means that agent 2 has already traded H2 with other agents or left with her own house H2 before agent 1 is able to form a cycle with agent 2. Without loss of generality, similarly we safely assume that this is the same for agent 2 and H3, where H3 must have left the available preference list before agent 2 trades or leaves (forming a cycle). The same assumption could be made for the rest of all agents and houses.

At last, H1 must have left the available preference lists before agent n trades or leaves, which follows that agent 1 can only trade H1 or leaves after H1 has left the preference lists. This apparently is a contradiction.
Overall, the outcome from house-trading game with ties using TTC algorithm is in the weak core.■