(Un)stable matchings with blocking costs

We introduce and study weighted bipartite matching problems under strict preferences where blocking edges can be paid for, thus imposing costs rather than constraints as in classical models. We focus on the setting in which the weight of an edge represents the benefit from including it in the matching and/or the cost if it is a blocking edge. We show that this setting encompasses interesting special cases that remain polynomially-solvable, although it becomes APX-hard even in a quite restricted case.