圖博弈論

在博弈論中，描述博弈論的常用方法有正則形式的博弈和擴展形式的博弈。圖博弈論是參與者之間簡潔博弈的表示形式。

考慮一個博弈，有$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 （頁面存檔備份，存於互聯網檔案館）".