N–Factor Satisfactory Roommates Problem with Three Roommates

 

NFactor Satisfactory Roommates Problem With Three Roommates

Published by : http://www.ijert.org

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Volume 13, Issue 02, February 2024

N. Logapriya and T. Ramachandran

Research scholar, Department of Mathematics,

M.V Muthiah Government Arts College for Women, Dindigul, Tamil Nadu 624001

Head, Department of Mathematics,

M.V Muthiah Government Arts College for Women, Dindigul, Tamil Nadu 624001

Abstract

The Three Person Satisfactory Roommates Problem (TPSRP) involves three people and a preference list that each of them will receive for their two partners. Each member of the set might be ranked in the order of preference with other (3n-1) members. A set of triples is referred to as a matching. In this paper, we extend the single preference list case into N – Factor TPSRP, which contains multiple factors; each member of the list provides their preference list; a better matching can be achieved by taking into account all the factors in the end; an example is provided to demonstrate the technique. This paper presents a novel sophisticated algorithm for finding perfect triples in rooms.

Keywords: Preference value, N – factors, perfect

matching, three-person roommates, modified preference value matrix.

1. INTRODUCTION

   One of the stable matching (SM) problems initially presented by Gale and Shapley [1] is the stable roommates’ problem (SRP). Since the set of stable matching remains the same if we convert an SM instance into an SRP instance by adding all other members who are of the exact same gender to the very end of each member’s preference list, it is widely known that the stable roommates problem is an extension of the stable marriage problem [2, 3].

   Irving [4] presented an () technique that

   determines if a stable matching exists or not given

   an instance of SRP. The methodology is based on

   the suppositions that is even and all preference lists in are full (that is, = {} for each

   ). A sample of SRP consists of two people, each of

   whom has a preference list that ranks the other two

   people in total order based on his preferences. An algorithm for the roommate problem was investigated by Linden et al. [5]. It matched soulmatesindividuals who share a preference for each otherfirst and then iterated through the procedure. With two roommates and explicit preferences, the original roommate problem is the focus of all this research.

   Bredereck et al. [6] in 2020 explored a unique variation of multidimensional roommate games with a central list or poset that acts as the source of all agents’ preference lists. McKay and Manlove [7] formalized a three-dimensional variant using generic additively separable preferences in which each agent provides an integer evaluation of each successive agent. This variant shows that the related preference issue is NP-complete and that a stable matching may not happen even in situations when the valuations are binary. Park [8] indicated that it is possible to find a stable matching in polynomial

   IJERTV13IS020040

   (This work is licensed under a Creative Commons Attribution 4.0 International License.)

   time that optimizes the utility of student preferences in a two-sided market with one-sided preference. Experiments also confirmed that the quality of assignments is enhanced. As a generalized roommate problem, balancing stability and efficiency in team creation is addressed [9]. It has been demonstrated by Kamiyama [10] that finding a stable matching in this situation is an NP-complete assignment.

   The 3-person room application, known as 3D-SR (3- Dimensional Stable Roommates), was further developed by Iwama et al. [11]. A 3D-SR instance consists of 3n individuals, each of whom has a

   preference list over the remaining (3

   1) individuals. Every individual has a completely

   ordered preference list that includes every other

   person ranked from 1 to 3 based on his preferences. There is now disconnected triples in

   a matching. If there are no three people, a matching

   is stable because each of them benefits when they form a new triple. We refer to a triple like this as a blocking triple. For a given instance, 3D-SR inquires as to whether a stable matching is there. Remember that in the instance of the traditional stable roommates’ dilemma (pertaining to two-person lodgings). The Satisfactory Roommates Problem (SRP) was initially introduced by Ramachandran et al. [12]. Using a Hungarian method, Logapriya and Ramachandran [13, 14] presented the three-person satisfactory roommate problem as well as incomplete lists. Ramachandran and Selvakumar [15] proposed N-factor SRP following that Ramachandran et al. [16] explored the variants of N- factor SRP with appropriate instances that revealed some intriguing results in the case of satisfactory roommates’ problems.

2. N-FACTOR SATISFACTORY ROOMMATES PROBLEM

   Based on the desires of the participants, the N-Factor Satisfactory Roommates Problem (N-Factor SFRP) has N number of preference lists. The N-Factor is introduced in the SFRP as a result of the members in this concern providing their own preference lists as distinct factors.

   The single preference list and its corresponding preference values are taken into consideration in the standard Three Person Satisfactory Roommates Problem (TPSRP). However, since N-Factors are being considered here and each problem instance

   has a different preference list, we will take intelligence, sports, music interest, and so forth into consideration. Each participant provides a preference list in their own order, which we may use to create the preference value matrix. To get the final result, we can use our TPSR Algorithm after adding up all of the preference value matrices. We employ terms that are associated with it, including Modified Preference Value Matrix and Preference Value Matrix. Based on the weights assigned to each factor, the satisfactory value matrices for each factor are added. The resulting matrix is subjected to the Hungarian algorithm, which produces the most optimal and appropriate matching between the members. To enhance comprehension, N-Factor SFRP is examined with appropriate examples and equal weight.

   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

   32

   In this paper, we extend the single preference list

   the persons by considering the first person as

   ,

   32

   case into N – Factor TPSRP, which contains multiple

   the second person as 32, the third person as 3 3 ,

   factors; each member of the list provides their

   preference list; a better matching can be achieved by taking into account all the factors in the end; an example is provided to demonstrate the technique.

   32

   the fourth person as 34 and so on.

   32

   Preference value matrix is defined by P:[Pij]

   Pij =

   32

   3 2 32

   { 3

   32

   if is the first or second preference of if is th preference of and = 3,4,5,6 . . upto (3 1)

   =

   Modified preference value matrix is defined by

   = =

   m(i,j), k = {

   + = 1,2, .3 ,

3. SATISFACTORY MATCHING ALGORITHM FOR N- FACTOR ROOMMATES

1. Get the preference lists from each person in each factor.
2. Form a preference valuematrix based on their preference lists.
3. Summing all the Preference Value Matrix (PVM) for each factor.
4. Considering the overall preference value matrix as a Maximization assignment problem.
5. Construct a Minimized Preference Value Matrix and applying Hungarian algorithm for that matrix.
6. The Resultant pairs must be the optimum pairs

   like (, ), (, ), (, ) and so on obtained.

7. Construct the Modified Preference Value matrix

   by considering the pairs (, ), (, ), (, ) as

   rows and 1,2, .3 members as column. By

   using MPVM definition which is given above.

8. Considering the Modified preference value matrix as a minimized assignment problem and apply Hungarian Algorithm for getting the optimum triples.
9. List out all the triples and let it be

   (, , ), (, , ), (, , ) ..

10. From the obtained triples, choose one by one and

    find the satisfactory value of each member of a group.

11. If (, , ) be the first triples, find the preference value of with respect to and , 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

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

12. After getting these three satisfactory values, find

    overall satisfaction for the triple (, , ). In the

    same manner repeat the process for all the

    remaining triples.

13. Now choose mutually exclusive and exhaustive triples which achieves the maximum level of satisfaction that be the optimum triples.
    1. EXAMPLE
       

       1	6	4 3	5 2
       2	3	4 5	1 6
       3	5	2 6	4 1
       4	1	2 6	3 5
       5	3	1 2	6 4
       6	4	2 1	5 3

        

       Consider the problem instance of TPSRP based on order of preference, here all the students are considering the Intelligence factor of the remaining students.

       SOLUTION:

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

       2

       second person as 3 2, third person as 3 3, fourth person as 34, fifth person as 3 5 . The preference values are

       2

       2

       2

       2

       presented in the form of matrix which is given below

       The preference value matrix for the Intelligence factor

       2	3	4	5	6
       1	3	4	2	4
       4	4	4	4	4

        

       1

       1

       2 2

       4 4 3 1

       4 4 4 4 4

       3 1 4

       2 4 3

       PVM

       4 4 4 4 4

       4 4 4 2

       1 3

       4 4 4 4 4

       4	4	4	4
       3	4	1	4	2
       4	4	4	4	4

        

       5 4 3 4 1 2

       4

       6

       Consider the problem instance of TPSRP based on order of preference, here all the students are considering the sports interest factor of the remaining students.

       1	4	5 6	2 3
       2	5	1 3	6 4
       3	2	6 5	4 1
       4	6	5 1	3 2
       5	3	4 1	2 6
       6	1	2 4	5 3

       2	3	4	5	6
       2	1	4	4	3
       4	4	4	4	4

        

       The preference values are presented in the form of matrix which is given below The preference value matrix for the sports interest factor

       1

       1

       2 4

       3 1 4 2

       4 4 4 4 4

       3 1 4

       2 3 4

       PVM

       4 4 4 4 4

       4 3 1 2 4 4

       4 4 4 4 4

       4	4	4	4
       4	4	1	3	2
       4	4	4	4	4

        

       5 3 2 4 4 1

       4

       6

       IJERTV13IS020040

       (This work is licensed under a Creative Commons Attribution 4.0 International License.)

       Consider the problem instance of TPSRP based on order of preference, here all the students are considering the Music interest factor of the remaining students.

       1	6	2 3	5 4
       2	5	1 3	6 4
       3	1	2 4	5 6
       4	5	3 2	6 1
       5	2	4 1	6 3
       6	4	5 3	2 1

       The preference values are presented in the form of matrix which is given below The preference value matrix for the Music interest factor

       2	3	4	5	6
       4	3	1	2	4
       4	4	4	4	4

        

       1

       1

       2 4

       3 1 4 2

       4 4 4 4 4

       3 4 4

       3 2 1

       PVM

       4 4 4 4 4

       4 1 3 4 4 2

       4 4 4 4 4

       4	4	4	4
       1	2	3	4	4
       4	4	4	4	4

        

       5 3 4 1 4 2

       4

       6

       Consider the problem instance of TPSRP based on order of preference, here all the students are considering the Spiritual interest factor of the remaining students.

       1	4	6 5	3 2
       2	1	5 6	3 4
       3	5	6 2	1 4
       4	1	6 5	2 3
       5	4	1 3	6 2
       6	4	1 3	2 5

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

       The preference value matrix for the Spiritual interest factor

       2	3	4	5	6
       1	2	4	3		4
       4	4	4	4	4

        

       1

       1

       2 4

       2 1 4 3

       4 4 4 4 4

       3 2 3

       1 4 4

       PVM

       4 4 4 4 4

       4 4 2 1

       3 4

       4 4 4 4 4

       4	4	4	4
       4	2	3	4	1
       4	4	4	4	4

        

       5 4 1 3 4 2

       4

       6

       Consider the problem instance of TPSRP based on order of preference, here all the students are considering the Cultural interest factor of the remaining students.

       1	2	6 4	3 5
       2	3	1 6	5 4
       3	2	5 4	6 1
       4	5	2 1	3 6
       5	6	1 4	3 2
       6	5	4 3	1 2

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

       2	3	4	5	6
       4	2	3	1	4
       4	4	4	4	4

        

       The preference value matrix for the Cultural interest factor

       1

       1

       2 4

       4 1 2 3

       4 4 4 4 4

       3 1 4

       3 4 2

       PVM

       4 4 4 4 4

       4 3 4 2 4 1

       4 4 4 4 4

       4	4	4	4
       2	1	3	4	4
       4	4	4	4	4

        

       5 4 1 2 3 4

       4

       6

       Summing all the Preference Value Matrix,

       PVM

       4

       4

       4

       4

       4

       4

       4

       1	2	3	4	5	6
       	12	11	16	12	19
       	4	4	4	4	4
       				17	11
       4
       9 19			11	17	14
       4	4

        

       1

       2 18

       3

       16 8

       4 15 14 11

       16 14

       4 4 4 4 4

       4	4	4	4
       14	13	11	19	13
       4	4	4	4	4

        

       5 18 11 14 16

       6

       11

       4

       From the above 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 7 8 3 7 0

       4 4 4 4

       2 1

       3 11 2 8

       4 4 4 4 4

       10 8 2 5

       mPVM 3 4 0

       4 4 4

       4

       4

       4

       4	4	4
       1 8 5 3 8
       4	4	4	4
       5 4	6 4	8 4	0	6 4

        

       4 4 5 8

       5

       6

       3 5

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

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

       To find the optimum triples, from the mPVM choose (1,6) pair, the first row sixth 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, 6)

       (2, 3) 0

       7 6 3 7

       4 4 4 4

       10 1 7

       4 4 4

       (3, 2) 10

       8 2 5

       MmPVM

       (4, 5)

       4 4 4 4

       1 2 3 2

       4 4 4 4

       (5,1)

       7 1 2 7

       4 4 4 4

       (6, 4)

       5 6 6 6

       4 4 4 4

       Considering this above matrix as the minimization assignment problem and apply Hungarian algorithm then get the optimum triples.

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

       To obtain abest three personsas a roommate, by calculate anindividual preference value and overall satisfaction.

       Choose the first triple (1,4,6), to get 1st person satisfactory value, by adding the 1st persons preference value in the preference value matrix with respect to 4th person and 6th person and An individual satisfaction level can be obtained .

       Now choose mutually exclusive and exhaustive triples,

       Table 1. Individual and overall satisfaction of possible triples

       INDIVIDUAL SATISFACTION

       S.NO
       1	(1,4,6)	1 4 & 6 = 87.5%.	80.83%	79.5
       		4 1 & 6 = 72.5%.
       		6 1 & 4 = 82.5%.
       2	(2,3,5)	2 3 & 5 = 82.5%.	78.3%
       		3 2 & 5 = 90%.
       		5 2 & 3 = 62.5%.
       3	(1,2,3)	1 2 & 3 = 57.5%.	70.83%	72.4
       		2 1 & 3 = 85%.
       		3 1 & 2 = 70%.
       4	(4,5,6)	4 5 & 6 = 75%.	74.16%
       		5 4 & 6 = 67.5%.
       		6 4 & 5 = 80%.
       5	(1,3,5)	1 3 & 5 = 57.5%.	67.5%	66.65
       		3 1 & 5 = 65%.
       		5 1 & 3 = 80%.
       6	(2,4,6)	2 4 & 6 = 47.5%.	65.8%
       		4 2 & 6 = 70%.
       		6 2 & 4 = 80%.

       Table 1 depicts the results that the roommates 1,4 and 6 having the highest percentage as the roommates. As well as 2,3 and 5 also having the highest percentage as the roommates. So we conclude that the triples (1,4,6) and (2,3,5) are the satisfactory roommates.

    2. CONCLUSION

In this research, we defined a preference value for the preferene lists of roommate instances with three-person rooms, and we developed an algorithm for N factors TPSMA. First, this method produces a perfectly satisfactory pair matching; second, it produces a triple matching. Examining the data, we find that the acquired matching produces excellent triple matching. Upon analysis of the data, we deduce that the optimal level of satisfaction is reached by perfect triple matching. We have demonstrated the rapidness and effectiveness of TPSMA. Thus, the roommate problem’s N-Factor Satisfactory matching with all other extended situations is an outcome of TPSMA.

REFERENCES

[1] Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69(1), 915.

https://doi.org/10.1080/00029890.1962.11989827

[2] Gusfield, D., & Irving, R. W. (1989). The stable marriage problem: Structure and algorithms. MIT Press.

[3] Gusfield, D. (1988). The structure of the stable roommate problem-efficient representation and enumeration of all stable assignments. SIAM Journal on Computing, 17(4), 742769.

https://doi.org/10.1137/0217048

[4] Irving, R. W. (1985). An efficient algorithm for the stable roommates problem. Journal of Algorithms, 6(4), 577595.

https://doi.org/10.1016/0196-6774(85)90033-1

[5] van der Linden, M., Leo, G., Lou, J., Vorobeychik, Y.,

& Wooders, M. H. (2016). Matching soulmates.

[6] Bredereck, R., Heeger, K., Knop, D., & Niedermeier,

R. (2020). Multidimensional stable roommates with master list. In Proceedings of the Wine 2020, 12495 (pp. 5973). Springer. https://doi.org/10.1007/978-3- 030-64946-3_5

[7] McKay, M., & Manlove, D. (2021). The three- dimensional stable roommates problem with additively separable preferences. In International Symposium on Algorithmic Game Theory (pp. 266280). Springer International Publishing.

[8] Park, S. (2024). Stable marriage with one-sided preference. arXiv preprint arXiv:2401.03231.

[9] Atef Yekta, H., Bergman, D., & Day, R. (2023). Balancing stability and efficiency in team formation as a generalized roommate problem. Naval Research Logistics (NRL), 70(1), 7288.

https://doi.org/10.1002/nav.22084

[10] Kamiyama, N. (2024). The strongly stable matching problem with closures. arXiv preprint arXiv:2401.02666.

[11] Iwama, K., Miyazaki, S., & Okamoto, K. (2007). Stable roommates problem with triple rooms. In 10th Korea- Japan Joint Workshop on Algorithms and Computation (pp. 105112).

[12] Ramachandran, T., Velusamy, K., & Selvakumar, T. (2011). Satisfactory roommates problem. International Journal of Mathematical Archives, 2(9), 16791682.

[13] Logapriya, N., & Ramachandran, T. (2023). Three persons satisfactory roommates problem. Gradiva Review Journal, ISSN, 0363(8257), 9(8).

[14] Logapriya, N., & Ramachandran, T. (2023). Three persons satisfactory roommates problem with incomplete list. Communications on Applied Nonlinear Analysis, 30(4), 5866.

[15] Ramachandran, T., & Selvakumar, T. (2014). N-factor Satisfactory Roommates problem. In Proceedings of the International Conference on Mathematical Sciences, 1 (pp. 116118).

[16] Ramachandran, T., Udayakumar, D., & Selvakumar, T. (2015). Variants of N Factor satisfactory roommates problem. International Journal of Engineering Research and Technology (IJERT), 04(01).