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

No: arbitrary ties can produce an assignment that is not Pareto optimal. A two-student counterexample suffices. Give the first student value $1$ for both rooms; give the second student value $1$ for $r_1$ and $0$ for $r_2$. If the first student breaks the tie by taking $r_1$, the second must take $r_2$, and the utility vector is $(1,0)$.

Swapping the rooms gives utility vector $(1,1)$, so it is a Pareto improvement. Both choices in the original run maximized the corresponding student's available room value. The strict-ranking argument from (a) fails because the first student's utility need not decrease when that student's room changes.