Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

58 
https://internationalpubls.com 

Three Persons Satisfactory Roommates Problem with Incomplete List 

 

N. Logapriya1 and T. Ramachandran2 
1Department of Mathematics, M.V Muthiah Government Arts College for Women, Dindigul, Tamil Nadu 624001 

g-mail: logapriya848@gmail.com 
2Department of Mathematics, M.V Muthiah Government Arts College for Women, Dindigul, Tamil Nadu 624001 

g-mail: yasrams@gmail.com 

 

Article History: 

Received: 25-08-2023 

Revised: 28-09-2023 

Accepted: 22-10-2023 

Abstract:  

The Satisfactory Roommates Problem (SFRP) is the problem of finding satisfactory matching 

between any pair of roommates.  In the complete list (SFRP) each person in the set of even 

cardinality 2𝑛 ranks the 2𝑛 − 1 others in order of preference. In the incomplete list (SFRPI) there 

is some member in the group prefers less than 2𝑛 − 1 members. There are 3𝑛 people in this Three 

Persons Satisfactory Roommates Problem with incomplete list (TPSRPI), and each person has a 

preference list for their two companions. Some people have preferences that are fewer than 3𝑛 − 1.  

A set of triples is referred to as a matching. A new, complex algorithm for locating perfect triples 

in rooms is presented in this study.  

Keywords: Incomplete list, preference value, satisfactory value matrix, perfect matching, three 

person rooms, modified satisfactory value matrix. 

1. Introduction 

The Stable Marriage with Incomplete Preference Lists (SMI) is a generalization of the SM. In the event 

that an individual decides that one or more members of the set are not suitable as a mate, those 

individuals are removed from their list of preferences, resulting in an incomplete preference list. The 

preferences of agents over other agents as roommates, where the preferences may have ties or be 

incomplete, characterize the Stable Roommates problem with Ties and Incomplete lists (SRTI), a 

matching problem.  

The analysis was further developed  by Brio et al. [1] to include the Stable Roommates problem with 

incomplete lists. Two variations of the traditional Stable Roommates (SR) problem with incomplete 

(but strictly ordered) preference lists (SRI) that are degree-constrained—that is, preference lists with 

restricted length—were examined by Cseh et al. [2]. In the presence of ties and incomplete lists, Adil 

et al. [3] examined the parameterized complexity of NP-hard optimization variants of stable 

roommates and stable matching. Fidan and Erdem [4] presented a knowledge-based approach to SRTI 

that takes domain-specific knowledge into account and looks into its practical use for matching up 

students in a university dorm. A formal framework known as SRTI-ASP was presented by Erdem and 

Fidan [5]. It makes use of the Answer Set Programming logic programming paradigm, which is proven 

and sufficiently generic to handle a large number of these SR variations. 

An undirected non-bipartite graph 𝐺 = (𝑉, 𝐸) is a perfect illustration of the highly stable roommates 

problem with incomplete lists and ties (SRTI). An adjacency list is a list of ties, or vertices that are 

equally excellent for a given vertex. The set of all highly stable matchings can be represented by a 

partial order with 𝑂(𝑚) elements, as demonstrated by Kunysz [6] and provided an 𝑂(nm) strategy for 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

59 
https://internationalpubls.com 

creating this kind of representation. The algorithms are predicated on a straightforward reduction to 

the problem's bipartite form. Bredereck et al. [7] examined the boundary between W[1]-hardness and 

fixed-parameter tractability of stable roommates with ties and incomplete lists from the perspective of 

parameterized graph algorithmics. 

Irving [8] provided an 𝑂(𝑚) algorithm that, given an instance 𝐼 of SR, finds a stable matching or states 

that none exists. The approach is predicated on the assumptions that all preference lists in 𝐼 are 

complete (that is, 𝐴𝑖 = 𝐴 ∖ {𝑎𝑖} for each 𝑎𝑖 ∈ 𝐴 ) and 𝑛 is even. However, it is simple to apply the 

algorithm to the problem model that is described here, which is the incomplete list problem [9]. The 

problem of finding large weakly stable matchings in the presence of incomplete preference lists 

containing onesided ties was examined by Lam and Plaxton [10]. Additionally shown a polynomial-

time approach that produces a 1 + 1/𝑒 better approximation ratio. The approach is based on a proposal 

process wherein numerical priorities are utilized for tiebreaking and are modified based on the outcome 

of a linear program.  

SR was expanded to three-person rooms by Iwama et al. [11], this system is known as 3D-SR (3-

Dimensional Stable Roommates).  The three-person satisfying roommate dilemma is made up of 

3𝑛 person (3D-SR) who may have a list of preferences over the other three persons (3𝑛 − 1). Every 

individual has a fully ordered preference list that includes every other person ranked from 1 to 3𝑛 − 1 

based on his preferences. This study uses the same TPSR approach to discover a satisfactory match 

for the roommate's problem with an incomplete list, which is an extension of the three-person 

roommate's problem. 

2. Satisfactory Roommate’s Problem with Incomplete list in two roommates            

A traditional Satisfactory Roommate's Problem (SFRP) where each group member will receive a 

complete preference list. The term SFRPI refers to the Satisfactory Roommates Problem, which is 

characterized by an incomplete preference list [12]. In other words, some members of the group of 2𝑛 

members are preferred above members of 2𝑛 − 1. The SMAR procedure, which is detailed in the 

SFRPI, can be used to produce satisfactory matching for this particular type of SFRPI problem. 

Participant p is acceptable to participant 𝑞 if it appears on 𝑞's preference list and undesirable otherwise. 

Displaying the members' preference lists as a satisfactory value matrix. 𝑆𝑉𝑀 =  [𝑎𝑖𝑗], where [𝑎𝑖𝑗] is 

equal to the sum of the preference values of the  𝑗th  member with regard to the ith member, the 

preference value of the  𝑖th  member with respect to the  𝑗th  member, and the preference value of the 

 𝑖th  member with respect to the  𝑗th member. If 𝑖 =  𝑗, then [𝑎𝑖𝑗] is not specified. This equal 𝑆𝑖𝑗 =

 𝑃𝑖𝑗  +  𝑃𝑗𝑖. 𝑃 stands for the preference value, which is defined as the value that is assigned to each 

member in the preference list based on their relative preference. For example, the first member is 

represented as 
𝑛−1

𝑛−1
, the second as 

𝑛−2

𝑛−1
,  the third as 

𝑛−3

𝑛−1
 and so on [13]. The assignment technique is 

used to determine a satisfactory fit between roommates. Using the Hungarian algorithm, SVM on one-

to-one optimum matching is obtained. 

 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

60 
https://internationalpubls.com 

3. Three Person Satisfactory Matching (TPSM)  

In this paper, we propose an algorithm to find triple roommates from a group of 3n person based on 

their preference lists and some members prefer less than 3n-1 persons. This algorithm provides a 3n 

set of triple roommates based on the individual satisfactory level.  

Preference value (TPSRP) is defined as the value assigned to the members in the preference list 

according to the order of preference with respect to the persons by considering the first person as 
3𝑛−2

3𝑛−2
, 

the second person as 
3𝑛−2

3𝑛−2
, the third person as 

3𝑛−3

3𝑛−2
 , the fourth person as 

3𝑛−4

3𝑛−2
 and so on. If the person 

i did not prefer j, then jth place in ith list must be considered as infinity.  

𝑃: [𝑃𝑖𝑗] defines the preference value matrix. 

𝑃𝑖𝑗 = {

3𝑛−2

3𝑛−2
                                       if j is the first or second preference of i

  
3𝑛−𝑘

3𝑛−2
    if j is  𝑘th  preference of i and k = 3,4,5,6 … … upto (3n − 1)

 −                                                                                                               if i = j

  

The modified preference value matrix is defined as follows:  

 𝑚(𝑖𝑗),𝑘 = {
−                if k = i and k = j 

𝑃𝑖𝑘 + 𝑃𝑗𝑖       k = 1,2, … .3n ≠ i, j   
 

 

3.1 Algorithm (TPSMA) 

1. Get the preference lists from each person. 

2. Form a preference value matrix based on their preference lists. 

3. Considering the preference value matrix as a Maximization assignment problem.  

4. Construct a Minimized Preference Value Matrix and applying Hungarian algorithm for that 

matrix. 

5. The Resultant pairs must be the optimum pairs like (i,j), (k,l), (m,n) and so on obtained. 

6. Construct the Modified Preference Value matrix by considering the pairs (i,j), (k,l), (m,n) … 

as rows and 1,2,….3n members as column. By using MPVM definition which is given above. 

7.  Considering the Modified preference value matrix as a minimized assignment problem and 

apply Hungarian Algorithm for getting the optimum triples.  

8. List out all the triples and let it be (i,j,k), (l,m,n), (i,l,n)….. 

9. From the obtained triples, choose one by one and find the satisfactory value of each member 

of a group.  

10. If (i,j,k) be the first triples, find the preference value of i with respect to j and k, then adding 

the preference values. Now we get the overall preference value and multiply the value by 50. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

61 
https://internationalpubls.com 

It gives a satisfactory value of i with respect to j and k. similarly find the satisfactory value of 

j w.r.to i & k, also for k w.r.to i & j.  

11. After getting these three satisfactory values, find overall satisfaction for the triple (i,j,k). In 

the same manner repeat the process for all the remaining triples. 

12. Now choose mutually exclusive and exhaustive triples which achieves the maximum level 

of satisfaction that is the optimum triples.   

 

4.  Example : Consider the problem instance of TPSRP based on order of preference 

1 3  4  2  5  6 

2 5  3  1  6  4 

3 2  4  6  5  1 

4 3  1  6  2 

5 2  6  3  1   

6 3  5  4  2  1 

 

Solution:  

The given preference list can be constructed as a preference value matrix by considering first person 

as  
3𝑛−2

3𝑛−2
, second person as 

3𝑛−2

3𝑛−2
, third person as 

3𝑛−3

3𝑛−2
, , fourth person as 

3𝑛−4

3𝑛−2
, fifth person as 

3𝑛−5

3𝑛−2
. The 

preference value of the persons 3,4,2,5,6 is 
4

4
, 

4

4
, 

3

4
, 

2

4
 and 

1

4
 with respect to person 1. The preference 

value of persons 5,3,1,6,4 is 
4

4
, 

4

4
, 

3

4
, 

2

4
, and 

1

4
  with respect to person 2. The preference value for persons 

2,4,6,5,1 is 
4

4
, 

4

4
, 

3

4
, 

2

4
, and 

1

4
  with respect to person 3. The preference value for persons 3,1,6,2 is 

4

4
, 

4

4
, 

3

4
, 

2

4
,  with respect to person 4. The preference value for persons 2,6,3,1 is 

4

4
, 

4

4
, 

3

4
, 

2

4
 with respect to person 

5. The preference value for members 3,5,4,2,1 is 
4

4
, 

4

4
, 

3

4
, 

2

4
 and 

1

4
   with respect to person 6. The 

preference values are presented in the form of matrix which is given below 

 

 

 

 

 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

62 
https://internationalpubls.com 

The preference value matrix 

                 

1 2 3 4 5 6

3 4 4 2 1
1

4 4 4 4 4

3 4 1 4 2
2

4 4 4 4 4

1 4 4 2 3
3

4 4 4 4 4

4 2 4 3
4

4 4 4 4

2 4 3 4
5

4 4 4 4

1 2 4 3 4
6

4 4 4 4 4

PVM

−

−

−
=

− −

− −

−

 

From the preference value matrix to construct the minimized preference value matrix by subtracting 

all the elements in the matrix from the highest element in the matrix. Then the Minimized preference 

value matrix given below 

The minimized preference value matrix 

           

1 2 3 4 5 6

1 2 3
1 0 0

4 4 4

1 3 2
2 0 0

4 4 4

3 2 1
3 0 0

4 4 4

2 1
4 0 0

4 4

2 1
5 0 0

4 4

3 2 1
6 0 0

4 4 4

mPVM

−

−

−
=

− −

− −

−

 

Considering the mPVM as the assignment problem and applying Hungarian algorithm for finding the 

optimum pairs. 

(1,4),(2,3),(3,2),(4,1),(5,6),(6,5) be the optimum pairs. 

             



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

63 
https://internationalpubls.com 

To find the optimum triples, from the mPVM choose (1,4) pair, the first row fourth column   

corresponding element 0 and add with entire first row and assign that particular element place with -. 

Likewise, choose the next pair (2,3), the second row third column element 0 and add with entire second 

row and assign that particular element place with -. Similarly, repeat the process for all optimum pairs. 

Then the resultant matrix will be a Modified Minimum Preference Value Matrix (MmPVM). 

The modified minimum preference value matrix is given below, 

1 2 3 4 5 6

1 2 3
(1,4) 0

4 4 4

1 3 2
(2,3) 0

4 4 4

3 2 1
(3,2) 0

4 4 4

2 1
(4,1) 0

4 4

2 1
(5,6) 0

4 4

3 2 1
(6,5) 0

4 4 4

MmPVM

− −

− −

− −
=

− − −

− − −

− −

 

Considering this above matrix as the assignment problem and apply Hungarian algorithm then get the 

optimum triples. 

The triples are (1,4,2), (2,3,5), (3,2,4) (4,1,6), (5,6,1), (6,3,5). 

To obtain a best three persons as a roommate, by calculate an individual preference value and overall 

satisfaction.  

Choose the first triple (1,4,2), to get 1st person satisfactory value, by adding the 4th person’s preference 

value in the preference value matrix with respect to 4th person and 3rd person and an individual 

satisfaction level  can be obtained to multiplying by 50.  

That is 1 → 
4

4
 + 

3

4
 = 

7

4
  × 50 = 87.5%.  

4 → 
4

4
 + 

2

4
 =  

6

4
  × 50 = 75%. 

 2 → 
3

4
 + 

1

4
 =  1 × 50 = 50%. 

Find the average for the individual satisfaction for getting the overall satisfaction level. That is, 

87.5+75+50 = 
212.5

3
 = 70.8 %. 

9970.8% will be the overall satisfaction for the 1st, 4th, 2nd person as the roommates.  



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

64 
https://internationalpubls.com 

Similarly this process can be applied for all the triples which we have.  

Now choose mutually exclusive and exhaustive triples,  

Then the result as shown in the table 1,  

Table 1. Three person individual and overall satisfactory matching 

S.No Possible Triples Individual Satisfaction Overall Satisfaction 

 

1 

 

(1,4,2) 

1 → 2 & 4 = 87.5%.  

70.8% 

 

 

77 

2 → 1 & 4 = 50%. 

4 → 1 & 2 = 75%. 

 

2 

 

(3,5,6) 

3 → 5 & 6 = 62.5%.  

83.33% 5 → 3 & 6 = 87.5%. 

6 → 3 & 5 = 100%. 

 

3 

 

(2,3,5) 

2 → 3 & 5 = 100%.  

87.5% 

 

 

77 

3 → 2 & 5 = 75%. 

5 → 2 & 3 = 87.5%. 

 

4 

 

(4,1,6) 

4 →  1 & 6 = 87.5%.  

66.66% 1 →  4 & 6 = 62.5%. 

6 →  1 & 4 = 50%. 

 

5 

 

(5,6,1) 

5 →  1 & 6 = 75%.  

58.33% 

 

 

69 

6 →  1 & 5 = 62.5%. 

1 →  5 & 6 = 37.5%. 

 

6 

 

(3,2,4) 

3 →  2 & 4 = 100%.  

79.16% 2 →  3 & 4 = 62.5%. 

4 →  2 & 3 = 75%. 

 

From the above table, the overall satisfaction of the triples (1,2,4), (3,5,6) and (2,3,5), (1,4,6) are 77 

percentage, that is both have the same overall satisfaction percentage. Then we have to move the other 

hand for finding the best triples as the roommates.  

Consider the individual satisfaction percentage for possible triples, and calculate the range of them. 

We know that, the lowest range is the best one. The range can be calculated by subtracting the lowest 

value from the highest value. 

In the possible triple (1,2,4), the highest percentage is 87.5 and the lowest percentage is 50. Then the 

range is 87.5 – 50 =37.5% 

In the possible triple (3,5,6), the highest percentage is 100 and the lowest percentage is 62.5. Then the 

range is 100 – 62.5 =37.5% 

In the possible triple (2,3,5), the highest percentage is 100 and the lowest percentage is 75. Then the 

range is 100 – 75 =25% 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

65 
https://internationalpubls.com 

In the possible triple (1,4,6), the highest percentage is 87.5 and the lowest percentage is 50. Then the 

range is 87.5 – 50 =37.5% 

By examine the range of the triples, (2,3,5) have the lowest range percentage. So, we conclude that, 

the triples (2,3,5) and (1,4,6) best triples as the roommates.  

5. Conclusion  

In this paper, we proposed a preference value for the preferred incomplete lists of roommate’s instances 

with three person rooms, and described an Algorithm TPSMA. This algorithm yields a triple matching 

in addition to a perfect, satisfactory matching pair in its initial place. We determine that the acquired 

matching yields flawless triple matching after looking over the data. Here, we've demonstrated the 

speed and effectiveness of TPSMA. This algorithm produces a matching where every pair reaches the 

highest level of satisfaction possible. Thus, roommates with incomplete lists are satisfactorily matched 

according to TPSMA results. 

References 

[1] Biró, P., Manlove, D. F., & McDermid, E. J. (2012). “Almost stable” matchings in the 

Roommates problem with bounded preference lists. Theoretical Computer Science, 432, 10-

20. 

[2] Cseh, Á., Irving, R. W., & Manlove, D. F. (2019). The stable roommates problem with short 

lists. Theory of Computing Systems, 63, 128-149. 

[3] Adil, D., Gupta, S., Roy, S., Saurabh, S., & Zehavi, M. (2018). Parameterized algorithms for 

stable matching with ties and incomplete lists. Theoretical Computer Science, 723, 1-10. 

[4] Fidan, M., & Erdem, E. (2021). Knowledge-based stable roommates problem: a real-world 

application. Theory and Practice of Logic Programming, 21(6), 852-869. 

[5] Erdem, E., Fidan, M., Manlove, D., & Prosser, P. (2020). A general framework for stable 

roommates problems using answer set programming. Theory and Practice of Logic 

Programming, 20(6), 911-925. 

[6] Kunysz, A. (2016). The strongly stable roommates problem. In 24th Annual European 

Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 

[7] Bredereck, R., Heeger, K., Knop, D., & Niedermeier, R. (2022). Parameterized complexity of 

stable roommates with ties and incomplete lists through the lens of graph 

parameters. Information and Computation, 289, 104943. 

[8] Irving, R. W. (1985). An efficient algorithm for the “stable roommates” problem. Journal of 

Algorithms, 6(4), 577-595. 

[9] Gusfield, D., & Irving, R. W. (1989). The stable marriage problem: structure and algorithms. 

MIT press. 

[10] Lam, C. K., & Plaxton, C. G. (2019). A (1+ 1/e)-approximation algorithm for maximum stable 

matching with one-sided ties and incomplete lists. In Proceedings of the Thirtieth Annual 

ACM-SIAM Symposium on Discrete Algorithms (pp. 2823-2840). Society for Industrial and 

Applied Mathematics. 

[11] Iwama, K., Miyazaki, S., & Okamoto, K. (2007). Stable roommates problem with triple 

rooms. Proceedings of WAAC, 7, 105-112.  



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 30 No. 4 (2023) 

 

 

66 
https://internationalpubls.com 

[12] Ramachandran, T., Velusamy, K., & Selvakumar, T. (2012). Satisfactory Roommates Problem 

with Incomplete List. International Journal of Computational Science and Mathematics. ISSN, 

0974-3189, 4(1), 19-22. 

[13] Logapriya, N., & Ramachandran, T. (2023). Three Persons Satisfactory Roommates Problem. 

Gradiva Review Journal, ISSN- 0363 8257, 9(8). 

[14] On the nonlinear Volterra equation with conformable derivative . (2023). Advances in the 

Theory of Nonlinear Analysis and Its Application, 7(2), 292-302.