Random matchings

Random matchings are the subject of two new papers.

The first (not in chronological order:) IMPLEMENTING RANDOM ASSIGNMENTS: A GENERALIZATION OF THE BIRKHOFF-VON NEUMANN THEOREM by ERIC BUDISH, YEON-KOO CHE, FUHITO KOJIMA, AND PAUL MILGROM

Abstract. "The literature on random mechanisms often describes outcomes incompletely as "random assignments" expressing the expected number of objects of each type assigned to different agents and a set of feasibility constraints that a pure assignment must satisfy. We provide a necessary and sufficient condition (the "bihierarchy" condition) for the set of constraints to have the property that if the random assignment satisfies them, then it is implementable by a lottery over feasible pure assignments. Our theorem maximally generalizes the celebrated Birkhoff-von Neumann theorem. We also provide an algorithm to implement any such random assignment. Several applications are described, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) twosided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications outside economics, generalizing previous results on the minimize makespan problem in the computer science literature."

The second (no significance to the ordering aside from when I read them) is "An Equivalence result in School Choice" by Jay Sethuraman
ABSTRACT: "The main result of the paper is a proof of the equivalence of single and multiple lottery mechanisms for the problem of allocating students to schools in which students have strict preferences and the schools are indifferent. This solves a recent open problem proposed by Pathak, who was motivated by the practical problem of assigning students to high schools in New York City. In proving this result, a new approach is introduced, that simplifies and unifies all the known equivalence results in the house allocation literature. Along the way, two new mechanisms—Partitioned Random Priority and Partitioned Random Endowment—are introduced for the house allocation problem. These mechanisms generalize several known and well-studied mechanisms for the house allocation problem and are particularly appropriate for many-to-one versions of the problem, the school choice problem being the most prominent."

(And here's a link to the earlier paper by Parag Pathak: Lotteries in Student Assignment: The Equivalence of Queueing and a Market-Based Approach)