图博弈论

在博弈论中，描述博弈论的常用方法有正则形式的博弈和扩展形式的博弈。图博弈论是参与者之间简洁博弈的表示形式。

考虑一个博弈，有$n$个参与者，每个人有$m$种策略。我们将任何一个参与者表示为一个图中的节点，在这个图中，每个参与者都有一个效用函数，这个效用函数仅仅与其邻居有关。该效用函数依赖的其他参与者越少，图示也就越小。

形式定义

博弈由图$G$表示，其中每个参与者由图中的一个节点表示，当且仅当图中的两个节点$i$和$j$的效用函数相互依赖时，则它们之间有一条边。$G$中的每个节点$i$有一个函数$u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R}$，其中$d_{i}$是顶点$i$的度数。$u_{i}$是参与者$i$之策略以及其邻居之策略的效用函数。

博弈规模的表示

对于一个有$n$个参与者的博弈，每个参与者有$m$种可能的策略，博弈的规模就是$O(m^{n})$。该博弈的图规模为$O(m^{d})$，其中$d$为图中最大节点度。如果$d\ll n$，则图博弈规模远小于一般博弈的规模。

实例

当每个参与者的效用函数只依赖于另一个参与者时:

• 
  描述博弈的图

图的最大度为1，因此博弈可以用$n$个大小为$m^{2}$的图表示，所以总大小是$nm^{2}$.

纳什均衡

找到纳什均衡所需时间与图的大小呈指数相关。如果图博弈的图是树，只需多项式时间就能找到纳什均衡。如果最大的节点度数大于3，这个问题就是NP完全问题。

延伸阅读

• Michael Kearns (2007) "Graphical Games （页面存档备份，存于互联网档案馆）".
• Michael Kearns, Michael L. Littman and Satinder Singh (2001) "Graphical Models for Game Theory （页面存档备份，存于互联网档案馆）".