CIICADA Lab, Australian National University, Canberra, 2601, Australia.
Sci Rep. 2023 Feb 1;13(1):1833. doi: 10.1038/s41598-023-28627-8.
In this paper, we analyse two-player games by their response graphs. The response graph has nodes which are strategy profiles, with an arc between profiles if they differ in the strategy of a single player, with the direction of the arc indicating the preferred option for that player. Response graphs, and particularly their sink strongly connected components, play an important role in modern techniques in evolutionary game theory and multi-agent learning. We show that the response graph is a simple and well-motivated model of strategic interaction which captures many non-trivial properties of a game, despite not depending on cardinal payoffs. We characterise the games which share a response graph with a zero-sum or potential game respectively, and demonstrate a duality between these sets. This allows us to understand the influence of these properties on the response graph. The response graphs of Matching Pennies and Coordination are shown to play a key role in all two-player games: every non-iteratively-dominated strategy takes part in a subgame with these graph structures. As a corollary, any game sharing a response graph with both a zero-sum game and potential game must be dominance-solvable. Finally, we demonstrate our results on some larger games.
在本文中，我们通过反应图来分析两人游戏。反应图的节点是策略组合，对于单个玩家的策略不同的组合之间存在有向边，边的方向表示该玩家的偏好选项。反应图，特别是它们的汇点强连通分量，在现代进化博弈论和多智能体学习技术中起着重要作用。我们表明，反应图是一个简单而有充分动机的策略交互模型，它捕获了游戏的许多非平凡性质，尽管不依赖于基数收益。我们分别刻画了与零和博弈或势博弈具有相同反应图的游戏，并证明了这两个集合之间的对偶性。这使我们能够了解这些特性对反应图的影响。匹配便士和协调游戏的反应图在所有两人游戏中都起着关键作用：每个非迭代占优策略都参与具有这些图结构的子游戏。作为推论，任何与零和博弈和势博弈具有相同反应图的游戏都必须是可支配求解的。最后，我们在一些更大的游戏上展示了我们的结果。
