# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

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

Contributed by:
Daniel McDonald

ResourceFunction["FindStableMatching"][<| finds a stable matching between the elements | |

ResourceFunction["FindStableMatching"][<| gives each element | |

ResourceFunction["FindStableMatching"][{ automatically uses indices as names. |

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.

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]= |

Assign capacities to certain elements:

In[4]:= |

Out[5]= |

Enter preferences as lists:

In[6]:= |

Out[7]= |

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]= |

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]= |

- 1.0.0 – 17 August 2021

This work is licensed under a Creative Commons Attribution 4.0 International License