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(2ⁿ) to O(n²) through a sufficient statistic representation based on coalition size, follower reach, and terminal status, while achieving O(n⁴) 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 ${\displaystyle \frac{{\epsilon }_i}{1-\gamma }}$, 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.

Cooperating game theory is becoming increasingly popular in AI, data science, and game theory applications in sharing and circular economy. Social media shows us the impact of many influencers on millions (even hundreds of millions) of followers, which raised the need to have a new model of coalition game, in which the influence or dependence of players on others are not equal, some have more than others. In this paper, we introduce a relational dependency game with new properties of minimal winning coalitions and maximal losing coalitions and their in-depth relationship with different approaches from simple games. In this new model, unlike simple games, all winning coalitions have the same payoff but losing coalitions have different payoffs, which coincides with Leo Tolstoy’s philosophy: all happy families are alike, but each unhappy family is unhappy in its way. The algorithm to find a minimal winning coalition among maximal losing coalitions is addressed in this paper. In this new model, unlike a simple game, we present the relational dependency coalition game model in which players depend on or do not depend on one another when they share a common interest in achieving a specific goal or outcome. The players must find a minimal winning coalition on which all players of the game depend on achieving the highest payoff. Closure operations and choice functions arise naturally in this game when there is a one-to-one correspondence between the winning coalition/losing coalition and the closure operation/choice function. And the game becomes more complex when relational independence lives with dependency among players. How to have a structural representation of relational independence along with dependency and how to describe a minimal winning collation on a simple hypergraph is also addressed in the paper.

Peri-urban agriculture (PA) offers significant social, economic, and environmental benefits but also presents challenges. By leveraging opportunities and addressing challenges, PA can become more sustainable. In tropical regions, integrating high-value crops such as coffee and rubber into forest garden models could support PA. Expanding High-Value Intercropping Forest Garden (HIFG) synergies into a multi-farmer coalition of pesticide-free coffee, pesticide-free rubber, and free-range chicken farmers can enhance resource sharing and waste management, improving sustainability and efficiency. This study examines the evolutionary game dynamics of a four-party cooperation model, involving the local government and three smallholder farmers (CFA: Coffee family A, RFB: Rubber family B, and CFC: Chicken family C). The aim is to optimize resource sharing and waste management to increase efficiency and reduce waste. We develop a multifaceted evolutionary game model to analyze stakeholder behaviors under government incentives. Stability analysis identifies Evolutionarily Stable Strategies (ESSs) within this framework. MATLAB simulations, based on HIFG data from Vietnam’s central highlands, validate the results. Our findings highlight the importance of government support, subsidies, and the costs incurred in resource sharing and waste management. These factors are key to achieving a stable equilibrium and promoting sustainable farming. The research emphasizes the role of government policies in fostering cooperation, resource optimization, and waste reduction, ultimately contributing to a more efficient and resilient agricultural supply chain. The paper concludes with recommendations to strengthen resource sharing and circular economy practices in urban agriculture, advancing the Sustainable Development Goals (SDGs).

The collaboration between celebrities, macro-influencers, and micro-influencers plays a pivotal role in amplifying the effectiveness and longevity of environmental sustainability messages. This study introduces the concept of a minimal coalition of influencers capable of efficiently promoting a sustainability message to the public. To address this, we propose a novel framework for Approximate Relational Games (ARG), which quantifies the degree of dependency of a follower on an influencer through a Dependency Decision Table (DDT). The DDT tracks follower reactions, categorized as “Like only” or “Like and Share”, across a series of posts by the influencer. By setting a threshold for the degree of dependency, we focus on followers with stronger relational dependencies, eliminating those with weaker associations. This method enables the identification of a minimal winning coalition of influencers who can effectively disseminate the sustainability message despite resource constraints, both financial and non-financial. Utilizing combinatorial tools such as closure operators and choice functions, we present a method for determining minimal winning coalitions with polynomial time complexity. This approach offers a cost-effective solution for green organizations and governments aiming to maximize the impact of their campaigns. To validate the proposed model and algorithms, we conduct Python-based simulations using data from five real-world Facebook influencers, both macro and micro-tier, complemented by manual calculations. The results demonstrate the efficacy and computational efficiency of the proposed framework in optimizing influencer marketing strategies for promoting environmental sustainability.

This paper addresses the critical challenge of identifying cost-effective coalitions of social media influencers to promote environmental sustainability (ES) messages under budget constraints. Traditional influencer marketing often relies on heuristics that ignore relational dependencies and heterogeneous agent costs, leading to redundant coverage and suboptimal resource allocation. To overcome these limitations, we introduce a novel Relational Cooperative Game (RG) framework that formalizes pre-determined dependencies among influencers and followers using closure operators, enabling a portfolio of polynomial-time identification algorithms for Minimal Winning Coalitions (MWCs). We further extend this model to the Weighted Cost-Relational Game (WCRG) to optimize campaigns with heterogeneous influencer costs. We prove that finding a Minimum-Cost Winning Coalition (MCWC) is NP-hard via reduction from weighted set cover and propose two complementary algorithms: (1) a Greedy Cost–Benefit (GCB) algorithm that operates in polynomial time and empirically achieves optimal solutions across all tested instances; a logarithmic approximation guarantee is established for the restricted single-antecedent model; and (2) an Integer Linear Programming (ILP) formulation enhanced with Strongly Connected Component (SCC) preprocessing to handle cyclic dependencies and yield exact optimal solutions for moderate instances. Extensive empirical validation, ranging from a representative six-agent cyclic scenario to large-scale synthetic networks (up to 300 agents), confirms the framework’s robustness and scalability. Results demonstrate that GCB consistently achieves optimal solutions (approximation ratio = 1.000×) with subsecond runtime (<0.2 s) and minimal memory overhead (<50 MB), while ILP-SCC leverages graph condensation for rapid exact solving. Compared to size-based baselines, WCRG achieves up to 95.2% cost savings by systematically leveraging cost-efficient micro-influencers, empirically validating that minimizing coalition size does not guarantee cost efficiency. These findings establish WCRG as a scalable, budget-aware optimization toolkit for maximizing the impact of sustainability campaigns through relational coalition design.