## Aniket Bhatnagar* , Varun Gambhir* and Manish Kumar Thakur*## |

Algorithm | Count of man (m), woman (n) | | MAWM | [TeX:] $$\begin{array} { l } { \operatorname { Mean } \pm \left( \sqrt { \sigma ^ { 2 } / p } \right) } \\ { \text { for } p = 10 \text { runs } } \end{array}$$ | |

| [TeX:] $$\begin{array} { l } { \operatorname { Mean } \pm \left( \sqrt { \sigma ^ { 2 } / p } \right) } \\ { \text { for } p = 10 \text { runs } } \end{array}$$ | ||||

1 (m=n) | 1000, 1000 | NA | NA | 43.64 | NA |

2.1 (m=n) | 1000, 1000 | 43.07 | 42.62±0.31 | 62.73 | 62.45±0.38 |

2.2 (when m>n) | 1000, 800 | 41.54 | 41.10±0.49 | 63.85 | 63.15±0.43 |

2.2 (when m<n) | 800, 1000 | 42.25 | 41.13±0.84 | 68.32 | 67.91±0.28 |

3.1 (m=n) | 1000, 1000 | 70.70 | 70.23±0.28 | 72.93 | 72.81±0.10 |

3.2 (when m>n) | 1000, 800 | 71.12 | 70.97±0.11 | 73.66 | 73.38±0.19 |

3.2 (when m<n) | 800, 1000 | 73.41 | 73.32±0.10 | 79.81 | 79.55±0.18 |

Gale-Shapley (m=n) | 1000, 1000 | NA | NA | 35.58 | NA |

Each GA based algorithm had been run ten times (i.e., p=10) and each run involved 10000 iterations, i.e., K=10000.

FS=fitness score, NA=not applicable.

Further, these preference lists (preferences of 1000 men for 1000 women and vice versa) were given as inputs to the Gale-Shapley algorithm. The Gale-Shapley algorithm too successfully identified the unique pairing of each man with a woman. The *weighted matchings* against these pairs had been averaged out to compute the MAWM. The achieved MAWM by Gale-Shapley algorithm was 35.58.

Table 1 consolidates the MAWM achieved by the algorithms presented in this paper including the Gale-Shapley algorithm. As seen in Table 1, out of the four algorithms (including Gale and Shapley) applicable for the scenario, where m=n, Algorithm 3.1 (i.e*.* GA based approach with a guided population) had shown the best performance to maximize the profit of matrimonial websites in terms of achieved MAWM. One of the reasons behind this might be the guided chromosome in the initial population which ensured that the global/final fitness score of a chromosome is never less than the fitness score of the guided chromosome. Further, as seen from the Table 1, variations (standard deviation) in the achieved MAWM is negligible for all the 10 runs of each of the GA based algorithm, where m=n.

Similarly, as seen in Table 1, Algorithm 3.2 performed better than Algorithm 2.2 under the scenario, where m<n. Both algorithms utilized the capability of GA, however, the reason behind the better performance of Algorithm 3.2 might be the guided chromosome in the initial population. Finally, the same reason might be applicable for the better performance of Algorithm 3.2 than Algorithm 2.2 for the scenario, where m>n. Further, 10 runs of these algorithms had shown little variations (standard deviations) in the achieved MAWM.

In each of the conducted experiment for Algorithm 2 (randomly generated chromosomes), significant improvement has been observed in the fitness scores of the initially selected chromosome and the best chromosome after 10000 iterations of an experiment. Mean of the 10 fitness scores of the initially selected chromosomes corresponding to the 10 experiments conducted for Algorithm 2.1 is 42.62±0.31. This mean is improved significantly to 62.45±0.38 for the best chromosome after 10000 iterations of each experiment. It is evident from Table 1 that significant improvement has been observed for Algorithm 2.2 (when, m>n) and Algorithm 2.2 (when, m<n). Further, mean of the 10 fitness scores of the guided chromosomes corresponding to the 10 experiments conducted for Algorithm 3.1 is 70.23±0.28. This mean is improved significantly to 72.81±0.1 for the best chromosome after 10000 iterations of each experiment. Similar improvements have been observed in the experiments conducted for Algorithm 3.2 (when, m>n) and Algorithm 3.2 (when, m<n).

In this paper we presented a new perspective to SMP in profit maximization of matrimonial websites. Instead of qualitative preference list, we defined the quantitative/weighted preferences computed using profile (personal details) and expectations (in partner of opposite gender) of the users registered on matrimonial websites. The objective of all the algorithms presented in this paper was to make such pairs/matching of men and women which maximizes the profit (in terms of MAWM) of matrimonial websites. Greedy and Genetic algorithm based algorithms have been proposed in this paper to solve the problem in different scenarios, *viz.* (a) m (count of men) =n (count of women); (b) m>n; and (c) m<n. As discussed in Section 4, the set of algorithms (Algorithm 3) outperformed other algorithms *(viz.* Greedy based, and GA based where chromosomes are randomly generated) including Gale-Shapley algorithm under the scenario where, m=n.

As the future extension, the new perspective presented in this paper may also be applied to some other applications of bipartite matching viz. student project allocation, hospital resident problem, etc*.* As discussed in Section 4, another extension of current work is to train/tune the weights associated with the features for further observations.

- 1 D. Gale, "The two-sided matching problem: origin, development and current issues,"
*International Game Theory Review, 2001*, vol. 3, no. 2-3, pp. 237-252. doi:[[[10.1142/S0219198901000373]]] - 2 D. F. Manlove, G. O'Malley, "Student-project allocation with preferences over projects,"
*Journal of Discrete Algorithms, 2008*, vol. 6, no. 4, pp. 553-560. doi:[[[10.1016/j.jda.2008.07.003]]] - 3 J. Wu, "Stable matching beyond bipartite graphs," in
*Proceedings of 2016 IEEE International Parallel and Distributed Processing Symposium Workshops*, Chicago, IL, 2016;pp. 480-488. doi:[[[10.1109/IPDPSW.2016.207]]] - 4 D. Gale, L. S. Shapley, "College admissions and the stability of marriage,"
*The American Mathematical Monthly, 1962*, vol. 69, no. 1, pp. 9-15. doi:[[[10.1515/9781400865307-024]]] - 5 D. G. McVitie, L. B. Wilson, "The stable marriage problem,"
*Communications of the ACM, 1971*, vol. 14, no. 7, pp. 486-490. doi:[[[10.1145/362619.362631]]] - 6 R. W . Irving, P . Leather, D. Gusfield, "An efficient algorithm for the "optimal" stable marriage,"
*Journal of the ACM, 1987*, vol. 34, no. 3, pp. 532-543. doi:[[[10.1145/28869.28871]]] - 7 I. Damianidis, Master’ s thesis, University of BorasSweden, 2011.custom:[[[-]]]
- 8 K. Iwama, S. Miyazaki, "A survey of the stable marriage problem and its variants," in
*Proceedings of International Conference on Informatics Education and Research for Knowledge-Circulating Society*, Kyoto, Japan, 2008;pp. 131-136. doi:[[[10.1109/ICKS.2008.7]]] - 9
*M. S. Pini, F. Rossi, B. Venable, and T. Walsh, "Stable marriage problems with quantitative preferencesm" 2010 (Online). Available:*, https://arxiv.org/abs/1007.5120 - 10 M. Baıou, M. Balinski, "Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry),"
*Discrete Applied Mathematics, 2000*, vol. 101, no. 1-3, pp. 1-12. doi:[[[10.1016/s0166-218x(99)00203-6]]] - 11 I. Bello, S. Lianshuan, "Genetic algorithm for the stable marriage problem (SMP),"
*International Journal of Science and Research, 2016*, vol. 5, no. 6, pp. 939-944. doi:[[[10.21275/v5i3.nov161892]]] - 12 M. S. Pini, F. Rossi, K. B. Venable, T. Walsh, "Stability, optimality and manipulation in matching problems with weighted preferences,"
*Algorithms, 2013*, vol. 6, no. 4, pp. 782-804. doi:[[[10.3390/a6040782]]] - 13
*Membership option of BharatMatrimony (Online). Available:*, http://www.bharatmatrimony.com/payments/paymentoptions.php - 14 A. L. Corcoran, R. L. Wainwright, Practical Handbook of Genetic Algorithms. Boca Laton, FL: CRC Press, pp. 143-172, 1995.custom:[[[-]]]
- 15 A. Banks, J. Vincent, C. Anyakoha, "A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications,"
*Natural Computing, 2008*, vol. 7, no. 1, pp. 109-124. doi:[[[10.1007/s11047-007-9050-z]]] - 16
*Category:Stable sorts (Online). Available:*, https://en.wikipedia.org/wiki/Category:Stable_sorts

He was one of the undergraduate students at Jaypee Institute of Information Technology, Noida, India and completed his under-graduation (B.Tech. in Computer Science Engineering) in 2017. His research interest includes the evolutionary algorithms, combinatorial optimization problems, and machine learning. He actively participates in several online/onsite competitive programming challenges and secured good ranks.

He completed his B.Tech. in Computer Science Engineering from Jaypee Institute of Information Technology, Noida, India in 2017. His research interest includes the machine learning and evolutionary algorithms for combinatorial optimization problems. Besides academics he is actively involved in various online/onsite competitive programming challenges as participant and secured good ranks.

He is currently working as Assistant Professor (Senior Grade) in the Department of CSE at Jaypee Institute of Information Technology (JIIT), Noida. He completed his Ph.D. in 2014 from JIIT, Noida and his M.Tech in Computer Science from Birla Institute of Technology, Mesra, Ranchi, India. His research interest includes, evolutionary algorithms, graph algorithms, parallel and distributed computing, video processing, and machine learning.