or教學(xué)投影片(第13章)(ok)

1、第十三章競(jìng)賽理論,林吉仁 著高立圖書(shū)公司出版,作業(yè)研究,林吉仁著,13-1概　論,競(jìng)賽理論 (game theory) 又稱(chēng)遊戲理論或?qū)掷碚摳?jìng)賽中有至少兩位的競(jìng)賽者，每位競(jìng)賽者的目標(biāo)互相衝突，彼此對(duì)抗，因此競(jìng)賽者均有種種的策略，以期能打敗其他競(jìng)賽者而獲得最大報(bào)酬或最小損失。,林吉仁著,13-2競(jìng)賽的類(lèi)型,機(jī)率競(jìng)賽 v.s 策略競(jìng)賽 策略競(jìng)賽可分為：兩人競(jìng)賽、多人(兩人以上)競(jìng)賽常數(shù)和競(jìng)賽、非常數(shù)和競(jìng)賽。本書(shū)討論零和競(jìng)

2、賽是一種特殊的常數(shù)和競(jìng)賽單純策略競(jìng)賽與混合策略競(jìng)賽確定性競(jìng)賽與機(jī)率性競(jìng)賽,林吉仁著,13-3 競(jìng)賽的基本元素與假設(shè),競(jìng)賽架構(gòu)中有三種基本元素： 競(jìng)賽者 (player)：至少兩人 ( 方 )，但三人以上的競(jìng)賽不在本書(shū)範(fàn)圍 策略 (strategy)：每位競(jìng)賽者至少有2個(gè)策略。但每回合雙方僅可選定一個(gè)策略 報(bào)酬 (payoff)：選定策略後的報(bào)酬。當(dāng)雙方均採(cǎi)用最佳策略時(shí)，所獲得之報(bào)酬稱(chēng)為競(jìng)賽值 (value of the gam

3、e)。競(jìng)賽值為0的競(jìng)賽，稱(chēng)為公平的競(jìng)賽。,林吉仁著,報(bào)酬矩陣：競(jìng)賽的基本假設(shè)： 雙方均知道報(bào)酬矩陣 雙方均採(cǎi)理性的行動(dòng)，追求最大報(bào)酬或最小損失 雙方均採(cǎi)取保守戰(zhàn)略,林吉仁著,13-4 凌越規(guī)則,優(yōu)勢(shì)策略 與 劣勢(shì)策略凌越規(guī)則如下： 每個(gè)第 i1 列元素 ? 同行第 i2 列元素，則可刪去第 i2 列 每個(gè)第 j1 行元素 ? 同列第 j2 行元素，則可刪去第 j2 行,林吉仁著,例題13-1,林吉仁著,解：,林吉仁

4、著,重要性質(zhì),? 定義13-1 ?在 m?n 報(bào)酬矩陣的競(jìng)賽，若甲方採(cǎi)用第 i 個(gè)策略的機(jī)率為 xi，則稱(chēng)機(jī)率向量 R =[x1, x2, ?, xm] 為甲方的策略；乙方採(cǎi)用第j個(gè)策略的機(jī)率為 yj，則稱(chēng) C=[y1, y2, ?, yn] 為乙方的策略。 ? 定理13-1 ?若A報(bào)酬矩陣的甲方最佳決策為R*，乙方最佳決策為C*，則競(jìng)賽值E (R*, C*) = R*A(C*)T。 ? 定理13-2 ?每個(gè)競(jìng)賽的競(jìng)賽值是唯一的,林

5、吉仁著,13-5單純策略競(jìng)賽,甲方準(zhǔn)則：小中取大，自每一列中先選出最小值，再自這些數(shù)值中找出最大值 乙方準(zhǔn)則：大中取小，先自每一行中選出最大值，再自這些數(shù)值中找出最小值甲方、乙方所選取的元素為同一個(gè)時(shí)，此元素稱(chēng)為鞍點(diǎn)。有鞍點(diǎn)的矩陣其競(jìng)賽為單純策略競(jìng)賽，雙方的最佳決策，競(jìng)賽值均可自鞍點(diǎn)求出無(wú)鞍點(diǎn)的矩陣則為混合策略競(jìng)賽,林吉仁著,例題13-2,設(shè)兩人零和競(jìng)賽報(bào)酬陣為 請(qǐng)求雙方的最佳決策及競(jìng)賽值？,林吉仁著,解：,,,∴

6、有鞍點(diǎn)的競(jìng)賽，競(jìng)賽值6 甲方最佳決策R*= [0,0,1,0]，即第Ⅲ策略乙方最佳決策C*= [0,0,1,0]，亦為第Ⅲ策略,林吉仁著,13-5 2?2混合策略競(jìng)賽,無(wú)鞍點(diǎn)的混合策略的競(jìng)賽，雙方常因應(yīng)對(duì)方行動(dòng)調(diào)整自己的行動(dòng)，因此只能以機(jī)率來(lái)描述雙方的策略。 一般而言，無(wú)鞍點(diǎn)的競(jìng)賽必須利用線性規(guī)劃模式加以求解 2?2 矩陣的競(jìng)賽另有公式法 m?2，或 2?n 矩陣的競(jìng)賽可用圖解法或拆成多個(gè)2?2競(jìng)賽再比較,林吉仁著,林吉仁

7、著,林吉仁著,例題13-3,解：,林吉仁著,林吉仁著,例題13-4,解：,林吉仁著,林吉仁著,13-7線性規(guī)劃法,林吉仁著,林吉仁著,例題13-5,假設(shè)甲、乙兩人玩剪刀、石頭、布猜拳遊戲，勝方自敗方獲得1元，平手則報(bào)酬為0，請(qǐng)寫(xiě)出報(bào)酬矩陣，並求雙方最佳決策與競(jìng)賽值。,解：,林吉仁著,林吉仁著,林吉仁著,13-8兩策略競(jìng)賽之解法,求解m?2或2?n的競(jìng)賽矩陣方法有： (1) 將競(jìng)賽拆成數(shù)個(gè)2?2子競(jìng)賽 (sub-game)

8、 再求解 (2) 將線性規(guī)劃模式簡(jiǎn)化，利用圖解法加 以求解。,林吉仁著,13-8-1a 2?2子競(jìng)賽矩陣法,林吉仁著,例題13-6,解：,林吉仁著,林吉仁著,林吉仁著,林吉仁著,13-8-1b 2?2子競(jìng)賽矩陣法,林吉仁著,13-8-2 2?n,m?2競(jìng)賽之圖解法,林吉仁著,林吉仁著,例題13-7,解：,林吉仁著,林吉仁著,圖13-1,林吉仁著,林吉仁著,圖13-2,林吉仁著,例題13-8,林吉仁著,解

9、：,林吉仁著,圖13-3,林吉仁著,林吉仁著,林吉仁著,13-9 解題步驟,兩人零和競(jìng)賽解題可依循以下步驟：步驟1：以小中取大，大中取小準(zhǔn)則尋找鞍點(diǎn)； 有鞍點(diǎn)，停止運(yùn)算；無(wú)鞍點(diǎn)到步驟2步驟2：以凌越規(guī)則簡(jiǎn)化矩陣步驟3：(1)2?2 矩陣，以公式法、圖解法、線性 規(guī)劃法求解 (2)2?n，m?2 矩陣以圖解法或線性規(guī)劃法