Manipulation With(out) Money in Matching Market

Abstract

The issue of manipulation in the stable marriage game is well-known and have been studied for many decades. The question of weighted manipulation where each manipulative action is charged individually and the question is to decide if a favorable outcome can be attained within a pre-specified budget has only recently been considered by Boehmer et al. [SAGT’20]. They considered several manipulative actions with uniform cost. In this paper, we generalise that model and consider arbitrary cost functions. Moreover, we study an additional question where given a manipulative action and an agent, the goal is to match the agent under a stable matching with the cost not exceeding the budget. We formally address some questions raised by Boehmer et al. and in the process show that in this extended model, all problems under consideration are intractable and even exhibit parameterized hardness. The most intriguing aspect of the analysis is that we are able to identify a common underlying structural property that makes each of the problems hard despite the fact that the manipulative action undertaken and/or the desired outcomes are very different from each other. Moreover, Boehmer et al.’s work revealed several dichotomies–be it classical or parameterized–and therefore it is apriori not obvious why in the weighted setting all problems must be W[1]-hard with respect to the combined parameter of budget and the number of unmatched vertices in a stable matching before manipulation. We discuss our analysis by way of presenting a metagadget that is at the heart of each hardness result, and show how to enrich it in different ways to yield hardness result for each of the individual problems.