cs.AIMar 9, 2026

Visualizing Coalition Formation: From Hedonic Games to Image Segmentation

Authors: Pedro Henrique de Paula França, Lucas Lopes Felipe, Daniel Sadoc Menasché

Organizations: UFRJ

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We propose image segmentation as a visual diagnostic testbed for coalition formation in hedonic games. Modeling pixels as agents on a graph, we study how a granularization parameter shapes equilibrium fragmentation and boundary structure. On the Weizmann single-object benchmark, we relate multi-coalition equilibria to binary protocols by measuring whether the converged coalitions overlap with a foreground ground-truth. We observe transitions from cohesive to fragmented yet recoverable equilibria, and finally to intrinsic failure under excessive fragmentation. Our core contribution links multi-agent systems with image segmentation by quantifying the impact of mechanism design parameters on equilibrium structures.

Figures & tables

Figure 1: Segmentation of the same image for increasing values of γ\gamma . (a) Original image. (b) γ=10−6\gamma=10^{-6} . (c) γ=8×10−6\gamma=8\times 10^{-6} . (d) γ=10−5\gamma=10^{-5} . (e) γ=5×10−4\gamma=5\times 10^{-4} . (f) γ=2.5×10−1\gamma=2.5\times 10^{-1} .
Figure 2: Pipeline: (a) image →\rightarrow (b) graph construction (downsampled, 1 see Appendix A ) →\rightarrow (c) equilibrium partition (Section 2 ) →\rightarrow (d) segmented image →\rightarrow (e) ground truth evaluation (Section 3 ).
Figure 3: Projections from a multi-community partition. (a) Original image. (b) Binary ground-truth mask. (c) Equilibrium partition by hedonic mechanism. (d) Best single community selected by F1single\mathrm{F}_{1}^{\text{single}} at γ=7.63×10−6\gamma=7.63\times 10^{-6} . (e) Best subset of communities selected by F1union\mathrm{F}_{1}^{\text{union}} at γ=2.96×10−5\gamma=2.96\times 10^{-5} .
Figure 4: (a) Mean F1single\mathrm{F}_{1}^{\text{single}} and F1union\mathrm{F}_{1}^{\text{union}} as a function of γ\gamma (induced by density(G)/900\mathrm{density}(G)/900 ). (b) Global distributions of F1single\mathrm{F}_{1}^{\text{single}} and F1union\mathrm{F}_{1}^{\text{union}} over 100 images after selecting the best GT per image.
Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Diagnostic pipeline: image →\rightarrow graph →\rightarrow hedonic partition →\rightarrow binary projection and evaluation.
Figure 6: Diagnostics as a function of the resolution parameter γ\gamma . (a) Fragmentation KK vs. γ\gamma . (b) F1F_{1} vs. γ\gamma . Orange points correspond to F1,unionF_{1,\textrm{union}} and blue points to F1,singleF_{1,\textrm{single}} .
Figure 7: F1F_{1} vs # of communities KK . Orange and blue points correspond to F1,unionF_{1,\textrm{union}} and F1,singleF_{1,\textrm{single}} .
Figure 8: Global distribution of the number of communities KK over 100 images.
Figure 9: Peak example: the partition aligns closely with the selected ground truth. The best single coalition already attains F1single=0.9863\mathrm{F}_{1}^{\text{single}}=0.9863 , while the recoverable union slightly improves performance to F1union=0.9922\mathrm{F}_{1}^{\text{union}}=0.9922 .
Figure 10: Decay example: the partition exhibits severe failure, with no single coalition capturing the object well and only limited improvement under recoverable union. The scores are F1single=0.0370\mathrm{F}_{1}^{\text{single}}=0.0370 and F1union=0.2714\mathrm{F}_{1}^{\text{union}}=0.2714 .
Figure 11: Violin plots over 100 images with γ=density(G)/900\gamma=\mathrm{density}(G)/900 . In each panel, the top row shows F1single\mathrm{F}_{1}^{\text{single}} and the bottom row shows F1union\mathrm{F}_{1}^{\text{union}} .
More in this topic

Coalition Formation

See all 13 papers

Explore similar work

CardsList
Feb 24, 2026

Stability Under Valuation Updates in Coalition Formation

Coalition formation studies how to partition a set of agents into disjoint coalitions under consideration of their preferences. We study the classical objective of stability in a variant of additively separable hedonic games where agents can change their valuations. Our objective is to find a stable partition after each change. To minimize the reconfiguration cost, we search for nearby stable coalition structures. Our focus is on stability concepts based on single-agent deviations. We present a detailed picture of the complexity of finding nearby stable coalition structures in additively separable hedonic games, for both symmetric and non-symmetric valuations. Our results show that the problem is NP-complete for Nash stability, individual stability, contractual Nash stability, and contractual individual stability. We complement these results by presenting polynomial-time algorithms for contractual Nash stability and contractual individual stability under restricted symmetric valuations. Finally, we show that these algorithms guarantee a bounded average distance over long sequences of updates.

Fabian Frank, Matija Novaković, René Romen

Technical University of Munich

Coalition FormationCooperative Game Theory
AskPDF
Jun 19, 2026

Multiscale Exit-Join Dynamics: Tactical Consensus and Strategic Coalition Formation

This paper develops a multiscale model of coalition formation in which strategic exit-and-join decisions are coupled with tactical consensus dynamics inside coalitions. Coalition value is generated endogenously from within-coalition information aggregation, while Aumann-Dreze payoffs, switching frictions, and acceptance rules govern strategic reconfiguration. The framework introduces a fast-slow architecture in which transferable coalition value emerges from DeGroot-style consensus processes, while coalition structures evolve through incentive-driven exit-and-join dynamics. The analysis characterizes joint tactical-strategic equilibria, conditions for tactical and strategic unanimity, segregation, polarization, and cognitive barriers that sustain stable coalition structures. A fixed-point characterization and existence results are established for the coupled dynamics. Numerical experiments reveal an instability-consensus paradox: low or negative switching barriers may prevent strategic convergence while simultaneously promoting temporal mixing sufficient to achieve global tactical consensus. The results provide a unified perspective on coalition formation, consensus dynamics, information aggregation, and strategic stability in multi-agent systems.

Quanyan Zhu

Department of Electrical and Computer Engineering New York University Tandon School of Engineering Brooklyn, NY, USA

Cooperative Game TheoryMulti-Agent CoordinationOpinion DynamicsCoalition Formation
AskPDF
Feb 18, 2026

Control in Hedonic Games

We initiate the study of control in hedonic games, where an external actor influences coalition formation by adding or deleting agents. We consider three basic control goals (1) enforcing that an agent is not alone (NA); (2) enforcing that a pair of agents is in the same coalition (PA); (3) enforcing that all agents are in the same grand coalition (GR), combined with two control actions: adding agents (AddAg) or deleting agents (DelAg). We analyze these problems for friend-oriented and additive preferences under individual rationality, individual stability, Nash stability, and core stability. We provide a complete computational complexity classification for control in hedonic games.

Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić +1

TU Wien Vienna, Austria

Coalition FormationGame TheoryCooperative Game Theory
AskPDF