Dynamics in matching and coalition formation games with structural constraints

摘要

Matching and coalition formation are fundamental aspects in the organization of many multi-agent systems. In large populations, the emergence of coalitions is often restricted by structural constraints under which agents can reorganize, e.g., local visibility or externality constraints among the agents. We study this aspect using a novel framework for dynamics with constraints within the popular domain of hedonic coalition formation games. We analyze the effects of structural constraints on the convergence of matching and coalition formation processes to stable states. Our main result are tight characterizations for the constraint structures based on which dynamic coalition formation can stabilize quickly. We show a variety of convergence results for matching and coalition formation games with different forms of locality and externality constraints. In particular, we propose and analyze a new model of graph-based visibility for coalition formation games and tightly characterize the graph structures that allow polynomial-time convergence – it can be achieved if and only if coalition formation is based on complete or star graphs.