Coalition Manipulation of Gale-Shapley Algorithm
Abstract
It is well-known that the Gale-Shapley algorithm is not truthful for all agents. Previous studies in this category concentrate on manipulations using incomplete preference lists by a single woman and by the set of all women. Little is known about manipulations by a subset of women. In this paper, we consider manipulations by any subset of women with arbitrary preferences. We show that a strong Nash equilibrium of the induced manipulation game always exists among the manipulators and the equilibrium outcome is unique and Pareto-dominant. In addition, the set of matchings achievable by manipulations has a lattice structure. We also examine the super-strong Nash equilibrium in the end.
Cite
Text
Shen et al. "Coalition Manipulation of Gale-Shapley Algorithm." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11454Markdown
[Shen et al. "Coalition Manipulation of Gale-Shapley Algorithm." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/shen2018aaai-coalition/) doi:10.1609/AAAI.V32I1.11454BibTeX
@inproceedings{shen2018aaai-coalition,
title = {{Coalition Manipulation of Gale-Shapley Algorithm}},
author = {Shen, Weiran and Tang, Pingzhong and Deng, Yuan},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {1210-1217},
doi = {10.1609/AAAI.V32I1.11454},
url = {https://mlanthology.org/aaai/2018/shen2018aaai-coalition/}
}