Stable matching instances have unique prime factorizations and exact counts
Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
Data Structures and Algorithms
Summary
Finding stable matches is a classic math problem about pairing groups fairly. The authors show that any balanced instance can be uniquely broken down into fundamental parts called prime blocks. These blocks reveal deep connections between different ways to look at the problem's structure. They also count exactly how many cases can be broken down this way, showing most are decomposable, and provide a way to find this breakdown efficiently.
What this means in practice
- •For matching algorithm designers: Use unique prime factorizations to optimize the structure and execution of stable matching algorithms by handling decomposable instances separately.
- •For combinatorial optimization engineers: Employ the polynomial-time computable factorization as a tool to simplify large stable matching problems for better computational management.
Authors
Yoshiteru Ishida
Abstract
Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three different structures: the reachable execution digraph as a Cartesian product, the proposal-prefix antimatroid as a direct sum, and the stable-matching lattice as a direct product. The converse fails, and fails at every size from two on: two explicit families share the identical Boolean-cube execution while one is maximally decomposable with a single stable matching and the other is prime with n. Uniqueness yields an exact census, a recursion counting the prime instances at every size, under which exactly 88,478,208 of the 110,075,314,176 profiles with four agents on each side are decomposable and the decomposable fraction is asymptotically n! / n^(2n). The blocks are characterised as the square components of the mutual-rank filtration, so the partition is computable in polynomial time and the factorisation is a tool rather than only a fact.