Ex-post Stability under Two-Sided Matching: Complexity and Characterization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911457535328256 |
|---|---|
| author | Aziz, Haris Csáji, Gergely Biró, Péter |
| author_facet | Aziz, Haris Csáji, Gergely Biró, Péter |
| contents | A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering random matchings, ex-post stability is a fundamental stability concept. A prominent open problem is characterizing ex-post stability and establishing its computational complexity. We investigate the computational complexity of testing ex-post stability. Our central result is that when either side has ties in the preferences/priorities, testing ex-post stability is NP-complete. The result even holds if both sides have dichotomous preferences. On the positive side, we give an algorithm using an integer programming approach, that can determine a decomposition with a maximum probability of being weakly stable. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14821 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Ex-post Stability under Two-Sided Matching: Complexity and Characterization Aziz, Haris Csáji, Gergely Biró, Péter Computer Science and Game Theory Computational Complexity A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering random matchings, ex-post stability is a fundamental stability concept. A prominent open problem is characterizing ex-post stability and establishing its computational complexity. We investigate the computational complexity of testing ex-post stability. Our central result is that when either side has ties in the preferences/priorities, testing ex-post stability is NP-complete. The result even holds if both sides have dichotomous preferences. On the positive side, we give an algorithm using an integer programming approach, that can determine a decomposition with a maximum probability of being weakly stable. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time. |
| title | Ex-post Stability under Two-Sided Matching: Complexity and Characterization |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2411.14821 |