图博弈论

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

考虑一个博弈，有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，则图博弈规模远小于一般博弈的规模。

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

Image:GraphicalGameExample.png|描述博弈的图

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

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

评论 (0)