Scholarlink

<p>This paper proposes a practical framework that integrates deterministic synchronous value iteration with the theory of simple cooperative games to form minimal winning influencer coalitions in online social networks. The approach casts coalition building as a deterministic Markov decision process (MDP) whose terminal rewards are governed by a simple game characteristic function. A compact three-component state representation (coalition size, discretized reach, terminal flag) and three primitive actions (Add, Boost, Ignore) keep the state space finite, enabling exact value iteration with guaranteed convergence. To bridge the gap between the abstract MDP and real-world influencer data, where marginal reach increments depend on coalition composition, not merely on size, we introduce a fixed-order construction. A single greedy sequence of influencers is pre-computed once on the true follower-overlap data, and the Add action always selects the next influencer in that sequence; the marginal reach values fed into the MDP are then exact by construction, eliminating the need for instance-by-instance calibration. The learned optimal deterministic policy constructs a minimal winning coalition, and a subsequent local-search procedure refines it to a local optimum with respect to net follower reach without compromising minimality. We prove that value iteration converges to the unique optimal Q-function, that the extracted coalition is indeed minimal winning, and that the local search terminates at a locally optimal solution. The NP-hardness of finding a minimal winning coalition of maximum reach is established, justifying the heuristic nature of the reach improvement. For practitioners who prefer to retain compositional flexibility, a stochastic MDP variant that relaxes the fixed-order assumption is also outlined. Experiments on synthetic networks demonstrate that the local optimum coincides with the global optimum in all small instances, while the algorithm scales efficiently. The work delivers a production-ready framework for influencer marketing campaign design that bridges a previously unexplored gap between planning algorithms and cooperative game theory.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Integrated value iteration and simple games enable calibrated strategic coalition formation in social networks

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月27日

查看全文
  • Duc Nghia Vu,
  • Janos Demetrovics,
  • Duc Thi Vu

摘要

This paper proposes a practical framework that integrates deterministic synchronous value iteration with the theory of simple cooperative games to form minimal winning influencer coalitions in online social networks. The approach casts coalition building as a deterministic Markov decision process (MDP) whose terminal rewards are governed by a simple game characteristic function. A compact three-component state representation (coalition size, discretized reach, terminal flag) and three primitive actions (Add, Boost, Ignore) keep the state space finite, enabling exact value iteration with guaranteed convergence. To bridge the gap between the abstract MDP and real-world influencer data, where marginal reach increments depend on coalition composition, not merely on size, we introduce a fixed-order construction. A single greedy sequence of influencers is pre-computed once on the true follower-overlap data, and the Add action always selects the next influencer in that sequence; the marginal reach values fed into the MDP are then exact by construction, eliminating the need for instance-by-instance calibration. The learned optimal deterministic policy constructs a minimal winning coalition, and a subsequent local-search procedure refines it to a local optimum with respect to net follower reach without compromising minimality. We prove that value iteration converges to the unique optimal Q-function, that the extracted coalition is indeed minimal winning, and that the local search terminates at a locally optimal solution. The NP-hardness of finding a minimal winning coalition of maximum reach is established, justifying the heuristic nature of the reach improvement. For practitioners who prefer to retain compositional flexibility, a stochastic MDP variant that relaxes the fixed-order assumption is also outlined. Experiments on synthetic networks demonstrate that the local optimum coincides with the global optimum in all small instances, while the algorithm scales efficiently. The work delivers a production-ready framework for influencer marketing campaign design that bridges a previously unexplored gap between planning algorithms and cooperative game theory.