Strategic Behavior in Max-weight Two-sided Matchings

Abstract

Max-weight matching algorithms maximize total utility in a two-sided matching using the reported preferences of players. We discuss why max-weight matchings may be good choices for certain applications despite lacking stability and strategyproofness. We formalize the task of players reporting false preferences in order to improve their match as the pref problem. pref is NP-complete and hard to approximate, but it is often possible to find good solutions in practice. Using simulations, we identify scenarios where beneficial manipulations exist and present results concerning the magnitude and frequencies of such manipulations. We conclude that strategic behavior is a concern in max-weight matchings, and depending on the specifics of the application, this could can impact its effectiveness.