Near-Feasible Stable Matchings: Incentives and Optimality

Stable matching is a fundamental area with many practical applications. Recent work has introduced the paradigm of near-feasibility in capacitated matching settings, where agent capacities are slightly modified to ensure the existence of desirable outcomes. While useful when no stable matching exists or when some agents are left unmatched otherwise, it has not previously been investigated whether near-feasible stable matchings satisfy desirable properties with respect to their stability in the original instance. Furthermore, prior work leaves open the deviation incentive issues that arise when the centralised authority modifies agents' capacities. We consider these issues in the Stable Fixtures problem model, which generalises many classical models through non-bipartite preferences and capacitated agents. We develop a formal framework combining near-feasibility and almost-stability to analyse and quantify agent incentives to adhere to computed matchings. We study the trade-offs between instability, capacity modifications, and computational complexity. Further, we show that different modification strategies significantly affect stability, but establish that minimal modifications and minimal deviation incentives are compatible and efficiently computable.