论文标题
对二元网络公共产品游戏复杂性的精致研究
A Refined Study of the Complexity of Binary Networked Public Goods Games
论文作者
论文摘要
我们研究了二进制网络公共物品游戏模型中几个组合问题的复杂性。在这个游戏中，玩家在网络中以顶点为代表，每个玩家的行动可以投资或不投资公共利益。每个球员的回报取决于投资和自己行动的邻居人数。我们研究了NASH均衡的计算行动曲线的复杂性，以及提供最大功利或平等社会福利的那些计算概况。我们表明，这些问题通常是NP-固定的，但是当给定网络仅限于某些特殊域，包括具有恒定有界树宽的网络，以及那些关键的集团图是森林的网络时，可以将其变为多项式时间。
We study the complexity of several combinatorial problems in the model of binary networked public goods games. In this game, players are represented by vertices in a network, and the action of each player can be either investing or not investing in a public good. The payoff of each player is determined by the number of neighbors who invest and her own action. We study the complexity of computing action profiles that are Nash equilibrium, and those that provide the maximum utilitarian or egalitarian social welfare. We show that these problems are generally NP-hard but become polynomial-time solvable when the given network is restricted to some special domains, including networks with a constant bounded treewidth, and those whose critical clique graphs are forests.
