cs.AI · 2108.05165 Copy arXiv ID · Aug 11, 2021 Save Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods Authors: Selin Eyupoglu , Muge Fidan , Yavuz Gulesen , Ilayda Begum Izci , Berkan Teber , Baturay Yilmaz , Ahmet Alkan , Esra Erdem
Abstract We study a variation of the Stable Marriage problem, where every man and every woman express their preferences as preference lists which may be incomplete and contain ties. This problem is called the Stable Marriage problem with Ties and Incomplete preferences (SMTI). We consider three optimization variants of SMTI, Max Cardinality, Sex-Equal and Egalitarian, and empirically compare the following methods to solve them: Answer Set Programming, Constraint Programming, Integer Linear Programming. For Max Cardinality, we compare these methods with Local Search methods as well. We also empirically compare Answer Set Programming with Propositional Satisfiability, for SMTI instances.
Explore similar work Jul 14, 2026 · Stephan A. Fahrenkrog-Petersen, Aleksander Figiel, Darya Melnyk +2 Bipartite Perfect Matchings AI Privacy Risks and Protection
Jul 6, 2026 · Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis Bipartite Perfect Matchings Matching Markets
Jul 26, 2026 · Johannes K. Fichte, Johanna Groven, Peter Jonsson +2 Satisfiability
Jul 14, 2026 · cs.DS J/K move · Enter open · S save
Stephan A. Fahrenkrog-Petersen, Aleksander Figiel, Darya Melnyk, Tijana Milentijević +1
The stable marriage problem appears in many privacy-sensitive domains, for example in the National Resident Matching Program in the US. In such applications, preserving the privacy of users' preference lists is essential to prevent strategic manipulation, discourage misreporting, and comply with data protection regulations. In this work, we investigate privacy attacks on stable marriage algorithms. Assuming that the attacker (e.g., the hospitals) can repeatedly interact with the stable marriage algorithm, we demonstrate how such interactions can reveal private preferences of the non-malicious side (e.g., the residents). We show that the widely applied Gale-Shapley Matching Algorithm, where the proposers' side is malicious, is vulnerable to privacy attacks and all honest agents' preferences can be revealed. We further investigate which preference distributions of the honest, non-malicious side are susceptible to privacy attacks and show that the Gale-Shapley Matching Algorithm where the honest side proposes can preserve privacy in non-susceptible preference distributions. We extend our results to the decentralized setting and show that the attacker's side can infer all preference orderings. In an experimental evaluation, we test privacy attacks on synthetic and real-world data and show that real-world data is indeed susceptible to privacy attacks. This work underlines a need for new privacy-preserving stable marriage algorithms.