擴展形式的博弈

博弈論中，與正則形式相應，擴展形式（英語：Extensive-form game）通過樹來描述博弈。每個節點（稱作決策節點）表示博弈進行中的每一個可能的狀態。博弈從唯一的初始節點開始，通過由參與者決定的路逕到達終端節點，此時博弈結束，參與者得到相應的收益。每個非終端節點只屬於一個參與者；參與者在該節點選擇其可能的行動，每個可能的行動通過邊從該節點到達另一個節點。

和正則形式不同，擴展形式允許互動的顯式模型（explicit modeling of interactions），互動中，一個參與者可以在博弈中多次行動，並且在不同的狀態中可以做出不同的行為。

表述[編輯]

完整的擴展形式表述包括：

博弈中的參與者
每個參與者能行動的所有機會。
每個參與者在行動時的選擇
每個參與者在行動時所知道的情況
每個參與者通過各種可能的行動之後的收益。

右圖是一個雙人博弈：1和2。每個非終端節點上的數字表示該節點所屬的參與者。終端節點上的數字表示參與者的收益（例如:2,1表示參與者1得到2，參與者2得到1）。圖片裏每個邊上的符號是這個邊所代表的行動的名字。

初始節點屬於參與者1，表示該參與者先動。博弈順序如下：參與者1選擇U或者D；參與者2觀察到參與者1的選擇，然後選擇U' 或者D' ，最後得到最終收益。四個終端節點代表四個結果：(U,U')，(U,D')，(D,U')和(D,D')。每個結果得到的收益分別是(0,0)，(2,1)，(1,2)和(3,1)。

如果參與者1選擇D，參與者2為了最大化收益，會選擇U'，最後參與者1隻能得到1。但是如果參與者1選擇U，參與者2為了最大化收益，會選擇D' ，此時參與者1得到2。所以參與者1會選擇U，參與者2選擇D' 。即是子博弈完美均衡。

無限行動空間[編輯]

參與者在一個特定的決策節點上可能有無數種可能的行動可以選擇。其表示方法是用弧形來連接從該決策節點延伸出的兩條邊。如果行動空間是在兩個數字之間的閉聯集（continuum），那麼把這兩個表示上下界限的數字分別放在弧的上方和下方，並用一個變數來表示其支付。此時無數個決策節點可以用一個在弧中心的節點所代替。這種表示方式同樣可以用在一個有限的行動空間中，只要該行動空間足夠大，此時不可能用邊來表示每個行動。

左側的樹表示這樣一個博弈：該博弈或者有一個無限行動空間（任何0到5000的實數），或者有一個很大的行動空間（可能是任何在0到5000的整數）。如果我們在這裏假設它表示兩個參與Stackelberg競爭的企業。公司的支付表示在左邊，其中q1和q2表示先行者公司以及追隨者公司分別採用的策略，c1和c2是常數（表示公司的機會成本）。該博弈的子博弈完美納殊均衡可以通過對支付函數求追隨者策略變數(q2)的一階偏導數表示其利潤最大化，並求出其最優反應函數， $q2(q1)=(5000-q1-c2)/2$ 。用同樣的方法計算先行者的最優反應函數，並假定先行者知道追隨者會選擇上述的行動，通過一階偏導數來解出 $q1*=(5000+c2-2c1)/2$ 。在將q1*代入到追隨者的最優反應函數中， $q2*=(5000+2c1-3c2)/4$ ，此時(q1*,q2*)就是子博弈完美納殊均衡。如果假設 c1=c2=1000，那麼子博弈完美納殊均衡的解就是(2000,1000)。

不完美資訊[編輯]

樹圖清楚地表示了參與者1先動，參與者2觀察到參與者1的行動。然而，一些博弈並不是這樣。參與者並不是一直能觀察到另一個人的選擇（例如，同時行動或者行動被隱藏）。資訊集合是決策節點的組合：

每個節點都屬於一個參與者。
參與者無法區分資訊集合里的多個節點。也就是說：如果資訊集合有多個節點，資訊集合所屬的參與者就不知道能往哪個節點移動。

完美資訊的博弈是指在博弈的任何階段，每個參與者都清楚博弈之前發生的所有行動，也即每個資訊集合都是一個單元素集合。沒有完美資訊的博弈具有不完美資訊。

左圖中的博弈中，參與者2行動時不知道參與者1的選擇，除此之外和第一個博弈相同。第一個博弈具有完美資訊；而左圖中的沒有。如果兩個參與者都是理性的，並且都知道對方也是理性人，對方知道的資訊，自己也能獲得（即參與者1知道參與者2知道參與者1是理性的，參與者2同樣也知道，如此循環下去），

公理的公式化[編輯]

博弈論是一種數學理論，所以上述的博弈樹結構可以轉化為公式表達。

擴展形式的有限樹是這樣一個結構 $\Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\{A(H)\}_{H\in \mathbf {H} }],a,\rho ,u\rangle$ 其中：

${\mathcal {K}}=\langle V,v^{0},T,p\rangle$ 表示一個有限的樹。 $V$ 是樹的所有節點， $v^{0}\in V$ 表示唯一的初始節點， $T\subset V$ 表示所有的終端節點（ $D=V\setminus T$ 是決策節點）以及函數 $p:V\rightarrow D$ 表示博弈的規則，
$\mathbf {H}$ 表示 $D$ 里包含的資訊，
$A(H)$ 是資訊集合 $H\in \mathbf {H}$ 所允許的可能的行動。所有的行動表示為 ${\mathcal {A}}$ 。

參考文獻[編輯]

Dresher M. (1961). The mathematics of games of strategy: theory and applications (Ch4: Games in extensive form, pp74--78). Rand Corp. ISBN 0-486-64216-X
Fudenberg D and Tirole J. (1991) Game theory (Ch3 Extensive form games, pp67-106). Mit press. ISBN 0-262-06141-4
Luce R.D. and Raiffa H. (1957). Games and decisions: introduction and critical survey. (Ch3: Extensive and Normal Forms, pp39-55). Wiley New York. ISBN 0-486-65943-7
Osborne MJ and Rubenstein A. 1994. A course in game theory (Ch6 Extensive game with perfect information, pp. 89-115). MIT press. ISBN 0-262-65040-1

參見[編輯]