Implementing Random Assignments: A Generalization of the Birkhoff-von Neumann Theorem

Abstract. The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide sev-eral applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two-sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature