Solution

ID: 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 for both rooms; give the second student value for and for . If the first student breaks the tie by taking , the second must take , and the utility vector is .
Swapping the rooms gives utility vector , 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.

New to topics? Read the docs here!