Document Open Access Logo

Popular Matchings with One-Sided Bias

Author Telikepalli Kavitha

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.70.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Author Details

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

Funding

Supported by the DAE, Government of India, under project no. 12-R&D-TFR-5.01-0500.

Acknowledgements

Work done at MPI for Informatics, Saarland Informatics Campus, Germany. Thanks to Yuri Faenza for discussions that led to this problem and his helpful comments on the manuscript. Thanks to the reviewers for their valuable suggestions on improving the presentation.

Cite AsGet BibTex

Telikepalli Kavitha. Popular Matchings with One-Sided Bias. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.70

Abstract

Let G = (A ∪ B,E) be a bipartite graph where A consists of agents or main players and B consists of jobs or secondary players. Every vertex has a strict ranking of its neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M to N is at least the number that prefer N to M. Popular matchings always exist in G since every stable matching is popular. A matching M is A-popular if for any matching N, the number of agents (i.e., vertices in A) that prefer M to N is at least the number of agents that prefer N to M. Unlike popular matchings, A-popular matchings need not exist in a given instance G and there is a simple linear time algorithm to decide if G admits an A-popular matching and compute one, if so. We consider the problem of deciding if G admits a matching that is both popular and A-popular and finding one, if so. We call such matchings fully popular. A fully popular matching is useful when A is the more important side - so along with overall popularity, we would like to maintain "popularity within the set A". A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Bipartite graphs
  • Stable matchings
  • Gale-Shapley algorithm
  • LP-duality

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. D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007. 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. Canadian Resident Matching Service. How the matching algorithm works. URL: http://carms.ca/algorithm.htm.
  5. M.-J.-A.-N. de C. (Marquis de) Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. L'Imprimerie Royale, 1785. Google Scholar
  6. Condorcet method. URL: https://en.wikipedia.org/wiki/Condorcet_method.
  7. Á. Cseh and T. Kavitha. Popular edges and dominant matchings. Mathematical Programming, 172(1):209-229, 2018. Google Scholar
  8. 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
  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. D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11:223-232, 1985. Google Scholar
  12. P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Science, 20:166-173, 1975. Google Scholar
  13. D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989. Google Scholar
  14. C.-C. Huang and T. Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180-194, 2013. Google Scholar
  15. C.-C. Huang and T. Kavitha. Popularity, mixed matchings, and self-duality. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2294-2310, 2017. Google Scholar
  16. T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43:52-71, 2014. Google Scholar
  17. 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
  18. T. Kavitha, J. Mestre, and M. Nasre. Popular mixed matchings. Theoretical Computer Science, 412:2679-2690, 2011. Google Scholar
  19. D. F. Manlove and C. Sng. Popular matchings in the capacitated house allocation problem. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 492-503, 2006. Google Scholar
  20. J. Mestre. Weighted popular matchings. ACM Transactions on Algorithms, 10(1):2:1-2:16, 2014. Google Scholar
  21. National Resident Matching Program. Why the match? URL: http://www.nrmp.org/whythematch.pdf.
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 Imprint Privacy Contact