  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 $M_A$ and $M_B$ be the sets of
stable matchings of the resulting pair of instances $A$ and $B$, and let
$\mathcal{L}_A$ and $\mathcal{L}_B$ be the corresponding lattices of stable
matchings. We prove that the matchings in $M_A \cap M_B$ form a sublattice of
both $\mathcal{L}_A$ and $\mathcal{L}_B$ and those in $M_A \setminus M_B$ form
a join semi-sublattice of $\mathcal{L}_A$. These properties enable us to obtain
a polynomial time algorithm for not only finding a stable matching in $M_A \cap
M_B$, 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.
