1
$\begingroup$

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm does). The only solution I have is to recursively enumerate all the possible matchings, discarding the recursive branches which do not satisfy the conditions. This algorithm has a complexity of O(n!), with n being the number of items in each set.

I found this similar question that shows that the upper bound to the number of solutions is exponential. Is there any better algorithm than the one I have so far?

In the context of similar questions, this paper by Gusfield comes up. However, it solves a different problem.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Here is some idea that should at least prune the search by some chunk (probably not asymptotically): Compute the man-optimal stable matching with GS and the woman-optimal stable matching with GS with roles of men and women reversed. These two matchings give you the top and bottom element of the lattice of all stable matchings. If it's the same, you are already done, otherwise, restrict your search on this lattice by using only the lattice operations. $\endgroup$
    – ttnick
    Commented Nov 2, 2023 at 12:46
  • 2
    $\begingroup$ Because there can be exponentially many solutions, any such algorithm will have to take exponential time in the worst case. Are you sure you want to know all solutions? Is it possible you have an XY problem? $\endgroup$
    – D.W. ♦
    Commented Nov 2, 2023 at 18:32
  • 1
    $\begingroup$ @ttnick I have looked into the lattice of all stable matchings. It seems to me that you can't use lattice operations to explore the lattice starting from the top and bottom elements, since applying the operations to these two elements always returns one of the two. Am I perhaps missing something? $\endgroup$
    – void
    Commented Nov 2, 2023 at 18:55
  • $\begingroup$ @D.W. Yes, I need all the solutions: it's the starting point of an assignment. We'll have to expand the problem further, but first we need an algorithm to obtain all the solutions. $\endgroup$
    – void
    Commented Nov 2, 2023 at 18:56
  • 1
    $\begingroup$ @void, sorry that was not phrased too well: Giving top and bottom matching this gives you for every man $m$ with preference list $[w_{m1}, w_{m2}, \ldots, w_{mn}]$ the sublist $[w_{mk}, \ldots, w_{m\ell}]$ of women for which there exists a stable matching containing $\{m, w_{mj}\}$. In that sense, it restricts your search space. If you have managed to find more matchings, you will also be able to find even more by applying join and meet. $\endgroup$
    – ttnick
    Commented Nov 3, 2023 at 15:06

1 Answer 1

Reset to default
1
$\begingroup$

I worked with OP on this problem. This is what we found.

The problem solved by Gusfield in the paper "Three Fast Algorithms for Four Problems in Stable Marriage" does indeed include a solution to this problem. It should be noted, however, that the algorithm for building the graph of rotations contains an error (also, the paper in general is very hard to parse). We corrected that error.

The algorithm proposed there requires linear time for each stable matching. C. Palmer and D. Pálvölgyi find in "At most 3.55n stable matchings" that the number of stable matchings is O(3.55^n). Putting these two things together, we find that Gusfield's algorithm takes O(n * 3.55^n).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.