= Solution
\b[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>.
|| $S_1$ room
|| $S_2$ room
|| Optimal $S_3$ room
|| Resulting $U_2$
| $r_1$
| $r_2$
| $r_4$
| $0.5$
| $r_1$
| $r_3$
| $r_2$
| $0.7$
| $r_1$
| $r_4$
| $r_2$
| $0$
| $r_2$
| $r_1$
| $r_4$
| $0$
| $r_2$
| $r_3$
| $r_4$
| $0.7$
| $r_2$
| $r_4$
| $r_3$
| $0.4$
| $r_3$
| $r_1$
| $r_2$
| $0.4$
| $r_3$
| $r_2$
| $r_4$
| $0.5$
| $r_3$
| $r_4$
| $r_2$
| $0$
| $r_4$
| $r_1$
| $r_2$
| $0.4$
| $r_4$
| $r_2$
| $r_1$ or $r_3$
| $0.9$
| $r_4$
| $r_3$
| $r_2$
| $0.7$
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.
Back to article page
