Minimax and Preferential Almost-Stable Matchings

In the fundamental Stable Marriage and Stable Roommate problems, there are inherent trade-offs between the size and stability of solutions. While the existence of desirable stable matchings can famously be determined in linear time when considering strict ordinal preferences, the computation of matchings that minimise the instability, either due to the presence of additional constraints on the size of the matching, or due to restrictive preference cycles, gives rise to a collection of infamously intractable almost-stable matching problems. To better understand and deal with individual and collective incentives in such settings, we introduce two new perspectives on these problems. The first applies a minimax principle, seeking a matching that minimises the maximum number of blocking pairs that any single agent is involved in, thus limiting individual incentives to deviate. The second requires that a given set of agents is in few blocking pairs, or even entirely free of blocking pairs, motivated by contexts where some agents are unwilling or unable to deviate. Surprisingly, both of these directions prove computationally intractable in strong ways: for example, it is NP-hard to decide whether a matching exists where no agent is in more than one blocking pair, even under bounded preference lists. On the positive side, we identify polynomial-time and fixed-parameter tractable cases, providing practical algorithmic tools for multi-agent systems where stability cannot be fully guaranteed, and offering new insights into the structure of almost-stable matchings.