A collection of functions for solving and analyzing school-choice problems. See examples/Tutorial.jl for usage examples.

Some of the algorithms in this module are optimized for preference lists given in "permutation" order, and others in "rating" order. Which order is used can be confirmed by inspecting each function call. If the input calls for students, then the function expects "rating" order, where if column i of students is [3, 1, 2], this implies that school 1 is i's 3rd choice, school 2 is her 1st choice, and school 3 is her 2nd choice. If the input calls for students_inv, then the expected input is [2, 3, 1], which means the same. These can be trivially related via invperm().

DA_rank_dist(students, schools, capacities; verbose, rev)

Convenience function that runs DA and outputs the cumulative rank distribution data.

RSD(students_inv, capacities)

Random serial dictatorship mechanism for one-sided matching (i.e. schools have neutral preferences).

TTC(students_inv, assn; verbose)

Uses the top-trading cycles allocation to find the market core, given an initial assignment. The implementation follows Nisan et al. (2007), §10.3.

TTC_match(students, capacities; verbose)

Uses TTC to find a heuritically optimal one-sided school assignment. Seeds with RSD.

argsort(vec)

Associate each item in vec with its (descending) rank. Convenience wrapper of sortperm().

assignmentfrompreflists(students_inv, students_dist, cutoffs;
                    return_demands=false)

Return assignment associated with given cutoffs and, if return_demands=true, the demands. For demands only, demandfrompreflists() is faster. Ignores capacity constraints.

choiceaugmented(arr, targets, blend_target=0, blend_others=0; return_add)

Tiebreaker function for the choice-augmented deferred acceptance mechanism described by Abdulkadiroğlu et al. (2015). Primary tiebreaking is accomplished by allowing students to signal a target school; secondary ties are broken by independent STB lotteries in the target and other schools (by default). Or, indicate another mechanism by configuring blend_target and blend_others, following ?hybridtiebreaking.

return_add is a Bool indicating whether to return the tiebreaking numbers (lottery numbers) as second entry of output tuple.

Truncate a cutoff vector to the probability simplex. Useful because some methods produce negative cutoffs while iterating.

cycle_DFS(edges)

Given the edges of a graph (in dictionary form), uses depth-first search to find cycles. Assumes all cycles are node disjoint.

deferredacceptance(students, schools, capacities; verbose, rev)

Given an array of student preferences, where students[i, j] indicates the rank that student j gave to school i, and an array of the transposed shape indicating the schools' rankings over the students, uses student-proposing DA to compute a stable assignment. Returns a vector of schools corresponding to each student (m + 1 indicates unassigned) and a list of the student rankings associated with each match. Both sets of preferences must be strict; use STB() or similar to preprocess if your data does not satisfy this.

Set rev=true to use school-proposing DA instead.

demandfromMNL_iid(qualities, cutoffs)

Return demand for each school given a set of cutoffs and ignoring capacity, using multinomial logit choice model and assuming scores are iid uniform (equivalent to MTB when schools have no preferences).

Satifies WGS and score independence, so equilibrium can be computed using DA_nonatomic_lite().

demandfromMNL_singlescore(qualities, cutoffs)

Return demand for each school given a set of cutoffs and ignoring capacity, using multinomial logit choice model and assuming all schools use a single score (equivalent to STB when schools have no preferences).

Satisfies WGS but not score independence, so equilibrium must be computed using nonatomic_tatonnement().

demandfrommixedMNL_tscores(qualities, profile_dist, blends, cutoffs;
                    n_points=10000, verbose=false, montecarlo=false)

Return demand for each school given a set of cutoffs and ignoring capacity, using mixed multinomial logit choice model with p student profiles and t test scores shared among schools.

qualities is a C by p matrix, where C is the number of schools. Each column of qualities gives the quality vector with respect to a student profile. This generalizes demandfromMNL_iid().

If an applicant's test score vector is x, then her composite score at school c is blend[c, :] * x, where blend[c, :] is a school-specific convex combination of the t test scores, which we assume are iid uniform. This generalizes demandfromMNL_singlescore().

n_points is the approximate number of test points to use if montecarlo evaluation is selected. Which method is more effecient depends on the problem dimensions, but in general, for problems with many schools or tests, consider MC.

Satisfies WGS but not score independence, so equilibrium must be computed using nonatomic_tatonnement().

demandfrompreflists(students, students_dist, cutoffs)

Return demand for each school given a set of cutoffs and ignoring capacity, using given preference lists and assuming iid scores at each school.

Satifies WGS and score independence, so equilibrium can be computed using DA_nonatomic_lite().

hybridtiebreaking(arr, blend; return_add)

Given schools' ranked preference lists, which may contain ties, break ties using a hybrid tiebreaking rule as indicated by entries of blend. blend should be a row vector with one entry on $[0, 1]$ for each column in arr. 0 means that school will use STB, 1 means MTB, and a value in between yields a convex combination of the rules, which produces interesting results but has not yet been theoretically analyzed. If blend is a scalar, use the same value at all schools. Undefined behavior for values outside the $[0, 1]$ interval.

return_add is a Bool indicating whether to return the tiebreaking numbers (lottery numbers) as second entry of output tuple.

ismarketclearing(qualities, capacities, cutoffs;
                 tol=1e-6)

Check if a set of cutoffs is market clearing with respect to the given nonatomic market. Nonatomic analogue of isstable() by Lemma 1 of Azevedo and Leshno (2016).

ismarketclearing(qualities, capacities, cutoffs;
                 tol=1e-6)

Check if a set of cutoffs is market clearing with respect to the given nonatomic market. Nonatomic analogue of isstable() by Lemma 1 of Azevedo and Leshno (2016).

ismarketclearing(students, students_dist, capacities, cutoffs;
                 tol=1e-6)

Check if a set of cutoffs is market clearing with respect to the given nonatomic market. Nonatomic analogue of isstable() by Lemma 1 of Azevedo and Leshno (2016).

isstable(students, schools, capacities, assn; verbose)

Test if a discrete matching is stable. Allows for ties in school rankings.

multipletiebreaking(arr)

Given schools' ranked preference lists, which may contain ties, break ties using the multiple tiebreaking rule by adding to arr a column of random floats having the same shape, then ranking the result columnwise.

nonatomicdeferredacceptance(students, students_dist, schools, capacities;
             verbose, rev, return_cutoffs, tol)

Nonatomic (continuous) analogue of deferredacceptance(). Students are a continuum of profiles distributed over a fixed set of student preference lists, and school capacities are fractions of the total student population. School preferences are optional. If you pass schools=nothing, it assumes that student preferability is uncorrelated with student profile, and the schools simply accept the best students from each profile. This is the more realistic case; the algorithm is not incentive compatible if schools can favor students based on the students' preferences.

When school preferences are not nothing, rev is a placeholder and reverse mode has not yet been implemented.

Returns a tuple expressing the assignment as an array, where the [i, j]entry indicates the measure of students having preference listjadmitted to schooliandi + 1` indicates nonassignment, and a vector giving the average utility in each preference list.

Set return_cutoffs=true to get the score cutoffs associated with the match, after Azevedo and Leshno (2016). These cutoffs are the state space of the algorithm and therefore more numerically accurate than the assignment array itself. To get only the cutoffs, use nonatomicdeferredacceptance_iid() (which this function wraps wheen schools===nothing) or nonatomictatonnement() (which is not a DA algorithm but can compute equilibrium cutoffs in a wider range of scenarios).

nonatomicdeferredacceptance_iid(demand, capacities;
                  verbose, rev, tol, maxit)

Nonatomic (continuous) analogue of deferredacceptance(), simplified to return only the score cutoffs associated with each school, where demand is given by an arbitrary function that takes score cutoffs as inputs. This algorithm assumes that student preferability is independent at each school and that the demand function satisfies weak gross substitutability. To relax the former assumption, use nonatomictatonnement().

nonatomicdeferredacceptance_iid(students, students_dist, capacities;
                  verbose, rev, tol)

Nonatomic (continuous) analogue of deferredacceptance(), simplified to return only the score cutoffs associated with each school, after Azevedo and Leshno (2016).

Students are a continuum of profiles distributed over a fixed set of student preference lists, and school capacities are fractions of the total student population. Returns only the cutoffs; use assignmentfrompreflists() to get the match array or nonatomicdeferredacceptance() for a wrapper function.

nonatomicsecant(demand, capacities; verbose, tol, maxit)

Search for a market-clearing cutoff vector using a modified secant method with tâtonnement as a fallback when change in demand is small. Less theoretically legit than nonatomictatonnement() but tends to make fewer calls to demand().

demand is a school demand function that takes cutoffs as input.

nonatomictatonnement(demand, capacities; verbose, tol, β, maxit)

Search for a market-clearing cutoff vector using a modified tâtonnement process. Analogous to nonatomicdeferredacceptance_iid() but more robust; nonatomictatonnement() converges for any demand function that satisfies weak gross substitutability.

demand is a school demand function that takes cutoffs as input.

β is a step size parameter, where the step size is 1 / nit ^ β, where nit is the iteration number.

numericaladmitrate(B, cutoffs; n_points=1000)

Numerically compute the admissions rate for each school when school's blends are the rows of B and scores are iid uniform. That is, compute the probability that B[c, :] * x >= cutoffs[c], where x is iid uniform. Uses a meshgrid iterator with (about) n_points of evaluation.

singletiebreaking(arr)

Given schools' ranked preference lists, which may contain ties, break ties using the single tiebreaking rule by generating a column of floats, adding this column to each column of arr, and ranking the result columnwise.

welfaretiebreaking(students, schools, blend; equity, return_add)

Given schools' ranked preference lists, which contain ties, first break ties using student welfare, then break subsequent ties using a hybrid tiebreaking rule indicated by entries of blend. Or in equity=true mode, break ties by minimizing student welfare, which gives priority in DA to students whose current assignment is poor. See ?hybridtiebreaking for an explanation of how to configure blend.

blend=0 is known as the Boston mechanism.

return_add is a Bool indicating whether to return the tiebreaking numbers (lottery numbers) as second entry of output tuple.