论文标题
关于二进制网络公共物品游戏的参数化复杂性
On Parameterized Complexity of Binary Networked Public Goods Game
论文作者
论文摘要
在二进制网络的公共物品游戏中，每个玩家都需要决定她是否参与了一个公共项目，该项目的实用程序是由社区平等共享的。我们研究了决定是否存在此类游戏中是否存在纯粹的策略NASH平衡（PSNE）的问题。该问题已经众所周知是NP完整的。我们在参数化复杂性理论的镜头下提供了对该问题的细粒分析。我们考虑各种自然图参数，并显示W [1] - hard度或表现出FPT算法。我们最终展示了一些特殊的图形类别，例如路径，周期，双关键，完整的图表，如果玩家的效用函数完全均匀，它们总是具有PSNE。
In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show either W[1]-hardness or exhibit an FPT algorithm. We finally exhibit some special graph classes, for example path, cycle, bi-clique, complete graph, etc., which always have a PSNE if the utility function of the players are fully homogeneous.
