论文标题
寻找纯粹的离散优先游戏和网络协调游戏的纯纳什平衡
On Finding Pure Nash Equilibria of Discrete Preference Games and Network Coordination Games
论文作者
论文摘要
本文介绍了计算纯纳什均衡的问题的复杂性，用于离散的首选项游戏和网络协调游戏，而不是$ o（\ log n）$ - 树宽和树公制空间。首先，我们估计具有至少三种策略的离散度量空间上的离散偏好游戏的最佳响应动态迭代次数。其次，我们提出了足够的条件，即我们具有多项式时间算法，可以在网格图上找到离散的首选项游戏的纯纳什平衡。最后，我们讨论了找到纯净的NASH平衡的复杂性，该平衡是为了满足次要性的两种战略网络协调游戏。在这种情况下，如果每个成本函数都是对称的，则游戏是多项式时间，可在路径度量空间上的离散偏好游戏还原。
This paper deals with the complexity of the problem of computing a pure Nash equilibrium for discrete preference games and network coordination games beyond $O(\log n)$-treewidth and tree metric spaces. First, we estimate the number of iterations of the best response dynamics for a discrete preference game on a discrete metric space with at least three strategies. Second, we present a sufficient condition that we have a polynomial-time algorithm to find a pure Nash equilibrium for a discrete preference game on a grid graph. Finally, we discuss the complexity of finding a pure Nash equilibrium for a two-strategic network coordination game whose cost functions satisfy submodularity. In this case, if every cost function is symmetric, the games are polynomial-time reducible to a discrete preference game on a path metric space.
