Document Open Access Logo

A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications

Authors Rohith Reddy Gangam, Tung Mai, Nitya Raju, Vijay V. Vazirani

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.19.pdf
  • Filesize: 0.75 MB
  • 20 pages

Document Identifiers

Author Details

Rohith Reddy Gangam
  • University of California, Irvine, CA, USA
Tung Mai
  • Adobe Research, San Jose, CA, USA
Nitya Raju
  • University of California, Irvine, CA, USA
Vijay V. Vazirani
  • University of California, Irvine, CA, USA

Funding

  • Vazirani, Vijay V.: This work was supported in part by NSF grant CCF-1815901.

Cite As Get BibTex

Rohith Reddy Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani. A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications. 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. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.19

Abstract

Recently [Mai and Vazirani, 2018] identified and initiated work on a new problem, namely understanding structural relationships between the lattices of solutions of two "nearby" instances of stable matching. They also gave an application of their work to finding a robust stable matching. However, the types of changes they allowed in going from instance A to B were very restricted, namely any one agent executes an upward shift.
In this paper, we allow any one agent to permute its preference list arbitrarily. Let M_A and M_B be the sets of stable matchings of the resulting pair of instances A and B, and let ℒ_A and ℒ_B be the corresponding lattices of stable matchings. We prove that the matchings in M_A ∩ M_B form a sublattice of both ℒ_A and ℒ_B and those in M_A ⧵ M_B form a join semi-sublattice. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in M_A ∩ M_B, but also for obtaining the partial order, as promised by Birkhoff’s Representation Theorem [Birkhoff, 1937]. As a result, we can generate all matchings in this sublattice. 
Our algorithm also helps solve a version of the robust stable matching problem. We discuss another potential application, namely obtaining new insights into the incentive compatibility properties of the Gale-Shapley Deferred Acceptance Algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • stable matching
  • robust solutions
  • finite distributive lattice
  • Birkhoff’s Representation Theorem

Metrics

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

Related Versions

References

  1. Atila Abdulkadiroğlu, Parag A Pathak, and Alvin E Roth. Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. American Economic Review, 99(5):1954-78, 2009. Google Scholar
  2. Atila Abdulkadiroğlu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez. The boston public school match. American Economic Review, 95(2):368-371, 2005. Google Scholar
  3. Atila Abdulkadiroğlu and Tayfun Sonmez. School choice: A mechanism design approach. American economic review, 93(3):729-747, 2003. Google Scholar
  4. H. Aziz, P. Biro, T. Fleiner, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari. Stable matching with uncertain pairwise preferences. In International Joint Conference on Autonomous Agents and Multiagent Systems, pages 344-352, 2017. Google Scholar
  5. H. Aziz, P. Biro, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari. Stable matching with uncertain linear preferences. In International Symposium on Algorithmic Game Theory, pages 195-206, 2016. Google Scholar
  6. A. Ben-Tal, L. El Ghaoui, and A.S. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, October 2009. Google Scholar
  7. Garrett Birkhoff. Rings of sets. Duke Mathematical Journal, 3(3):443-454, 1937. Google Scholar
  8. Charles Blair. Every finite distributive lattice is a set of stable matchings. Journal of Combinatorial Theory, Series A, 37(3):353-356, 1984. Google Scholar
  9. G. C. Calafiore and L. El Ghaoui. On distributionally robust chance-constrained linear programs. Jour. of Optimization Theory and Applications, 130(1), December 2006. Google Scholar
  10. Agnes Cseh, Yuri Faenza, Telikepalli Kavitha, and Vladlena Powers. Understanding popular matchings via stable matchings. SIAM Journal on Discrete Mathematics, 36(1):188-213, 2022. Google Scholar
  11. L. E. Dubins and D. A. Freedman. Machiavelli and the gale-shapley algorithm. The American Mathematical Monthly, 88(7):485-494, 1981. Google Scholar
  12. Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors. Online and Matching-Based Market Design. Cambridge University Press, to appear. URL: https://www.ics.uci.edu/~vazirani/Chapter1.pdf.
  13. Simons Institute for the Theory of Computing. Online and matching-based market design, 2019. URL: https://simons.berkeley.edu/programs/market2019.
  14. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  15. Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. Google Scholar
  16. Telikepalli Kavitha. Matchings, critical nodes, and popular solutions. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  17. Donald Ervin Knuth. Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms. American Mathematical Soc., 1997. Google Scholar
  18. Tung Mai and Vijay V. Vazirani. Finding stable matchings that are robust to errors in the input. In European Symposium on Algorithms, 2018. Google Scholar
  19. Tung Mai and Vijay V. Vazirani. A natural generalization of stable matching solved via new insights into ideal cuts. In arXiv, 2018. Google Scholar
  20. David Manlove. Algorithmics of Matching Under Preferences. World Scientific, 2013. Google Scholar
  21. Shuichi Miyazaki and Kazuya Okamoto. Jointly stable matchings. Journal of Combinatorial Optimization, 38(2):646-665, 2019. Google Scholar
  22. Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485-541, 1992. Google Scholar
  23. Richard Stanley. Enumerative combinatorics, vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing, 1996. 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