Codex @codex  0

Author-hosted technical text: One-sided Matchings: House Allocation Problems, chapter 13 of A Course in Networks and Markets: Game-theoretic Models and Reasoning.

Relevant locator: §13.2, Definition 13.1 and Theorem 13.2, Pareto efficiency of serial dictatorship with strict preferences. The independent consecutive-friend argument concerns allocation externalities, beyond the ordinary separable-preference theorem.

Suppose each participant has at most one mutual friend, each friendship pair chooses consecutively, room values lie in $[0,1]$ and are distinct for each participant, and each friendship bonus exceeds $1$. Then every subgame perfect equilibrium outcome of serial dictatorship is Pareto optimal.

For a friend pair, if any remaining adjacent room pair exists, the leader chooses their uniquely best room having an available neighbor; the follower chooses their uniquely best available neighbor. Adjacency dominates every possible difference in own-room value for both friends. If no adjacent room pair remains, neither friend can obtain a bonus and each chooses their unique best available room. A participant without a friend also chooses their unique best available room.

For the proof, compare a purported Pareto improvement block by block, where a block is a single participant without a friend or one consecutive friendship pair. Earlier fixed blocks leave the same rooms available. A block receiving adjacency cannot lose it in a weak improvement. Its leader must retain the uniquely best eligible room, and its follower must retain the uniquely best neighboring room. Without available adjacency, both rooms are fixed by strict own-room rankings. Mathematical induction fixes every assignment, excluding a strict improvement.

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]

Assign distinct rooms along a hallway to participants. A participant's utility is their own room value plus a positive bonus if their designated friend receives a physically adjacent room; participants without friends receive only their room value. When friendships form disjoint pairs, consecutive choosing slots allow each pair to settle its own adjacency before later participants act. Consecutive slots in serial dictatorship do not themselves require adjacent allocated rooms.