Worst- and Average-Case Robustness of Stable Matchings: (Counting) Complexity and Experiments
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917751911612416 |
|---|---|
| author | Boehmer, Kimon Boehmer, Niclas |
| author_facet | Boehmer, Kimon Boehmer, Niclas |
| contents | Focusing on the bipartite Stable Marriage problem, we investigate different robustness measures related to stable matchings. We analyze the computational complexity of computing them and analyze their behavior in extensive experiments on synthetic instances. For instance, we examine whether a stable matching is guaranteed to remain stable if a given number of adversarial swaps in the agent's preferences are performed and the probability of stability when applying swaps uniformly at random. Our results reveal that stable matchings in our synthetic data are highly unrobust to adversarial swaps, whereas the average-case view presents a more nuanced and informative picture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09160 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Worst- and Average-Case Robustness of Stable Matchings: (Counting) Complexity and Experiments Boehmer, Kimon Boehmer, Niclas Computer Science and Game Theory Focusing on the bipartite Stable Marriage problem, we investigate different robustness measures related to stable matchings. We analyze the computational complexity of computing them and analyze their behavior in extensive experiments on synthetic instances. For instance, we examine whether a stable matching is guaranteed to remain stable if a given number of adversarial swaps in the agent's preferences are performed and the probability of stability when applying swaps uniformly at random. Our results reveal that stable matchings in our synthetic data are highly unrobust to adversarial swaps, whereas the average-case view presents a more nuanced and informative picture. |
| title | Worst- and Average-Case Robustness of Stable Matchings: (Counting) Complexity and Experiments |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.09160 |