2025/05/31 by Hosseini, Hadi, Grzegorz Lisowski, Lisowski, Grzegorz +2
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.2506.00554
openalex publication_date 2025/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Deferred Acceptance (DA) algorithm is an elegant procedure for finding a stable matching in two-sided matching markets. It ensures that no pair of agents prefers each other to their matched partners. In this work, we initiate the study of two-sided manipulations in matching markets as non-cooperative games. We introduce the accomplice manipulation game, where a man misreports to help a specific woman obtain a better partner, whenever possible. We provide a polynomial time algorithm for finding a pure strategy Nash equilibrium (NE) and show that our algorithm always yields a stable matching - although not every Nash equilibrium corresponds to a stable matching. Additionally, we show how our analytical techniques for the accomplice manipulation game can be applied to other manipulation games in matching markets, such as one-for-many and the standard self-manipulation games. We complement our theoretical findings with empirical evaluations of different properties of the resulting NE, such as the welfare of the agents.