TL;DR
This paper introduces a flexible Answer Set Programming (ASP) framework to solve complex variants of the Stable Marriage Problem, including those with ties and incomplete preference lists (SMTI). By leveraging off-the-shelf ASP solvers, the authors provide the first exact implementation for finding optimal stable matchings (e.g., egalitarian, minimum regret) without needing to design custom algorithms for every new problem tweak.
What Problem Does This Paper Address?
The Stable Marriage Problem (SMP) is a classic algorithmic challenge: given two groups (e.g., men and women, or doctors and hospitals) with ranked preferences for each other, how do you pair them up so that no two individuals would rather be with each other than their assigned partners?
While the standard SMP is solved efficiently by the famous Gale-Shapley algorithm, real-world applications (like kidney exchanges or medical residency placements) are much messier. Participants might have incomplete lists (refusing to match with certain partners) or ties (indifference between two partners). Furthermore, when multiple stable matchings exist, administrators usually want to find the "best" one based on specific optimality criteria—such as maximizing the total number of matches or ensuring fairness between the two groups.
Traditionally, every time a new variant or optimality criterion is introduced, computer scientists have to invent and prove a brand-new, highly specialized algorithm. This paper asks: can we instead use a declarative logic programming approach to model and solve all these variants within a single, easily adaptable framework?
Methods
The authors tackle this using Answer Set Programming (ASP), a form of declarative programming well-suited for NP-hard search and optimization problems. Instead of writing step-by-step instructions on how to find a matching, the authors write logical rules defining what a stable matching is.
- Base Encoding: They first encode the SMTI (Stable Marriage with Ties and Incomplete lists) variant into standard ASP rules, mimicking the proposal and acceptance logic of the Gale-Shapley algorithm.
- Optimization via Saturation: Finding an optimal stable matching (e.g., one that minimizes the worst-case regret among all participants) is an NP-hard problem. To solve this, the authors use the saturation technique combined with a disjunctive, negation-as-failure-free (naf-free) ASP program. This multi-part program generates candidate solutions and systematically filters out sub-optimal ones by comparing their calculated costs.
- Solver: The resulting logic programs are executed using DLV, a highly efficient off-the-shelf ASP solver capable of handling aggregates and disjunctions.
Datasets
Not discussed in the paper. The authors use small, handcrafted toy examples to illustrate the logic and correctness of their ASP encodings, but do not evaluate the approach on large-scale empirical datasets or benchmarks.
Key Insights and Ideas
- The Power of Declarative Flexibility: The primary advantage of ASP is how easily it accommodates new constraints. For example, extending the standard 2D matching problem to a 3D matching problem (e.g., matching men, women, and children) simply requires adding an extra parameter to the ASP predicates, rather than overhauling an entire procedural algorithm.
- First Exact Implementation for SMTI Optimization: While approximation algorithms exist, this paper provides the first exact implementation capable of finding sex-equal, minimum regret, egalitarian, or maximum cardinality stable matchings in instances that allow both ties and unacceptable partners.
- Handling NP-Hardness Natively: By translating the optimality requirements into a SAT-like completion and using the saturation technique, the heavy lifting of navigating the NP-hard search space is entirely offloaded to the highly optimized DLV solver.
Key Results
The results in this paper are theoretical and structural rather than empirical:
- Mathematical Soundness: The authors formally prove a bijective correspondence between the answer sets of their ASP programs and the weakly stable matchings of the SMTI instances. If the ASP program outputs a solution, it is guaranteed to be a valid (and, where applicable, optimal) stable matching.
- Complexity of the Encodings: The authors analyze the size of the grounded ASP rules (where $k$ is the maximum number of men or women). The base SMTI program generates $O(k^2)$ rules. The optimal programs generate $O(k^3)$ rules for minimum regret and maximum cardinality, and $O(k^4)$ rules for sex-equality and egalitarity (due to how weights are counted).
- 3D Matching: They successfully demonstrate that the same logical framework can be extended to solve the 3D stable matching problem, generating $O(k^3)$ grounded rules.
Limitations and Future Work
- Lack of Empirical Benchmarking: The paper does not provide execution times or memory usage statistics. Because the grounded rules scale up to $O(k^4)$ for certain optimality criteria, the approach may face severe memory and performance bottlenecks on very large real-world datasets (e.g., thousands of participants).
- Future Work: The authors suggest that their framework can be readily adapted to other optimality criteria (like "popular matchings" or Pareto optimality) and entirely different matching structures, such as the Stable Roommate Problem (where matches are found within a single group rather than between two distinct groups).
Summary updated