Chen, Jiehua and Schlotter, Ildikó (2026) Control and Bribery in Stable Marriage and Roommates: A Complete Complexity Landscape. In: The 19th International Symposium on Algorithmic Game Theory (SAGT 2026), Augsburg, Germany. (In Press)
|
Text
Control_in_Stable_Roommates.pdf - Published Version Download (546kB) | Preview |
Abstract
We study control and bribery problems for stable matchings: a central authority (the controller, resp., briber) may add agents, delete agents, delete acceptable pairs, swap two adjacent agents in some agent's preference list, or arbitrarily reorder some agent's preference list, in an instance of Stable Marriage or Stable Roommates. We extend previous work on control and bribery in stable matchings by Boehmer et al. (2021). We consider goals capturing individual and pair inclusion, stability, and uniqueness requirements: matching a designated agent, matching a designated pair, realizing a stable matching consistent with a given matching, making a given matching the unique stable matching, or guaranteeing that a stable (resp., perfect and stable) matching exists. We provide a unified complexity map for all non-trivial action--goal combinations in both settings, consolidating known results and extending the study to the roommates model, where stable matchings need not exist.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | Ildikó Anna Schlotter |
| Date Deposited: | 16 Sep 2026 06:14 |
| Last Modified: | 16 Sep 2026 06:14 |
| URI: | https://real.mtak.hu/id/eprint/246267 |
Actions (login required)
 |
View Item |
