Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching

Mircea-Adrian Digulescu

doi:doi:10.11648/j.ajcst.20220502.24

| Peer-Reviewed

Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching

Mircea-Adrian Digulescu

Published in American Journal of Computer Science and Technology (Volume 5, Issue 2)

Received: 10 April 2022 Accepted: 26 April 2022 Published: 24 May 2022

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The Stable Marriage Problem, as proposed by Gale and Shapley, considers producing a bipartite matching between two equally sized sets of boys (proposers) and respectively girls (acceptors), each member having a total preference order over the other set, such that the outcome is stable. This paper considers the Game directly induced by this problem and analyze the case when proposers collude. A linear time method for determining the unique optimal collusion matching which is farsightedly stable (liner in the number of bits of the input), under the following assumptions: (i) the sole utility in the Game is the rank of the match in own preference list (in particular, proposers are indifferent as to how other proposers fare); (ii) proposers make proposals iff farsightedly such plays would strictly improve their own outcome (thus proposers cooperate by refraining from making proposals which can only harm others, but not strictly help them; also, they cannot make concessions to others which harm themselves). It is proved that this optimal outcome is actually stronger than a Strong Nash Equilibrium - no alternative feasible (realistic, rational) coalition exists which can offer at least one member a strictly better outcome under these assumptions. This paper also shows why some prior results pertaining to collusion of proposers do not always yield a realistic outcome.

Published in	American Journal of Computer Science and Technology (Volume 5, Issue 2)
DOI	10.11648/j.ajcst.20220502.24
Page(s)	122-133
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Stable Marriage, Farsighted Stability, Gale-Shapley, Collusion, Strategic Play

References

[1]	D. Gale, L. S. Shapley, College Admissions and the Stability of Marriage, The American Mathematical Monthly, 69, 1 (1962), pp. 9-15.
[2]	R. W. Irving, Stable marriage and indifference, Discrete Applied Mathematics, 48, 3, (1994), pp. 261-272.
[3]	L. E. Dubins and D. A. Freedman, Machiavelli and the Gale-Shapley Algorithm, The American Mathematical Monthly, Vol. 88, No. 7 (Aug. - Sep., 1981), pp. 485-494 Published by: Mathematical Association of America DOI: 10.2307/2321753 Stable URL: http://www.jstor.org/stable/2321753
[4]	David Gale and Marilda Sotomayor, Ms. Machiavelli and the Stable Matching Problem, The American Mathematical Monthly, Vol. 92, No. 4 (Apr., 1985), pp. 261-268 Published by: Mathematical Association of America DOI: 10.2307/2323645 Stable URL: http://www.jstor.org/stable/2323645
[5]	Nicole Immorlica, Mohammad Mahdian, Marriage, honesty, and stability, SODA 2005 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Pages 53-62 ISBN: 0-89871-585-7.
[6]	Alvin E Roth, Misrepresentation and stability in the marriage problem, Journal of Economic Theory, Volume 34, Issue 2, December 1984, Pages 383-387.
[7]	David F Manlove, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita, Hard variants of stable marriage, Theoretical Computer Science, Volume 276, Issues 1- 2, 6 April 2002, Pages 261-279 doi: 10.1016/S0304- 3975(01)00206-7.
[8]	Alvin E Roth, The college admissions problem is not equivalent to the marriage problem, Journal of Economic Theory Volume 36, Issue 2, August 1985, Pages 277-288.
[9]	Chung-Piaw Teo, Jay Sethuraman, Wee-Peng Tan, Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Permalink, Permalink: http://dx.doi.org/10.1287/mnsc.47.9.1252.9784, Received: January 1, 1999, Published Online: September 1, 2001, Page Range: 1252-1267.
[10]	Chien-Chung Huang, Cheating by Men in the Gale- Shapley Stable Matching Algorithm, Algorithms ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, pp 418-431, DOI 10.100711841036 39, Print ISBN 978-3- 540-38875-3.
[11]	David J. Abraham, Katarina Cechl´ arov´ a, David F. Manlove, Kurt Mehlhorn, Pareto Optimality in House Allocation Problems, Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005. Proceedings DOI 10.100711602613 115 Print ISBN 978-3-540-30935-2.
[12]	Kazuo Iwama, Shuichi Miyazaki, A Survey of the Stable Marriage Problem and Its Variants, Informatics Education and Research for Knowledge-Circulating Society, 2008. ICKS 2008. International Conference on, Publisher: IEEE DOI: 10.1109/ICKS.2008.7 Print ISBN: 978-0-7695-3128-1.
[13]	Rahul Jain, Designing a strategic bipartite matching market, Decision and Control, 2007 46th IEEE Conference on Publisher: IEEE DOI: 10.1109/CDC.2007.4434797 Print ISSN: 0191-2216
[14]	Yunan Gu, Yanru Zhang, Miao Pan, Zhu Han, Matching and Cheating in Device to Device Communications Underlying Cellular Networks IEEE Journal on Selected Areas in Communications (Volume: 33, Issue: 10, Oct. 2015), DOI: 10.1109/JSAC.2015.2435361 Print ISSN: 0733-8716.
[15]	Klaus, Bettina-Elisabeth and Klijn, Flip and Walzl, Markus, Farsighted Stability for Roommate Markets (May 26, 2009), Harvard Business School, NOM Unit Working Paper No. 09-135, Available at SSRN: https://ssrn.com/abstract=1410230 or http://dx.doi.org/10.2139/ssrn.1410230
[16]	Y Deng, W Shen, P Tang, Coalition manipulations of the gale-shapley algorithm arXiv preprint arXiv: 1502.07823, 2015 - arxiv.org.
[17]	Sinan Aksoy, Adam Azzam, Chaya Coppersmith, Julie Glass, Gizem Karaali, Xueying Zhao and Xinjing Zhu, Coalitions and cliques in the school choice problem INVOLVE 8: 5 (2015) dx.doi.org/10.2140/involve.2015.8.801.
[18]	Mircea Digulescu - Strategic Play in Stable Marriage Problem, arXiv arXiv (2016) https://arxiv.org/abs/1608.07575, DOI: 10.13140/RG.2.2.20331.75041.
[19]	Wako, J. Algorithmica (2010) 58: 188. https://doi.org/10.1007/s00453-010-9388-y

Cite This Article

Plain Text BibTeX RIS

APA Style

Mircea-Adrian Digulescu. (2022). Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching. American Journal of Computer Science and Technology, 5(2), 122-133. https://doi.org/10.11648/j.ajcst.20220502.24

Copy | Download

ACS Style

Mircea-Adrian Digulescu. Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching. Am. J. Comput. Sci. Technol. 2022, 5(2), 122-133. doi: 10.11648/j.ajcst.20220502.24

Copy | Download

AMA Style

Mircea-Adrian Digulescu. Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching. Am J Comput Sci Technol. 2022;5(2):122-133. doi: 10.11648/j.ajcst.20220502.24

Copy | Download

@article{10.11648/j.ajcst.20220502.24,
  author = {Mircea-Adrian Digulescu},
  title = {Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching},
  journal = {American Journal of Computer Science and Technology},
  volume = {5},
  number = {2},
  pages = {122-133},
  doi = {10.11648/j.ajcst.20220502.24},
  url = {https://doi.org/10.11648/j.ajcst.20220502.24},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajcst.20220502.24},
  abstract = {The Stable Marriage Problem, as proposed by Gale and Shapley, considers producing a bipartite matching between two equally sized sets of boys (proposers) and respectively girls (acceptors), each member having a total preference order over the other set, such that the outcome is stable. This paper considers the Game directly induced by this problem and analyze the case when proposers collude. A linear time method for determining the unique optimal collusion matching which is farsightedly stable (liner in the number of bits of the input), under the following assumptions: (i) the sole utility in the Game is the rank of the match in own preference list (in particular, proposers are indifferent as to how other proposers fare); (ii) proposers make proposals iff farsightedly such plays would strictly improve their own outcome (thus proposers cooperate by refraining from making proposals which can only harm others, but not strictly help them; also, they cannot make concessions to others which harm themselves). It is proved that this optimal outcome is actually stronger than a Strong Nash Equilibrium - no alternative feasible (realistic, rational) coalition exists which can offer at least one member a strictly better outcome under these assumptions. This paper also shows why some prior results pertaining to collusion of proposers do not always yield a realistic outcome.},
 year = {2022}
}

Copy | Download

TY  - JOUR
T1  - Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching
AU  - Mircea-Adrian Digulescu
Y1  - 2022/05/24
PY  - 2022
N1  - https://doi.org/10.11648/j.ajcst.20220502.24
DO  - 10.11648/j.ajcst.20220502.24
T2  - American Journal of Computer Science and Technology
JF  - American Journal of Computer Science and Technology
JO  - American Journal of Computer Science and Technology
SP  - 122
EP  - 133
PB  - Science Publishing Group
SN  - 2640-012X
UR  - https://doi.org/10.11648/j.ajcst.20220502.24
AB  - The Stable Marriage Problem, as proposed by Gale and Shapley, considers producing a bipartite matching between two equally sized sets of boys (proposers) and respectively girls (acceptors), each member having a total preference order over the other set, such that the outcome is stable. This paper considers the Game directly induced by this problem and analyze the case when proposers collude. A linear time method for determining the unique optimal collusion matching which is farsightedly stable (liner in the number of bits of the input), under the following assumptions: (i) the sole utility in the Game is the rank of the match in own preference list (in particular, proposers are indifferent as to how other proposers fare); (ii) proposers make proposals iff farsightedly such plays would strictly improve their own outcome (thus proposers cooperate by refraining from making proposals which can only harm others, but not strictly help them; also, they cannot make concessions to others which harm themselves). It is proved that this optimal outcome is actually stronger than a Strong Nash Equilibrium - no alternative feasible (realistic, rational) coalition exists which can offer at least one member a strictly better outcome under these assumptions. This paper also shows why some prior results pertaining to collusion of proposers do not always yield a realistic outcome.
VL  - 5
IS  - 2
ER  -

Copy | Download

Author Information

Mircea-Adrian Digulescu

Computer Science Department, Faculty of Mathematics and Computer Science, University of Bucharest, Bucharest, Romania

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Mircea-Adrian Digulescu. (2022). Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching. American Journal of Computer Science and Technology, 5(2), 122-133. https://doi.org/10.11648/j.ajcst.20220502.24

Copy | Download

ACS Style

Mircea-Adrian Digulescu. Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching. Am. J. Comput. Sci. Technol. 2022, 5(2), 122-133. doi: 10.11648/j.ajcst.20220502.24

Copy | Download

AMA Style

Mircea-Adrian Digulescu. Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching. Am J Comput Sci Technol. 2022;5(2):122-133. doi: 10.11648/j.ajcst.20220502.24

Copy | Download

@article{10.11648/j.ajcst.20220502.24,
  author = {Mircea-Adrian Digulescu},
  title = {Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching},
  journal = {American Journal of Computer Science and Technology},
  volume = {5},
  number = {2},
  pages = {122-133},
  doi = {10.11648/j.ajcst.20220502.24},
  url = {https://doi.org/10.11648/j.ajcst.20220502.24},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajcst.20220502.24},
  abstract = {The Stable Marriage Problem, as proposed by Gale and Shapley, considers producing a bipartite matching between two equally sized sets of boys (proposers) and respectively girls (acceptors), each member having a total preference order over the other set, such that the outcome is stable. This paper considers the Game directly induced by this problem and analyze the case when proposers collude. A linear time method for determining the unique optimal collusion matching which is farsightedly stable (liner in the number of bits of the input), under the following assumptions: (i) the sole utility in the Game is the rank of the match in own preference list (in particular, proposers are indifferent as to how other proposers fare); (ii) proposers make proposals iff farsightedly such plays would strictly improve their own outcome (thus proposers cooperate by refraining from making proposals which can only harm others, but not strictly help them; also, they cannot make concessions to others which harm themselves). It is proved that this optimal outcome is actually stronger than a Strong Nash Equilibrium - no alternative feasible (realistic, rational) coalition exists which can offer at least one member a strictly better outcome under these assumptions. This paper also shows why some prior results pertaining to collusion of proposers do not always yield a realistic outcome.},
 year = {2022}
}

Copy | Download

TY  - JOUR
T1  - Farsighted Collusion in Stable Marriage Problem, with No Self-Harmful Plays: Efficient Algorithm for Determining the Unique Man-Optimal Matching
AU  - Mircea-Adrian Digulescu
Y1  - 2022/05/24
PY  - 2022
N1  - https://doi.org/10.11648/j.ajcst.20220502.24
DO  - 10.11648/j.ajcst.20220502.24
T2  - American Journal of Computer Science and Technology
JF  - American Journal of Computer Science and Technology
JO  - American Journal of Computer Science and Technology
SP  - 122
EP  - 133
PB  - Science Publishing Group
SN  - 2640-012X
UR  - https://doi.org/10.11648/j.ajcst.20220502.24
AB  - The Stable Marriage Problem, as proposed by Gale and Shapley, considers producing a bipartite matching between two equally sized sets of boys (proposers) and respectively girls (acceptors), each member having a total preference order over the other set, such that the outcome is stable. This paper considers the Game directly induced by this problem and analyze the case when proposers collude. A linear time method for determining the unique optimal collusion matching which is farsightedly stable (liner in the number of bits of the input), under the following assumptions: (i) the sole utility in the Game is the rank of the match in own preference list (in particular, proposers are indifferent as to how other proposers fare); (ii) proposers make proposals iff farsightedly such plays would strictly improve their own outcome (thus proposers cooperate by refraining from making proposals which can only harm others, but not strictly help them; also, they cannot make concessions to others which harm themselves). It is proved that this optimal outcome is actually stronger than a Strong Nash Equilibrium - no alternative feasible (realistic, rational) coalition exists which can offer at least one member a strictly better outcome under these assumptions. This paper also shows why some prior results pertaining to collusion of proposers do not always yield a realistic outcome.
VL  - 5
IS  - 2
ER  -

Copy | Download