AAMAS Conference 2026 Conference Paper
Minimax and Preferential Almost-Stable Matchings
- Frederik Glitzner
- David Manlove
In the fundamental Stable Marriage and Stable Roommates problems, there are inherent trade-offs between the size and the 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 initiate deviations even in the presence of such opportunities. Surprisingly, both of these directions prove computationally intractable in strong ways: for example, it is NP-complete 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.