Stability Under Valuation Updates in Coalition Formation

摘要

Coalition formation studies how to partition a set of agents into disjoint coalitions based on their preferences. In this paper, we consider the class of additively separable hedonic games and study the setting in which agents' valuations of each other evolve over time. Since rearranging coalitions can be costly, our goal is to find a stable partition close to the current one, where distance is measured by the number of agents that must change coalition. We study this problem for four stability notions based on single-agent deviations: Nash, individual, contractual Nash, and contractual individual stability. For all four, deciding whether a close stable partition exists is NP-complete, even under severe restrictions on the valuations and even when only a single valuation changes. On the positive side, we give polynomial-time algorithms for the two contractual notions under restricted symmetric valuations, and show that over long sequences of updates, these algorithms maintain stability with constant average reconfiguration cost.