Document Open Access Logo

Stable Matchings with One-Sided Ties and Approximate Popularity

Author Telikepalli Kavitha

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.22.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Telikepalli Kavitha
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

  • Kavitha, Telikepalli: Supported by the Department of Atomic Energy, Government of India, under project no. RTI4001.

Acknowledgements

Thanks to the reviewers for their helpful comments and suggestions.

Cite As Get BibTex

Telikepalli Kavitha. Stable Matchings with One-Sided Ties and Approximate Popularity. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.22

Abstract

We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices in A rank their neighbors in a strict order of preference while vertices in B are allowed to have weak rankings, i.e., ties are allowed in their preferences. Stable matchings always exist in G and are easy to find, however popular matchings need not exist and it is NP-complete to decide if one exists. This motivates the "approximately popular" matching problem. 
A well-known measure of approximate popularity is low unpopularity factor. We show that when each tie in G has length at most k, there always exists a stable matching whose unpopularity factor is at most k. Our proof is algorithmic and we compute such a stable matching in polynomial time. Our result can be considered to be a generalization of Gärdenfors' result (1975) which showed that when rankings are strict, every stable matching is popular. 
There are several applications where the size of the matching is its most important attribute. What one seeks here is a maximum matching M such that there is no maximum matching more popular than M. When rankings are weak, it is NP-hard to decide if G admits such a matching. When ties are one-sided and of length at most k, we show a polynomial time algorithm to find a maximum matching whose unpopularity factor within the set of maximum matchings is at most 2k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Bipartite graphs
  • Maximum matchings
  • Unpopularity factor

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. Bauckholt, K. Pashkovich, and L. Sanitá. On the approximability of the stable marriage problem with one-sided ties. URL: http://arxiv.org/abs/1805.05391.
  2. S. Bhattacharya, M. Hoefer, C.-C. Huang, T. Kavitha, and L. Wagner. Maintaining near-popular matchings. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP)(II), pages 504-515, 2015. Google Scholar
  3. P. Biro, R. W. Irving, and D. F. Manlove. Popular matchings in the marriage and roommates problems. In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pages 97-108, 2010. Google Scholar
  4. P. Biro, D. F. Manlove, and S. Mittal. Size versus stability in the marriage problem. Theoretical Computer Science, 411:1828-1841, 2010. Google Scholar
  5. Á. Cseh. Popular matchings. Trends in Computational Social Choice, Ulle Endriss (ed.), 2017. Google Scholar
  6. Á. Cseh, C.-C. Huang, and T. Kavitha. Popular matchings with two-sided preferences and one-sided ties. SIAM Journal on Discrete Mathematics, 31(4):2348-2377, 2017. Google Scholar
  7. A. L. Dulmage and N. S. Mendelsohn. Coverings of bipartite graphs. Canadian Journal of Mathematics, 10:517-534, 1958. Google Scholar
  8. Y. Faenza and T. Kavitha. Quasi-popular matchings, optimality, and extended formulations. Mathematics of Operations Research, 47(1):427-457, 2022. Google Scholar
  9. Y. Faenza, T. Kavitha, V. Powers, and X. Zhang. Popular matchings and limits to tractability. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2790-2809, 2019. Google Scholar
  10. D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  11. P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Science, 20:166-173, 1975. Google Scholar
  12. S. Gupta, P. Misra, S. Saurabh, and M. Zehavi. Popular matching in roommates setting is NP-hard. ACM Transactions on Computation Theory, 13(2):1-20, 2021. Google Scholar
  13. C.-C. Huang and T. Kavitha. Near-popular matchings in the roommates problem. SIAM Journal on Discrete Mathematics, 27(1):43-62, 2013. Google Scholar
  14. C.-C. Huang and T. Kavitha. Improved approximation algorithms for two variants of the stable marriage problem with ties. Mathematical Programming, 154(1):353-380, 2015. Google Scholar
  15. K. Iwama, S. Miyazaki, and N. Yamauchi. A 1.875-approximation algorithm for the stable marriage problem. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 288-297, 2007. Google Scholar
  16. K. Iwama, S. Miyazaki, and N. Yamauchi. A 25/17-approximation algorithm for the stable marriage problem with one-sided ties. Algorithmica, 68(3):758-775, 2014. Google Scholar
  17. T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  18. Z. Király. Better and simpler approximation algorithms for the stable marriage problem. Algorithmica, 60(1):3-20, 2011. Google Scholar
  19. C.-K. Lam and C. G. Plaxton. A (1+1/e)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2823-2840, 2019. Google Scholar
  20. L. Losász and M. D. Plummer. Matching theory. North-Holland, Mathematics Studies 121, 1986. Google Scholar
  21. D. F. Manlove and R. W. Irving. Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems. Journal of Combinatorial Optimization, 16:279-292, 2008. Google Scholar
  22. M. McCutchen. The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN), pages 593-604, 2008. Google Scholar
  23. W. R. Pulleyblank. Chapter 3, matchings and extensions. The Handbook of Combinatorics, R.L. Graham, M. Grötschel, and L. Lovasz (ed.), 1995. Google Scholar
  24. S. Ruangwises and T. Itoh. Unpopularity factor in the marriage and roommates problems. Theory of Computing Systems, 65(3):579-592, 2021. Google Scholar
  25. M. Soldner. Optimization and measurement in humanitarian operations: Addressing practical needs. PhD thesis, Georgia Institute of Technology, 2014. Google Scholar
  26. A.C. Trapp, A. Teytelboym, A. Martinello, T. Andersson, and N. Ahani. Placement optimization in refugee resettlement. Working paper, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact