Relational and Weighted Cost-Relational Cooperative Games for Influencer Coalition Optimization in Environmental Sustainability: Algorithms, Complexity, and Cost Efficiency

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.