2026-07-23T20:02:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17411 2024-03-06T10:59:41Z ddc:004 open_access

A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications Gangam, Rohith Reddy Mai, Tung Raju, Nitya Vazirani, Vijay V. stable matching robust solutions finite distributive lattice Birkhoff’s Representation Theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohith Reddy Gangam and Tung Mai and Nitya Raju and Vijay V. Vazirani 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.19 urn:nbn:de:0030-drops-174114 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.19 eng https://creativecommons.org/licenses/by/4.0/legalcode