Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods
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. This paper is under consideration for acceptance in Theory and Practice of Logic Programming (TPLP).
Code (1)
Similar Papers 제목 키워드 기반
Roommates with Convex Preferences
Roommate problems with convex preferences always have stable matchings. Efficiency and individual rationality are, moreover, compatible with strategyproofness in such convex roommate problems. Both of these results fail …
An n-ary Constraint for the Stable Marriage Problem
We present an n-ary constraint for the stable marriage problem. This constraint acts between two sets of integer variables where the domains of those variables represent preferences. Our constraint enforces stability and…
ARCA General Framework for Stable Roommates Problems using Answer Set Programming
The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agent…
Matching with Incomplete Preferences
I study a two-sided marriage market in which agents have incomplete preferences -- i.e., they find some alternatives incomparable. The strong (weak) core consists of matchings wherein no coalition wants to form a new mat…
A Tie-breaking based Local Search Algorithm for Stable Matching Problems
The stable marriage problem with incomplete lists and ties (SMTI) and the hospitals/residents problem with ties (HRT) are important in matching theory with broad practical applications. In this paper, we introduce a tie-…