Computer scientists have introduced a continuous valuation framework for relational dependency coalitional games, moving beyond conventional binary classifications of winning and losing coalitions. In relational dependency coalitional games, coalition formation models multi-agent collaboration where interactions and dependencies among participating agents are dictated by relational database constraints. Historically, these systems evaluated coalitions through simple binary models that treated coalitions strictly as winning or losing based on superkey properties, which failed to reflect partial information gain across noisy or incomplete decision data.
To overcome the limitations of rigid binary assessments, the researchers formulated a continuous valuation structure rooted in rough set theory. Within this mathematical architecture, the characteristic function is directly defined as the quality of classification derived from tuple agree sets. Theoretical analysis confirmed that this valuation is monotonic, guaranteeing that expanding a coalition does not diminish its overall formal evaluation score within the relational structure.
The study further revealed that this rough set valuation is not universally submodular. By establishing an explicit XOR-style counterexample, the researchers demonstrated that submodular properties do not hold in general relational settings, although they successfully delineated a restricted coverage-separability condition under which submodularity is preserved.
Building upon the continuous valuation function, the authors constructed a comprehensive dynamic programming framework designed to evaluate multiple coalition structure generation algorithms. The framework benchmarked Exact DP, which deliberately disables heuristic pruning to establish a certified reference welfare, alongside DP-AB, an ablated dynamic programming variant equipped with caching and heuristic singleton-sum pruning to optimize computational resource usage.
To address computational scaling, the researchers also examined heuristic optimization techniques, focusing on SG-CSG and its enhanced counterpart SG-CSG+. SG-CSG operates as a polynomial-time pairwise greedy heuristic, whereas SG-CSG+ expands search capabilities through triple-merge lookahead and random restarts. In benchmark evaluations against toy, synthetic, and real-world decision tables, SG-CSG secured high welfare in environments characterized by low-order dependency structures but struggled when positive coalition value emerged exclusively from higher-order coalitions. The extended SG-CSG+ algorithm successfully mitigated this limitation on high-synergy synthetic instances.
Empirical testing across standard datasets, including Play Tennis, Iris, and the 13-attribute UCI Wine dataset, confirmed the practical behavior, scalability, and interpretability of the model. Evaluated alongside external generic baselines such as LS-CSG and SA-CSG, the mid-scale Wine dataset functioned as a rigorous stress-test for heuristic escape capabilities and the scalability limits of Exact DP. The complete simulation environment, including reproduction code, experimental output, and metadata, was documented in a unified supplemental simulation.
In relational dependency coalitional games, agent interactions correspond to relational database constraints evaluated across decision tables. Defining the characteristic function through rough set classification quality over tuple agree sets enables the framework to capture incremental information gain.
The identified coverage-separability condition outlines the precise boundary where submodularity is preserved.
Subject of Research: Coalition structure generation in relational dependency coalitional games using rough set theory
Article Title: Continuous Coalition Structure Generation in Relational Dependency Games via Rough Set Valuation and Agree Sets
Article References: Vu, D. N., Demetrovics, J., & Vu, D. T. (2026). Continuous Coalition Structure Generation in Relational Dependency Games via Rough Set Valuation and Agree Sets. International Journal of Computational Intelligence Systems. https://doi.org/10.1007/s44196-026-01637-w
Image Credits: AI Generated
DOI: 10.1007/s44196-026-01637-w
Keywords: relational dependency games, coalition structure generation, rough set theory, agree sets, quality of classification, monotonicity, submodularity, dynamic programming, Exact DP, DP-AB, SG-CSG, SG-CSG+, greedy heuristics, decision tables, UCI Wine dataset, Iris dataset
News Source: Denise Maddox. (November 20, 2026). Continuous Rough Set Valuation Enables Dynamic Coalition Formation in Relational Games. Scienmag.



