文章基本信息

标题：Pure Nash Equilibria in Resource Graph Games
本地全文：下载
作者：Tobias Harks ; Max Klimm ; Jannik Matuschke 等
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2021
卷号：72
页码：1-29
DOI：10.1613/jair.1.12668
语种：English
出版社：American Association of Artificial
摘要：This paper studies the existence of pure Nash equilibria in resource graph games a general class of strategic games succinctly representing the players’ private costs. These games are defined relative to a finite set of resources and the strategy set of each player corresponds to a set of subsets of resources. The cost of a resource is an arbitrary function of the load vector of a certain subset of resources. As our main result we give complete characterizations of the cost functions guaranteeing the existence of pure Nash equilibria for weighted and unweighted players respectively. For unweighted players pure Nash equilibria are guaranteed to exist for any choice of the players’ strategy space if and only if the cost of each resource is an arbitrary function of the load of the resource itself and linear in the load of all other resources where the linear coefficients of mutual influence of different resources are symmetric. This implies in particular that for any other cost structure there is a resource graph game that does not have a pure Nash equilibrium. For weighted games where players have intrinsic weights and the cost of each resource depends on the aggregated weight of its users pure Nash equilibria are guaranteed to exist if and only if the cost of a resource is linear in all resource loads and the linear factors of mutual influence are symmetric or there is no interaction among resources and the cost is an exponential function of the local resource load.We further discuss the computational complexity of pure Nash equilibria in resource graph games showing that for unweighted games where pure Nash equilibria are guaranteed to exist it is coNP-complete to decide for a given strategy profile whether it is a pure Nash equilibrium. For general resource graph games we prove that the decision whether a pure Nash equilibrium exists is Σ p 2 -complete.
关键词：game theory;multiagent systems