Robust Stable Matchings: Dealing with Changes in Preferences
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917198546599936 |
|---|---|
| author | Gangam, Rohith Reddy Mai, Tung Raju, Nitya Vazirani, Vijay V. |
| author_facet | Gangam, Rohith Reddy Mai, Tung Raju, Nitya Vazirani, Vijay V. |
| contents | We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances $A$ and $B$ on the same set of agents, a matching is said to be robust if it is stable under both instances. This notion captures desirable robustness properties in matching markets where preferences may evolve, be misreported, or be subject to uncertainty. While the classical theory of stable matchings reveals rich lattice, algorithmic, and polyhedral structure for a single instance, it is unclear which of these properties persist when stability is required across multiple instances. Our work initiates a systematic study of the structural and computational behavior of robust stable matchings under increasingly general models of preference changes.
We analyze robustness under a hierarchy of perturbation models:
1. a single upward shift in one agent's preference list,
2. an arbitrary permutation change by a single agent, and
3. arbitrary preference changes by multiple agents on both sides.
For each regime, we characterize when:
1. the set of robust stable matchings forms a sublattice,
2. the lattice of robust stable matchings admits a succinct Birkhoff partial order enabling efficient enumeration,
3. worker-optimal and firm-optimal robust stable matchings can be computed efficiently, and
4. the robust stable matching polytope is integral (by studying its LP formulation).
We provide explicit counterexamples demonstrating where these structural and geometric properties break down, and complement these results with XP-time algorithms running in $O(n^k)$ time, parameterized by $k$, the number of agents whose preferences change. Our results precisely delineate the boundary between tractable and intractable cases for robust stable matchings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07959 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Robust Stable Matchings: Dealing with Changes in Preferences Gangam, Rohith Reddy Mai, Tung Raju, Nitya Vazirani, Vijay V. Computer Science and Game Theory We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances $A$ and $B$ on the same set of agents, a matching is said to be robust if it is stable under both instances. This notion captures desirable robustness properties in matching markets where preferences may evolve, be misreported, or be subject to uncertainty. While the classical theory of stable matchings reveals rich lattice, algorithmic, and polyhedral structure for a single instance, it is unclear which of these properties persist when stability is required across multiple instances. Our work initiates a systematic study of the structural and computational behavior of robust stable matchings under increasingly general models of preference changes. We analyze robustness under a hierarchy of perturbation models: 1. a single upward shift in one agent's preference list, 2. an arbitrary permutation change by a single agent, and 3. arbitrary preference changes by multiple agents on both sides. For each regime, we characterize when: 1. the set of robust stable matchings forms a sublattice, 2. the lattice of robust stable matchings admits a succinct Birkhoff partial order enabling efficient enumeration, 3. worker-optimal and firm-optimal robust stable matchings can be computed efficiently, and 4. the robust stable matching polytope is integral (by studying its LP formulation). We provide explicit counterexamples demonstrating where these structural and geometric properties break down, and complement these results with XP-time algorithms running in $O(n^k)$ time, parameterized by $k$, the number of agents whose preferences change. Our results precisely delineate the boundary between tractable and intractable cases for robust stable matchings. |
| title | Robust Stable Matchings: Dealing with Changes in Preferences |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.07959 |