论文标题
超模型游戏的最佳目标
Optimal Targeting in Super-Modular Games
论文作者
论文摘要
我们研究具有二元动作和许多玩家有限的超模型游戏的最佳目标问题。所考虑的问题在于选择最小尺寸的球员的子集，以便当这些玩家的动作被迫获得受控的值时，而其他玩家的行动被迫反复发挥最佳响应动作时，系统将融合到游戏的最大NASH平衡。我们的主要贡献包括表明该问题是NP完整的，并提出了具有可证明的收敛性能的有效迭代算法。我们详细讨论网络协调游戏的特殊情况及其与凝聚力概念的关系。最后，我们通过模拟基于经典网络中心度度量的幼稚启发式方法来显示我们方法的强度。
We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm with provable convergence properties for its solution. We discuss in detail the special case of network coordination games and its relation with the notion of cohesiveness. Finally, we show with simulations the strength of our approach with respect to naive heuristics based on classical network centrality measures.
