Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2408.16271 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |