Matchings under Stability, Minimum Regret, and Forced and Forbidden Pairs in Marriage Problem

Mandal, Pinaki and Roy, Souvik (2021): Matchings under Stability, Minimum Regret, and Forced and Forbidden Pairs in Marriage Problem.

Abstract

We provide a class of algorithms, called men-women proposing deferred acceptance (MWPDA) algorithms, that can produce all stable matchings at every preference profile for the marriage problem. Next, we provide an algorithm that produces a minimum regret stable matching at every preference profile. We also show that its outcome is always women-optimal in the set of all minimum regret stable matchings. Finally, we provide an algorithm that produces a stable matching with given sets of forced and forbidden pairs at every preference profile, whenever such a matching exists. As before, here too we show that the outcome of the said algorithm is women-optimal in the set of all stable matchings with given sets of forced and forbidden pairs.

• Item Type: MPRA Paper
• Language: English
• Keywords: Two-sided matching; Marriage problem; Pairwise stability; Stability; Minimum regret; Forced and forbidden pairs
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory

References

[1] Atila Abdulkadiroglu and Tayfun Sonmez. Matching markets: Theory and practice. Advances in Economics and Econometrics, 1:3–47, 2013.

[2] Vania MF Dias, Guilherme D Da Fonseca, Celina MH De Figueiredo, and Jayme L Szwarcfiter. The stable marriage problem with restricted pairs. Theoretical Computer Science, 306(1-3):391–405, 2003.

[3] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962.

[4] David Gale and Marilda Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11(3):223–232, 1985.

[5] Dan Gusfield. Three fast algorithms for four problems in stable marriage. SIAM Journal on Computing, 16(1):111–128, 1987.

[6] Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989.

[7] Robert W Irving and Paul Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15(3):655–667, 1986.

[8] Alexander S Kelso Jr and Vincent P Crawford. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, pages 1483–1504, 1982.

[9] Donald E Knuth. Mariages stables et leurs relations avec dautres problemes combinatoires. English translation in "Stable marriage and its relation to other combinatorial problems", Volume 10 of CRM Proceedings and Lecture Notes, American Mathematical Society, 1997. Les Presses de lUniversite de Montreal, 1976.

[10] Ruth Martınez, Jordi Masso, Alejandro Neme, and Jorge Oviedo. An algorithm to compute the full set of many-to-many stable matchings. Mathematical Social Sciences, 47(2):187–210, 2004.

[11] David G McVitie and Leslie B Wilson. The stable marriage problem. Communications of the ACM, 14 (7):486–490, 1971.

[12] DG McVitie and Leslie B Wilson. Stable marriage assignment for unequal sets. BIT Numerical Mathematics, 10(3):295–309, 1970.

[13] Alvin E Roth. The college admissions problem is not equivalent to the marriage problem. Journal of economic Theory, 36(2):277–288, 1985.

[14] Alvin E Roth and Marilda Sotomayor. The college admissions problem revisited. Econometrica: Journal of the Econometric Society, pages 559–570, 1989.

[15] Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485–541, 1992.