Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women
The goal of the stable marriage problem is to match by pair two sets composed by the same number of elements. Due to its widespread applications in the real world, especially the unique importance to the centralized matchmaker, a very large number of questions have been extensively studied in this f...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2018/7409397 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832557071960113152 |
|---|---|
| author | Gui-Yuan Shi Yi-Xiu Kong Bo-Lun Chen Guang-Hui Yuan Rui-Jie Wu |
| author_facet | Gui-Yuan Shi Yi-Xiu Kong Bo-Lun Chen Guang-Hui Yuan Rui-Jie Wu |
| author_sort | Gui-Yuan Shi |
| collection | DOAJ |
| description | The goal of the stable marriage problem is to match by pair two sets composed by the same number of elements. Due to its widespread applications in the real world, especially the unique importance to the centralized matchmaker, a very large number of questions have been extensively studied in this field. This article considers a generalized form of the stable marriage problem, where different numbers of men and women need to be matched pairwise and the emergence of single men or women is inevitable. Theoretical analysis and numerical simulations confirm that even a small deviation on the number of men and women from the equality condition can have a large impact on the matching solution of the Gale-Shapley algorithm. These results provide insights to many of the real-world applications when matching two sides with an unequal number. |
| format | Article |
| id | doaj-art-0986f3372419459d8198e7de53d15077 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-0986f3372419459d8198e7de53d150772025-02-03T05:43:36ZengWileyComplexity1076-27871099-05262018-01-01201810.1155/2018/74093977409397Instability in Stable Marriage Problem: Matching Unequally Numbered Men and WomenGui-Yuan Shi0Yi-Xiu Kong1Bo-Lun Chen2Guang-Hui Yuan3Rui-Jie Wu4Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 233003, ChinaFaculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 233003, ChinaFaculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 233003, ChinaFintech Research Institute, Shanghai University of Finance and Economics, Shanghai 200433, ChinaDepartment of Physics, University of Fribourg, Fribourg 1700, SwitzerlandThe goal of the stable marriage problem is to match by pair two sets composed by the same number of elements. Due to its widespread applications in the real world, especially the unique importance to the centralized matchmaker, a very large number of questions have been extensively studied in this field. This article considers a generalized form of the stable marriage problem, where different numbers of men and women need to be matched pairwise and the emergence of single men or women is inevitable. Theoretical analysis and numerical simulations confirm that even a small deviation on the number of men and women from the equality condition can have a large impact on the matching solution of the Gale-Shapley algorithm. These results provide insights to many of the real-world applications when matching two sides with an unequal number.http://dx.doi.org/10.1155/2018/7409397 |
| spellingShingle | Gui-Yuan Shi Yi-Xiu Kong Bo-Lun Chen Guang-Hui Yuan Rui-Jie Wu Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women Complexity |
| title | Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women |
| title_full | Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women |
| title_fullStr | Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women |
| title_full_unstemmed | Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women |
| title_short | Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women |
| title_sort | instability in stable marriage problem matching unequally numbered men and women |
| url | http://dx.doi.org/10.1155/2018/7409397 |
| work_keys_str_mv | AT guiyuanshi instabilityinstablemarriageproblemmatchingunequallynumberedmenandwomen AT yixiukong instabilityinstablemarriageproblemmatchingunequallynumberedmenandwomen AT bolunchen instabilityinstablemarriageproblemmatchingunequallynumberedmenandwomen AT guanghuiyuan instabilityinstablemarriageproblemmatchingunequallynumberedmenandwomen AT ruijiewu instabilityinstablemarriageproblemmatchingunequallynumberedmenandwomen |