Social network games

Social network games
复制标题

社交网络游戏

DOI：
--
复制
发表时间：
2012
期刊：
Journal of Logic and Computation
影响因子：
0.7
通讯作者：
K. Apt
K. Apt
中科院分区：
计算机科学4区
文献类型：
--
作者：
Sunil Simon;K. Apt

文献摘要

被引文献

相似文献

htmlabstr社交网络领域的自然目标之一是 预测代理人的行为。为了更好地了解各种 通过社交网络的产品[2]引入了阈值模型， 受其邻居影响的节点可以采用七个中的一个， 其他的选择。分析这种产品采用的后果 我们在这里将每一个这样的社交网络与一个自然的战略游戏联系起来， 在特工之间。 在这些博弈中，每个参与人的收益都有微弱的增加， 博弈者选择他的策略，这与拥挤度正好相反 平板电脑设备.不选择任何产品的可能性导致两个特殊的 纳什均衡（Nash equilibrium） 我们证明了这样的博弈可能没有纳什均衡， 确定纳什均衡的存在性，也是一种特殊类型， 是NP完全的。这意味着对于更一般的类也有同样的结果 即多矩阵博弈。情况发生了变化， 社交网络的底层图是一个DAG，一个简单的循环，或者更多 通常没有源节点。对于这三个类，我们确定 纳什均衡存在的复杂性。 我们还澄清了这些类别的游戏的地位和COM- 有限最佳响应特性（FBRP）和有限阻抗的复杂性， 证明性质（FIP）。此外，我们引入了一个新的性质， 一致FIP，当底层图是一个简单的环时， cle，但在一般情况下确定它是co-NP-hard的，并且当 底层图没有源节点。后者的复杂性导致 也成立的性质是一个弱非循环的游戏。初步 这篇文章的版本是[19]。
htmlabstractOne of the natural objectives of the field of the social networks is to predict agents’ behaviour. To better understand the spread of various products through a social network [2] introduced a threshold model, in which the nodes influenced by their neighbours can adopt one out of sev- eral alternatives. To analyze the consequences of such product adoption we associate here with each such social network a natural strategic game between the agents. In these games the payoff of each player weakly increases when more players choose his strategy, which is exactly opposite to the congestion games. The possibility of not choosing any product results in two special types of (pure) Nash equilibria. We show that such games may have no Nash equilibrium and that determining an existence of a Nash equilibrium, also of a special type, is NP-complete. This implies the same result for a more general class of games, namely polymatrix games. The situation changes when the underlying graph of the social network is a DAG, a simple cycle, or, more generally, has no source nodes. For these three classes we determine the complexity of an existence of (a special type of) Nash equilibria. We also clarify for these categories of games the status and the com- plexity of the finite best response property (FBRP) and the finite im- provement property (FIP). Further, we introduce a new property of the uniform FIP which is satisfied when the underlying graph is a simple cy- cle, but determining it is co-NP-hard in the general case and also when the underlying graph has no source nodes. The latter complexity results also hold for the property of being a weakly acyclic game. A preliminary version of this paper appeared as [19]