Varients of Weighted N-Factor Marriage Problem using SMA

Varients of Weighted N-Factor 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

1. 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 N-factors 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).

   1. 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 one-one 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].

      Factor-F1				Factor-F2				Factor-F3
      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 N-factors, 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.

   2. 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.

   3. 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.

   4. 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%.

   5. CONCLUSION

In this study, N-Factor 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 N-Factors. 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

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

2. 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 1-5, 2005. Proceedings.

3. R.W. Irving, Man-Exchange Stable Marriage, University of Glasgow, Computing Science Department Research Report, TR-2004-177, August 2004.

4. 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(1-3): (2002), pp167-181.

5. T.Ramachandran, K.Velusamy and T.Selvakumar.Satisfactory Marriage Problem. International journal of Computational Science and Mathematics.Vol.4,2012,no.1,23-27.

   m

   2 60 10 15

   m 19 1 2

   3 60 4 5

6. T.Ramachandran and K.Velusamy. N-Factor Marriage Problem Using SMA. Proceedings of the International Conference on Mathematical Methods and Computation ,Jamal Mohamed College(Autonomous), Tiruchirappalli, India, 13-14 February 2014

7. T.Ramachandran and K.Velusamy, Weighted N-Factor Marriage Problem Using SMA, Volume(3) December 2014 .