Improved upper bound on number of stable matchings in pairing problems
A Sub-$3^n$ Upper Bound on the Number of Stable Matchings
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Counting how many stable ways to match pairs of men and women can be tricky and has interested researchers for decades. The authors found a better way to limit the maximum number of these stable matchings, showing it is less than three times itself for each person involved. They built on earlier math methods by including more detailed relationships and introduced new tools to understand these matchings. This brings the upper estimate closer to the lowest known estimates, narrowing the possible range.
What this means in practice
- •For market designers: Use improved bounds to understand the complexity of matching markets with stable outcomes, aiding in efficient market analysis and design.
- •For matching algorithm developers: Utilize tighter upper bounds on stable matchings to optimize and benchmark algorithms that find or enumerate stable matches.
A theory result. No direct application yet.
Authors
Ken-ichi Kawarabayashi, Hikaru Wada, Masataka Yoneda
Abstract
We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.