Abstract
We study the problem of finding maximum weakly stable matchings when preference lists are incomplete and contain one-sided ties of bounded length. We show that if the tie length is at most L, then it is possible to achieve an approximation ratio of \(1 + (1 - \frac{1}{L})^L\). We also show that the same ratio is an upper bound on the integrality gap, which matches the known lower bound. In the case where the tie length is at most 2, our result implies an approximation ratio and integrality gap of \(\frac{5}{4}\), which matches the known UG-hardness result.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Some of the literature on stable matching with indifferences does not allow an agent to be indifferent between being matched to an agent and being unmatched. Our formulation of the smoti problem allows for this possibility, since we can have \(i=_j0\) for any man i and woman j.
References
Bauckholt, F., Pashkovich, K., Sanità, L.: On the approximability of the stable marriage problem with one-sided ties (2018). arXiv:1805.05391
Chiang, R., Pashkovich, K.: On the approximability of the stable matching problem with ties of size two (2019). arXiv:1808.04510
Dean, B.C., Jalasutram, R.: Factor revealing LPs and stable matching with ties and incomplete lists. In: Proceedings of the 3rd International Workshop on Matching Under Preferences, pp. 42–53 (2015)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9–15 (1962)
Gale, D., Sotomayor, M.A.O.: Some remarks on the stable matching problem. Discrete Appl. Math. 11(3), 223–232 (1985)
Halldórsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Randomized approximation of the stable marriage problem. Theoret. Comput. Sci. 325(3), 439–465 (2004)
Halldórsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation results for the stable marriage problem. ACM Trans. Algorithms 3(3), 30 (2007)
Huang, C.C., Kavitha, T.: Improved approximation algorithms for two variants of the stable marriage problem with ties. Math. Program. 154(1), 353–380 (2015)
Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48(3), 261–272 (1994)
Iwama, K., Miyazaki, S., Yanagisawa, H.: A 25/17-approximation algorithm for the stable marriage problem with one-sided ties. Algorithmica 68(3), 758–775 (2014)
Király, Z.: Linear time local approximation algorithm for maximum stable marriage. Algorithms 6(3), 471–484 (2013)
Lam, C.K., Plaxton, C.G.: A \((1 + 1/e)\)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2823–2840 (2019)
Lam, C.K., Plaxton, C.G.: Maximum stable matching with one-sided ties of bounded length. Technical report TR-19-03, Department of Computer Science, University of Texas at Austin, July 2019
McDermid, E.: A 3/2-approximation algorithm for general stable marriage. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 689–700. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02927-1_57
Paluch, K.: Faster and simpler approximation of stable matchings. Algorithms 7(2), 189–202 (2014)
Radnai, A.: Approximation algorithms for the stable marriage problem. Master’s thesis, Department of Computer Science, Eötvös Loránd University (2014)
Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991–1016 (1984)
Rothblum, U.G.: Characterization of stable matchings as extreme points of a polytope. Math. Program. 54(1), 57–67 (1992)
Vande Vate, J.H.: Linear programming brings marital bliss. Oper. Res. Lett. 8(3), 147–153 (1989)
Yanagisawa, H.: Approximation algorithms for stable marriage problems. Ph.D. thesis, Graduate School of Informatics, Kyoto University (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Lam, CK., Plaxton, C.G. (2019). Maximum Stable Matching with One-Sided Ties of Bounded Length. In: Fotakis, D., Markakis, E. (eds) Algorithmic Game Theory. SAGT 2019. Lecture Notes in Computer Science(), vol 11801. Springer, Cham. https://doi.org/10.1007/978-3-030-30473-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-30473-7_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30472-0
Online ISBN: 978-3-030-30473-7
eBook Packages: Computer ScienceComputer Science (R0)