Strategic Manipulation of Preferences in the Rank Minimization Mechanism

We consider one-sided matching problems, where agents are allocated items based on stated preferences. Posing this as an assignment problem, the average rank of obtained matchings can be minimized using the rank minimization (RM) mechanism. RM matchings can have significantly better rank distributions than matchings obtained by mechanisms with random priority, such as Random Serial Dictatorship. However, these matchings are sensitive to preference manipulation from strategic agents. In this work, we derive a best response strategy for a scenario where agents aim to be matched to their top-𝑛 preferred items using the RM mechanism under a simplified cost function. This strategy is then extended to a first-order heuristic strategy for being matched to the top-𝑛 items in a setup that minimizes the average rank. Based on this finding, an empirical study is conducted examining the impact of the firstorder heuristic strategy. The study utilizes data from both simulated markets and real-world matching markets in Amsterdam, taking into account variations in item popularity, fractions of strategic agents, and the preferences for the 𝑛 most favored items. For most scenarios, RM yields more rank efficient matches than Random Serial Dictatorship, even when agents apply the first-order heuristic strategy. In competitive markets, the matching performance can become worse when 50% of agents or more want to be matched to their top-1 or top-2 preferred items and apply the first-order heuristic strategy to achieve this.