1 Introduction
The Stable Roommates problem [Gale and Shapley (1962)]
(SR) is a matching problem (wellstudied in Economics and Game Theory) characterized by the preferences of an even number
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 agents into pairs that are acceptable to each other (i.e., they are in the preference lists of each other), and the matching is stable (i.e., there exist no two agents who prefer each other to their roommates, and thus block the matching).SR is an interesting computational problem, not only due to its applications (e.g., for pairing in largescale chess competitions [Kujansuu et al. (1999)], for campus house allocation [Arkin et al. (2009)], pairwise kidney exchange [Roth et al. (2005)], creating partnerships in P2P networks [Gai et al. (2007)]) but also due to its computational properties described below.
Incomplete preference lists with ties. Upon a question posed by Knuth 1997 in 1976 about the existence of an algorithm for SR, Irving 1985 developed a lineartime algorithm for SR. Meanwhile, researchers have started investigating variations of SR motivated by further observations and applications. For instance, in practice (like largescale chess tournaments), agents may find it difficult to rank a large number of alternatives in strict order of preference. With such motivations, SR has been studied with incomplete preference lists (SRI) Gusfield and Irving (1989), with preference lists including ties (SRT) Ronn (1990), and with incomplete preference lists including ties (SRTI) Irving and Manlove (2002). Interestingly, some of these slight variations (i.e., the existence of a stable matching in SRT and SRTI) are proven to be NPcomplete (Table 1).
Stable and more fair solutions. With the motivation of finding more fair stable solutions, variations of SR have been studied. For instance, Egalitarian SR aims to maximize the total satisfaction of preferences of all agents; it is NPhard Feder (1992). Rank Maximal SRI aims to maximize the number of agents matched with their first preference, and then, subject to this condition, to maximize the number of agents matched with their second preference, and so on; it is also NPhard Cooper (2020).
Not stable but goodenough solutions. As first noted by Gale and Shapley 1962, unlike the Stable Marriage problem (SM), there is no guarantee to find a solution to every SR problem instance (i.e., there might be no stable matching). When an SR instance does not have a stable solution, variations of SR have been studied to find a goodenough solution. Almost SR aims to minimize the total number of blocking pairs (i.e., pairs of agents who prefer each other to their roommates); it is NPhard Abraham et al. (2005).
Alongside these interests in SR, some exact methods and software SRItoolkit (2019); MatchingToolkit (2020) have been developed to solve SR and SRI (both solvable in polytime) using Constraint Programming (CP) Prosser (2014), and based on Irving’s algorithm Irving (1985). However, to the best of the authors’ knowledge, there is no exact method (except for the enumeration based method for Egalitarian SRI) and implementation, that provides a solution to any intractable variation of SR, described in three groups above.
Our Contributions. We introduce a formal framework and its implementation, called SRTIASP, that are general enough to provide solutions to all variations of SR mentioned above, including the intractable decision/optimization versions: SRT, SRTI, Egalitarian SRTI, Rank Maximal SRTI, Almost SRTI. SRTIASP provides a flexible framework to study variations of SR.
SRTIASP utilizes a logic programming paradigm, called Answer Set Programming (ASP) Brewka et al. (2016), to declaratively solve stable roommates problems. We represent SRI and its variations in the expressive formalism of ASP, and SRTIASP computes models of these formulations using the ASP solver Clingo Gebser et al. (2011). For each variation of SR, given a problem instance, SRTIASP returns a solution (or all solutions) if one exists; otherwise, it returns that the problem does not have a solution. We prove that SRTIASP is sound and complete (Theorem 1).
We have evaluated SRTIASP over different sizes of SRI instances (randomly generated with the software SRItoolkit (2019), called SRICP from now on) to understand its scalability, as the input size, and the degree of completeness of preference lists increase. We have developed a method to add ties to these instances, and empirically analyzed the scalability of SRTIASP on SRTI instances as well.
We have compared SRTIASP with SRICP, over SRI instances. We have also investigated the use of SRICP to solve Egalitarian SRI, Rank Maximal SRI and Almost SRI based on enumerationbased bruteforce methods, and compared SRTIASP with these methods.
In addition, we have compared SRTIASP with the ASP method proposed by Amendola 2018 for SR (called SRAF from now on) based on Argumentation Framework (AF) Dung (1995), over SR instances.
Problem  Complexity 

SR  P Irving (1985) 
SRI  P Gusfield and Irving (1989) 
SRTI (super)  P Irving and Manlove (2002) 
SRTI (strong)  P Kunysz (2016); Scott (2005) 
SRT (weak) (and thus SRTI (weak))  NPcomplete (Ronn, 1990, Thm 1.1, Prop 2.2) 
SRTI (weak)  NPcomplete (Irving et al., 2009, Thm 5) 
Egalitarian SR  NPhard (Feder, 1992, Thm 8.3) 
Egalitarian SRI  NPhard (Cseh et al., 2019, Cor 4) 
Almost SR (and thus SRT (weak))  NPhard (Abraham et al., 2005, Thm 1) 
Almost SRI  NPhard (Biró et al., 2012, Thm 1) 
for short lists of size 3
2 Stable Roommates Problems
Let us start with defining the Stable Roommate problem with Incomplete lists (SRI). Let be a finite set of agents. For every agent , let be a strict and total ordering of preferences over a subset of . We refer to as agent ’s preference list. For two agents and , we denote by that prefers to . Since the ordering of preferences is strict and total, for every agent , for every two distinct agents and in , either or . Note that the preferences of agents with respect to are transitive and asymmetric. If an agent is in ’s preference list, then is called acceptable to . We denote by the collection of all preference lists.
A matching for a given SRI instance is a function such that, for all such that and , if and only if . If agent is mapped to itself, we then say he/she is single.
A matching is blocked by a pair () if

both agents and are acceptable to each other,

is single with respect to , or , and

is single with respect to , or .
A matching for SRI is called stable if it is not blocked by any pair of agents. Fig. 1 illustrates three examples for SRI.
sri7  sri4  sri8 

The Stable Roommates problem (SR) is a special case of SRI where the preference orderings are strict and complete (i.e., for every agent , ), and is even.
Ties. The Stable Roommates problem with Ties and Incomplete Lists (SRTI) is a variation of SRI where the preference lists are partial orderings and where incomparability is transitive. In this context, ties correspond to indifference in the preference lists: an agent is indifferent between the agents and , denoted by , if and . There are three levels of stability Irving and Manlove (2002): weak stability, strong stability, and super stability. We will focus on weak stability in this paper, since it is a harder problem compared to the other two versions (Table 1). Relative to weak stability, a pair of agents blocks a matching if conditions B1–B3 hold.
The Stable Roommates problem with Ties (SRT) is a special case of SRTI where the preference ordering of each agent is over and complete, and is even.
Note that, while the problems SR and SRI are in P, SRT and SRTI under weak stability are NPcomplete (Table 1).
Fairness. When an SRI instance has many stable matchings, it may be useful to identify a stable matching that is fair to all agents. Different fairness criteria on top of stability have led to optimization variations of SRI.
Let denote the set of all stable matchings of a given SRI instance . For every agent and every agent , let denote the rank of agent in the preference list of agent . We assume that agents prefer matching with a roommate: for every agent , let be a number larger than for every .
Egalitarian SRI aims to maximize the total satisfaction of preferences of all agents. Let be a matching. For every agent , we define the satisfaction of ’s preferences with respect to as follows: if . Then the total satisfaction of preferences of all agents is defined as follows: Note that for SRI, all matching have the same number of contributions of values to . Since the preferred agents have lower rankings, the total satisfaction of preferences of all agents is maximized when is minimized. Then, a matching with the minimum is egalitarian.
Rank Maximal SRI considers different fairness criterion: it aims to maximize the number of agents matched with their first preferences, and then, subject to this condition, to maximize the number of agents matched with their second preference, and so on. We start with the set of all matchings of a given SRI instance , and define a series of subsets of these matchings where the maximum number of agents are matched with their ’th preferences:
Then, a matching is rankmaximal.
Consider the SRI instance sri8 illustrated in Fig. 1, with two stable matchings. Stable matching is egalitarian and is rankmaximal.
Almost stable. Unlike the Stable Marriage problem, there is no guarantee to find a solution to every SRI problem instance (cf. sri4 in Fig. 1). When an SRI instance does not have a stable matching, further variations of SRI have been studied to find a goodenough solution.
Almost SRI aims to minimize the total number of blocking pairs. Let denote the set of blocking pairs of a given matching . A matching is almost stable if it is blocked by the minimum number of pairs.
3 Answer Set Programming
SRTIASP utilizes Answer Set Programming (ASP) Brewka et al. (2016) to declaratively solve stable roommates problems. The idea of problem solving with ASP is (1) to represent the given problem by a program whose answer sets Gelfond and Lifschitz (1988, 1991) characterize the solutions of the problem, and (2) to solve the problem using answer set solvers, like Clingo Gebser et al. (2011).
Why ASP? We use ASP as an underlying paradigm for modeling and solving stable roommates problems for the following reasons. (1) Deciding whether a program in ASP has an answer set is NPcomplete Dantsin et al. (2001), so ASP is expressive enough for solving hard SR problems. (2) ASP has expressive languages with a rich set of utilities, such as nondeterministic choices, hard constraints, weighted weak constraints with priorities, and thus allow us to easily formulate different variations of SR. (3) Efficient ASP solvers, like Clingo, supports these utilities. (4) Such an elaboration tolerant McCarthy (1998) representation framework and flexible software environment are useful in studying and understanding variations of SR in different applications. (5) Due to declarative problem solving in the formal framework of ASP, we can easily prove the soundness and completeness of SRTIASP (see Theorem 1).
Programs in ASP Let us briefly describe the syntax of programs and useful constructs used in the paper. We consider ASP programs that consist of rules of the form
(1) 
where , Head is an atom or , and each is an atom. A rule is called a fact if and a (hard) constraint if Head is .
Cardinality expressions are special constructs of the form where each is an atom and and are nonnegative integers denoting the lower and upper bounds Simons et al. (2002). Programs using these constructs can be viewed as abbreviations for programs that consist of rules of the form (1). Such an expression describes the subsets of the set whose cardinalities are at least and at most . Cardinality expressions can be used in heads of rules; then they generate many answer sets whose cardinality is at least and at most .
Schematic variables A group of rules that follow a pattern can be often described in a compact way using “schematic variables”. For instance, the cardinality expression can be represented as , along with a definition of that describes the ranges of variables: .
Weighted weak constraints with priorities The ASP programs can be augmented with “weak constraints”—expressions of the following form Buccafurri et al. (2000):
Here, is a formula (as in the body of a rule) with the terms . Intuitively, whenever an answer set for a program satisfies , the tuple contributes a cost of to the total cost function of priority . The ASP solver tries to find an answer set with the minimum total cost. For instance, the following weak constraint
instructs Clingo to compute an answer set that does not include both and , if possible. However, if Clingo cannot find such an answer set, it is allowed to compute an answer set with these atoms and but with an additional cost of 1 per each such . Weak constraints are considered by Clingo according to their priorities.
4 Solving SRI using ASP
We formalize the input of an SRI instance in ASP by a set of facts using atoms of the forms (“ is an agent in ”) and (“agent prefers agent to agent , i.e., ”). For instance, the preference list of agent in sri4 of Fig. 1 is described by the following facts:
For every agent , since prefers being matched with a roommate in instead of being single, for every , we also add facts of the form . For the example above, the input also includes the facts:
In the ASP formulation of SRI, the variables , , and denote agents in . The program starts with the definition of preferences of agents with respect to :
(2) 
The first rule expresses that being single is the least preferred option. The second rule expresses that the preference relation is transitive.
Based on the preferences of agents, we define the concept of acceptability for each agent:
(3) 
and the concept of mutual acceptability:
(4) 
The output of an SRI instance is characterized by atoms of the form (“agents and are roommates”). The ASP formulation of SRI first generates pairs of roommates. For every agent , exactly one mutual acceptable agent is nondeterministically chosen as by the choice rules:
(5) 
Here, the roommate relation is symmetric:
(6) 
The agents who are not matched with a roommate are single agents:
(7) 
Then, the stability of the generated matching is ensured by the hard constraints:
(8) 
Here, atoms of the form describe the blocking pairs (i.e., conditions B1–B3):
(9) 
where in each rule, and atoms describe that agent prefers agent to her/his roommate :
(10) 
Given the ASP formulation whose rules are described above and the ASP description of an SRI instance , the ASP solver Clingo generates a stable matching (or all stable matchings), if one exists; otherwise, it returns that there is no solution. This is possible since the ASP program (i.e., (2)–(10)) is sound and complete.
Theorem 1
Given an SRI instance , for each answer set for , the set of atoms of the form in encodes a stable matching to the SRI problem instance. Conversely, each stable matching for the given SRI instance corresponds to a single answer set for .
First, we show that the answer set for (2)–(4) correctly describes the acceptability relation.

[(i)]

The answer set describes the acceptability of every pair of agents and to each other (by means of atoms of the ).
Next, we show that the answer set for (2)–(6) correctly characterizes a matching.

[(i)]

Every answer set for the top part evaluated with respect to , describes a function, via atoms of the form , which maps every agent to exactly one agent so that and are acceptable to each other (when ). Moreover, every such mapping can be characterized by a unique answer set for .
Next, using Proposition 3 of Erdogan and Lifschitz 2004 three times, we show that adding definitions (7), (10), and (9) to (2)–(6) one by one conservatively extends the answer sets for (2)–(6), by describing singles (by means of atoms of the ), preferences of every agent over her/his roommate (by means of atoms of the ), and then blocking pairs (by means of atoms of the ).
Finally, we show that stability is guaranteed by (8), using Proposition 2 of Erdogan and Lifschitz 2004. Therefore, there is a onetoone correspondence between every answer set for (2)–(8) and every stable matching.
Ties (weak stability). As noted by Cseh 2019, relative to weak stability, stability in SRTI instances can be defined in exactly the same way as for SRI. Therefore, we can use the SRI formulation to solve SRTI instances too.
Fairness. Let us describe the ranks of agents by a set of facts using atoms of the form (“the rank of agent according to agent ’s preferences is ”). For each agent , since ’s preference ordering is total, we can define the ranks as follows: the ’th agent in the preference list of has rank , and has a rank larger than the ranks of .
Egalitarian SRI aims to maximize the total satisfaction of preferences of all agents by a matching . The satisfaction of an agent ’s preferences with respect to is defined as the rank of . Since more preferred agents have lower ranks, the total satisfaction of preferences of all agents is maximized when is minimized. Therefore, to solve Egalitarian SRI, we simply add to the SRI formulation , the weighted weak constraints:
which instruct Clingo to minimize the sum of the ranks of roommates.
Rank Maximal SRI tries to maximize the number of agents matched with their first preferences, and, subject to this condition, tries to maximize the number of agents matched with their second preferences, and so on. Such an iterative definition can be modeled elegantly by the following weak constraints:
Note that the priorities of these weak constraints are defined as for every pair of roommates (), where . As the rank changes from to , the priority decreases. The ASP solver Clingo handles weak constraints with respect to their priorities. On the other hand, note that the weights of these weak constraints are specified as 1 for every pair of roommates (). Therefore, Clingo first considers the highest priority , and tries to minimize the total weights of agents matched with their first preferences. Then, Clingo considers the next highest priority , and further tries to minimize the total weights of agents matched with their second preferences, and so on. In this way, Clingo finds a rank maximal stable matching.
Almost stable. Almost SRI aims to minimize the total number of blocking pairs for a matching . For that, we simply replace the hard constraint (8) that ensures stability, with the following weak constraints in our ASP formulation of SRI:
Elaboration tolerance. According to McCarthy 1998, a representation is elaboration tolerant to the extent that it is convenient to modify a set of formulas expressed in the formalism to take into account new phenomena, and the simplest kind of elaboration is the addition of new formulas. In that sense, our representation of SRI is elaboration tolerant to variations of SRI, since the program is not changed at all (e.g., we add new rules to for Egalitarian SRI) or it is changed minimally (e.g., we replace a hard constraint by a weak constraint for Almost SRI).
5 Experimental Evaluations
We have experimentally evaluated SRTIASP to understand its scalability over intractable SRTI problems, and how it compares with two closely related methods over tractable SR problems.
Setup. We have generated instances using the random instance generator that comes with SRICP. It is based on the following idea Mertens (2005): 1) generate a random graph ensemble according to the ErdosRenyi model Erdös and Rényi (1960), where is the required number of agents and
is the edge probability (i.e., each pair of vertices is connected independently with probability
); 2) since the edges characterize the acceptability relations, generate a random permutation of each agent’s acceptable partners to provide the preference lists. We define the completeness degree for an instance as the percentage .In our experiments, we have used Clingo (Version 5.2.2) on a machine with Intel Xeon(R) W2155 3.30GHz CPU and 32GB RAM.
Scalability of SRTIASP: SRI and its variations. We have generated instances of different sizes, where the number of agents are 20, 40, 60, 80,100, 150 and 200, and the completeness degrees are 25%, 50%, 75% and 100%. For each number of agents and for each completeness degree, we have generated 20 instances. We have experimented with these randomly generated instances to analyze the scalability of SRTIASP for SRI, Egalitarian SRI, Rank Maximal SRI, and Almost SRI. The results are shown in Table 2. We make the following observations from this table:

The computation times for finding a stable matching (if one exists) and finding out that there exists no stable matching are comparable to each other.
Consider, for instance, the completeness degree 25%, and 80 agents. For 13 (out of 20) instances, the average CPU time to compute a stable matching is 0.167 seconds. For the remaining 7 instances, the average CPU time to find that a stable matching does not exist is 0.183 seconds. These timings are comparable to each other.

Computing an egalitarian stable matching generally takes slightly less time than computing a rank maximal stable matching.
For instance, for the 13 instances with a stable matching, computing egalitarian stable matchings takes on average 0.255 seconds; computing rank maximal stable matchings takes a similar amount of time, 0.256 seconds. For larger instances, we can observe that the latter takes a bit more time.

Computing an almost stable matching significantly takes more time, compared to computing an egalitarian or a rank maximal stable matching.

Solving the optimization variants of SRI takes significantly more time, compared to solving SRI.
For instance, for the 7 instances without any stable matching, computing almost stable matchings takes in 4.416 seconds on average.
The observations O2 and O3 are interesting, considering all the three optimization variations of SRI are NPhard. Though, the observation O4 (better illustrated in Fig. 2) is not surprising, considering that SRI is in P (Table 1).
We can can further observe the following about scalability:

As the completeness degree increases, the computation times increase.

As the number of agents increases, the computation times increase.
Scalability of SRTIASP: SRI vs. SRTI. To experiment with SRTIASP on SRTI instances (under weak stability), we have randomly generated ties for the randomly generated SRI instances with the completeness degree . For each agent , we have 1) identified the set of agents that are not acceptable to and vice versa, and randomly picked one of these agents, say , 2) identified the set of agents that are acceptable to and vice versa, and randomly picked one of these agents, say , and 3) added in preference list of so that is indifferent between and . We have added ties as many as of the number of agents. The results of these experiments are shown in Table 3. We can observe the following:

Solving SRTI takes significantly more time, compared to solving SRI.

SRI instances that do not have any stable matching, often have stable matchings after ties are added.
The observation O7 is expected, since SRTI is NPcomplete whereas SRI is in P (Table 1). O8 is reasonable since adding ties reduces the number of potential blocking pairs in general, and thus allows SRTIASP to explore more possibilities.
#instances  SRTIASP  SRICP  

completeness  with a  average time (sec)  average time (sec)  
degree  #agents  solution  exists solution  no solution  exists solution  no solution 
25%  80  13  0.167  0.183  0.318  0.310 
100  14  0.370  0.442  0.389  0.492  
150  8  1.995  1.994  0.704  0.697  
200  10  8.794  8.323  1.047  0.999  
50%  80  13  0.852  1.106  0.481  0.475 
100  12  3.192  2.828  0.674  0.646  
150  14  15.88  15.59  1.267  1.211  
200  9  69.65  72.08  1.940  1.960  
75%  80  8  3.971  3.346  0.684  0.682 
100  13  11.062  8.801  0.967  0.961  
150  9  50.52  51.70  1.795  1.780  
200  12  175.81  202.46  3.214  3.263  
100%  80  13  7.396  7.426  0.883  0.912 
100  10  24.435  16.268  1.190  1.175  
150  11  112.23  113.21  2.593  2.674  
200  12  388.58  353.8  5.074  5.061 
Scalability of SRTIASP vs. SRICP. We have experimented with SRICP SRItoolkit (2019), which utilizes the CP solver Choco (Version 2.1.5), on the SRI instances generated by SRICP’s random instance generator. The results for 80–200 agents are shown in Table 4.

For large SRI instances, SRICP performs significantly better than SRTIASP.
This observation has led to the following idea (mentioned by Prosser 2014) for SRI instances that have stable matchings: “Can we solve Egalitarian SRI faster than SRTIASP, by first enumerating all stable matchings using SRICP, and then finding the optimal one?” We have noticed that the instances (generated by the random instance generator of SRICP) generally have one or two stable matchings. In that case, the answer to this question is Yes. This observation contradicts with the theoretical result on the NPhardness of Egalitarian SRI. So we have generated some instances with more stable matchings. For example, for an instance (sri90) with 90 agents and with more than 9 million stable matchings, SRTIASP takes 1.75 seconds to find an egalitarian stable matching whereas SRICP can not enumerate all these solutions (due to fast consumption of memory). For SRI instances with many stable matchings, it may be better to use SRTIASP to solve Egalitarian SRI; further investigations are planned as part of our future work.
Meanwhile, we have investigated a similar question for SRI instances that do not have any stable matching: “Can we solve Almost SRI instances with agents faster than SRTIASP, by checking whether removing agents (i.e., potential blocking pairs) leads to a stable matching?” We have observed that, for small SRI instances with one blocking pairs, the answer to this question is Yes: If we remove two agents, then we can find a stable matching. For larger instances with many blocking pairs, the answer is negative. For example, for an instance (sri60a) with 60 agents, that does not have any stable matching, we have observed that SRTIASP finds an almost stable matching with 10 blocking pairs in 9.057 seconds. With the enumeratetest method mentioned in the question, we have to enumerate (more than ) instances, and check them one by one using SRICP until an almost stable matching is found. Assuming that SRICP takes 0.001 seconds per instance, in the worst case we will have to test all instances, and it will take at least 2 years. This observation confirms with the theoretical result on the NPhardness of Almost SRI; further investigations are planned as part of our future work.
#instances  SRTIASP  SRAF  

completeness  with a  average time (sec)  average time (sec)  
degree  #agents  solution  exists solution  no solution  exists solution  no solution 
25%  80  13  0.167  0.183  0.118  0.126 
100  14  0.370  0.442  0.242  0.254  
150  8  1.995  1.994  1.002  1.077  
200  10  8.794  8.323  2.674  2.604  
50%  80  13  0.852  1.106  0.521  0.527 
100  12  3.192  2.828  1.073  1.01  
150  14  15.88  15.59  5.029  4.918  
200  9  69.65  72.08  13.35  14.19  
75%  80  8  3.971  3.346  1.248  1.252 
100  13  11.062  8.801  2.795  2.772  
150  9  50.52  51.70  12.65  12.222  
200  12  175.81  202.46  36.35  35.72  
100%  80  13  7.396  7.426  2.525  2.523 
100  10  24.435  16.268  5.677  5.479  
150  11  112.23  113.21  24.94  24.75  
200  12  388.58  353.8  77.89  74.67 
Scalability of SRTIASP vs. SRAF The ASPbased method SRAF Amendola (2018) utilizes abstract argumentation frameworks Dung (1995) for the Stable Marriage problem. According to SRAF, an argumentation framework models an SR instance if the arguments in Arg are pairs of different agents, and the attacks in satisfy the following properties: (i) and , or (ii) and . For every SR instance, once the arguments and attacks are generated, they are translated into a program using the existing methods Wu et al. (2009). In particular, for every argument in AF, if are the arguments that attack , the following rule is included in :
There is a onetoone correspondence between the answer sets for the program and the stable extensions of AF, due to Theorem 2 of Amendola 2018.
We have extended SRAF’s argumentation framework from SR to SRI, by defining the arguments as pairs of agents that are acceptable to each other. implemented (in Python) the transformation of an SRI instance into an argumentation framework AF and then to a program . We have experimented with this extended SRAF (called SRIAF from now on) on the SR instances generated by SRICP’s random instance generator. The results are shown in Table 5.

For large SRI instances, SRIAF performs significantly better than SRTIASP.
6 Conclusion
We have developed a formal framework, called SRTIASP, that is sound and complete (Theorem 1) and general enough to provide solutions to various stable roommates problems, such as, SR, SRI, SRT, SRTI, Egalitarian SRTI, Rank Maximal SRTI, Almost SRTI. Except for SR and SRI, all these variations are intractable (Table 1). Our ongoing work involves extending SRTIASP to other computationally hard stable roommates problems.
Since SRTIASP utilizes Answer Set Programming (ASP), the formulations of problems are concise and elaboration tolerant, and thus SRTIASP provides a flexible framework to study variations of stable roommates problems. Having such a flexible framework and implementation is valuable for studies in matching theory.
We have evaluated SRTIASP over different sizes of randomly generated SRI instances, and have made many interesting observations (O1–O10) about its scalability over different intractable variations of SRI, and in comparison with SRICP and SRAF over tractable variations of SR. The results of our empirical analysis of SRTIASP are promising, in particular, for computationally hard problems. Considering that the input sizes of the instances are large enough for many dormitories, the results of experiments are also promising for realworld applications.
Comparisons with SRICP and SRIAF has helped us to better observe the flexibility of SRTIASP due to elaboration tolerant ASP representations. It is easier to extend SRTIASP to address different variations of SR, while SRICP and SRIAF require further studies in modeling as well as implementation. Note that SRICP uses Choco via a Java wrapper, and SRIAF solves SRI via an argumentation framework. As a future work, we plan to investigate how SRICP and SRIAF can be extended to SRTI and its intractable versions.
The Stable Marriage problem with Ties (SMT) under strong stability, which can be solved with a polynomial time algorithm Irving (1994), has been used as a benchmark in ASP competitions. Its representation is based on ranks instead of preferences, and does not utilize choice rules, cardinality expressions or weak constraints. With its intractable variations (under weak stability), SRTIASP contributes to ASP studies by providing an elaboration tolerant formulation and a complementary and rich set of benchmark instances of Stable Roommates problems.
References
 Abraham et al. (2005) Abraham, D. J., Biró, P., and Manlove, D. F. 2005. “almost stable” matchings in the roommates problem. In International Workshop on Approximation and Online Algorithms. Springer, 1–14.
 Amendola (2018) Amendola, G. 2018. Solving the stable roommates problem using incoherent answer set programs. In Proc. of RiCeRcA.
 Arkin et al. (2009) Arkin, E. M., Bae, S. W., Efrat, A., Okamoto, K., Mitchell, J. S. B., and Polishchuk, V. 2009. Geometric stable roommates. Inf. Process. Lett. 109, 4, 219–224.
 Biró et al. (2012) Biró, P., Manlove, D. F., and McDermid, E. J. 2012. “Almost stable” matchings in the roommates problem with bounded preference lists. Theoretical Computer Science 432, 10 – 20.
 Brewka et al. (2016) Brewka, G., Eiter, T., and Truszczynski, M. 2016. Answer set programming: An introduction to the special issue. AI Magazine 37, 3, 5–6.
 Buccafurri et al. (2000) Buccafurri, F., Leone, N., and Rullo, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12, 5, 845–860.
 Cooper (2020) Cooper, F. 2020. Fair and large stable matchings in the stable marriage and studentproject allocation problems. Ph.D. thesis, University of Glasgow.
 Cseh et al. (2019) Cseh, Á., Irving, R. W., and Manlove, D. F. 2019. The stable roommates problem with short lists. Theory of Computing Systems 63, 1, 128–149.
 Dantsin et al. (2001) Dantsin, E., Eiter, T., Gottlob, G., and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv. 33, 3, 374–425.
 Dung (1995) Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and nperson games. AIJ 77, 2, 321 – 357.
 Erdem and Lifschitz (2003) Erdem, E. and Lifschitz, V. 2003. Tight logic programs. TPLP 3, 45, 499–518.
 Erdogan and Lifschitz (2004) Erdogan, S. T. and Lifschitz, V. 2004. Definitions in answer set programming. In Proc. of LPNMR.
 Erdös and Rényi (1960) Erdös, P. and Rényi, A. 1960. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 17–61.
 Feder (1992) Feder, T. 1992. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences 45, 2, 233 – 284.
 Gai et al. (2007) Gai, A.T., Mathieu, F., de Montgolfier, F., and Reynier, J. 2007. Stratification in P2P networks: Application to BitTorrent. In Proc. of ICDCS. 30.
 Gale and Shapley (1962) Gale, D. and Shapley, L. S. 1962. College admissions and the stability of marriage. The American Mathematical Monthly 69, 1, 9–15.
 Gebser et al. (2011) Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., and Schneider, M. T. 2011. Potassco: The Potsdam Answer Set Solving Collection. AI Communications 24, 2, 107–124.
 Gelfond and Lifschitz (1988) Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of ICLP. 1070–1080.
 Gelfond and Lifschitz (1991) Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.
 Gusfield and Irving (1989) Gusfield, D. and Irving, R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, USA.
 Irving (1985) Irving, R. W. 1985. An efficient algorithm for the “stable roommates” problem. Journal of Algorithms 6, 4, 577–595.
 Irving (1994) Irving, R. W. 1994. Stable marriage and indifference. Discrete Applied Mathematics 48, 3, 261–272.
 Irving and Manlove (2002) Irving, R. W. and Manlove, D. F. 2002. The stable roommates problem with ties. Journal of Algorithms 43, 1, 85–105.
 Irving et al. (2009) Irving, R. W., Manlove, D. F., and O’Malley, G. 2009. Stable marriage with ties and bounded length preference lists. Journal of Discrete Algorithms 7, 2, 213 – 219.
 Knuth (1997) Knuth, D. 1997. Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. In Volume 10 of CRM Proc. Mariages Stables (in English), 1976.
 Kujansuu et al. (1999) Kujansuu, E., Lindberg, T., and Makinen, E. 1999. The stable roomates problem and chess tournament pairings. Divulgaciones Matemáticas 7, 19–28.
 Kunysz (2016) Kunysz, A. 2016. The Strongly Stable Roommates Problem. In Proc. of ESA. Vol. 57. 60:1–60:15.
 Lifschitz and Turner (1994) Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proc. of ICLP. 23–37.
 Manlove (1999) Manlove, D. 1999. Stable marriage with ties and unacceptable partners.
 MatchingToolkit (2020) MatchingToolkit. 2020. http://matwa.optimalmatching.com/.
 McCarthy (1998) McCarthy, J. 1998. Elaboration tolerance. In Proc. of CommonSense.
 Mertens (2005) Mertens, S. 2005. Random stable matchings. Journal of Statistical Mechanics: Theory and Experiment 2005, 10, P10008–P10008.
 Prosser (2014) Prosser, P. 2014. Stable roommates and constraint programming. In Proc. of CPAIOR. 15–28.
 Ronn (1990) Ronn, E. 1990. Npcomplete stable matching problems. Journal of Algorithms 11, 2, 285 – 304.
 Roth et al. (2005) Roth, A. E., Sönmez, T., and Ünver, M. U. 2005. Pairwise kidney exchange. Journal of Economic Theory 125, 2, 151 – 188.
 Scott (2005) Scott, S. 2005. A study of stable marriage problems with ties. Ph.D. thesis, University of Glasgow.
 Simons et al. (2002) Simons, P., Niemelae, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. AIJ 138, 1, 181–234.
 SRItoolkit (2019) SRItoolkit. 2019. http://www.dcs.gla.ac.uk/~pat/roommates/distribution/ (20191121).
 Wu et al. (2009) Wu, Y., Caminada, M., and Gabbay, D. M. 2009. Complete extensions in argumentation coincide with 3valued stable models in logic programming. Studia Logica 93, 23, 383–403.
Comments
There are no comments yet.