| Peer-Reviewed

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

Received: 10 April 2022     Accepted: 26 April 2022     Published: 24 May 2022
Views:       Downloads:
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), 2022. 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
  • 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
  • Computer Science Department, Faculty of Mathematics and Computer Science, University of Bucharest, Bucharest, Romania

  • Sections