Document Open Access Logo

Fairly Popular Matchings and Optimality

Author Telikepalli Kavitha

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.41.pdf
  • Filesize: 0.79 MB
  • 22 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. Thanks to Yuri Faenza and Jaikumar Radhakrishnan for useful discussions.

Cite As Get BibTex

Telikepalli Kavitha. Fairly Popular Matchings and Optimality. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.41

Abstract

We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices have strict preferences over their neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M is at least the number that prefer N; thus M does not lose a head-to-head election against any matching where vertices are voters. It is easy to find popular matchings; however when there are edge costs, it is NP-hard to find (or even approximate) a min-cost popular matching. This hardness motivates relaxations of popularity. 
Here we introduce fairly popular matchings. A fairly popular matching may lose elections but there is no good matching (wrt popularity) that defeats a fairly popular matching. In particular, any matching that defeats a fairly popular matching does not occur in the support of any popular mixed matching. We show that a min-cost fairly popular matching can be computed in polynomial time and the fairly popular matching polytope has a compact extended formulation. 
We also show the following hardness result: given a matching M, it is NP-complete to decide if there exists a popular matching that defeats M. Interestingly, there exists a set K of at most m popular matchings in G (where |E| = m) such that if a matching is defeated by some popular matching in G then it has to be defeated by one of the matchings in K.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Bipartite graphs
  • Stable matchings
  • Mixed matchings
  • Polytopes

Metrics

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

References

  1. A. Abdulkadiroğlu and T. Sönmez. School choice: a mechanism design approach. American Economic Review, 93(3):729-747, 2003. Google Scholar
  2. E. Balas. Disjunctive programming. Annals of Discrete Mathematics, 5:3-51, 1979. Google Scholar
  3. S. Baswana, P. P. Chakrabarti, S. Chandran, Y. Kanoria, and U. Patange. Centralized admissions for engineering colleges in India. INFORMS Journal on Applied Analytics, 49(5):338-354, 2019. Google Scholar
  4. 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
  5. Canadian Resident Matching Service. How the matching algorithm works. URL: http://carms.ca/algorithm.htm.
  6. Á. Cseh. Popular matchings. Trends in Computational Social Choice, Ulle Endriss (ed.), 2017. Google Scholar
  7. Á. Cseh and T. Kavitha. Popular edges and dominant matchings. Mathematical Programming, 172(1):209-229, 2018. Google Scholar
  8. L. Ehlers and T. Morrill. (Il)legal assignments in school choice. The Review of Economic Studies, 87(4):1837-1875, 2020. Google Scholar
  9. Y. Faenza and T. Kavitha. Quasi-popular matchings, optimality, and extended formulations. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 325-344, 2020. Google Scholar
  10. 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
  11. T. Feder. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences, 45(2):233-284, 1992. Google Scholar
  12. T. Feder. Network flow and 2-satisfiability. Algorithmica, 11(3):291-319, 1994. Google Scholar
  13. T. Fleiner. A fixed-point approach to stable matchings and some applications. Mathematics of Operations Research, 28(1):103-126, 2003. Google Scholar
  14. D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  15. D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11(3):223-232, 1985. Google Scholar
  16. P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Science, 20:166-173, 1975. Google Scholar
  17. D. Gusfield and R. W. Irving. The stable marriage problem: Structure and algorithms. MIT Press, 1989. Google Scholar
  18. C.-C. Huang and T. Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180-194, 2013. Google Scholar
  19. C.-C. Huang and T. Kavitha. Popularity, mixed matchings, and self-duality. Mathematics of Operations Research, 46(2):405-427, 2021. Google Scholar
  20. R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, 34(3):532-543, 1987. Google Scholar
  21. T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  22. T. Kavitha. Popular half-integral matchings. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 22:1-22:13, 2016. Google Scholar
  23. T. Kavitha. Matchings, critical nodes, and popular solutions. In Proceedings of the the 41st Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 25:1-25:19, 2021. Google Scholar
  24. T. Kavitha. Maximum matchings and popularity. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), pages 85:1-85:21, 2021. Google Scholar
  25. T. Kavitha. Min-cost popular matchings. In Proceedings of the the 40th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 25:1-25:17, 2021. Google Scholar
  26. T. Kavitha, J. Mestre, and M. Nasre. Popular mixed matchings. Theoretical Computer Science, 412:2679-2690, 2011. Google Scholar
  27. 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
  28. National Resident Matching Program. Why the Match? URL: http://www.nrmp.org/whythematch.pdf.
  29. U. G. Rothblum. Characterization of stable matchings as extreme points of a polytope. Mathematical Programming, 54:57-67, 1992. Google Scholar
  30. T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 216-226, 1978. Google Scholar
  31. C.-P. Teo and J. Sethuraman. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 23(4):874-891, 1998. Google Scholar
  32. E. G. Thurber. Concerning the maximum number of stable matchings in the stable marriage problem. Discrete Mathematics, 248(1-3):195-219, 2002. Google Scholar
  33. J. H. Vande Vate. Linear programming brings marital bliss. Operations Research Letters, 8(3):147-153, 1989. 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