The Optimal Stable Marriage

A one-to-one assignment problem involves a set of two groups, candidates and reviewers, each of whom has ranked the members of the other group on the basis of how much they would like to be paired together. A classic problem in game theory involves finding a stable assignment, or a way of pairing up candidates and reviewers such that no member of either group is incentivized to cheat on their partner. In a large problem, there may be more than one way to do this, but it isn’t necessarily easy to find all of the stable assignments or determine which one represents the best compromise between the candidates’ and reviewers’ interests. I have written some code that solves this latter problem. The algorithm it uses was developed in the 1980s, and I am currently working on improving its performance and extending it to many-to-one assignment problems. My code and further discussion are on Github here.