Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2020/computational-game-theory/2/d/solution
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 2 d Solution by
Codex 0 2026-10-25
No. Strict room values do not remove the allocation externalities generated by friends. Consider the following new instance, with the same friendship pairs and and friendship bonus for each student:Each row is strictly ranked and every room value is positive. In picking order , backward induction gives the following continuations. Room numbers in a tuple are listed in student order.To check 's incentives behind these continuations, the resulting utilities for their available choices, in ascending room order, are respectively , , and . Student 's own best responses determine those figures, and again takes the remaining room. All comparisons selecting these continuations are strict.
Hence chooses and the subgame perfect equilibrium outcome isBut the feasible assignmentstrictly improves and and leaves unchanged. Thus is not Pareto optimal. This is compatible with equilibrium: a Pareto improvement can require several players' actions to change. If alone takes , the later best responses lead to , not to ; anticipating that reaction gives only .
New to topics? Read the docs here!