Could an alternating approach yield a fairer solution to the stable marriage problem?

Question

With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the proposers keep walking down the list from their best preference downwards till the stable solution is found, while the reviewers walk up the list from where they start.

To improve the fairness to both parties, consider an alternating variant of the algorithm, where in each cycle, proposers and reviewers exchange roles (for example, in each cycle, men and women switch between the role of proposer and reviewer). Would this terminate with a stable match? If yes, would the resulting stable match be fairer to both parties than the original G-S algorithm?

Answer 1

The idea of the Gale-Shapley algorithm is to consider the graph of possible matchings (i.e. marriages) and trim edges that cannot happen in a stable matching. Eventually, we cannot trim any more edges, and then we can read from the graph a stable matching, indeed both the man-optimal and the woman-optimal stable matchings. For this view, check out for example the beginning of Section 6.3 in this paper. In your algorithm, you haven't specified how the final matching is generated (though perhaps it follows from the proposal terminology), so it's hard to evaluate the result. However, since the graph you'll get in the end is probably the same as in the symmetric Gale-Shapley algorithm, the usual extraction procedures probably wouldn't produce anything other than the two optimal stable matchings. Perhaps it's best if you gave a complete pseudocode of the algorithm, and also tested it on a few sample inputs.

The stable matchings form a lattice structure, so you might think it helps to take the two optimal matchings and generate something "in the middle". However, since they are the top and bottom elements in the lattice, neither the join nor the meet would produce anything new. Instead, there are ways to generate random stable matchings, and these might be fairer to both parties.

For more information, consult Knuth's Marriages Stables (available also in English) and Gusfield and Irving's The Stable Marriage Problem: Structure and Algorithms.