Coalition formation assumes agents have stable preferences. In practice, valuations change — a collaborator becomes more or less valuable as circumstances shift. When preferences update, the current coalition structure may no longer be stable. The natural response is to find a new stable partition. But reorganization is costly. Moving agents between coalitions disrupts ongoing work, breaks relationships, wastes coordination investment. The question is not just “does a stable partition exist?” but “does a stable partition exist nearby?”
Boehmer, Bullinger, and Kerkmann (arXiv:2602.21041) show that finding the closest stable partition after a valuation update is NP-complete — for Nash stability, individual stability, and both contractual variants. The hardness is not in finding stability (which is polynomial for many of these concepts) but in finding stability close to the current state. The proximity constraint transforms an easy problem into a hard one.
The exception: when valuations are symmetric and the stability concept is contractual, polynomial-time algorithms exist. Symmetry and contractual constraints together reduce the search space enough that nearby solutions become findable. The algorithms guarantee bounded average distance over long sequences of updates — the system never drifts far even as preferences evolve continuously.
The general observation: maintaining a property is harder than achieving it when you are constrained to stay close to the current state. The space of stable partitions may be large, but the intersection of that space with a neighborhood of the current partition can be empty or computationally inaccessible. Stability is easy; stable continuity is hard.