Public Interface

deferred_acceptance(prop_prefs, resp_prefs, prop_caps, resp_caps)

Compute a stable matching by the DA algorithm for a many-to-many matching problem.

Arguments

• prop_prefs::Matrix{Int} : Array of shape (n+1, m) containing the proposers' preference orders as columns, where m is the number of proposers and n is that of the responders. prop_prefs[j, i] is the j-th preferred responder for the i-th proposer, where "responder 0" represents "vacancy".
• resp_prefs::Matrix{Int} : Array of shape (m+1, n) containing the responders' preference orders as columns. resp_prefs[i, j] is the i-th preferred proposer for the j-th responder, where "proposer 0" epresents "vacancy".
• prop_caps::Vector{Int} : Vector of length n containing the proposers' capacities.
• resp_caps::Vector{Int} : Vector of length n containing the responders' capacities.

Returns

• prop_matches::Vector{Int} : Vector of length m representing the matches for the proposers, where the responders who proposer i is matched with are contained in prop_matches[prop_indptr[i]:prop_indptr[i+1]-1].
• resp_matches::Vector{Int} : Vector of length n representing the matches for the responders, where the proposers who responder j is matched with are contained in resp_matches[resp_indptr[j]:resp_indptr[j+1]-1].
• prop_indptr::Vector{Int} : Contains index pointers for prop_matches.
• resp_indptr::Vector{Int} : Contains index pointers for resp_matches.

deferred_acceptance(prop_prefs, resp_prefs)

Compute a stable matching by the DA algorithm for a one-to-one matching (marriage) problem.

Arguments

• prop_prefs::Matrix{Int} : Array of shape (n+1, m) containing the proposers' preference orders as columns, where m is the number of proposers and n is that of the responders. prop_prefs[j, i] is the j-th preferred responder for the i-th proposer, where "responder 0" represents "being-single".
• resp_prefs::Matrix{Int} : Array of shape (m+1, n) containing the responders' preference orders as columns. resp_prefs[i, j] is the i-th preferred proposer for the j-th responder, where "proposer 0" represents "being-single".

Returns

• prop_matches::Vector{Int} : Vector of length m representing the matches for the proposers, where prop_matches[i] is the responder who proposer i is matched with.
• resp_matches::Vector{Int} : Vector of length n representing the matches for the responders, where resp_matches[j] is the proposer who responder j is matched with.

deferred_acceptance(s_prefs, c_prefs, caps[, proposal])

Compute a stable matching by the DA algorithm for a many-to-one matching (college admission) problem.

Arguments

• s_prefs::Matrix{Int} : Array of shape (n+1, m) containing the students' preference orders as columns, where m is the number of students and n is that of the colleges. s_prefs[j, i] is the j-th preferred college for the i-th studnet, where "college 0" represents "being single".
• c_prefs::Matrix{Int} : Array of shape (m+1, n) containing the colleges' preference orders as columns. c_prefs[i, j] is the i-th preferred student for the j-th college, where "student 0" represents "vacancy".
• caps::Vector{Int} : Vector of length n containing the colleges' capacities.
• proposal::Type(SProposing) : SProposing runs the student-proposing DA algorithm, while CProposing runs the college-proposing algorithm. Default to the former.

Returns

• s_matches::Vector{Int} : Vector of length m representing the matches for the students, where s_matches[i] is the college that proposer i is matched with.
• c_matches::Vector{Int} : Vector of length n representing the matches for the colleges, where the students who college j is matched with are contained in c_matches[indptr[j]:indptr[j+1]-1].
• indptr::Vector{Int} : Contains index pointers for c_matches.

random_prefs([rng, ]m, n[, ReturnCaps]; allow_unmatched=true)

Generate random preference order lists for two groups, say, m males and n females.

Each male has a preference order over femals [1, ..., n] and "unmatched" which is represented by 0, while each female has a preference order over males [1, ..., m] and "unmatched" which is again represented by 0.

The argument ReturnCaps should be supplied in the context of college admissions, in which case "males" and "females" should be read as "students" and "colleges", respectively, where each college has its capacity.

The optional rng argument specifies a random number generator.

Arguments

• m::Integer : Number of males.
• n::Integer : Number of females.
• ::Type{ReturnCaps} : If supplied, caps is also returned.
• ;allow_unmatched::Bool(true) : If false, return preference order lists of males and females where 0 is always placed in the last place, (i.e., "unmatched" is least preferred by every individual).

Returns

• m_prefs::Matrix{Int} : Array of shape (n+1, m), where each column contains a random permutation of 0, 1, ..., n.
• f_prefs::Matrix{Int} : Array of shape (m+1, n), where each column contains a random permutation of 0, 1, ..., m.
• caps::Vector{Int} : Vector of length n containing each female's (or college's) capacity. Returned only when ReturnCaps is supplied.

Examples

julia> m_prefs, f_prefs = random_prefs(4, 3);

julia> m_prefs
4x4 Array{Int64,2}:
 3  3  1  3
 0  2  3  1
 2  1  2  0
 1  0  0  2

julia> f_prefs
5x3 Array{Int64,2}:
 1  2  4
 4  3  1
 3  4  2
 0  0  0
 2  1  3

julia> m_prefs, f_prefs = random_prefs(4, 3, allow_unmatched=false);

julia> m_prefs
4x4 Array{Int64,2}:
 1  3  1  2
 2  1  3  3
 3  2  2  1
 0  0  0  0

julia> f_prefs
5x3 Array{Int64,2}:
 1  2  3
 2  3  4
 4  1  1
 3  4  2
 0  0  0

julia> s_prefs, c_prefs, caps = random_prefs(4, 3, ReturnCaps);

julia> s_prefs
4x4 Array{Int64,2}:
 2  1  2  1
 1  3  1  0
 3  2  3  3
 0  0  0  2

julia> c_prefs
5x3 Array{Int64,2}:
 3  4  1
 0  1  4
 4  3  0
 1  2  3
 2  0  2

julia> caps
3-element Array{Int64,1}:
 1
 2
 2