Solving stable matching problems using answer set programming

Sofie De Clercq, Steven Schockaert, Martine De Cock, Ann Nowé

Abstract

Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed. This paper is under consideration in Theory and Practice of Logic Programming (TPLP).

Introduction

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, the goal is to pair them such 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—such as kidney exchanges or medical residency placements—are often more complex.

Participants in these scenarios might have incomplete lists (refusing to match with certain partners) or ties (indifference between two partners). Furthermore, when multiple stable matchings exist, administrators often seek the "best" one based on specific optimality criteria, such as maximizing the total number of matches or ensuring fairness between groups. Traditionally, every new variant or optimality criterion required a specialized, hand-crafted algorithm. This research proposes a shift toward a declarative logic programming approach to model and solve these variants within a single, adaptable framework.

Methodology: The ASP Framework

The authors utilize Answer Set Programming (ASP), a declarative programming paradigm well-suited for NP-hard search and optimization problems. Unlike procedural programming, which requires step-by-step instructions on how to find a matching, ASP allows researchers to write logical rules defining what constitutes a stable matching.

1. Base Encoding

The framework first encodes the Stable Marriage with Ties and Incomplete lists (SMTI) variant into standard ASP rules. These rules mimic the proposal and acceptance logic of the Gale-Shapley algorithm but are expressed as logical constraints.

2. 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 employ 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 against a set of logical conditions.

3. Solver Integration

The resulting logic programs are executed using DLV, a highly efficient off-the-shelf ASP solver. By leveraging DLV, the framework can handle complex aggregates and disjunctions, offloading the heavy lifting of navigating the NP-hard search space to a highly optimized engine.

Key Insights and Innovations

  • Declarative Flexibility: The primary advantage of ASP is the ease with which new constraints can be added. 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 for complex matching problems, this work 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 optimality requirements into a SAT-like completion and using the saturation technique, the framework provides a robust way to solve problems that are computationally prohibitive for standard procedural approaches.

Results and Complexity

The paper establishes several theoretical and structural milestones:

  • 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. This ensures that any solution output by the ASP program is guaranteed to be a valid stable matching.
  • Encoding Complexity: The authors analyzed the size of the grounded ASP rules relative to the number of participants ($k$):
  • Base SMTI: $O(k^2)$ rules.
  • Minimum Regret/Max Cardinality: $O(k^3)$ rules.
  • Sex-Equality/Egalitarianism: $O(k^4)$ rules (due to weight counting requirements).
  • 3D Matching Extension: The framework successfully demonstrated that the same logical structure could solve 3D stable matching problems, generating $O(k^3)$ grounded rules.

Limitations and Future Work

While the theoretical results are robust, the paper lacks empirical benchmarking on large-scale datasets. Because the grounded rules scale up to $O(k^4)$ for certain criteria, the approach may face memory and performance bottlenecks when applied to very large real-world datasets involving thousands of participants.

Future research directions include adapting the framework to other optimality criteria, such as "popular matchings" or Pareto optimality, and applying the logic to the Stable Roommate Problem, where matches are found within a single group rather than between two distinct sets.

Summary updated

Abstract

Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed. This paper is under consideration in Theory and Practice of Logic Programming (TPLP).
BibTeX
@inproceedings{clercq2016solving,
  author = {Sofie De Clercq and Steven Schockaert and Martine De Cock and Ann Nowé},
  title = {{Solving stable matching problems using answer set programming}},
  booktitle = {Theory Pract. Log. Program},
  year = {2016},
  url = {https://openreview.net/forum?id=UYbRIMzNwzB},
}
Figure