2018/04/16 by Rohith Reddy Gangam, Tung Mai, Gangam, Rohith Reddy +5 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1804.05537
openalex publication_date 2018/04/16 · openalex created_date 2022/08/12 · openalex updated_date 2026/07/28
Recently MV18 identified and initiated work on the new problem of 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 MA and MB be the sets of stable matchings of the resulting pair of instances A and B, and let LA and LB be the corresponding lattices of stable matchings. We prove that the matchings in MA ∩ MB form a sublattice of both LA and LB and those in MA ∖ MB form a join semi-sublattice of LA. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in MA ∩ MB, but also for obtaining the partial order, as promised by Birkhoff's Representation Theorem, thereby enabling us to 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.