An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints

Author Yu Yokoi



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.71.pdf
  • Filesize: 0.76 MB
  • 16 pages

Document Identifiers

Author Details

Yu Yokoi
  • National Institute of Informatics, Hitotsubashi, Chiyoda-ku, Tokyo, Japan

Acknowledgements

The author thanks the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Yu Yokoi. An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.71

Abstract

We present a polynomial-time 3/2-approximation algorithm for the problem of finding a maximum-cardinality stable matching in a many-to-many matching model with ties and laminar constraints on both sides. We formulate our problem using a bipartite multigraph whose vertices are called workers and firms, and edges are called contracts. Our algorithm is described as the computation of a stable matching in an auxiliary instance, in which each contract is replaced with three of its copies and all agents have strict preferences on the copied contracts. The construction of this auxiliary instance is symmetric for the two sides, which facilitates a simple symmetric analysis. We use the notion of matroid-kernel for computation in the auxiliary instance and exploit the base-orderability of laminar matroids to show the approximation ratio. In a special case in which each worker is assigned at most one contract and each firm has a strict preference, our algorithm defines a 3/2-approximation mechanism that is strategy-proof for workers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Algorithmic game theory
Keywords
  • Stable matching
  • Approximation algorithm
  • Matroid
  • Strategy-proofness

Metrics

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

References

  1. A. Abdulkadiroğlu, P. A. Pathak, and A. E. Roth. The New York city high school match. American Economic Review, 95:364-367, 2005. Google Scholar
  2. A. Abdulkadiroğlu, P. A. Pathak, and A. E. Roth. Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. American Economic Review, 99(5):1954-1978, 2009. Google Scholar
  3. A. Abdulkadiroğlu, P. A. Pathak, A. E. Roth, and T. Sönmez. The Boston public school match. American Economic Review, 95:368-371, 2005. Google Scholar
  4. P. Biró, T. Fleiner, R. W. Irving, and D. F. Manlove. The college admissions problem with lower and common quotas. Theoretical Computer Science, 411(34):3136-3153, 2010. Google Scholar
  5. J. E. Bonin and T. J. Savitsky. An infinite family of excluded minors for strong base-orderability. Linear Algebra and its Applications, 488:396-429, 2016. Google Scholar
  6. S. Braun, N. Dwenger, D. Kübler, and A. Westkamp. Implementing quotas in university admissions: An experimental analysis. Games and Economic Behavior, 85:232-251, 2014. Google Scholar
  7. R. A. Brualdi. Induced matroids. Proceedings of the American Mathematical Society, 29(2):213-221, 1971. Google Scholar
  8. F. Cooper and D. Manlove. A 3/2-approximation algorithm for the student-project allocation problem. In Proc. 17th International Symposium on Experimental Algorithms (SEA 2018), volume 103, pages 8:1-8:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  9. L. Ehlers, I. E. Hafalir, M. B. Yenmez, and M. A. Yildirim. School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory, 153:648-683, 2014. Google Scholar
  10. T. Fife and J. Oxley. Laminar matroids. European Journal of Combinatorics, 62:206-216, 2017. Google Scholar
  11. L. Finkelstein. Two algorithms for the matroid secretary problem. Master’s thesis, Technion-Israel Institute of Technology, Faculty of Industrial and Management Engineering, 2011. Google Scholar
  12. T. Fleiner. A matroid generalization of the stable matching polytope. In Proc. Eighth International Conference on Integer Programming and Combinatorial Optimization (IPCO 2001), volume 2081 of LNCS, pages 105-114. Springer-Verlag, Berlin & Heidelberg, 2001. 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. T. Fleiner and N. Kamiyama. A matroid approach to stable matchings with lower quotas. Mathematics of Operations Research, 41(2):734-744, 2016. Google Scholar
  15. D. Fragiadakis and P. Troyan. Improving matching under hard distributional constraints. Theoretical Economics, 12(2):863-908, 2017. Google Scholar
  16. D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  17. M. Goto, A. Iwasaki, Y. Kawasaki, R. Kurata, Y. Yasuda, and M. Yokoo. Strategyproof matching with regional minimum and maximum quotas. Artificial Intelligence, 235:40-57, 2016. Google Scholar
  18. D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, 1989. Google Scholar
  19. K. Hamada, S. Miyazaki, and H Yanagisawa. Strategy-proof approximation algorithms for the stable marriage problem with ties and incomplete lists. In Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), volume 149 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  20. J. W. Hatfield and P. R. Milgrom. Matching with contracts. American Economic Review, 95(4):913-935, 2005. Google Scholar
  21. C. C. Huang. Classified stable matching. In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2010), pages 1235-1253. SIAM, Philadelphia, 2010. Google Scholar
  22. A. W. Ingleton. Transversal matroids and related structures. In Higher Combinatorics (M. Aigner eds.), pages 117-131. Reidel, Dordrecht, 1977. Google Scholar
  23. R. W. Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261-272, 1994. Google Scholar
  24. K. Iwama, D. F. Manlove, S. Miyazaki, and Y. Morita. Stable marriage with incomplete lists and ties. In Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP1999), pages 443-452. Springer, 1999. Google Scholar
  25. K. Iwama, S. Miyazaki, and N. Yamauchi. A 1.875-approximation algorithm for the stable marriage problem. In Proc. 18th annual ACM-SIAM symposium on Discrete algorithms (SODA2007), pages 288-297. SIAM, Philadelphia, 2007. Google Scholar
  26. K. Iwama, S. Miyazaki, and N. Yamauchi. A (2-c1/(√n))-approximation algorithm for the stable marriage problem. Algorithmica, 51(3):342-356, 2008. Google Scholar
  27. Y. Kamada and F. Kojima. Efficient matching under distributional constraints: Theory and applications. American Economic Review, 105(1):67-99, 2015. Google Scholar
  28. Y. Kamada and F. Kojima. Stability concepts in matching under distributional constraints. Journal of Economic Theory, 168:107-142, 2017. Google Scholar
  29. Y. Kamada and F. Kojima. Stability and strategy-proofness for matching with constraints: A necessary and sufficient condition. Theoretical Economics, 13(2):761-793, 2018. Google Scholar
  30. Z. Király. Better and simpler approximation algorithms for the stable marriage problem. Algorithmica, 60(1):3-20, 2011. Google Scholar
  31. Z. Király. Linear time local approximation algorithm for maximum stable marriage. Algorithms, 6(3):471-484, 2013. Google Scholar
  32. D. E. Knuth. Stable Marriage and Its Relation to Other Combinatorial Problems. American Mathematical Society, Providence, 1996. Google Scholar
  33. F. Kojima, A. Tamura, and M. Yokoo. Designing matching mechanisms under constraints: An approach from discrete convex analysis. Journal of Economic Theory, 176:803-833, 2018. Google Scholar
  34. D. F. Manlove. Algorithmics of Matching under Preferences. World Scientific Publishing, Singapore, 2013. Google Scholar
  35. D. F. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage. Theoretical Computer Science, 276(1-2):261-279, 2002. Google Scholar
  36. E. Mcdermid. A 3/2-approximation algorithm for general stable marriage. In Proc. 36th International Colloquium on Automata, Languages, and Programming (ICALP2009), pages 689-700. Springer, 2009. Google Scholar
  37. J. G. Oxley. Matroid Theory (2nd ed.). Oxford University Press, Oxford, 2011. Google Scholar
  38. K. Paluch. Faster and simpler approximation of stable matchings. Algorithms, 7(2):189-202, 2014. Google Scholar
  39. A. E. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. The Journal of Political Economy, 92(6):991-1016, 1984. Google Scholar
  40. A. E. Roth. On the allocation of residents to rural hospitals: A general property of two-sided matching markets. Econometrica, 54(2):425-427, 1986. Google Scholar
  41. A. E. Roth and E. Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American economic review, 89(4):748-780, 1999. Google Scholar
  42. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Heidelberg, 2003. Google Scholar
  43. H. Yanagisawa. Approximation algorithms for stable marriage problems. Ph.D. Thesis, Kyoto University, 2007. Google Scholar
  44. Y. Yokoi. A generalized polymatroid approach to stable matchings with lower quotas. Mathematics of Operations Research, 42(1):238-255, 2017. Google Scholar
  45. Y. Yokoi. An approximation algorithm for maximum stable matching with ties and constraints. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.03076.
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