Deterministic Q-Learning with Relational Game Theory: Polynomial-Time Convergence to Minimal Winning Coalitions in Symmetric Influence Networks and Extension

This paper presents a theoretically grounded integration of deterministic Q-learning with relational game theory (QLRG) for efficiently identifying minimal winning coalitions in Online Social Networks (OSNs). We address the fundamental challenge that coalition formation is NP-hard under traditional approaches by leveraging structural properties of relational dependencies and Armstrong’s axioms to transform the problem into one solvable in polynomial time. Our framework reduces the state space from exponential O(2n) to O(n2) through a sufficient statistic representation based on coalition size, follower reach, and terminal status, while achieving O(n4) time complexity under deterministic, static, and sufficiently symmetric influence structures. The QLRG framework introduces three critical innovations: (1) a principled agent selection mechanism derived directly from the Q-function that eliminates heuristic weight tuning; (2) a formal Boost action defined through temporal closure operators that captures influence spread dynamics; and (3) a constrained MDP formulation that enforces relational consistency through action elimination rather than penalty terms. We prove that the Bellman optimality operator forms a contraction mapping, guaranteeing deterministic convergence to optimal policies with established rates of O(1/√k) for decreasing learning rates or linear convergence up to bias for constant rates. To bridge the gap between this idealized model and the asymmetry inherent in real OSNs, we further develop a cluster-based sufficient statistics approach. By partitioning the network into communities with bounded internal variation, we relax the global symmetry requirement while preserving polynomial state space complexity, and obtaining a single within-community swap changes the optimal Q-value by at most εi1−γ, which is a local Lipschitz continuity result. The implications of this are both theoretical and practical, and they form the bedrock for relaxing the global symmetry assumption in the QLRG framework. Empirical validation on synthetic networks satisfying the symmetry assumption demonstrates that QLRG consistently identifies minimal winning coalitions matching the optimal solutions found by exhaustive search, while operating with polynomial-time complexity. Unlike conventional approaches, our framework simultaneously satisfies four critical properties: deterministic convergence, policy optimality, minimal coalition identification, and computational tractability. The work bridges computational social science and operations research, providing a mathematically rigorous foundation for strategic decision-making in influencer marketing and coalition formation. While the framework requires symmetry assumptions that may only hold approximately in real-world OSNs, it establishes an idealized baseline for future extensions addressing stochasticity, dynamics, and partial observability. This research represents a paradigm shift from empirical improvements to theoretically grounded convergence guarantees for coalition formation problems, demonstrating how structural mathematical insights can transform intractable problems into efficiently solvable ones without sacrificing solution quality.