查看“︁图博弈论”︁的源代码

{{NoteTA
|G1=博弈论
}}
{{No footnotes|time=2021-09-29T03:57:26+00:00}}
在[[博弈论]]中，描述博弈论的常用方法有[[正则形式的博弈]]和[[扩展形式的博弈]]。'''图博弈论'''是参与者之间简洁博弈的表示形式。

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

== 形式定义 ==
博弈由[[图 (数学)|图]]<math>G</math>表示，其中每个参与者由图中的一个节点表示，[[当且仅当]]图中的两个节点<math>i</math>和<math>j</math>的效用函数相互依赖时，则它们之间有一条边。<math>G</math>中的每个节点<math>i</math>有一个函数<math>u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow\mathbb{R}</math>，其中<math>d_i</math>是顶点<math>i</math>的[[度 (图论)|度]]数。<math>u_{i}</math>是参与者<math>i</math>之策略以及其邻居之策略的效用函数。

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

==实例==
当每个参与者的效用函数只依赖于另一个参与者时:
<gallery>
Image:GraphicalGameExample.png|描述博弈的图
</gallery>

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

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

== 延伸阅读 ==

* Michael Kearns (2007) "[http://www.cis.upenn.edu/~mkearns/papers/agt-kearns.pdf Graphical Games] {{Wayback|url=http://www.cis.upenn.edu/~mkearns/papers/agt-kearns.pdf |date=20220120230241 }}".
* Michael Kearns, Michael L. Littman and Satinder Singh (2001) "[http://www.cis.upenn.edu/~mkearns/papers/graphgames.pdf Graphical Models for Game Theory] {{Wayback|url=http://www.cis.upenn.edu/~mkearns/papers/graphgames.pdf |date=20210929033657 }}".

{{博弈论}}

[[Category:博弈论]]