Two-Sided Manipulation Games in Stable Matching Markets
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912406093955072 |
|---|---|
| author | Hosseini, Hadi Lisowski, Grzegorz Pathak, Shraddha |
| author_facet | Hosseini, Hadi Lisowski, Grzegorz Pathak, Shraddha |
| contents | The Deferred Acceptance (DA) algorithm is an elegant procedure for finding a stable matching in two-sided matching markets. It ensures that no pair of agents prefers each other to their matched partners. In this work, we initiate the study of two-sided manipulations in matching markets as non-cooperative games. We introduce the accomplice manipulation game, where a man misreports to help a specific woman obtain a better partner, whenever possible. We provide a polynomial time algorithm for finding a pure strategy Nash equilibrium (NE) and show that our algorithm always yields a stable matching - although not every Nash equilibrium corresponds to a stable matching. Additionally, we show how our analytical techniques for the accomplice manipulation game can be applied to other manipulation games in matching markets, such as one-for-many and the standard self-manipulation games. We complement our theoretical findings with empirical evaluations of different properties of the resulting NE, such as the welfare of the agents. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00554 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-Sided Manipulation Games in Stable Matching Markets Hosseini, Hadi Lisowski, Grzegorz Pathak, Shraddha Computer Science and Game Theory Multiagent Systems The Deferred Acceptance (DA) algorithm is an elegant procedure for finding a stable matching in two-sided matching markets. It ensures that no pair of agents prefers each other to their matched partners. In this work, we initiate the study of two-sided manipulations in matching markets as non-cooperative games. We introduce the accomplice manipulation game, where a man misreports to help a specific woman obtain a better partner, whenever possible. We provide a polynomial time algorithm for finding a pure strategy Nash equilibrium (NE) and show that our algorithm always yields a stable matching - although not every Nash equilibrium corresponds to a stable matching. Additionally, we show how our analytical techniques for the accomplice manipulation game can be applied to other manipulation games in matching markets, such as one-for-many and the standard self-manipulation games. We complement our theoretical findings with empirical evaluations of different properties of the resulting NE, such as the welfare of the agents. |
| title | Two-Sided Manipulation Games in Stable Matching Markets |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2506.00554 |