Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous

Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous

Rohit Vaish, Dinesh Garg

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 437-443. https://doi.org/10.24963/ijcai.2017/62

We study the problem of manipulation of the men-proposing Gale-Shapley algorithm by a single woman via permutation of her true preference list. Our contribution is threefold: First, we show that the matching induced by an optimal manipulation is stable with respect to the true preferences. Second, we identify a class of optimal manipulations called inconspicuous manipulations which, in addition to preserving stability, are also nearly identical to the true preference list of the manipulator (making the manipulation hard to be detected). Third, for optimal inconspicuous manipulations, we strengthen the stability result by showing that the entire stable lattice of the manipulated instance is contained inside the original lattice.‚Äč
Keywords:
Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems
Agent-based and Multi-agent Systems: Social Choice Theory