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 γ . (a) Original image. (b) γ=10−6 . (c) γ=8×10−6 . (d) γ=10−5 . (e) γ=5×10−4 . (f) γ=2.5×10−1 .
Figure 2: Pipeline: (a) image → (b) graph construction (downsampled, 1 see Appendix A ) → (c) equilibrium partition (Section 2 ) → (d) segmented image → (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 at γ=7.63×10−6 . (e) Best subset of communities selected by F1union at γ=2.96×10−5 .
Figure 4: (a) Mean F1single and F1union as a function of γ (induced by density(G)/900 ). (b) Global distributions of F1single and F1union over 100 images after selecting the best GT per image.
Figure 6: Diagnostics as a function of the resolution parameter γ . (a) Fragmentation K vs. γ . (b) F1 vs. γ . Orange points correspond to F1,union and blue points to F1,single .
Figure 7: F1 vs # of communities K . Orange and blue points correspond to F1,union and F1,single .
Figure 8: Global distribution of the number of communities K 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 , while the recoverable union slightly improves performance to F1union=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 and F1union=0.2714 .
Figure 11: Violin plots over 100 images with γ=density(G)/900 . In each panel, the top row shows F1single and the bottom row shows F1union .