Paper deep dive
Visualizing Coalition Formation: From Hedonic Games to Image Segmentation
Pedro Henrique de Paula França, Lucas Lopes Felipe, Daniel Sadoc Menasché
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/13/2026, 12:37:47 AM
Summary
The paper proposes using image segmentation as a visual diagnostic testbed for coalition formation in hedonic games. By modeling pixels as agents on a graph, the authors study how a resolution parameter (gamma) influences equilibrium fragmentation and boundary structure. They evaluate the mechanism on the Weizmann single-object benchmark, demonstrating that while high fragmentation often occurs, the foreground objects remain 'recoverable' through union-based F1 metrics, bridging multi-agent systems with computer vision.
Entities (6)
Relation Signals (3)
Resolution Parameter (gamma) → controls → Coalition Granularity
confidence 98% · The resolution parameter γ modulates coalition granularity
Constant Potts Model → ismodeledas → Hedonic Games
confidence 95% · Felipe et al. (2025) modeled the Constant Potts Model (CPM) ... as an additively separable potential hedonic game.
Hedonic Games → isusedfor → Image Segmentation
confidence 95% · We propose image segmentation as a visual diagnostic testbed for coalition formation in hedonic games.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.07890v1
- Canonical: https://arxiv.org/abs/2603.07890v1
Trouble viewing inline? Open PDF directly →
Full Text
45,141 characters extracted from source content.
Expand or collapse full text
Visualizing Coalition Formation: From Hedonic Games to Image Segmentation Pedro H. de Paula França UFRJ pedro.franca@ufrj.br &Lucas Lopes Felipe UFRJ lucaslopesf2@gmail.com &Daniel Sadoc Menasché UFRJ sadoc@ic.ufrj.br 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. 1 Introduction (a) (b) (c) (d) (e) (f) Figure 1: Segmentation of the same image for increasing values of γ. (a) Original image. (b) γ=10−6γ=10^-6. (c) γ=8×10−6γ=8× 10^-6. (d) γ=10−5γ=10^-5. (e) γ=5×10−4γ=5× 10^-4. (f) γ=2.5×10−1γ=2.5× 10^-1. Coalition formation is a common emergent behavior in multi-agent systems and mechanism design: agents optimize individual utilities under interaction constraints, and equilibria appear as partitions of the population (Bogomolnaia and Jackson, 2002). We leverage intuitive image segmentation to interpret a multi-agent coalition mechanism, providing a quantitative measure of a resolution parameter that controls coalition granularity. Image segmentation is an essential task across a range of scientific and technological domains (Mittal et al., 2022). The resolution parameter γ modulates coalition granularity (Traag et al., 2011), fundamentally reshaping the equilibrium structure of the system (Felipe et al., 2025). By adjusting γ, the system can span the full spectrum of partitions, ranging from a single grand coalition as γ→0γ→ 0 to a set of individual singletons as γ→1γ→ 1. Figure 1 illustrates how image segmentation visualizes this transition from smaller to larger values of γ (Fig. 1(b) to Fig. 1(f)), mapping different partition equilibria to varying levels of spatial granularity. Indeed, a central challenge for mechanism designers is identifying the specific value of γ that yields meaningful equilibria for a given real-world application. (a) (b) (c) (d) (e) 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). We bridge image segmentation and the proposed coalition mechanism by representing the image as a graph where pixels act as nodes. In this framework, the primary distinction between methods lies in the edge construction, which encodes pairwise similarities according to specific schemes (Shi and Malik, 1997; Galun et al., 2003; Alpert et al., 2007). This formulation effectively casts the segmentation task as a network clustering or community detection problem (Avrachenkov et al., 2018). Our key contribution lies in using the pipeline in Figure 2 to bridge the gap between multi-agent systems and intuitive image segmentation tasks, so as to quantify the impact of the resolution parameter on equilibrium structures. At the core of the pipeline lies the coalition mechanism (Figure 2(c)), which determines the specific cluster assignment for each pixel; these assignments then serve as labels to reconstruct the segmented image (Figure 2(d)). In Section 2, we detail the mechanism based on hedonic games (Felipe et al., 2025). Section 3 then evaluates the overlap between the equilibrium partitions produced by the mechanism and the ground-truth foreground coalition (Figure 2(e)). Section 4 concludes with a summary of our contributions and future work.111We detail our graph construction in Appendix A. While it is impactful for performance, our mechanism is agnostic to the specific construction method as long as the input is a weighted graph; thus, evaluating alternatives remains future work. Figs. 2(b) and 2(c) are downsampled versions of Fig. 2(a) for visual clarity. 2 Hedonic Mechanism for Coalition Formation A hedonic game is a naturally decentralized coalition formation game in which an agent’s preference depends strictly on the composition of its own coalition (Aziz and Savani, 2016). A potential game allows unilateral improvements by individual agents to be aligned with the maximization of a global potential function, where local dynamics can be interpreted as hill-climbing a single objective (Monderer and Shapley, 1996). Felipe et al. (2025) modeled the Constant Potts Model (CPM) (Traag et al., 2011), a quality function known for being a resolution-limit-free method (Fortunato and Barthelemy, 2007), as an additively separable potential hedonic game. The CPM is decomposed into individual agent utilities (hedonic potentials). This frames the mechanism as a non-cooperative game while remaining aligned with a global quality function, ensuring that selfish agents’ decisions yield stable, cooperative coalitions. Potential. Each player seeks to belong to the community that maximizes its utility, in which better balances attraction to well-connected neighbors against a penalty for joining large, weakly connected coalitions. For a node v and community C, we define Potentialvγ(C)=(1−γ)d(v,C)−γd¯(v,C)Potential_v^γ(C)=(1-γ)\,d(v,C)-γ\, d(v,C) (1) where d(v,C)d(v,C) denotes the degree of v in community C, while d¯(v,C) d(v,C) is the number of non-neighbors in community C, therefore |C|=1+d(v,C)+d¯(v,C)|C|=1+d(v,C)+ d(v,C) is the number of nodes in C. The parameter γ∈[0,1]γ∈[0,1] controls the trade-off between cohesion and coalition size: small γ favors larger cohesive regions, while larger γ penalizes large communities and promotes fragmentation into smaller coalitions (Figure 1). Input : Weighted Graph G=(V,E,w)G=(V,E,w), resolution γ, partition π(0)π^(0) Output : Equilibrium partition π=C1,…,CKπ=\C_1,…,C_K\ 1 2if π(0)π^(0) not provided then Assign each node to its own community ⊳ Initialize a singleton partition 3 change ← true ⊳ Activate the main improvement loop 4 5while change do ⊳ Iterate while at least one beneficial node move occurs change ← false ⊳ Clear the change flag 6 7 foreach node v∈Vv∈ V do ⊳ Scan all nodes (pixels) σv← _v← current community of v ⊳ Retrieve current community σv _v 8 σ⋆←argmaxCPotentialvγ(C)σ ← _CPotential_v^γ(C) ⊳ get community maximizing potential 9 10 if Potentialvγ(σ⋆)>Potentialvγ(σv)Potential_v^γ(σ )>Potential_v^γ( _v) then ⊳ Check for strict potential improvement 11 Move v to σ⋆σ ⊳ Reassign the node’s community 12 change ← true ⊳ Mark change occurred to force another pass 13 14 15 Algorithm 1 Hedonic optimization: The algorithm terminates at a locally stable equilibrium. Equilibrium. An equilibrium is a stable partition π=C1,…,CKπ=\C_1,…,C_K\ where no agent has an incentive to change their community. This state is reached when every node is locally stable, meaning its current community CσvC_ _v provides a potential greater than or equal to any other community CkC_k: Potentialvγ(Cσv)≥Potentialvγ(Ck)∀k≠σv.Potential_v^γ(C_ _v) _v^γ(C_k) ∀ k≠ _v. (2) A partition is considered a solution to the community detection problem if it satisfies two conditions: • Internal Stability: No node wants to leave its current community. • External Stability: No node wants to join a different existing community. In this state, each node v is assigned to a community σv _v that maximizes its individual utility σv∈argmaxkPotentialvγ(Ck) _v∈ _kPotential_v^γ(C_k). Movement only occurs if a change offers a strictly higher utility. If multiple communities provide the same maximum utility, the node remains in its current community. Algorithm 1 outlines the hedonic game mechanism,222Algorithm 1 presents a simplified version of the optimization process to illustrate the underlying mechanics. In practice, scanning all nodes (Line 1) results in many “ignorable checks” that do not yield strict improvements. To achieve high performance, we utilize the community_leiden method (Traag et al., 2019) (of the igraph Python library) optimizing the CPM (Traag et al., 2011), which serves as the core of our pipeline. which relies on a potential function bounded by 2|V|22|V|^2. Given a rational resolution parameter γ=b/κγ=b/κ, every improving move increases the potential by at least 1/κ1/κ, guaranteeing convergence in O(κ⋅|V|2)O(κ·|V|^2) steps (Felipe et al., 2025). 3 Results To quantify how γ shapes equilibrium partitions and yields meaningful segmentations, we evaluate the converged partitions using two post-hoc accuracy metrics inspired by Alpert et al. (2007). For each image, we select one binary ground-truth (GT), denoted by Y, where Y∈0,1H×WY∈\0,1\^H× W: • F1singleF_1^single (Dominant-Coalition Accuracy): Evaluates the F1F_1 score of the single community Ck∈πC_k∈π that maximizes the F1F_1 score relative to Y; • F1unionF_1^union (Recoverable-Union Accuracy): Evaluates the F1F_1 score of the subset of communities S⊆C1,…,CKS \C_1,…,C_K\ whose union maximizes the F1F_1 score relative to Y. F1F_1 is the harmonic mean of precision and recall (Christen et al., 2023). Specifically, F1singleF_1^single measures the emergence of a cohesive foreground, while F1unionF_1^union assesses whether the foreground object, even if fragmented, remains “recoverable” from the equilibrium structure. Formal definitions, algorithmic details, and additional properties of F1singleF_1^single and F1unionF_1^union are provided in Appendix F. We use the Weizmann Segmentation Evaluation Database (Alpert et al., 2007) to obtain images with known ground truth, which is used exclusively at evaluation time. Note that we restrict our analysis to the single-object subset (100 natural images, 3 human ground-truth masks per image) and leave the two-object subset for future work. Experiments can be reproduced at: https://github.com/henriquepedro1991/hedonic-games-to-image-segmentation. Resolution Design. We extend the approach of Avrachenkov et al. (2018)—setting the resolution as the graph’s edge density—by proposing a scaling approach to evaluate varying density ratios: γ=density(G)c,density(G)=2|E||V|(|V|−1),γ= density(G)c, (G)= 2|E||V|(|V|-1), where c is a fixed constant. This normalization allows γ to act as a consistent local decision threshold across graphs of varying sparsity. Figure 4 highlights the key insights from our experiments (see Appendix B for additional details). Our numerical results identified c=900c=900 as the optimal value to place most instances in the fragmented-but-recoverable regime (Figure 4(a)). Across all images, we obtain [F1union]≈0.828E[F_1^union]≈ 0.828 (median ≈0.868≈ 0.868) and [F1single]≈0.488E[F_1^single]≈ 0.488, with an average gap [F1union−F1single]≈0.340E[F_1^union-F_1^single]≈ 0.340 (cf. Figure 4(b)). The significant average performance gap suggests that many apparent segmentation failures are actually fragmented, yet entirely recoverable, equilibria. Indeed, the partition produced by the hedonic mechanism often contains the object, but distributed across several coalitions. (a) (b) (c) (d) (e) 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 F1singleF_1^single at γ=7.63×10−6γ=7.63× 10^-6. (e) Best subset of communities selected by F1unionF_1^union at γ=2.96×10−5γ=2.96× 10^-5. (a) (b) Figure 4: (a) Mean F1singleF_1^single and F1unionF_1^union as a function of γ (induced by density(G)/900density(G)/900). (b) Global distributions of F1singleF_1^single and F1unionF_1^union over 100 images after selecting the best GT per image. 4 Conclusion We proposed image segmentation as an interpretable testbed for studying equilibrium in hedonic games. This spatial and visual setting makes equilibrium structures directly inspectable, providing an intuitive way to analyze how coalition mechanisms behave. In particular, it highlights how a resolution parameter reshapes equilibrium geometry in a visually grounded domain. Our results demonstrate that a density-normalized rule, γ=density(G)/cγ=density(G)/c, places most instances in favorable regimes by successfully preventing extreme over- or under-fragmentation (Appendix C). Appendix D reveals that a low F1union−F1singleF_1^union-F_1^single gap indicates either mutual success for cohesive structures or intrinsic failure for detailed objects. Appendix E confirms the robustness of the mechanism, demonstrating no difference in equilibrium accuracy whether initializing as a fragmenting grand coalition or as merging isolated nodes. Finally, Appendix F formalizes the computation of these binary projections and establishes the theoretical recoverability limits of F1unionF_1^union. Future work includes evaluating alternative graph constructions and the Weizmann two-object subset. We also aim to investigate the relationship between accuracy and resolution, focusing on merging fragmented but recoverable coalitions to reduce the gap between F1singleF_1^single and F1unionF_1^union. References S. Alpert, M. Galun, R. Basri, and A. Brandt (2007) Image segmentation by probabilistic bottom-up aggregation and CUE integration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Cited by: §1, §3, §3. K. E. Avrachenkov, A. Y. Kondratev, V. V. Mazalov, and D. G. Rubanov (2018) Network partitioning algorithms as cooperative games. Computational Social Networks 5 (1). External Links: Document Cited by: §1, §3. H. Aziz and R. Savani (2016) Hedonic games. In Handbook of Computational Social Choice, p. 356–376. Cited by: §2. A. Bogomolnaia and M. O. Jackson (2002) The stability of hedonic coalition structures. Games and Economic Behavior 38 (2), p. 201–230. Cited by: §1. J. Carreira and C. Sminchisescu (2011) CPMC: Automatic object segmentation using constrained parametric min-cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (7), p. 1312–1328. Cited by: Appendix A. P. Christen, D. J. Hand, and N. Kirielle (2023) A review of the f-measure: its history, properties, criticism, and alternatives. ACM Computing Surveys 56 (3), p. 1–24. Cited by: §3. L. L. Felipe, K. Avrachenkov, and D. S. Menasché (2025) From Leiden to Pleasure Island: The Constant Potts Model for community detection as a hedonic game. Physica A: Statistical Mechanics and its Applications, p. 130989. Cited by: §1, §1, §2, §2. S. Fortunato and M. Barthelemy (2007) Resolution limit in community detection. Proceedings of the national academy of sciences 104 (1), p. 36–41. Cited by: §2. Galun, Sharon, Basri, and Brandt (2003) Texture segmentation by multiscale aggregation of filter responses and shape elements. In Proceedings Ninth IEEE International Conference on Computer Vision, p. 716–723. Cited by: §1. H. Mittal, A. C. Pandey, M. Saraswat, S. Kumar, R. Pal, and G. Modwel (2022) A comprehensive survey of image segmentation: clustering methods, performance parameters, and benchmark datasets. Multimedia Tools and Applications 81 (24), p. 35001–35026. Cited by: §1. D. Monderer and L. S. Shapley (1996) Potential games. Games and economic behavior 14 (1), p. 124–143. Cited by: §2. J. Shi and J. Malik (1997) Normalized cuts and image segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), p. 731–737. Cited by: §1. V. A. Traag, P. Van Dooren, and Y. Nesterov (2011) Narrow scope for resolution-limit-free community detection. Physical Review E 84 (1), p. 016114. Cited by: §1, §2, footnote 2. V. A. Traag, L. Waltman, and N. J. van Eck (2019) From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9 (1), p. 5233. Cited by: footnote 2. Appendix A Pixel-Graph Construction Image Graph Partitioned Graph Segmented Image F1F_1 vs. GT Figure 5: Diagnostic pipeline: image → graph → hedonic partition → binary projection and evaluation. Recall that our pipeline is given by Figure 5. Next, we focus on the pixel-graph construction (Image → Graph). Each image is converted into an undirected weighted pixel graph G=(V,E,w)G=(V,E,w), where each pixel corresponds to a node and candidate edges connect spatially adjacent pixels under an 8-neighborhood system, including horizontal, vertical, and diagonal neighbors. Rather than using a binary adjacency rule based on exact intensity agreement, we assign each neighboring pair (u,v)(u,v) a continuous affinity weight that combines color similarity and boundary evidence. Let I(u)∈[0,255]3I(u)∈[0,255]^3 denote the RGB vector at pixel u, and let B:Ω→[0,1]B: →[0,1] be a normalized edge map used as a proxy for boundary probability. For each adjacent pair (u,v)(u,v), we define wuv=exp(−‖I(u)−I(v)‖22σcolor2)exp(−maxB(u),B(v)σedge2).w_uv= \! (- \|I(u)-I(v)\|_2^2 _color^2 ) \! (- \B(u),B(v)\ _edge^2 ). (3) In our implementation, B is obtained from a normalized Canny edge map, used as a lightweight proxy for contour strength rather than the original gPb detector. Thus, affinities are high when adjacent pixels have similar RGB values and low when they lie near strong image boundaries. Edges with very small affinity are discarded, yielding a sparse local graph. This construction biases the graph toward forming coalitions inside locally homogeneous color regions while reducing affinity across strong visual discontinuities. Consequently, the subsequent community-detection hedonic game is encouraged to group pixels within coherent regions and to place coalition boundaries near salient contours. Although this construction is inspired by pairwise affinity ideas used in graph-based segmentation, it is not a full CPMC (Carreira and Sminchisescu, 2011) formulation: unlike CPMC, we do not solve seeded constrained parametric min-cut problems. Instead, we use the resulting weighted pixel graph as input to the hedonic optimization described in Section 2. Note that for the qualitative visualizations in Fig. 2(b)-(c), the graphs were constructed using a downsampled version of the original image to ensure the nodes and edges remain discernible for the reader. However, all quantitative experiments and results reported in Section 3 were conducted using the original pixel-level resolution of the Weizmann dataset without any pre-processing or scaling. Appendix B Numerical Report We evaluate the proposed diagnostic framework on the Weizmann single-object subset, focusing on how the resolution parameter γ shapes equilibrium structure in hedonic coalition formation and how this structure is reflected by the complementary scores F1singleF_1^single and F1unionF_1^union. Our goal is to characterize equilibrium regimes and failure modes of the mechanism. Protocol and Ground-Truth Selection. Each image has three human ground-truth (GT) masks. For each GT we compute F1singleF_1^single and F1unionF_1^union, and then select, per image, the GT that maximizes F1unionF_1^union. We found low sensitivity to the choice of ground truth, as reported in Appendix E. Unless otherwise stated, we use the density-normalized resolution γ=density(G)/900γ=density(G)/900. Figure 4(a) reports the mean F1singleF_1^single and F1unionF_1^union over 100 images as a function of γ, while Figure 4(b) shows their global distributions. Regime Transitions. As shown in Figure 4(a), for γ<10−7γ<10^-7, F1singleF_1^single and F1unionF_1^union are close on average, indicating a cohesive regime in which the foreground typically appears as a single dominant coalition. As γ increases, the two curves separate: F1singleF_1^single decreases markedly, while F1unionF_1^union remains comparatively high over a broad interval. This gap characterizes a fragmented but recoverable regime, where the foreground is present in the partition but distributed across multiple coalitions. For larger γ, the behavior becomes more heterogeneous across images: F1unionF_1^union often remains high, while F1singleF_1^single becomes non-monotone, showing a partial rebound followed by a mild decline. This pattern is consistent with highly fragmented partitions in which the foreground can still be recovered by aggregating multiple coalitions, even though it rarely emerges as a single dominant one. Operationally, the pair (F1single,F1union)(F_1^single,F_1^union) distinguishes three broad situations: cohesive success (both high), recoverable fragmentation (large gap), and intrinsic failure (both low). Average Performance. Across all images, we obtain [F1union]≈0.828E[F_1^union]≈ 0.828 (median ≈0.868≈ 0.868) and [F1single]≈0.488E[F_1^single]≈ 0.488, with an average gap [F1union−F1single]≈0.340E[F_1^union-F_1^single]≈ 0.340 (cf. Figure 4(b)). This large systematic gap shows that many apparent failures under a dominant-coalition criterion arise from the difficulty of recomposing fragmented equilibria into a single binary mask. Qualitative extremes further clarify this interpretation: Appendix D contrasts a peak case, where both projections closely match the object, with a decay case, where even recoverable union cannot recover a good foreground mask. Robustness to Initialization. We repeat the protocol with two extreme initializations: singleton (each node starts alone) and one-coalition (all nodes start together), and observe negligible differences between them (Appendix E). We also analyze fragmentation via the number of communities K: K increases monotonically with γ, and high F1singleF_1^single occurs mainly at small K, whereas high F1unionF_1^union appears across a wide range of K. Additional diagnostics are provided in Appendix C. These regimes also suggest distinct failure modes. A large F1union−F1singleF_1^union-F_1^single gap indicates recoverable fragmentation, where the object is distributed across multiple coalitions. Cases where both scores are low are more consistent with intrinsic failure or background leakage, in which the partition itself does not support accurate figure–ground recovery even under recoverable recomposition. Appendix C Fragmentation Diagnostics This appendix provides detailed diagnostics relating fragmentation level, resolution, and performance. We begin by examining how the number of communities K produced by the hedonic optimization varies with the resolution parameter γ, as well as how overall F1F_1 scores depend on γ. Figure 6(a) shows K versus γ. While the scatter exhibits substantial dispersion, there is a positive upward trend: larger values of γ are associated, on average, with larger numbers of communities, indicating increasingly fragmented equilibrium partitions. Figure 6(b) shows F1F_1 versus γ. The plot suggests that F1unionF_1^union tends to attain higher and more stable values across the considered range of γ, whereas F1singleF_1^single is more dispersed and harder to predict. In particular, F1singleF_1^single typically takes lower values for intermediate values of γ, consistent with a fragmentation regime in which the foreground is split across multiple communities. (a) (b) Figure 6: Diagnostics as a function of the resolution parameter γ. (a) Fragmentation K vs. γ. (b) F1F_1 vs. γ. Orange points correspond to F1,unionF_1, union and blue points to F1,singleF_1, single. Next, we relate fragmentation directly to performance. Figure 7 shows F1F_1 versus the number of communities K. Values of F1singleF_1^single exhibit substantial dispersion and are strongly concentrated at small K, suggesting that dominant-coalition recovery typically requires low fragmentation and becomes unreliable as fragmentation increases. In contrast, high F1unionF_1^union values are observed across a wider range of K, indicating that the foreground can remain recoverable even when distributed across many communities. Figure 7: F1F_1 vs # of communities K. Orange and blue points correspond to F1,unionF_1, union and F1,singleF_1, single. Finally, Figure 8 shows the histogram of K over all images. The distribution suggests that the density-normalized choice γ=density(G)/cγ=density(G)/c places a substantial number of instances in an intermediate fragmentation regime, rather than at extreme values of very small or very large K. Figure 8: Global distribution of the number of communities K over 100 images. Appendix D Qualitative Extremes: Peak and Decay Cases To complement the aggregate trends reported in Section 3, we present two qualitative extremes that help interpret how the scores F1singleF_1^single and F1unionF_1^union arise in practice. We select one peak case, corresponding to the image with the highest F1unionF_1^union in the dataset, and one decay case, corresponding to the image with the lowest F1unionF_1^union. These examples clarify how the same multi-coalition mechanism can produce either highly recoverable partitions or severe failure under fragmentation and/or background leakage. In both cases, panels (a) and (b) show the original image and the selected ground-truth mask, respectively; panel (c) shows the best single-community projection associated with F1singleF_1^single, and panel (d) shows the recoverable union used to compute F1unionF_1^union. D.1 Peak case Figure 9 shows a representative case in which the partition aligns very well with the object. The best single coalition already captures most of the foreground, yielding F1single=0.9863F_1^single=0.9863, and the recoverable union provides only a marginal improvement, reaching F1union=0.9922F_1^union=0.9922. This is consistent with a cohesive regime in which the object emerges almost entirely as a single dominant coalition. (a) Original image (b) Selected ground truth (c) Best single coalition (d) Recoverable union Figure 9: Peak example: the partition aligns closely with the selected ground truth. The best single coalition already attains F1single=0.9863F_1^single=0.9863, while the recoverable union slightly improves performance to F1union=0.9922F_1^union=0.9922. D.2 Decay case Figure 10 shows the opposite extreme. Here the partition fails to produce a coalition that matches the object well, giving F1single=0.0370F_1^single=0.0370. Even after recoverable recomposition, the result remains poor, with F1union=0.2714F_1^union=0.2714. This case is representative of intrinsic failure under severe fragmentation and/or figure–ground mixing: the object is not cleanly represented in the partition, so even an optimistic oracle union cannot recover a high-quality binary mask. Taken together, these qualitative extremes reinforce the interpretation of the two-score diagnostic. In peak cases, both F1singleF_1^single and F1unionF_1^union are high, indicating that the foreground is well represented and largely cohesive in the partition. In decay cases, both scores are low, indicating that the limitation is not merely downstream recomposition, but rather the inability of the partition itself to represent the object cleanly under the chosen graph construction and resolution regime. (a) Original image (b) Selected ground truth (c) Best single coalition (d) Recoverable union 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.0370F_1^single=0.0370 and F1union=0.2714F_1^union=0.2714. Appendix E Sensitivity to Initialization and to Ground Truth Labels Figure 11 summarizes the F1F_1 distributions across all images for each ground truth under both initialization strategies. Recall that the dataset provides three ground truth labels. Each column of Figure 11 corresponds to the use of a different label. Each plot reports the distribution over 100 images, with the top row corresponding to F1singleF_1^single and the bottom row to F1unionF_1^union. Figure 11(a) shows the results obtained with singleton initialization (each node starts alone), while Figure 11(b) reports the one-coalition initialization (all nodes start together). We observe nearly identical distributions across both cases, indicating negligible sensitivity to initialization. (a) Singleton initialization. (b) One-coalition initialization. Figure 11: Violin plots over 100 images with γ=density(G)/900γ=density(G)/900. In each panel, the top row shows F1singleF_1^single and the bottom row shows F1unionF_1^union. Appendix F Details of Binary Projections and F1F_1 Computation This appendix provides a detailed mathematical specification of the binary projections F1singleF_1^single and F1unionF_1^union, as well as the underlying F1F_1 measure used throughout the paper. F1singleF_1^single (dominant coalition). Let ∈1,…,KH×WL∈\1,…,K\^H× W be the label image. For each community label k, define Y^k(p)=[(p)=k] Y_k(p)= 1[L(p)=k], and set F1single(Π)=maxkF1(Y^k,Y)F_1^single( )= _kF_1( Y_k,Y). This score measures whether the foreground object emerges as a single dominant coalition. F1unionF_1^union (recoverable union). Using the ground-truth mask only at evaluation time, we construct Y^S(p)=⋁k∈S[(p)=k] Y_S(p)= _k∈ S 1[L(p)=k] via a greedy forward pass that initializes S with the label attaining F1singleF_1^single, orders the remaining communities by their individual F1(Y^k,Y)F_1( Y_k,Y) scores, and then scans this list once, adding communities while their inclusion increases the current F1F_1 (with a cap on merged labels). The resulting score F1union(Π)=F1(Y^S,Y)F_1^union( )=F_1( Y_S,Y) upper-bounds how well the foreground can be recovered from the partition. F.1 Binary Masks and Pixel Sets Let the image domain be Ω=1,…,H×1,…,W =\1,…,H\×\1,…,W\. The ground-truth foreground mask is Y(p)∈0,1,p∈Ω,Y(p)∈\0,1\, p∈ , and the predicted community labeling is (p)∈1,…,K.L(p)∈\1,…,K\. For any binary mask B:Ω→0,1B: →\0,1\, define the corresponding foreground pixel set ℬ=p∈Ω:B(p)=1,=p∈Ω:Y(p)=1.B=\p∈ :B(p)=1\, =\p∈ :Y(p)=1\. F.2 Precision, Recall, and F1F_1 Given a predicted mask B, we define Precision(B,Y)=|ℬ∩||ℬ|,Recall(B,Y)=|ℬ∩|||.Precision(B,Y)= |B ||B|, (B,Y)= |B ||Y|. The F1F_1 score is the harmonic mean of precision and recall: F1(B,Y)=2Precision(B,Y)Recall(B,Y)Precision(B,Y)+Recall(B,Y)=2|ℬ∩||ℬ|+||.F_1(B,Y)= 2\,Precision(B,Y)\,Recall(B,Y)Precision(B,Y)+Recall(B,Y)= 2|B ||B|+|Y|. F.3 F1singleF_1^single: Dominant-Coalition Projection For each community label k, we define the induced binary mask Y^k(p)=[(p)=k],k=p:(p)=k. Y_k(p)= 1[L(p)=k], _k=\p:L(p)=k\. The dominant-coalition score is F1single(Π)=maxk∈1,…,KF1(Y^k,Y)=maxk2|k∩||k|+||.F_1^single( )= _k∈\1,…,K\F_1( Y_k,Y)= _k 2|C_k ||C_k|+|Y|. Thus, F1singleF_1^single measures whether there exists a single community whose pixels align well with the foreground object. F.4 F1unionF_1^union: recoverable union For any subset of labels S⊆1,…,KS \1,…,K\, define the union mask Y^S(p)=⋁k∈S[(p)=k],S=⋃k∈Sk. Y_S(p)= _k∈ S 1[L(p)=k], _S= _k∈ SC_k. The corresponding F1F_1 score is F1(Y^S,Y)=2|S∩||S|+||.F_1( Y_S,Y)= 2|U_S ||U_S|+|Y|. We construct S by a forward selection procedure that uses ground truth only at evaluation time: 1. Compute F1(Y^k,Y)F_1( Y_k,Y) for all labels k and sort labels in decreasing order of this score. 2. Initialize S with the label attaining F1,single(Π)F_1, single( ). 3. Scan the sorted list once and add a label k to S while F1(Y^S∪k,Y)>F1(Y^S,Y)F_1( Y_S∪\k\,Y)>F_1( Y_S,Y). The resulting score is F1union(Π)=F1(Y^S,Y).F_1^union( )=F_1( Y_S,Y). F1unionF_1^union approximates maxS⊆1,…,KF1(Y^S,Y), _S \1,…,K\F_1( Y_S,Y), which is the best achievable binary reconstruction from the given partition. F.5 Greedy Forward Procedure for Computing F1unionF_1^union Algorithm 2 summarizes the greedy forward procedure used throughout the paper to compute F1unionF_1^union. Starting from the best single community (the one attaining F1singleF_1^single), the method scans the remaining communities in decreasing order of their individual F1F_1 scores and adds a label only when its inclusion strictly improves the current union score. Input : Partition Π=C1,…,CK =\C_1,…,C_K\ (equivalently, label image L) Binary ground-truth mask Y∈0,1H×WY∈\0,1\^H× W Optional cap LmaxL_ on the number of merged labels Output : Selected label set S and score F1union(Π)=F1(Y^S,Y)F_1^union( )=F_1( Y_S,Y) 1 2Compute F1(Y^k,Y)F_1( Y_k,Y) for all k=1,…,Kk=1,…,K 3 Let k⋆∈argmaxkF1(Y^k,Y)k ∈ _kF_1( Y_k,Y) and initialize S←k⋆S←\k \ 4 Order the remaining labels k≠k⋆k≠ k by decreasing F1(Y^k,Y)F_1( Y_k,Y) 5 6foreach label k in the ordered list do 7 if LmaxL_ is specified and |S|=Lmax|S|=L_ then 8 break 9 10 if F1(Y^S∪k,Y)>F1(Y^S,Y)F_1( Y_S∪\k\,Y)>F_1( Y_S,Y) then 11 S←S∪kS← S∪\k\ 12 13 14 15return S and F1union(Π)=F1(Y^S,Y)F_1^union( )=F_1( Y_S,Y) 16 Algorithm 2 Greedy forward union used to compute F1unionF_1^union. F.6 Alternative Recoverable-Union Variant For completeness, Algorithm 3 presents a simple alternative union rule based on per-community overlap with the ground truth. Unlike the greedy forward procedure used for F1unionF_1^union, this variant evaluates each community independently and selects all labels whose individual overlap score exceeds a fixed threshold. We do not use this rule in the main experiments; it is included only to illustrate that multiple oracle-style unions are possible. Input : Partition Π=C1,…,CK =\C_1,…,C_K\ Binary ground-truth mask Y∈0,1H×WY∈\0,1\^H× W Overlap threshold τ∈[0,1]τ∈[0,1] Output : Selected label set S and union mask Y^S Y_S 1 2S←∅S← 3 4for k∈1,…,Kk∈\1,…,K\ do 5 Compute the individual overlap score of CkC_k with Y 6 if F1(Y^k,Y)>τF_1( Y_k,Y)>τ then 7 S←S∪kS← S∪\k\ 8 9 10 11return S and Y^S(p)=⋁k∈S[(p)=k] Y_S(p)= _k∈ S 1[L(p)=k] 12 Algorithm 3 Threshold-based recoverable union as an alternative oracle variant. F.7 Interpreting the Gap Between F1singleF_1^single and F1unionF_1^union • Small gap: foreground appears largely as a single coalition. • Large gap: foreground is distributed across several communities (fragmentation). • Both small: intrinsic failure (object not represented well in partition). Hence, the pair (F1single,F1union)(F_1^single,F_1^union) disentangles failures due to coalition structure from failures due to downstream binary projection. F.8 Toy Example: Dominant Coalition vs. Recoverable Union Consider an image with ||=100|Y|=100 foreground pixels and three communities C1,C2,C3C_1,C_2,C_3 with the following spatial overlaps: |1|=40,|2|=35,|3|=50,|C_1|=40, |C_2|=35, |C_3|=50, |1∩|=30,|2∩|=25,|3∩|=10.|C_1 |=30, |C_2 |=25, |C_3 |=10. Single-community scores. F1(C1)=2⋅3040+100=0.43,F1(C2)=2⋅2535+100=0.37,F1(C3)=2⋅1050+100=0.13.F_1(C_1)= 2· 3040+100=0.43, F_1(C_2)= 2· 2535+100=0.37, F_1(C_3)= 2· 1050+100=0.13. Thus, F1single=0.43.F_1^single=0.43. Union of communities. Let S=1,2S=\1,2\. Then |S|=75,|S∩|=55.|U_S|=75, |U_S |=55. F1(Y^S,Y)=2⋅5575+100=0.63.F_1( Y_S,Y)= 2· 5575+100=0.63. Hence, F1union=0.63>F1single.F_1^union=0.63>F_1^single. This example illustrates a fragmented-but-recoverable situation: no single community captures the object well, yet combining two communities yields good foreground reconstruction. F.9 Relation to Figure 3 The behavior visualized in Figure 3 corresponds to the label selection described in this section. In Figure 3(c), F1singleF_1^single selects the single community with the highest individual F1F_1 score. The F1unionF_1^union mask is formed by the greedy forward union described above, which aggregates communities whose addition improves the current F1F_1 score. This captures the entire object by aggregating the multiple fragments that individually correspond to parts of the foreground (e.g., S=1,2S=\1,2\ in the toy example), without requiring an iterative optimization search. F.10 When the Recoverable-Union Can Be Suboptimal The recoverable-union procedure is a heuristic for approximating maxS⊆1,…,KF1(Y^S,Y), _S \1,…,K\F_1( Y_S,Y), which is combinatorial in K. As with many subset-selection methods, optimality is not guaranteed. A typical failure mode occurs when two communities are individually weak predictors of the foreground but jointly complementary. For example, two communities may each cover disjoint halves of the object while also containing substantial background. Individually, neither improves F1F_1 enough to be selected, but together they would yield a strong score. Formally, the forward selection can fail when F1(Y^i,Y)≤F1(Y^S,Y)andF1(Y^j,Y)≤F1(Y^S,Y),F_1( Y_\i\,Y)≤ F_1( Y_S,Y) F_1( Y_\j\,Y)≤ F_1( Y_S,Y), but F1(Y^S∪i,j,Y)≫F1(Y^S,Y).F_1( Y_S∪\i,j\,Y) F_1( Y_S,Y). Exact subset search would recover i,j\i,j\, while forward selection would stop early. In practice, this pathology is rare in our setting because foreground fragments tend to have nontrivial individual spatial overlap with the object, making them attractive early additions. F.11 How Large Can the Gap F1union−F1singleF_1^union-F_1^single Be? In the worst case, the gap between F1unionF_1^union and F1singleF_1^single can be arbitrarily large. Consider an object split evenly across M disjoint communities, each containing exactly 1M|| 1M|Y| foreground pixels and no background. Then, for each community k, F1(Y^k,Y)=2⋅1M||1M||+||=2M+1.F_1( Y_\k\,Y)= 2· 1M|Y| 1M|Y|+|Y|= 2M+1. Thus, F1single=2M+1.F_1^single= 2M+1. If we union all M communities, we recover the full object: F1(Y^1,…,M,Y)=1,F1union=1.F_1( Y_\1,…,M\,Y)=1, _1^union=1. Hence, F1union−F1single=1−2M+1,F_1^union-F_1^single=1- 2M+1, which approaches 11 as M→∞M→∞. This construction demonstrates that a very low F1singleF_1^single does not necessarily indicate failure of coalition formation: it may simply reflect extreme fragmentation of an otherwise perfectly recoverable object. In contrast, small gaps between F1singleF_1^single and F1unionF_1^union indicate that even multi-coalition recomposition cannot recover the foreground, pointing to intrinsic failure modes such as background leakage or poor boundary placement. The pathological lower bound for F1singleF_1^single, under perfect recoverability, is formalized through the following proposition: Proposition 1 (Arbitrarily small F1singleF_1^single with F1union=1F_1^union=1). For any integer M≥1M≥ 1, there exists a partition Π=C1,…,CM =\C_1,…,C_M\ and a binary ground-truth mask Y such that F1union(Π)=1andF1single(Π)=2M+1.F_1^union( )=1 _1^single( )= 2M+1. Consequently, F1union(Π)−F1single(Π)=1−2M+1,F_1^union( )-F_1^single( )=1- 2M+1, which can be made arbitrarily close to 11 by taking M large. Proof sketch. Let Y contain |||Y| foreground pixels. Construct M disjoint communities C1,…,CMC_1,…,C_M such that each CkC_k contains exactly ||/M|Y|/M foreground pixels and no background pixels. Then for every k, TPk=||M,FPk=0,FNk=||−||M.TP_k= |Y|M, _k=0, _k=|Y|- |Y|M. Substituting into the F1F_1 identity F1=2TP2TP+FP+FNF_1= 2TP2TP+FP+FN gives F1(Y^k,Y)=2M+1F_1( Y_\k\,Y)= 2M+1, hence F1single(Π)=2M+1F_1^single( )= 2M+1. Moreover, the union Y^1,…,M Y_\1,…,M\ equals Y, so F1(Y^1,…,M,Y)=1F_1( Y_\1,…,M\,Y)=1. Since F1unionF_1^union is defined by a union-based projection, F1union(Π)=1F_1^union( )=1. ∎