Cluster-Based Q-Learning Relational Game (C-QLRG): A Practical Relaxation for Asymmetric Online Social Networks

The Q-Learning Relational Game (QLRG) framework provides a theoretically rigorous method for identifying minimal winning coalitions in online social networks (OSNs) under the restrictive assumption of global agent symmetry or uniform matroid structure. Real-world OSNs, however, exhibit significant asymmetry. This paper introduces the Cluster-Based Q-Learning Relational Game (C-QLRG), a practical extension that relaxes the global symmetry requirement by leveraging community structure. We partition the agent set into communities with bounded internal variation and represent the state solely by community membership counts of the seed set. Because the closure operator already captures all eventual influence spread, the problem reduces to a sequential seed selection task where the agent decides, at each step, from which community to add the next seed. We prove that the optimal Q-function of a suitably regularized reach-efficiency objective is Lipschitz continuous and derive a performance bound for the learned policy. The full algorithm is presented, and its complexity is analyzed. Empirical evaluations on a synthetic asymmetric network and Zachary’s Karate Club demonstrate that C-QLRG is highly sensitive to reward parameters, where default settings lead to premature stopping, but parameter tuning combined with a corrected minimality verification recovers high-efficiency coalitions by removing non-contributing agents. With tuned parameters, C-QLRG produces a near-winning coalition of size 11 and 99% reach on the synthetic network, surpassing the greedy baseline’s efficiency (size 12) despite a one-node coverage gap, while identifying the optimal winning coalition of size 1 on the Karate Club dataset, matching all baselines. The framework thus offers a principled trade-off between model fidelity and scalability, with the reward design choice being critical for practical deployment.