图博弈论

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

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

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

•  

  描述博弈的图

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

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

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