DeferredAcceptance: Solving and analyzing school-choice problems

I introduce DeferredAcceptance, a Julia package that solves both discrete and nonatomic school-choice problems using a variety of modern algorithms.


The stable assignment problem, introduced in the 1960s by David Gale and Lloyd Shapley, has recently elicited new interest due to its applications in public school assignment and a new, nonatomic framing that relates stable school assignments to market-clearing cutoff vectors. I introduce DeferredAcceptance, a Julia package for solving and analyzing school-choice problems. It provides several variations of the discrete Gale-Shapley and top-trading cycles algorithms, as well as a trio of memory-efficient algorithms for computing an equilibrium in nonatomic admissions markets. In the discrete case, while there are some open-source tools available for running the basic form of the Gale-Shapley algorithm, DeferredAcceptance enables seamless comparison of a variety of assignment procedures for given market data. In the nonatomic case, DeferredAcceptance provides school-demand functions based on the multinomial logit choice model and a variety of scoring schemes; it also permits a user-defined demand function, enabling simulation of a wide range of competitive scenarios.

See also: