Finding Personalized Good-Enough Solutions to Unsatisfiable Stable Roommates Problems

MÜGE FIDAN, ESRA ERDEM · 2025

Read Finding Personalized Good-Enough Solutions to Unsatisfiable Stable Roommates Problems by MÜGE FIDAN, ESRA ERDEM (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20010.txt.

Introduction

Pairing people as roommates by mutual taste sounds simple, yet some groups admit no stable pairing at all. Muge Fidan and Esra Erdem work on that hard case in 2025. A stable pairing is one where no two people would both rather ditch their assigned partners for each other.

When no such pairing exists, the pair aim for a good-enough one that is shaped to each person. Their method weighs more than ranked lists: it counts habits, settled likes, and each person's circle of favoured friends. Worked examples and tests show how the tailored pairings play out. The aim is a fair fallback for real tasks, from dorm rooms to shared flats, where a perfect stable match may be out of reach.

Catalog record

CREATORMÜGE FIDAN, ESRA ERDEM
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20010

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Finding Personalized Good-Enough Solutions to Unsatisfiable Stable Roommates Problems MÜGE FIDAN, ESRA ERDEM Abstract 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). Motivated by real-world applications, and considering that stable roommates problems do not always have solutions, we continue our studies to compute “good-enough” matchings. In addition to the agents’ habits and habitual preferences, we consider their networks of preferred friends, and introduce a method to generate personalized solutions to stable roommates problems. We illustrate the usefulness of our method with examples and empirical evaluations. keywords stable roommates problem, answer set programming, declarative problem solving 1 Introduction The Stable Roommates problem ( Gale and Shapley, 1962 ) (SR) is a matching problem (well-studied in Economics and Game Theory) characterized by the preferences of an even number n 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). Motivated by real-world applications, variations of SR have been investigated. For instance, students 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 ) . In this study, we focus on SRTI. As first noted by Gale and Shapley, 1962 , unlike the well-known 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). In real-world applications, 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, existing approaches consider more general variations of SR. For instance, Almost SR ( Abraham et al., 2005 ) aims to find a matching that minimize the total number of blocking pairs (i.e., pairs of agents who prefer each other to their roommates). Gärdenfors, 1975 consider “popularity” instead of stability and aims to find a matching that maximizes the number of agents who are better-off in this matching compared to other matchings. Thakur, 2021 introduces the property of “majority stability” to find a matching preferred by more than half of all agents over other matchings. Aziz et al., 2023 generalize the idea of majority stability by proposing “ k -stability” which aims to find a matching preferred by at least k out of the n agents. To relax restriction of popularity, Kavitha and Vaish, 2023 consider the notion of “semi-popularity” to find a matching which is undefeated by a majority of matchings. Afacan et al., 2016 introduce the notion of “sticky stability” to accommodate appeal costs in school placements, and allows priority violations when the rank difference between the claimed and the received objects are less than a certain threshold. In all these studies, every stable matching (if one exists) is also one of the targeted matchings, but not vice versa. We propose a different (but orthogonal) approach to find good-enough solutions, by extending the preference lists of agents with “suitable” candidates identified by further available knowledge. For instance, in our earlier work ( Fidan and Erdem, 2021 ) , we have introduced knowledge-based methods for SRTI, that identify suitable candidates by considering the habits (e.g., smoking, studying) of students, the preferences over the habits of their roommates, and the preferences and the constraints of the colleges (e.g., to increase diversity and inclusion). 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. In this study, motivated by the promising results of our earlier studies and further observations we have made in real-world applications with the help of different parties involved, we propose a new method to further extend preference lists to be able to find a matching when there is no stable matching. In particular, based on the observations, students often make new friends by meeting friends of their friends, our method extends the preference lists further by considering the networks of agent’s preferred friends. At this point, the curious reader may think rightfully that not every student would agree with the preference lists of their friends, but actually many of the students do prefer as roommates a preferred friend’s friend if they cannot be assigned to any of their preferred friends. Indeed, according to a poll survey, as shown in Fig. 1 , conducted with 101 students at Sabanci University, the majority ( 75.2\% ) of the participants have expressed their preference of a roommate from the preference lists of their friends, if they cannot be assigned to any of their preferred friends. Hence, based on these results, extending the preference lists, based on their networks of preferred friends, is beneficial to align with student’s expectations for assigning a roommate. Based on this observation, our method further extends the preference list of an agent x by including every agent y who is not in x ’s preference list but “ k -connected” to x (i.e., x and y are connected by a chain of k PFOAF–preferred friend of a friend–relations). Imagine that you’re about to start a new semester at the university, and you apply for a double room in a dormitory. You know that some of your friends will apply for a double room as well, so you also specify a list of your friends that you would like to roommate with. After the dormitory system collects all applications, it will try to find the “best” roommate for every applicant considering their preference lists, and place the applicants in double rooms. However, finding a “best” roommate for each applicant is a challenging task, and there is a chance that the dormitory system cannot match you with any of your friends on your preference list. In that case, would you prefer to roommate with someone from the preference lists of your friends? (a) Yes, I prefer this. (b) It does not matter, anyone will do. Figure 1: A poll survey given to a set of students at Sabanci University, to find out whether the student prefers as roommate (a) someone from the preference lists of

Read the complete text