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"][<|name1,1→list1,1,name1,2→list1,2,…|>,<|name2,1→list2,1,name2,2→list2,2,…|>] finds a stable matching between the elements name1,i and name2,j based on the preferences expressed in lists listk,l. ResourceFunction["FindStableMatching"][<|name1,1→{list1,1,n1,1},name1,2→{list1,2,n1,2},…|>,<|name2,1→{list2,1,n2,1},name2,2→{list2,2,n2,2},…|>] gives each element namei,j capacity ni,j. ResourceFunction["FindStableMatching"][{list1,1,list1,2,…},{list2,1,list2,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 aA, bB, 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 ni,j, namei,j can match up to ni,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.

## Examples

### Basic Examples (2)

Find a stable matching between two sets of preferences:

 In[1]:=
 Out[1]=

Find a stable matching between more complicated sets of preferences:

 In[2]:=
 Out[3]=

### Scope (2)

Assign capacities to certain elements:

 In[4]:=
 Out[5]=

Enter preferences as lists:

 In[6]:=
 Out[7]=

### Applications (2)

Given an equal number of men and women looking for mates of the opposite gender, it is always possible to pair them into stable marriages:

 In[8]:=
 Out[9]=

Assign graduating medical students to residency programs, each having a certain number of available slots:

 In[10]:=
 Out[11]=

### Possible Issues (1)

Reversing the order of the two preference inputs will still give a stable matching of the same size, but not necessarily the same one:

 In[12]:=
 In[13]:=
 Out[13]=
 In[14]:=
 Out[14]=

Daniel McDonald

## Version History

• 1.0.0 – 17 August 2021