圖賽局理論

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

考慮一個賽局，有$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 （頁面存檔備份，存於網際網路檔案館）".