Stable matching problem: Difference between revisions

Revision as of 20:38, 16 February 2020

Revision as of 21:21, 16 February 2020

Line 30:

* women get their first choice and men their third - (AZ, BX, CY).

All three are stable, because instability requires BOTHone of the participants to be happier with an alternative match. Giving one group their first choices ensures that the matches are stable because they would be unhappy with any other proposed match. Giving everyone their second choice ensures that any other match would be disliked by one of the parties. In general, the family of solutions to any instance of the stable marriage problem can be given the structure of a finite [[distributive lattice]],

and this structure leads to efficient algorithms for several problems on stable marriages.<ref>{{cite journal

| last = Gusfield | first = Dan | authorlink = Dan Gusfield