Non-uniformly Stable Matchings
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929478304792576 |
|---|---|
| author | Kamiyama, Naoyuki |
| author_facet | Kamiyama, Naoyuki |
| contents | Super-stability and strong stability are properties of a matching in the stable matching problem with ties. In this paper, we introduce a common generalization of super-stability and strong stability, which we call non-uniform stability. First, we prove that we can determine the existence of a non-uniformly stable matching in polynomial time. Next, we give a polyhedral characterization of the set of non-uniformly stable matchings. Finally, we prove that the set of non-uniformly stable matchings forms a distributive lattice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16271 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-uniformly Stable Matchings Kamiyama, Naoyuki Computer Science and Game Theory Super-stability and strong stability are properties of a matching in the stable matching problem with ties. In this paper, we introduce a common generalization of super-stability and strong stability, which we call non-uniform stability. First, we prove that we can determine the existence of a non-uniformly stable matching in polynomial time. Next, we give a polyhedral characterization of the set of non-uniformly stable matchings. Finally, we prove that the set of non-uniformly stable matchings forms a distributive lattice. |
| title | Non-uniformly Stable Matchings |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.16271 |