Potential games, originally introduced in the early 1990's by Lloyd Shapley, the 2012 Nobel Laureate in Economics, and his colleague Dov Monderer, are a very important class of models in game theory. They have special properties such as the existence of Nash equilibria in pure strategies. This note introduces graphical versions of potential games. Special cases of graphical potential games have already found applicability in many areas of science and engineering beyond economics, including artificial intelligence, computer vision, and machine learning. They have been effectively applied to the study and solution of important real-world problems such as routing and congestion in networks, distributed resource allocation (e.g., public goods), and relaxation-labeling for image segmentation. Implicit use of graphical potential games goes back at least 40 years. Several classes of games considered standard in the literature, including coordination games, local interaction games, lattice games, congestion games, and party-affiliation games, are instances of graphical potential games. This note provides several characterizations of graphical potential games by leveraging well-known results from the literature on probabilistic graphical models. A major contribution of the work presented here that particularly distinguishes it from previous work is establishing that the convergence of certain type of game-playing rules implies that the agents/players must be embedded in some graphical potential game.

本文介绍了潜力博弈及其图形化版本，比较新的工作发现了潜力博弈在很多实际问题中的应用，如网络路由和拥塞，分布式资源分配和图像分割等，图形潜力博弈具有协调、局部相互作用、格点、拥塞和派系等几种类型，通过概率图模型的相关结果，本文提供了几种图形潜力博弈的表述方法，并证明了特定类型的博弈规则的收敛意味着参与者必须嵌入某些图形潜力博弈中。