9博弈的矩陣形式

博弈的矩陣形式概要矩陣博弈：另一種博弈理論定義信息完全的博弈的最大最?。∕inimax）信息隱藏的博弈的最大最?。∕inimax）已有假設(shè)：倆人對弈：玩家A與B。信息完全：倆玩家親歷所有的狀態(tài)及決定。每個決定是順序做出。零和：A得到的等于B損失的。將取消這些限制。首先取消信息完全的假設(shè)，由此導(dǎo)出更實際的模型。博弈的擴(kuò)展形式：用樹代表博弈ABA玩家的一個純策略：該玩家為其所遇到的每種可能狀態(tài)而做的移動（走步）。ABAA的純策略：策略1：(1L,4L)策略2：(1L,4R)策略3：(1R,4L)策略4：(1R,4R)B的純策略：策略1：(2L,3L)策略2：(2L,3R)策略3：(2R,3L)策略4：(2R,3R) 一般情況：如果有N個狀態(tài)和M個移動，則有多少個純策略存在？（MN）A的純策略：策略I：(1L,4L)策略II：(1L,4R)策略III：(1R,4L)策略IV：(1R,4R)IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1B的純策略：策略I：(2L,3L)策略II：(2L,3R)策略III：(2R,3L)策略IV：(2R,3R)博弈的矩陣形式IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1博弈的矩陣形式博弈的矩陣范式：上表包含A與B的純策略的所有可能組合的回報值。該表完全表征博弈，無需關(guān)于規(guī)則等的任何額外信息。雖然在許多場合，純策略數(shù)目太大，不能用表來顯示，但矩陣是能用來導(dǎo)出博弈本質(zhì)的基本表征。A的純策略B的純策略Minimax：矩陣形式IIIIIIIV-1I-1-1+2+2+2II+4+4+2+2+1III+5+1+5+1+1IV+5+1+5+1所有行的極大值每行的極小值Minimax：矩陣形式IIIIIIIV-1I-1-1+2+2+2II+4+4+2+2+1III+5+1+5+1+1IV+5+1+5+1所有行的極大值每行的極小值極大值=博弈值=+2對于博弈矩陣每行所示的每種策略，A應(yīng)假設(shè)B會采用A策略下的最佳策略，即行中極小值的策略。因此，A能獲得的最佳值是各行極小值的最大值：相應(yīng)的純策略是該博弈的最佳解，即假設(shè)B表現(xiàn)最佳，A應(yīng)采用的最佳策略。Minimax：矩陣形式IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1+5+4+5+2每列的極大值所有列的極小值能用相反的論點(diǎn)。對于博弈矩陣每列所示的每種策略，B應(yīng)假設(shè)A會采用B策略下的最佳策略，即列中極大值的策略。因此，B玩家能獲得的最佳值是各列極大值的最小值：問題：得到的是一樣的結(jié)果嗎？總存在一個解嗎？Minimax還是Maximin？極小值=博弈值=+2IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1+5+4+5+2每列的極大值所有列的極小值注意到，兩種場合下得到一樣的值和一樣的策略。其它也總是這樣嗎？IIIIIIIV-1I-1-1+2+2+2II+4+4+2+2+1III+5+1+5+1+1IV+5+1+5+1所有行的極大值每行的極小值極大值=博弈值=+2極小值=博弈值=+2IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1+5+4+5+2每列的極大值所有列的極小值Minimax與Maximin（vonNeumann）第1基本定理：對一個信息完全的倆人零和對弈：對每位玩家，總存在一個最佳純策略Minimax=Maximin

注：這只是minimax搜索算法的博弈理論形式。信息隱藏的博弈另一個例子倆位玩家A與B，各有一枚硬幣他們選擇性地給對方看自己硬幣的正面或反面。如果他們都選擇正面，則B付給A兩塊錢。如果他們都選擇反面，則B付給A一塊錢。如果他們選擇不同的面，則A付給B一塊錢。示例的作用這個示例能模擬大量的實際情況。實例：A是一位店主，而B是一名檢察官。檢察官選一天來執(zhí)行檢查。店主挑某天來藏匿壞東西。如果各自的行動日不同，B贏；否則，A贏。這類實際問題能簡化為類似上面的硬幣游戲。擴(kuò)展形式AB問題：因為移動是同時進(jìn)行的，所以B不知道A的移動。博弈信息不再是完全的，而是有隱藏的了。HTH+2-1T-1+1BA矩陣形式容易驗證：maximin=-1，minimax=+1。不再有maximin=minimax。因此，也應(yīng)該不存在純策略解。事實上，一個信息隱藏的零和博弈是不存在純策略解的。為什么無純策略解？直覺：如果A考慮移動H，則他必須假設(shè)B會選擇對他最為不利的移動T。因此，A應(yīng)轉(zhuǎn)而嘗試移動T，但這一次他必須假設(shè)B會選擇對他最為不利的移動H。因此，A應(yīng)轉(zhuǎn)而嘗試移動H，但這一次他必須假設(shè)B會選擇對他最為不利的移動T。因此，A應(yīng)轉(zhuǎn)而嘗試移動T，但這一次他必須假設(shè)B會選擇對他最為不利的移動H。因此，A應(yīng)轉(zhuǎn)而嘗試移動H，但這一次他必須假設(shè)B會選擇對他最為不利的移動T?！璈TH+2-1T-1+1BA不是選擇一個固定的純策略，假設(shè)A以p為概率隨機(jī)選擇策略H，并以1-p為概率選擇策略T。如果B選移動H，A所期望的回報是：

p(+2)+(1-p)(-1)=3p-1如果B選移動T，A所期望的回報是：

p(-1)+(1-p)(+1)=-2p+1因此，最壞的情形是，B選擇在上述兩種場合中回報最小的那種策略：

min(3p-1,-2p+1)那么，A應(yīng)調(diào)整p，以使其回報最大(這與標(biāo)準(zhǔn)maximin程序相似)：

maxpmin(3p-1,-2p+1)采用隨機(jī)策略HTH+2-1T-1+1BA解的圖形化如B選H，則期望回報為3p-1如B選T，則期望回報為-2p+1不管B遵循什么可能的策略(概率為q)，所導(dǎo)致的回報都將位于與B的純策略相對應(yīng)的兩條直線之間解的圖形化min(3p-1,-2p+1)最佳p值：p*=argmaxpmin(3p-1,-2p+1)=2/5期望回報：maxpmin(3p-1,-2p+1)=1/5混合策略A不再可能找到一種純策略。需將問題稍加改變：假設(shè)對弈開始時，A隨機(jī)選擇一種純策略。在此場合，A選擇一種純策略的概率為p，選擇另一種純策略的概率為1-p。混合策略：隨機(jī)選擇純策略，且由概率p完全定義。問題：雖然A不能找到一種最佳純策略，但是能找到一種最佳混合策略p，對嗎？答案：對。從上面簡單例子得出的結(jié)果對一般博弈仍成立。由此可產(chǎn)生一個為零和博弈尋找最佳混合策略的方法?；旌喜呗缘淖畲笞钚。╲onNeumann）第2定理：對一個信息隱藏的倆人零和對弈：總存在一個最佳混合策略，并具有下面值：

maxpmin(pm11+(1-p)m21，pm12+(1-p)m22) 其中，對弈的矩陣形式為： 注：這是minimax結(jié)果在混合策略上的一個直接推廣。m11m12m21m22混合策略的最大最?。╲onNeumann）第2定理：對一個信息隱藏的倆人零和對弈：總存在一個最佳混合策略此外，與信息完全的對弈一樣，以怎樣的次序來看待玩家并不重要。因此，minimax等于maximin

：

maxpmin(pm11+(1-p)m21，pm12+(1-p)m22)=

minqmax(qm11+(1-q)m12，qm21+(1-q)m22)= 注：這是minimax結(jié)果在混合策略上的一個直接推廣。22對弈的方法因為兩個關(guān)于p的函數(shù)是線性的，所以可以在下面三種情況下到達(dá)極大值：p=0，p=1，兩直線的交點(diǎn)，如果在0與1之間的某值p處出現(xiàn)極大值。min(pm11+(1-p)m21，pm12+(1-p)m22)最大值最大值最大值一般場合：NM博弈22對弈的問題：A和B每位玩家各有2種策略。以上結(jié)果可推廣到NM博弈，但較難計算。一個混合策略是一個概率矢量p=(p1,…,pN)，其中pi是A選擇策略i的概率，且pi=1。用線性規(guī)劃求解下面問題來尋找最佳策略：A的期望回報，如B選擇純策略j，A以概率pi選擇純策略i。圖示：2M博弈minj(pm1j+(1p)m2j)maxpminj(pm1j+(1p)m2j)pm1j+(1p)m2j討論用來選擇最佳混合策略的判據(jù)是在數(shù)次博弈后A獲得的平均回報。用隨機(jī)挑選的純策略作為混合策略，并尋找最佳混合策略，這對嗎？實際上，這只是把通常情形下所發(fā)生的事實形式化而已。例如，撲克對弈中，如果A遵循某種單一純策略，即在每次處理一手特殊牌型時，采取相同的行動，則B能猜到并回應(yīng)這種策略，以降低A的回報。正確的做法是，根據(jù)某種策略，A隨機(jī)地改變處理每種牌型的方法。一個好的玩家應(yīng)用一種好的策