How to Secure General Acceptance for a Matching? - Inverse Popular Matchings

Abstract

Inverse optimization problems focus on minimizing the adjustments made to the input data to achieve a desired outcome. Popular matchings are relaxations of stable matchings that prioritize the overall welfare of society over individual preferences.  In this work, we aim to determine a minimum cost set of nodes in order to make a given matching popular by updating preferences at the chosen set. We show that the problem is NP-hard, even if the input matching is perfect or the graph is bipartite. If the desired matching is maximum size in the graph, we present a polynomial time algorithm to determine this minimum in bipartite graphs, and provide a dual characterization.