Editing Stable matching problem (section)

==Different stable matchings==
{{Main|Lattice of stable matchings}}
In general, there may be many different stable matchings. For example, suppose there are three men (A, B, C) and three women (X, Y, Z) which have preferences of:

: A: YXZ &nbsp; B: ZYX &nbsp; C: XZY &nbsp; 
: X: BAC &nbsp; Y: CBA &nbsp; Z: ACB

There are three stable solutions to this matching arrangement:

* men get their first choice and women their third – (AY, BZ, CX);
* all participants get their second choice – (AX, BY, CZ);
* women get their first choice and men their third – (AZ, BX, CY).

All three are stable, because instability requires 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 | author-link = Dan Gusfield
 | doi = 10.1137/0216010
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 873255
 | pages = 111–128
 | title = Three fast algorithms for four problems in stable marriage
 | volume = 16
 | year = 1987}}</ref>

In a uniformly-random instance of the stable marriage problem with {{mvar|n}} men and {{mvar|n}} women, the average number of stable matchings is asymptotically <math>e^{-1}n\ln n</math>.<ref>{{cite journal
 | last = Pittel | first = Boris
 | doi = 10.1137/0402048
 | issue = 4
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1018538
 | pages = 530–549
 | title = The average number of stable matchings
 | volume = 2
 | year = 1989}}</ref>
In a stable marriage instance chosen to maximize the number of different stable matchings, this number is an [[exponential function]] of {{mvar|n}}.<ref>{{cite conference
 | last1 = Karlin | first1 = Anna R. | author1-link = Anna Karlin
 | last2 = Gharan | first2 = Shayan Oveis
 | last3 = Weber | first3 = Robbie
 | editor1-last = Diakonikolas | editor1-first = Ilias
 | editor2-last = Kempe | editor2-first = David
 | editor3-last = Henzinger | editor3-first = Monika | editor3-link = Monika Henzinger
 | contribution = A simply exponential upper bound on the maximum number of stable matchings
 | doi = 10.1145/3188745.3188848
 | mr = 3826305
 | pages = 920–925
 | publisher = Association for Computing Machinery
 | title = Proceedings of the 50th Symposium on Theory of Computing (STOC 2018)
 | year = 2018| arxiv = 1711.01032
 | isbn = 978-1-4503-5559-9 }}</ref>
Counting the number of stable matchings in a given instance is [[♯P-complete|#P-complete]].<ref>{{cite journal
 | last1 = Irving | first1 = Robert W.
 | last2 = Leather | first2 = Paul
 | doi = 10.1137/0215048
 | issue = 3
 | journal = [[SIAM Journal on Computing]]
 | mr = 850415
 | pages = 655–667
 | title = The complexity of counting stable marriages
 | volume = 15
 | year = 1986}}</ref>