Function Repository Resource:

FindStableMatching

Find a stable matching between two sets of elements with expressed preferences for each other

Contributed by: Daniel McDonald

ResourceFunction["FindStableMatching"][<|name_1,1→list_1,1,name_1,2→list_1,2,…|>,<|name_2,1→list_2,1,name_2,2→list_2,2,…|>]

finds a stable matching between the elements name_1,i and name_2,j based on the preferences expressed in lists list_k,l.

ResourceFunction["FindStableMatching"][<|name_1,1→{list_1,1,n_1,1},name_1,2→{list_1,2,n_1,2},…|>,<|name_2,1→{list_2,1,n_2,1},name_2,2→{list_2,2,n_2,2},…|>]

gives each element name_i,j capacity n_i,j.

ResourceFunction["FindStableMatching"][{list_1,1,list_1,2,…},{list_2,1,list_2,2,…}]

automatically uses indices as names.

Details

Let A and B be sets such that each element of A has ranked all elements of B in order of preference, and each element of B has ranked all elements of A in order of preference. A stable matching (also known as a stable marriage) between A and B is a set of pairs such that for each pair {a,b}, we have a∈A, b∈B, and if a prefers b'∈B to b then b' does not prefer a to a', where a'∈A is matched with b'.

With a capacity n_i,j, name_i,j can match up to n_i,j times.

ResourceFunction["FindStableMatching"] employs the Gale–Shapley algorithm to find a stable matching of maximum size. If sets A and B have the same size (i.e. same total capacity), then a stable matching pairing all elements (at their full capacity) is guaranteed to exist.