Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 174 https://internationalpubls.com Three Persons Satisfactory Roommates Problem N. Logapriya1, 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: 26-01-2024 Revised: 12-04-2024 Accepted: 28-04-2024 Abstract: The Satisfactory Roommates Problem (SFRP) is the problem of finding satisfactory matching between any pair of roommates. In the SFRP, each person in the set of even cardinality 2n rank the 2n-1 others in order of preference. The satisfactory matching is the partition of the set into 2n/2 pairs of roommates based on the individual satisfactory level. In this Three Person Satisfactory Roommates Problem (TPSRP), there are 3n persons with a preference lists for each person for their two partners will be given. Every person in the set could be ranked other (3n-1) members in the order of preference. A matching is defined to be a set of triples. This paper provides a new elaborated algorithm for finding a perfect triples in the rooms. Key words: Preference value, Preference value matrix, perfect matching, three person roommates, modified preference value matrix. 1. Introduction The stable roommates’ problem, which we call SR, is one of the stable matching problems first introduced by Gale and Shapley. An instance of SR consists of 2n Person, each having a preference list which is a total order of other 2n – 1 person according to his preference. Kazuo Iwama, Shuichi Miyazali and Kazuya Okamoto they extend Stable Roommate to 3-person rooms, which is called 3D-SR (3-Dimensional Stable Roommates). An instance of 3D-SR consists of 3n persons, each having a preference list over remaining the (3n-1) persons. A preference list of each person is totally ordered list including all the other 3n – 1 person according to his preference. A matching is now set of n disjoint triples. A matching is stable if there is no three person, each of whom becomes better off if they constitute a new triple. Such a triple is called a blocking triple. 3D-SR asks if there exists a stable matching for a given instance. Recall that in the case of the classical stable roommates’ problem (for 2-person rooms). 2. Satisfactory Roommate’s Problem in two roommates The Satisfactory Roommates Problem (SFRP) is the problem of finding satisfactory matching pair of roommates in the group. In the SFRP, each person in the set of even cardinality 2n Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 175 https://internationalpubls.com ranks the (2n-1) others in order of preference. The satisfactory matching is the partition of the set into 2n/2 pairs of roommates based on the individual satisfactory level. Representing preference lists of the members as a satisfactory value matrix. SVM = [vij], where [vij] is not defined if i = j and if i ≠ j then [vij] is equal to the sum of preference value of jth member with respect to ith member and preference value of ith member and preference value of ith member with respect to jth member and it is equal to Sij = Pij + Pji. Where P represents the Preference value and it is defined as the value assigned to the members in the preference list according to the order of preference with respect to the members by considering the first member as 𝑛−1 𝑛−1 , the second member as 𝑛−2 𝑛−1 , the third member as 𝑛−3 𝑛−1 and so on. A Satisfactory matching between roommates is determined using the assignment technique. In order to get SVM on one-to-one optimum matching, the Hungarian algorithm is applied. 3. Three Person Satisfactory Matching (TPSM) In this paper we propose an algorithm to find triple roommates from the group of 3n person based on their preference lists. This algorithm provides n set of triple roommates based on the individual satisfactory level. Preference value (TPSRP) is defined as the value assigned to the persons 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. Preference value matrix is defined by P:[Pij] Pij = { 3𝑛−2 3𝑛−2 𝑖𝑓 𝑗 𝑖𝑠 𝑡ℎ𝑒 𝑓𝑖𝑟𝑠𝑡 𝑜𝑟 𝑠𝑒𝑐𝑜𝑛𝑑 𝑝𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑐𝑒 𝑜𝑓 𝑖 3𝑛−𝑘 3𝑛−2 𝑖𝑓 𝑗 𝑖𝑠 𝑘 𝑡ℎ 𝑝𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑐𝑒 𝑜𝑓 𝑖 𝑎𝑛𝑑 𝑘 = 3,4,5,6 … . . 𝑢𝑝𝑡𝑜 (3𝑛 − 1) − 𝑖𝑓 𝑖 = 𝑗 Modified preference value matrix is defined by m(i,j), k = { − 𝑖𝑓 𝑘 = 𝑖 𝑎𝑛𝑑 𝑘 = 𝑗 𝑃𝑖𝑘 + 𝑝𝑗𝑖 𝑘 = 1,2, … .3𝑛 ≠ 𝑖, 𝑗 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. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 176 https://internationalpubls.com 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. 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 be the optimum triples. 4. Example : Consider the problem instance of TPSRP based on order of preference 1 2 3 4 5 6 2 4 6 1 3 5 3 5 1 4 2 6 4 3 6 2 5 1 5 1 3 4 6 2 6 5 4 3 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 persons 2,3,4,5,6 are 4 4 , 4 4 , 3 4 , 2 4 , and 1 4 with respect to person 1. The preference value of persons 4,6,1,3,5 are 4 4 , 4 4 , 3 4 , 2 4 , and 1 4 with respect to person 2. The preference value for persons 5,1,4,2,6 are 4 4 , 4 4 , 3 4 , 2 4 , and 1 4 with respect to person 3. The preference value for persons 3,6,2,5,1 are 4 4 , 4 4 , 3 4 , 2 4 , and 1 4 with respect to person 4. The preference value for persons 1,3,4,6,2 are 4 4 , 4 4 , 3 4 , 2 4 , and 1 4 with respect to person 5. The preference value for persons 5,4,3,2,1 are 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 The preference value matrix Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 177 https://internationalpubls.com 1 2 3 4 5 6 4 4 3 2 1 1 4 4 4 4 4 3 2 4 1 4 2 4 4 4 4 4 4 2 3 4 1 3 4 4 4 4 4 1 3 4 2 4 4 4 4 4 4 4 4 1 4 3 2 5 4 4 4 4 4 1 2 3 4 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 2 3 2 0 0 4 4 4 2 1 3 3 0 0 4 4 4 3 1 2 4 0 0 4 4 4 3 1 2 5 0 0 4 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,2),(2,6),(3,5),(4,3),(5,1),(6,4) be the optimum pairs. To find the optimum triples, from the mPVM choose (1,2) pair, the first row second column corresponding element 0 and add with entire first row and assign that particular element place Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 178 https://internationalpubls.com with -. Likewise, choose the next pair (2,6), the second row sixth 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,2) 0 4 4 4 1 2 3 (2,6) 0 4 4 4 2 1 3 (3,5) 0 4 4 4 3 1 2 (4,3) 0 4 4 4 3 1 2 (5,1) 0 4 4 4 3 2 1 (6,4) 0 4 4 4 MmPVM − − − − − − = − − − − − − Considering this above matrix as the minimization assignment problem and apply Hungarian algorithm then get the optimum triples. The triples are (1,2,3), (2,6,4), (3,5,1) (4,3,6), (5,1,2), (6,4,5). To obtain a best three persons as a roommate, by calculate an individual preference value and overall satisfaction. Choose the first triple (1,2,3), to get 1st person satisfactory value, by adding the 1st person’s preference value in the preference value matrix with respect to 2nd person and 3rd person and An individual satisfaction level can be obtained to multiplying by 50. That is 1 → 4 4 + 4 4 = 2 × 50 = 100%. 2 → 3 4 + 2 4 = 5 4 × 50 = 62.5%. 3 → 4 4 + 2 4 = 6 4 × 50 = 75%. Find the average for the individual satisfaction for getting the overall satisfaction level. That is, 100+62.5+75 = 237.5 3 = 79 %. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 179 https://internationalpubls.com 79% will be the overall satisfaction for the 1st, 2nd, 3rd person as the roommates. Similarly these process can be apply 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,2,3) 1 → 2 & 3 = 100%. 79% 2 → 1 & 3 = 62.5%. 3 → 1 & 2 = 75%. 2 (4,5,6) 4 → 5 & 6 = 75%. 79% 5 → 4 & 6 = 62.5%. 6 → 4 & 5 = 50%. 3 (1,2,5) 1 → 2 & 5 = 75%. 63% 2 → 1 & 5 = 50%. 5 → 1 & 2 = 62.5%. 4 (3,4,6) 3 → 4 & 6 = 50%. 49% 4 → 3 & 6 = 100%. 6 → 3 & 4 = 87.5%. 5 (1,3,5) 1 → 3 & 5 = 75%. 92% 3 → 1 & 5 = 100%. 5 → 1 & 3 = 100%. 6 (2,4,6) 2 → 4 & 6 = 100%. 87.5% 4 → 2 & 6 = 87.5%. 6 → 2 & 4 = 75%. From the above table the roommates 1, 3 and 5 having the highest overall satisfaction. Then (1,3,5) be the first best triple roommates and automatically (2,4,6) be the next triple roommates. Note that the triple (2,4,6) also having the highest satisfaction on it. 5 Conclusion In this paper, we described an Algorithm TPSMA, by defining a preference value for the preference lists of roommates instance with three person rooms. This algorithm results, firstly a perfect satisfactory pair matching and secondly the triple matching. After examining the results we conclude that the perfect triple matching. We have shown TPSMA are quicker and efficient. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 180 https://internationalpubls.com 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. [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] .D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69(1962), pp 9-15. [14] Robert W.Irving An Efficient Algorithm for the Stable Roommates Problem, Journal of Algorithms 6(1985), 577-595. [15] D.Gusfield.The structure of the stable roommate problem-efficient representation and enumeration of all stable assignments. SIAM Journal of computing, 17(4):742-769, 1988. [16] T. Ramachandran., K.Velusamy., and T. Selvakumar., Satisfactory Roommates Problem, International journal of Mathematical Archives,2(9),2011,1679-1682.