Revision as of 21:21, 16 February 2020 edit BernardoSulzbach (talk \| contribs) Extended confirmed users 1,533 edits Reverted good faith edits by Jeremy rutman (talk): Maybe... but why caps? (TW) Tag: Undo ← Previous edit		Revision as of 12:17, 17 February 2020 edit undo Jeremy rutman (talk \| contribs) 80 edits Undid revision 941144552 by BernardoSulzbach (talk). Took out all caps tho I think they help since this it may not be at once obvious that this is so (as evidenced by incorrect original entry and bernardo's 'maybe' instead of 'correct') Tag: Undo Next edit →
Line 30: * women get their first choice and men their third - (AZ, BX, CY). All three are stable, because instability requires ~~one~~both 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

Stable matching problem: Difference between revisions