论文标题
图表上公共物品游戏的复杂性
Complexity of Public Goods Games on Graphs
论文作者
论文摘要
我们研究“网络上的公共产品游戏”的计算复杂性。在此模型中，图中的每个顶点都是一个代理，需要做出是否“产生好”的二进制决策。每个代理商的实用程序都取决于图表中产生良好的邻居数量以及自己的动作。可以通过“模式” $ t：{\ rm i \！n} \ rightArrow \ {0,1 \} $捕获这种依赖性，该\ rightarrow \ {0,1 \} $描述了代理商对产生商品的每个可能数量的邻居的最佳响应。回答[Papadimitriou and Peng，2021]的问题，我们证明，对于某些简单的模式$ t $，确定非平凡的纯nash平衡是否存在NP完整的问题。我们将结果扩展到了如此宽的这样的$ T $，但也为某些特定的简单模式$ t $找到了一种新的多项式时间算法。我们打开目标，以表征所有模式的复杂性。
We study the computational complexity of "public goods games on networks". In this model, each vertex in a graph is an agent that needs to take a binary decision of whether to "produce a good" or not. Each agent's utility depends on the number of its neighbors in the graph that produce the good, as well as on its own action. This dependence can be captured by a "pattern" $T:{\rm I\!N}\rightarrow\{0,1\}$ that describes an agent's best response to every possible number of neighbors that produce the good. Answering a question of [Papadimitriou and Peng, 2021], we prove that for some simple pattern $T$ the problem of determining whether a non-trivial pure Nash equilibrium exists is NP-complete. We extend our result to a wide class of such $T$, but also find a new polynomial time algorithm for some specific simple pattern $T$. We leave open the goal of characterizing the complexity for all patterns.
