论文标题
在二进制网络的公共物品游戏中，利他主义
On Binary Networked Public Goods Game with Altruism
论文作者
论文摘要
在古典二进制网络公共产品（BNPG）游戏中，玩家可以投资公共项目或决定不投资。根据所有球员的决定，每个球员都根据其公用事业功能获得奖励。但是，BNPG游戏的经典模型并不考虑玩家经常表现出来的利他主义，并且会显着影响平衡行为。 Yu等。 （2021）扩展了古典BNPG游戏，以捕捉玩家的利他方面。在本文中，我们首先研究了在具有利他主义的BNPG游戏中确定纯粹策略nash平衡（PSNE）的问题。该问题已经众所周知是NP完成。我们通过证明该问题在输入网络是树或完整的图表时接受有效的算法来补充这种硬度结果。我们进一步研究了利他主义网络修改问题，在该问题中，任务是通过添加或删除一些边缘来计算目标策略概况是否可以成为PSNE。该问题也已知NP完整。我们通过表现出难以理解的结果，即使是树木也可以增强这种硬度。我们工作的一个也许令人惊讶的发现是，即使在利他主义网络无方向性时，对于有限度图，上面的问题仍然是np-hard，但是当有利他主义网络被指向时，可以解决多项式时间。我们还显示了计算MSNE和一些参数化复杂性结果的一些结果。总而言之，我们的结果表明，与BNPG游戏中的玩家如何以理想的方式行事相比，预测BNPG游戏中的玩家的行为方式要容易得多。
In the classical Binary Networked Public Goods (BNPG) game, a player can either invest in a public project or decide not to invest. Based on the decisions of all the players, each player receives a reward as per his/her utility function. However, classical models of BNPG game do not consider altruism which players often exhibit and can significantly affect equilibrium behavior. Yu et al. (2021) extended the classical BNPG game to capture the altruistic aspect of the players. We, in this paper, first study the problem of deciding the existence of a Pure Strategy Nash Equilibrium (PSNE) in a BNPG game with altruism. This problem is already known to be NP-Complete. We complement this hardness result by showing that the problem admits efficient algorithms when the input network is either a tree or a complete graph. We further study the Altruistic Network Modification problem, where the task is to compute if a target strategy profile can be made a PSNE by adding or deleting a few edges. This problem is also known to be NP-Complete. We strengthen this hardness result by exhibiting intractability results even for trees. A perhaps surprising finding of our work is that the above problem remains NP-Hard even for bounded degree graphs when the altruism network is undirected but becomes polynomial-time solvable when the altruism network is directed. We also show some results on computing an MSNE and some parameterized complexity results. In summary, our results show that it is much easier to predict how the players in a BNPG game will behave compared to how the players in a BNPG game can be made to behave in a desirable way.
