论文标题
资源图游戏中的纯纳什平衡
Pure Nash Equilibria in Resource Graph Games
论文作者
论文摘要
本文研究了资源图游戏中纯纳什均衡的存在，这是一种通用类，用于简洁地代表玩家的私人费用。有一组有限的资源，每个玩家的策略集对应于一组资源子集。资源的成本是一个任意功能，取决于指定社区中资源的负载向量。作为我们的主要结果，我们对成本功能进行完整的特征，以确保分别为加权和未加权玩家存在纯净的NASH均衡。 1。对于未加权的玩家，只有在每个资源的成本是资源本身负载的任意功能，而在所有其他资源的负载中，纯净的NASH均衡就可以保证存在任何选择玩家的策略空间，而在所有其他资源的负载中有线性的函数，在这些资源的负载中，不同资源的相互影响的线性系数是对称的。 2.对于具有加权玩家的游戏，只有在所有资源负载中资源的成本是线性的，并且相互影响的线性因素是对称的，或者资源之间没有相互作用，并且资源之间没有相互作用，并且资源之间没有相互作用，并且资源之间没有相互作用，并且该资源之间没有相互作用，那么纯净的NASH平衡可以保证存在纯NASH平衡。 3。对于特殊情况是玩家的策略集是矩形，我们表明纯纳什均衡存在于本地单调性属性下，即使成本功能是特定于玩家的。我们指出，该结果的应用在双重负载平衡游戏中，这些游戏是由对反对外部攻击者和内部拥塞效应的网络基础架构的研究进行的。 4。最后，我们得出了硬度结果，以确定给定策略是否分别是网络路由游戏和Matroid游戏的纯NASH均衡。
This paper studies the existence of pure Nash equilibria in resource graph games, which are a general class of strategic games used to succinctly represent the players' private costs. There is 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 that depends on the load vector of the resources in a specified neighborhood. 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. 1. 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. 2. For games with weighted players, pure Nash equilibria are guaranteed to exist for any choice of the players' strategy space 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. 3. For the special case that the players' strategy sets are matroids, we show that pure Nash equilibria exist under a local monotonicity property, even when cost functions are player-specific. We point out an application of this result to bilevel load balancing games, which are motivated by the study of network infrastructures that are resilient against external attackers and internal congestion effects. 4. Finally, we derive hardness results for deciding whether a given strategy is a pure Nash equilibrium for network routing games and matroid games, respectively.
