`DeferredAcceptance.DeferredAcceptance`

— ModuleA 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()`

.

`DeferredAcceptance.DA_rank_dist`

— Method`DA_rank_dist(students, schools, capacities; verbose, rev)`

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

`DeferredAcceptance.RSD`

— Method`RSD(students_inv, capacities)`

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

`DeferredAcceptance.TTC`

— Method`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.

`DeferredAcceptance.TTC_match`

— Method`TTC_match(students, capacities; verbose)`

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

`DeferredAcceptance.argsort`

— Method`argsort(vec)`

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

.

`DeferredAcceptance.assignmentfrompreflists`

— Method```
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.

`DeferredAcceptance.choiceaugmented`

— Function`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.

`DeferredAcceptance.cutbox`

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

`DeferredAcceptance.cycle_DFS`

— Method`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.deferredacceptance`

— Method`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.

`DeferredAcceptance.demandfromMNL_iid`

— Method`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()`

.

`DeferredAcceptance.demandfromMNL_singlescore`

— Method`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()`

.

`DeferredAcceptance.demandfrommixedMNL_tscores`

— Method```
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()`

.

`DeferredAcceptance.demandfrompreflists`

— Method`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()`

.

`DeferredAcceptance.hybridtiebreaking`

— Function`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.

`DeferredAcceptance.ismarketclearing`

— Method```
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).

`DeferredAcceptance.ismarketclearing`

— Method```
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).

`DeferredAcceptance.ismarketclearing`

— Method```
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).

`DeferredAcceptance.isstable`

— Method`isstable(students, schools, capacities, assn; verbose)`

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

`DeferredAcceptance.multipletiebreaking`

— Method`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.

`DeferredAcceptance.nonatomicdeferredacceptance`

— Method```
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 list`

j`admitted to school`

i`and`

i + 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).

`DeferredAcceptance.nonatomicdeferredacceptance_iid`

— Method```
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()`

.

`DeferredAcceptance.nonatomicdeferredacceptance_iid`

— Method```
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.

`DeferredAcceptance.nonatomicsecant`

— Method`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.

`DeferredAcceptance.nonatomictatonnement`

— Method`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.

`DeferredAcceptance.numericaladmitrate`

— Method`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.

`DeferredAcceptance.singletiebreaking`

— Method`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.

`DeferredAcceptance.welfaretiebreaking`

— Function`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.