 Open Access
 Total Downloads : 168
 Authors : Dr. T. Ramachandran , Dr. D. Udayakumar, K. Velusamy
 Paper ID : IJERTV4IS020092
 Volume & Issue : Volume 04, Issue 02 (February 2015)
 Published (First Online): 04022015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Varients of Weighted NFactor Marriage Problem using SMA
Dr. T. Ramachandran Department of Mathematics, M.V.Muthiah Government Arts College for Women, Dindigul, Tamilnadu, – 624001
Dr. D. Udayakumar Department of Mathematics, Government Arts College, Karur Tamilnadu, 639005

Velusamy
Department of Mathematics, Chettinad College of Engineering & Technology,
Karur, Tamilnadu, 639114
Abstract This paper deals with the Marriage problem which was introduced by Gale and Shapley. GS algorithm was used to find solution for it. To solve a Marriage problem, only one factor has been used assuming that the preference list is based on a single factor. In this study, the researcher has introduced Nfactors with weightage (i.e. Dowry, Height, Weight, Colour and so on) in Marriage problem and Satisfactory Matching Algorithm has been applied to find solution for the marriage problem. The findings were discussed and illustrated with real life examples.
Keywords Preference Value, Mens Preference value Matrix (PMM), Womens Preference value Matrix (PMW), Satisfactory value Matrix (SMM/W), Satisfactory level, SMA algorithm, Assignment Technique (Hungarian).

INTRODUCTION
An instance I of the classical Stable Marriage problem(SM)[1] involves n men and n women, each of whom ranks all the members of the opposite sex in strict order of preference[2].A matching M in I is a oneone correspondence between the men and women. A (man, woman)pair(m,w) blocks M,or is a blocking pair with respect to M,if m prefers w to pW (m), and w prefers m to pM(w),where pM(q) denotes the partner of q in M.A matching that admits no blocking pair is said to be stable. It is known that every instance of SM admits at least one stable matching, and that such a matching can be found in O(n2) time using the Gale/Shapley algorithm[3,4].
FactorF1
FactorF2
FactorF3
m1
50%
w1
25%
m1
30%
w1
50%
m1
20%
w1
25%
m2
40%
w2
50%
m2
25%
w2
30%
m2
35%
w2
20%
m3
30%
w3
75%
m3
35%
w3
10%
m3
35%
w3
15%
A Satisfactory Marriage problem was solved in [5] by considering one factor in the preference lists. A Marriage problem, by considering Nfactors, was solved in [6].The weightage to the factors in preference lists of Marriage problem was solved in [7].In this problem, all members of set m and w consider a particular factor for equal proportion. But in real life situation, each member of set considers a factor for different proportion. In this paper, a solution to a marriage problem where each member considers each factor for different proportion has been discussed.

OBJECTIVE
The main objective of the study is to find out a satisfactory matching of a Marriage problem where each member of men and women considers each factor (in N factor) for different weightage.

NEED FOR THE STUDY
In real life there are many matching problems. Marriage matching has been chosen for the study as it will be apt to explain the situation. Marriage problems discussed earlier have stated that the solutions found were at times, it is men favorable or women favorable solutions. But, in the recent study, the researcher has narrated a best possible solution for both men and women. In that problem, more than one factor is considered in preference list and also weightage to each factor. But in real life situation, each member of set considers a factor for different proportion. This situation made the researcher to find solution to such problems.

PROBLEM FORMULATION
A Marriage problem consists of two sets i.e. men & women of size n. The n man considers a factor for more than one proportion in the preference lists. Similarly n woman considers a factor for more than one proportion in the preference lists. From the preference list, preference value matrix is found by considering the weightage of the factor for each member. To this matrix, SMA (Hungarian algorithm) was applied and matching was found.
The Related terminologies, Preference value, Mens and Womens Preference value, Mens Preference Value Matrix (PMM), Womens Preference Value Matrix (PMW), Satisfactory Value Matrix (SMM/W), Satisfactory level, Hungarian method of Assignment model and SMA algorithm are discussed in [5].
Example 1: Consider an instance with three men m1 , m2 , m3 and three women w1 , w2 , w3 and with three factors F1,F2,F3.The members of set of men and women consider each factor for different proportion which are given below.
The preference lists for three factors are given below in the order of preference.
Preference list based on Factor F
The resultant Satisfactory Value Matrix is
w1
3
w2
5
w3
13
2
3
10
17
71
4
12
60
3
73
73
7
60
60
6
m1
SMM(R) =
m2
m
m : w w w
1 3
w : m m m
1 2 3 1 1 1 2 3
m2: w1 w2 w3 w2: m1 m3 m2
m3: w2 w1 w3 w3: m2 m1 m3 Preference list based on Factor F2
m1: w1 w3 w2 w1: m3 m1 m2
m2: w2 w1 w3 w2: m1 m2 m3
m3: w3 w2 w1 w3: m2 m3 m1 Preference list based on Factor F3
m1: w1 w3 w2 w1: m1 m2 m3
m2: w1 w2 w3 w2: m1 m3 m2
m3: w3 w1 w2 w3: m2 m1 m3
The Satisfactory Value Matrix for Factor F1 with weightage is
w1 w2 w3
m
1
5 5
12
6
17
13
53
30
30
60
17
19
7
60
30
20
1
SMM(F1) =
m2
m3
w
w
w
m 19
2
7
1
30
5
30
SMM(F2)
=
1
9
11
3
20
60
37
1
5
60
3
12
The Satisfactory Value Matri for Factor F2 with weightage is
1 2 3
The matching, based on the three Factors with weightage, on applying SMA is (m1, w2), (m2,w1), (m3,w3) and satisfactory value for each pair is given in the following table.
Satisfactory matching
Satisfactory value
Satisfactory level of men
Satisfactory level of women
(m1,w2)
5/3
m1=2/3
w2=3/3
(m2,w1)
17/12
m2=11/12
w1=1/2
(m3,w3)
7/6
m3=4/5
w3=11/30
The matching obtained is the best matching for both the groups and satisfactory level of each group is optimum. The Satisfactory level of men and women are 56.08% and 43.92%.

CONCLUSION

In this study, NFactor Marriage problem with varying weight has been introduced. SMA algorithm helps to find out the matching between men and women for a marriage considering many factors with varying weightage. Each factor was studied with a real life example. It was found that both men and women gain high satisfactory level and gets optimal matching. Assignment technique was used to solve the problems with NFactors. This Technique helps the people to solve matching problems in real life situations and to take absolute decisions in a best possible manner.
REFERENCES
m2
m3
The Satisfactory Value Matrix for Factor F3 with weightage is
w1 w2 w3

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

Ismel Brito and Pedro Meseguer,Distributed Stable Marriage Problem, Principles and Practice of Constraint Programming – CP 2005 11th International Conference, CP 2005, Sitges, Spain, October 15, 2005. Proceedings.

R.W. Irving, ManExchange Stable Marriage, University of Glasgow, Computing Science Department Research Report, TR2004177, August 2004.

D.F. Man love. The structure of stable marriage with indifference.
SMM(F3) =
m 9 4 7
1 20 15 30
31 3 4
Discrete Applied Mathematics, 122(13): (2002), pp167181.

T.Ramachandran, K.Velusamy and T.Selvakumar.Satisfactory Marriage Problem. International journal of Computational Science and Mathematics.Vol.4,2012,no.1,2327.
m
2 60 10 15
m 19 1 2
3 60 4 5

T.Ramachandran and K.Velusamy. NFactor Marriage Problem Using SMA. Proceedings of the International Conference on Mathematical Methods and Computation ,Jamal Mohamed College(Autonomous), Tiruchirappalli, India, 1314 February 2014

T.Ramachandran and K.Velusamy, Weighted NFactor Marriage Problem Using SMA, Volume(3) December 2014 .