This June-2024 Challenge deals with the famous stable marriage problem formulated as follows:

“Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.”

A very good analysis of the problem is provided in the recent presentation given by Dr. Guido Tack. My solution is based on OpenRules Rule Solver. It includes two different implementation approaches described in this document. The complete decision model has been added to RuleSolver samples.

Approach 1. Dr. Guido Tack has already provided a very good analysis of the problem describing the famous Gale-Shapley algorithm and providing different implementations of complex marriage stability constraints using MiniZinc. However, the produced solutions did not look fair, and Guido attempted to find a “fair” solution using 3 interesting optimization criteria – still he admitted these attempts were not very successful. These considerations pushed me to consider a more simple approach with constraint relaxations. Instead of implementing complex marriage stability constraints I only implemented simple constraints that each person should marry one and only one person of the opposite gender. Then I summarized preferences for all pairs “man-woman” and “woman-man” and considered this sum as an optimization objective. When I minimized this objective, I receive a solution with the most top preferences being satisfied.

Approach 2. I still wanted to implement an approach similar to Guido’s solutions with explicitly specified marriage stability constraints and compare the results with my Approach 1.  I did it using a quite complex standard “Element” constraint from JSR-331 API. I used this approach to find Feasible, All, and Optimal solutions. It was good to see that both approaches produced the same optimal solutions.

Conclusion. The resulting decision model demonstrates that it is not always necessary to implement complex rules/constraints in the way they are presented in plain English descriptions. You frequently may get the same or better results by minimizing the accumulated violation of selected rules and constraints. The created implementations with various flavors are interchangeable and could be applied separately or in combinations.

The decision model provides a flexible infrastructure for representing and solving this relatively complex problem and its possible extensions. For instance, to make the decision model even more realistic we can relax marriage stability constraints and apply them only when spouse preferences are smaller than or equal to a certain “Stability Threshold”. The decision model let us to add more factors that will affect marriage stability without serious changes in the implementation. What is important is the fact that it is easy to add similar advancements to the decision model.

The integrated use of rule engines and constraint solvers within the same business decision models not only simplifies their implementations. It also provides other benefits: the simplicity of adding more test cases (in Excel or JSON formats), standard one-button deployment of this decision service as AWS Lambda or MS Azure functions, and natural incorporation of developed decision services into any production power decision-making application.

Read complete description