The Stable Roommates problems are characterized by the preferences of agents over other agents as roommates. A solution is 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 do not exist any two agents who prefer each other to their roommates, and thus block the matching). This study focuses on a human-centered and computationallychallenging interdisciplinary problem of the Stable Roommates problem and its variations. Motivated by realworld applications, and considering that stable roommates problems do not always have solutions, the goal is to develop novel computational methods to solve these problems, that are not only computationally eficient but also applicable in real-world to benefit humans.
The Stable Roommates problem 1[] (SR) is a matching problem (well-studied 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 areacceptable to each other (i.e., they are in the preference lists of each other), and the matching isstable (i.e., there exist no two agents who prefer each other to their roommates, and thus block the matching).
CEUR Workshop
ISSN1613-0073
SR is studied with incomplete preference lists (SRI)3[], with preference lists including ties (SRT)7[],
and with incomplete preference lists including ties (SRTI4)][. While SR and SRI are tractable 2[
Optimization variants of SR are also studied to find more fair stable solutions. For instance, Egalitarian SR aims to maximize the total satisfaction of preferences of all agents; it is NP-har9d].[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 NP-hard [11].
As first noted by Gale and Shapley [
Motivated by the real-world applications and the computational challenges, our study aims to develop methods for finding personalized, fair, relaxed, explainable solutions for SRTI taking into account further knowledge. To find such solutions, we introduce novel knowledge-based methods, and utilize Answer Set Programming (ASP) [18] based on answer set semantics [19, 20]. We use the ASP solverClingo [21] for declarative problem solving. all preference lists. that ∈ he/she is single.
and ∈ , () =
We define SRTI as in our earlier work [22]. Let be a finite set of agents. For every agent ∈ , let ⊆ \{}
be a set of agents that areacceptable to as roommates. For every in , we assume that prefers as a roommate compared to being single.
Let ≺ be a partial ordering o f ’s preferences over where incomparability is transitive. We refer to ≺ as agent ’s preference list. For two agent s and in , we denote by ≺ that prefers to . In this context, ties correspond to indiference in the preference lists: an agent is indiferent between the agents and , denoted by ∼ , if ⊀ and ⊀ . We denote by ≺ the collection of
such that, for all{, } ⊆ × such if and only i f( ) = . If agent is mapped to itself, we then say A matching is blocked by a pair {, } ⊆ × ( ≠ ) if
B2 is single with respect to , or ≺ () B3 is single with respect to , or ≺ ( ) , and .
A matching for SRTI is calledstable if it is not blocked by any pair of agents. is stable matching since it is not blocked by any pair of students.
is not stable matching since {, } blocks this matching, while
In our earlier work 2[
We have performed experiments to evaluateSRTI-ASP over diferent sizes of randomly generated SRTI instances in term of scalability of its variants (i.e., SRI, SRTI, Almost SRTI, optimization variants of SRTI). We have also comparedSRTI-ASP with two related approaches over diferent sizes of randomly generated SRI instances:SRI-CP [23] solves SRI using constraint programming, anSdRI-AF (extending from SR-AF [24]) solves SRI using an argumentation framework. Comparisons witShRI-CP and SRI-AF has helped us to better observe the flexibility of SRTI-ASP due to elaboration tolerant ASP representations. It is easier to extendSRTI-ASP to address diferent variations of SR, while SRI-CP and SRI-AF require further studies in modeling as well as implementation.
While the optimization variants of SRTI are based on domain-independent measures (e.g., Egalitarian),
in real-world applications (e.g., assigning students as roommates at a dormitory), there are also
domaindependent criteria based on further knowledge, such as the habits and desires of the students. With
this motivation, in our earlier work2[
In real-world applications, we have observed that the preference lists are often too short or empty (e.g., for freshmen students). Thus, for SRI and SRTI instances, it gets harder to find a stable matching: students who are not in the preference lists of each other are considered unacceptable to each other, and thus they cannot be matched. In such cases, we still need to find a matching that is “good-enough.”
To find good-enough matchings, in addition to Almost SRTI, we have proposed a novel approach,
called Knowledge-Based SRTI2[
Personalized-SRTIinfers a new type of preference ordering by considering (i) the importance of each domain-specific criterion for each agent (e.g., one student may give more importance to sleeping habits whereas another student may give more importance to smoking habits), and (ii) the agents’ preferred choices for each domain-specific criterion (e.g., whether a student prefers a roommate who does not smoke). Then, for each agent, it appends this new type of criteria-based personalized preference list inferred from the habitual preferences of the agent, to the end of the preference list given by the agent. A Personalized-SRTI instance defined over an agent set = { a, b, c, d, e}, a criteria list = ⟨ “smoking”, “room environment”, “sleep habits”, “study habits”⟩, and the following choice lists for each criterion, 1 = ⟨“Smoker”,“Non-smoker”⟩, 2 = ⟨“Quiet”,“Social”,“Social and quiet”⟩, 3 = ⟨“Goes to bed early”,“Goes to bed before midnight”,“Goes to bed after midnight ⟩, 4 = ⟨“Studies in the room”,“Studies out of the room”,“Studies in and out of the room”⟩. the same. Then, the inferred preference list ≺ is ⟨{, }⟩ .
Example 2. Consider the example shown in Table 3. The preference profile for student is ⟨2, 1, 3, 2⟩ where = ⟨ “smoking”, “environment”, “sleep habits”, “study habits”⟩. According to , prefers a roommate that is a “Non-smoker”, “Quiet”,“Goes to bed after midnight”,“Studies out of the room”. The weight list for is ⟨5,0,4,4⟩: the most important criterion for is “smoking”, and the “room environment” criterion is not important. We define a sorted profile our definition, the sorted profile for ′ ′ for each agent ∈ , with respect to and . According to = ⟨{(2,“smoking”)}, {(3,“sleep habits”), (2,“study habits”)}⟩. Hence, and are choice-acceptable for . With respect to , is indiferent between and since their choices are ′
′
Most-SRTI introduces a new incremental definition of a stable matching, by considering (i) the ordering of the most preferred criteria (e.g., identified by large surveys) and (ii) the agents’ preferred choices for each domain-specific criterion, with the motivation that the agents with close choices are matched. Most-SRTI aims to compute such most preferred criteria based stable matchings.
Utilizing these methods, we have extendedSRTI-ASP to consider domain-specific knowledge about each individual’s preferences about a set of criteria, and about the diversity preferences of dormitories and schools. We have experimentally evaluated our methods to understand their scalability, usefulness and applicability. We have observed the usefulness of this approach in computing not only good-enough matchings that are stable with respect to extended lists, but also more personalized, more diverse and/or more inclusive matchings.
Details of the definitions, the experimental evaluations and the real-world application of our knowledge-based methods are presented in our journal paper25[].
Although our knowledge-based methods that extend the preference lists of agents with suitable candidates by considering domain-specific knowledge are shown to be useful, it might not always be suficient to find suitable candidates because of relevant but inaccessible knowledge about the students, due to ethical and fairness concerns. For instance, although people with similar political opinions tend to get along better, it would not be appropriate to ask questions, in a roommate search questionnaire, about students’ political opinions. To address this limitation, we have been studying two diferent extensions to relax the problem, by further extending preference lis ts-P(ersonalized-SRTI) and by considering weaker notions of stability (Sticky-SRTI).
-Personalized-SRT.I Students often meet other students through mutual friends, e.g., the friends of their friends, and sometimes get along with each other. Based on this observation, we have proposed a new method [26] to further extend preference lists to be able to find a matching when there is no stable matching. In particular, for every agent , our method extends the preference list of by including every agent who is not already in ’s preference list but “ -connected” to (i.e., and are connected a chain of PFOAF—preferred friend of a friend—relations). Also, we have observed that some existing students may request not to be matched with some students (e.g., previous roommates). Based on this observation, we have extended our method to consider “forbidden pairs”. and the -extended lists ≺ ″
A -Personalized-SRTI instance, characterized by a set of students , sets − of unwanted students as roommates, of preferred students as roommates for = 1 and = 2 .
Student −
{} ⟨⟩ ≺
⟨⟩ ⟨⟩ ⟨⟩ ⟨⟩
′ ≺
⟨⟩ ⟨, ⟩
Unwanted sets and preference lists ≺ 1 ⟨⟩ ⟨⟩ ⟨{, }⟩ ⟨, ⟩ ⟨, ⟩ ⟨, , ⟩
⟨, ⟩ ⟨, {, }⟩ ≺ 1 ″ ≺ 2 ≺ 2 ″ ⟨⟩ ⟨, ⟩ ⟨, ⟩
⟨, , ⟩ ⟨, , ⟩ ⟨, , ⟩ ⟨, , ⟩ ⟨{, }, ⟩ ⟨, {, }, ⟩ Example 3. Consider the Personalized-SRTI instance, in Table 3, does not have a stable matching. Let us denote a pair {, } of students in by . Suppose that states that is unwanted − = {} . Then, − = {} . The -acceptability graph = ( , ) is defined as follows: = {, , , , } and = {, , , } , where every edge {, } ∈ denotes pairs of agents that know each other and none of them is unwanted by the other. We say that agents and form a -connected pairsif there exists a path of length that connects and in , and denotes the set of all -connected pairs in . According to the -acceptability graph = ( , ) , -connected pairs for = 1, 2, 3 are defined as follows: 1 = {, , , } , 2 = {, , , } , and 3 = {, } .
According to ≺′, student is indiferent between student and . We can break this tie by considering -connected pairs: ≺ ′ since is more close to rather than , i.e., there exist a value = 2 such that ∈ 2 and ∉ 2, but ∈ 3.
Table 4 shows -extended preference lists for each student, for = 1 and = 2 . Students and may be acceptable to . Since ∈ 1, ∉ 1 and ∈ 2, ∈≺ 1 and ≺ 2 .
For the running example, we can find a 1-stable matching 1 = {, , } . This solution is also 2-stable.
We have conducted experiments with both objective and subjective measures to evaluate the usefulness of the additional knowledge about the networks of the agents’ preferred friends. We have obtained promising results from the computational perspectives and from the users’ perspectives. For further information about this study, we refer the reader to our paper2[6].
Sticky-SRTI. Afacan et al. [27] have introduced the notion of “sticky stability” to accommodate appeal costs in school placements, and allows priority violations when the rank diference between the claimed and the received objects are less than a certain threshold. We plan to the use of sticky-stability in the context of SRTI to aid the computation of “good-enough” solutions.
Beyond computing solutions, we aim to makSeRTI-ASP transparent and interactive enough to provide evidence-based explanations. In our interactions with the dormitory administration or the student resources, we have observed their interests to know more about the recommended matching computed by our system SRTI-ASP: Why does (or does not) student match with student ? What if student matches with student ? etc. To increase the trust of the users, it is therefore desirable foSrRTI-ASP not only to compute solutions but also to generate explanations for the recommended matching, and to support interactive engagement with the user.
The author(s) have not employed any Generative AI tools. [6] S. Scott, A study of stable marriage problems with ties, University of Glasgow (United Kingdom), 2005. [7] E. Ronn, Np-complete stable matching problems, Journal of Algorithms 11 (1990) 285–304. [8] R. W. Irving, D. F. Manlove, G. O’Malley, Stable marriage with ties and bounded length preference lists, Journal of Discrete Algorithms 7 (2009) 213–219. [9] T. Feder, A new fixed point approach for stable networks and stable marriages, Journal of Computer and System Sciences 45 (1992) 233 – 284. [10] Á. Cseh, R. W. Irving, D. F. Manlove, The stable roommates problem with short lists, Theory of
Computing Systems 63 (2019) 128–149. [11] F. Cooper, Fair and large stable matchings in the Stable Marriage and Student-Project Allocation problems, Ph.D. thesis, University of Glasgow, 2020. [12] D. J. Abraham, P. Biró, D. F. Manlove, “Almost stable” matchings in the roommates problem, in:
International Workshop on Approximation and Online Algorithms, Springer, 2005, pp. 1–14. [13] P. Biró, D. F. Manlove, E. J. McDermid, “almost stable” matchings in the roommates problem with bounded preference lists, Theoretical Computer Science 432 (2012) 10–20. [14] E. Kujansuu, T. Lindberg, E. Makinen, The stable roomates problem and chess tournament pairings,
Divulgaciones Matematicas 7 (1999) 19–28. [15] E. M. Arkin, S. W. Bae, A. Efrat, K. Okamoto, J. S. B. Mitchell, V. Polishchuk, Geometric stable roommates, Inf. Process. Lett. 109 (2009) 219–224. [16] A. E. Roth, T. Sönmez, M. U. Ünver, Pairwise kidney exchange, Journal of Economic theory 125 (2005) 151–188. [17] A.-T. Gai, F. Mathieu, F. de Montgolfier, J. Reynier, Stratification in P2P networks: Application to
BitTorrent, in: Proc. of ICDCS, 2007, p. 30. [18] G. Brewka, T. Eiter, M. Truszczynski, Answer set programming: An introduction to the special issue, AI Magazine 37 (2016) 5–6. [19] M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: Proc. of ICLP,
MIT Press, 1988, pp. 1070–1080. [20] M. Gelfond, V. Lifschitz, Classical negation in logic programs and disjunctive databases, New
Generation Computing 9 (1991) 365–385. [21] M. Gebser, B. Kaufmann, R. Kaminski, M. Ostrowski, T. Schaub, M. T. Schneider, Potassco: The
Potsdam Answer Set Solving Collection, AI Communications 24 (2011) 107–124. [22] E. Erdem, M. Fidan, D. Manlove, P. Prosser, A general framework for stable roommates problems using answer set programming, Theory and Practice of Logic Programming 20 (2020) 911–925. [23] P. Prosser, Stable roommates and constraint programming, in: Proc. of CPAIOR, 2014, pp. 15–28. [24] G. Amendola, Solving the stable roommates problem using incoherent answer set programs (2018). [25] M. Fidan, E. Erdem, Knowledge-based stable roommates problem: A real-world application,
Theory and Practice of Logic Programming 21 (2021) 852–869. [26] M. Fidan, E. Erdem, Finding personalized good-enough solutions to unsatisfiable stable roommates problems, Theory and Practice of Logic Programming (2025). Accepted for publication. [27] M. O. Afacan, Z. H. Aliogullari, M. Barlo, Sticky matching in school choice, Economic Theory 64 (2016) 509–538.