Past exam of the computer science course of the University of Oxford / 2020 / Computational game theory / 2 / d

No. Strict room values do not remove the allocation externalities generated by friends. Consider the following new instance, with the same friendship pairs $\{S_1,S_4\}$ and $\{S_2,S_3\}$ and friendship bonus $0.4$ for each student:Each row is strictly ranked and every room value is positive. In picking order $S_1,S_2,S_3,S_4$, backward induction gives the following continuations. Room numbers in a tuple are listed in student order.To check $S_2$'s incentives behind these continuations, the resulting utilities for their available choices, in ascending room order, are respectively $(0.50,0.70,0.02)$, $(0.01,0.70,0.42)$, $(0.41,0.50,0.02)$ and $(0.41,0.90,0.70)$. Student $S_3$'s own best responses determine those figures, and $S_4$ again takes the remaining room. All comparisons selecting these continuations are strict.

Hence $S_1$ chooses $r_2$ and the subgame perfect equilibrium outcome isBut the feasible assignmentstrictly improves $S_1$ and $S_4$ and leaves $S_2,S_3$ unchanged. Thus $a$ is not Pareto optimal. This is compatible with equilibrium: a Pareto improvement can require several players' actions to change. If $S_1$ alone takes $r_1$, the later best responses lead to $(r_1,r_3,r_2,r_4)$, not to $a^{\prime }$; anticipating that reaction gives $S_1$ only $0.50$.