图博弈论

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

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

形式定义

博弈由 表示,其中每个参与者由图中的一个节点表示,当且仅当图中的两个节点  的效用函数相互依赖时,则它们之间有一条边。 中的每个节点 有一个函数 ,其中 是顶点 数。 是参与者 之策略以及其邻居之策略的效用函数。

博弈规模的表示

对于一个有 个参与者的博弈,每个参与者有 种可能的策略,博弈的规模就是 。该博弈的图规模为 ,其中 为图中最大节点度。如果 ,则图博弈规模远小于一般博弈的规模。

实例

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

图的最大度为1,因此博弈可以用 个大小为 的图表示,所以总大小是 .

纳什均衡

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

延伸阅读