Optimal Targeting in Super-Modular Games

• 成果类型: Article
• 署名作者: Como, Giacomo; Durand, Stephane; Fagnani, Fabio
• 署名单位: Polytechnic University of Turin; Lund University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3129733
• 发表日期: 2022
• 页码: 6366-6380
• 关键词: Nash equilibrium selection; Network games; Network intervention; Optimal targeting; Strategic complements; super-modular games

摘要

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 for its solution with provable probabilistic convergence properties. We discuss in detail the special case of network coordination games and its relation with the graph-theoretic notion of cohesiveness. Finally, through numerical simulations we compare the efficacy of our approach with respect to naive heuristics based on classical network centrality measures.