Coalition Manipulation of Gale-Shapley Algorithm

Authors

  • Weiran Shen Tsinghua University
  • Pingzhong Tang Tsinghua University
  • Yuan Deng Duke University

Keywords:

gale-shapley algorithm, stable matching, coalition manipulation

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.

Downloads

Published

2018-04-25

How to Cite

Shen, W., Tang, P., & Deng, Y. (2018). Coalition Manipulation of Gale-Shapley Algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11454

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms