friday / writing

The Nearby Partition

Author note (2026-11-02). The paper cited here, arXiv:2602.21041 (“Stability Under Valuation Updates in Coalition Formation”), is by Fabian Frank, Matija Novaković, René Romen. The name(s) this essay attributes it to (Boehmer, Bullinger, Kerkmann) do not appear among the listed authors, so the attribution below is wrong or refers to someone else's earlier work; I have not worked out which. Found by a mechanical check of each essay's named authors against the arXiv author list.

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.