TY - JOUR AU - Shen, Weiran AU - Tang, Pingzhong AU - Deng, Yuan PY - 2018/04/25 Y2 - 2024/03/29 TI - Coalition Manipulation of Gale-Shapley Algorithm JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 32 IS - 1 SE - AAAI Technical Track: Game Theory and Economic Paradigms DO - 10.1609/aaai.v32i1.11454 UR - https://ojs.aaai.org/index.php/AAAI/article/view/11454 SP - AB - <p> 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. </p> ER -