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

The assignment is Pareto optimal. Write $a_i$ for the room selected by the $i$th student. Suppose another assignment $a^{\prime }$ makes every student at least as well off. The first student already selected their uniquely most valuable room, so $a_1^{\prime }=a_1$. Once the rooms of students $1,\dots ,i-1$ are fixed, the rooms available to student $i$ in the original serial dictatorship are exactly the rooms that remain after those fixed assignments. Student $i$ chose the unique maximum among them, so weak improvement requires $a_i^{\prime }=a_i$.

Mathematical induction fixes every student's room. Thus $a^{\prime }=a$ and nobody can be strictly better off, contradicting the definition of a Pareto improvement. Strict room rankings and the absence of allocation externalities are the essential assumptions: a student's utility is determined solely by their own room.^[ref]

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.

The equilibrium assignment is $(S_1,S_2,S_3,S_4)\mapsto (r_2,r_3,r_4,r_1)$, with utility vector $(0.7,0.7,0.9,0.4)$. Apply backward induction to the finite perfect-information game, accounting for the two friendship pairs in every terminal assignment. Student $S_4$ receives the last room and has no remaining choice. Given the first two rooms, $S_3$ chooses the remaining room maximizing their own room value plus $0.4$ if adjacent to $S_2$.

The following complete third-stage comparisons summarize the continuations. The utility in the last column is $S_2$'s resulting utility, after $S_3$ makes the indicated best response.

For example, after $S_1$ takes $r_2$ and $S_2$ takes $r_3$, student $S_3$ compares $r_1$, giving $0$, with $r_4$, giving $0.5+0.4=0.9$. Choosing $r_4$ also gives $S_2$ the adjacency bonus, making $U_2=0.3+0.4=0.7$. The last room $r_1$ is adjacent to $S_1$'s $r_2$.

The table makes $S_2$ choose $r_3,r_3,r_2,r_2$ after first-stage choices $r_1,r_2,r_3,r_4$, respectively. Their resulting consequences for $S_1$ are $0.5,0.7,0$, and either $0$ or $0.4$. Thus $S_1$ strictly prefers $r_2$, proving the displayed outcome.

There is an off-path tie for $S_3$ after $(r_4,r_2)$, so the entire subgame perfect equilibrium strategy profile need not be unique. Either choice, or any mixture of them, gives $S_1$ at most $0.4$ after choosing $r_4$, below $0.7$. The equilibrium assignment on the played path is therefore unaffected by this tie. Specifying these optimal continuations at every history, including the unplayed ones, supplies a subgame perfect equilibrium rather than merely a proposed path.

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$.

Every subgame perfect equilibrium outcome is Pareto optimal under the stated consecutive-friend and bonus conditions. Partition the choosing order into blocks: a single student without a friend, or two friends who choose consecutively. Their slots in the choosing order are adjacent; the proof must separately establish when their allocated rooms will be adjacent.

Let $R$ be the rooms remaining before a friend block, with leader $i$ and follower $j$. Because $0\le v_{i,r},v_{j,r}\le 1$ and $f_i,f_j>1$, each friend strictly prefers every adjacent-to-friend allocation to every nonadjacent one. After leader $i$ takes room $r$ with an available adjacent room, follower $j$ therefore takes their uniquely highest-valued room among the available neighbors of $r$. The leader consequently knows they will receive the adjacency bonus.

If $R$ contains at least one pair of adjacent rooms, let $E(R)$ be its nonisolated rooms: the rooms having an available neighbor. Leader $i$ must choose from $E(R)$, because choosing there guarantees utility greater than $1$, whereas an isolated choice gives at most $1$. Since the bonus is then fixed and room values are distinct, the leader chooses their unique maximum-value room in $E(R)$. The follower chooses their unique best neighbor. Later students cannot change either allocated room, so later play cannot alter these two students' utilities.

If $R$ contains no adjacent pair, neither friend can obtain the bonus under any allocation of rooms from $R$. Both simply choose their uniquely most valuable remaining room in turn. Removing rooms cannot create a new physical adjacency, so no hidden later move can change that conclusion. A one-student block likewise chooses their unique best available room.

Now compare the equilibrium assignment $a$ with any proposed Pareto improvement $a^{\prime }$. Induct over these blocks, assuming earlier blocks' rooms are already fixed. Thus $a$ and $a^{\prime }$ have the same remaining set $R$ at the present block. A lone student's room must stay fixed by strict preferences.

For a friend block obtaining adjacency in $a$, both students must retain adjacency in $a^{\prime }$: losing a bonus larger than $1$ cannot be compensated by any room-value increase. The leader's room in $a^{\prime }$ must therefore belong to $E(R)$. It cannot differ from the unique highest-valued room the leader selected there without reducing that leader's utility. Once the leader's room is fixed, the follower likewise must retain the uniquely best available neighbor. If $R$ has no adjacent pair, both rooms stay fixed by the ordinary strict-ranking argument.

Thus every block's rooms are unchanged. The only assignment weakly improving all students is $a$ itself, so no strict improvement is possible. This proves Pareto efficiency of serial dictatorship with consecutive friends. The proof applies to every subgame perfect equilibrium, since the required choices at each block are strict best responses determined by the available rooms.