My previous post concerned fairly assigning students to campus housing based only on the students’ preferences. From a comment by Mark C. Wilson, I learn that this problem has a large literature, and is called either house assignment or one-sided matching. The lottery system I described for solving it (in which the students are randomly ordered and, in that order, choose their preferred house among the ones still available) is called random serial dictatorship. Here, “dictatorship” means that one person chooses the outcome, “serial” means they take turns being that one person, and “random” means that the order in which they take turns is randomized. And the property that I called “stability” (that no subset of students can, after the fact, trade assignments and all improve) is more often called “Pareto optimality”.

The definition of stability (or Pareto optimality) involves arbitrary reassignments among arbitrary subsets of students, so testing it directly would take exponential time. But it turns out to be possible to recognize stable assignments much more easily, based on the fact that the only assignments that can be stable are the ones that could have been chosen by a serial dictatorship. My previous post explains why serial dictatorships are stable: in every subset of students, the first student to choose gets an unimprovable assignment.

To see that every stable assignment can be constructed in this way, consider an arbitrary assignment \(A\) (not necessarily stable) and construct a directed graph \(G\) from \(A\) as follows. The vertices of \(G\) will be the students and the houses, and each edge will connect a student to a house or vice versa, so \(G\) will be bipartite. It includes a single outgoing edge from each student, to the house that student is assigned to. However, there may be multiple incoming edges, one from each house that the student would prefer over their actual assignment.

If \(A\) happens to have been created by a serial dictatorship, then consider the steps of the serial dictatorship process (in which either a student chooses a house, or a house becomes full) and use the chronological ordering of these steps to place the vertices of \(G\) into a sequence. This sequence is necessarily a topological ordering, meaning that each edge of \(G\) is directed from earlier in the sequence to later. For, a student cannot choose a house after that house becomes full, so the outgoing edge for each student is properly oriented. And a student cannot pass up a preferred house unless that house is already full, so the incoming edge for each student is properly oriented as well. Thus, when \(A\) comes from a serial dictatorship, \(G\) is a directed acyclic graph.

The reverse is true as well: when \(G\) is a directed acyclic graph, its assignment \(A\) could have been formed by a serial dictatorship. For, every directed acyclic graph has a topological order. If we construct the serial dictatorship for the student ordering given by a topological order, the students will necessarily choose assignment \(A.\) In particular, when \(G\) is acyclic, \(A\) is stable.

And finally, when \(G\) is not acyclic, \(A\) is not stable. For, suppose \(G\) has a cycle. Then, if we reverse that cycle and consider the new outgoing edges from each student vertex of the cycle, we will find a subset of students (the ones in the cycle) and a reassignment of those students (the new outgoing edges) that improves the assignment of everyone in the subset.

Based on this characterization, we can test whether a given assignment is stable, find a serial dictatorship ordering for it when it is stable, or find an unstable subset of students when it is not, in time linear in the input size (the preference listings of all the students). The problem becomes one of testing whether a given graph is a directed acyclic graph, finding a topological ordering for it, or finding a cycle in it, all of which have standard algorithms taking linear time.