English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently MV18 identified and initiated work on the new problem ofunderstanding structural relationships between the lattices of solutions of two"nearby" instances of stable matching. They also gave an application of theirwork to finding a robust stable matching. However, the types of changes theyallowed in going from instance $A$ to $B$ were very restricted, namely any oneagent executes an upward shift. In this paper, we allow any one agent topermute its preference list arbitrarily. Let $M_A$ and $M_B$ be the sets ofstable matchings of the resulting pair of instances $A$ and $B$, and let$\mathcal{L}_A$ and $\mathcal{L}_B$ be the corresponding lattices of stablematchings. We prove that the matchings in $M_A \cap M_B$ form a sublattice ofboth $\mathcal{L}_A$ and $\mathcal{L}_B$ and those in $M_A \setminus M_B$ forma join semi-sublattice of $\mathcal{L}_A$. These properties enable us to obtaina polynomial time algorithm for not only finding a stable matching in $M_A \capM_B$, but also for obtaining the partial order, as promised by Birkhoff'sRepresentation Theorem, thereby enabling us to generate all matchings in thissublattice. Our algorithm also helps solve a version of the robust stablematching problem. We discuss another potential application, namely obtainingnew insights into the incentive compatibility properties of the Gale-ShapleyDeferred Acceptance Algorithm.

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