稳定婚姻实例解决方案的最大数量是多少？

Question

每个稳定婚姻问题至少有一个解决方案。然而，如何知道解决稳定婚姻问题的最大数量？ Gale-Shapley算法只能找到一个人为最优解。如果我们使用女性最佳方法来运行Gale-Shapley，那么可能有另一种解决方案。一个稳定婚姻的例子最多有两个解决方案吗？或者Gale-Shapley只能找到两种解决方案，除此之外还有其他一些解决方案。

感谢您的任何帮助答案！

Answer 1

见https://cstheory.stackexchange.com/questions/5619/what-is-the-maximum-number-of-stable-marriages-for-an-instance-of-the-stable-mar在那里讨论了指数最坏情况下的下界欧米茄（2.28^n）的稳定婚姻，给出了所有用于n男性/女性（通过给一个家庭的例子，其中这么多稳定的婚姻是可能）。