第 7 章 馬可夫鏈與賽局理論.

Presentation on theme: "第 7 章 馬可夫鏈與賽局理論."— Presentation transcript:

1 第 7 章 馬可夫鏈與賽局理論

2 7.1 馬可夫鏈 例題1 股票的觀察 億平對某一家航空公司的股票很有興趣，持續觀察了一段時間，發現其收盤價(closing price) 的漲跌僅與前一日的收盤價有關。他於各交易日結束時做記錄，若當天的收盤價比前一個交易日的收盤價高、不變或低，則相對登錄為上漲、持平或下跌。億平的這一連串的觀察，可視為馬可夫鏈。 Tan/管理數學 第7章 第344頁

3 例題 2 股票的觀察 承例題1。據億平觀察所得，若該股票當天的收盤價高於前一天，則次日的收盤價會上漲、持平或下跌的機率分別為0.2, 0.3與0.5；若該股票當天的收盤價與前一天相同，則次日的收盤價會上漲、持平或下跌的機率分別為0.5, 0.2與0.3；若該股票當天的收盤價低於前一天，則次日的收盤價會上漲、持平或下跌的機率分別為0.4, 0.4與0.2。請利用樹狀圖敘述狀態間遞移的機率。 Tan/管理數學 第7章 第344頁

4 例題 2 股票的觀察（續） 解： 本例的馬可夫鏈由三種狀態組成：上漲、持平或下跌。若現階段是上漲，則由上漲的狀態遞移到其他狀態之機率，標示於樹狀圖的分枝上，見圖1的最左圖。至於現階段是持平或下跌狀態，其對應的樹狀圖亦分別繪於圖1。 Tan/管理數學 第7章 第 頁

5 遞移機率 敘述馬可夫過程中由某個狀態到達下一個狀態的機率(如例題2中的機率)，稱為遞移機率(transition probabilities)。這些遞移機率可用矩陣式來表達。假設有一馬可夫鏈的試驗，各階段的結果有三種狀態，分別命名為狀態1、2、3，則由狀態1到達試驗的下個階段結果－－狀態1、2、3 的遞移機率，即為給定狀態1，而下一個階段進入狀態1、2、3的條件機率，可分別寫成P (狀態1 | 狀態1)、P (狀態2 | 狀態1)及P (狀態3 |狀態1)。若我們使用矩陣的元素符號，可記成 Tan/管理數學 第7章 第345頁

6 遞移機率 這裡元素a的第一個下標代表試驗的下一階段到達之狀態，我們稱為次態(next state)，而第二個下標則代表現在的狀態，稱為現態。若以樹狀圖表示，則有如下關係： Tan/管理數學 第7章 第345頁

7 遞移機率 同樣地，由狀態2 及3到達下一階段之狀態的條件機率可寫成 及 Tan/管理數學 第7章 第345頁

8 遞移機率 若以矩陣表示，其形式如下 Tan/管理數學 第7章 第 頁

9 例題 3 將例題2中的遞移機率以矩陣表示。 解： 例題2的馬可夫鏈有三個狀態，我們以狀態1、2、3分別代表上漲、持平或下跌的狀態。因此當現態為狀態1時，次一階段到達狀態1、2、3的遞移機率分別為 Tan/管理數學 第7章 第346頁

10 例題 3（續） 解（續）： 以此類推，故用矩陣表示則為 Tan/管理數學 第7章 第346頁

11 遞移機率 遞移矩陣 具n個狀態的馬可夫鏈可用n × n的遞移矩陣(transition matrix) T來表示，其
元素為aij (1  i  n; 1  j  n)： 且遞移矩陣T有如下性質： 對任意的i與j，aij  0。 矩陣T的每一行的總和均等於1。 Tan/管理數學 第7章 第 頁

12 例題 4 都市與郊區間的人口流動 政府預期每年居住在都市的人口會有3%遷移到郊區，且居住在郊區的人口會有6%遷移到都市。現在已知人口的分布有65%住在都市，其餘35%住在郊區。假設總人口數維持不變，試問一年後的人口分布情形如何？ Tan/管理數學 第7章 第347頁

13 例題 4 都市與郊區間的人口流動（續） 解： 我們可以利用樹狀圖及條件機率求解。本例的樹狀圖繪於圖2。由條件機率的性質可知，隨機抽取一人，則他(或她) 1年後會住在都市的機率為 (0.65)(0.97) + (0.35)(0.06) = 1年後會住在郊區的機率為 (0.65)(0.03) + (0.35)(0.94) = 因此，1年後的人口分布為65.15%居住於都市，而34.85%的人口居住於郊區。 Tan/管理數學 第7章 第347頁

14 例題 4 都市與郊區間的人口流動（續） 解（續）： Tan/管理數學 第7章 第347頁

15 例題 5 都市與郊區間的人口流動 承例題4，試問2 年後居住於都市的人口比例有多少？3 年後呢？ 解：
例題 5 都市與郊區間的人口流動 承例題4，試問2 年後居住於都市的人口比例有多少？3 年後呢？ 解： 令X2 代表2年後人口分布的行向量。若將X1 視為「初始」人口分布，則X2 只是下一階段的人口分布，因此，可乘上一個T矩陣求得分布 Tan/管理數學 第7章 第348頁

16 例題 5 都市與郊區間的人口流動（續） 解（續）： 類似的做法可得X3 如下
例題 5 都市與郊區間的人口流動（續） 解（續）： 類似的做法可得X3 如下 亦即3 年後居住於都市的人口佔65.41%，居住於郊區的人口佔34.59%。 Tan/管理數學 第7章 第348頁

17 分布向量 由前面的例子可以看出， X0 , X1 , X2 , X3之間存在如下關係式： X1 = TX0 , X2 = TX1 = T2X0及X3 = TX2 = T3X0，由此我們可以進行歸納。 Tan/管理數學 第7章 第349頁

18 分布向量 假設有一具備n個狀態的馬可夫鏈，系統一開始處於狀態1、狀態2、…、狀態n的機率分別寫成p1, p2, ... , pn，則其機率分配可表成n維向量如下： 稱為分布向量(distribution vector)。若T是該馬可夫鏈的n × n遞移矩陣，則系統經過m次的觀察後，新的分布向量為 (1) Tan/管理數學 第7章 第349頁

19 例題 6 計程車的移動區域 吉利計程車行為了方便追蹤所屬計程車的動向，將市鎮劃分成三個區域：區域1、區域2 及區域3。吉利計程車行的管理者根據過往的紀錄得知，在區域1上車的顧客，有60%在同一區域下車，30%在區域2下車，10%在區域3下車。在區域2上車的顧客，有40%在區域1下車，30%在區域2下車，30%在區域3下車。另外在區域3上車的顧客，有30%在區域1下車，30%在區域2下車，40%在區域3下車。 Tan/管理數學 第7章 第349頁

20 例題 6 計程車的移動區域（續） 又知某一天開始營運時，有80%的計程車分布於區域1，15%的計程車分布於區域2，5%的計程車分布於區域3，又知計程車空車時會固定在原區域內逗留直至招到乘客為止。 a. 利用馬可夫鏈敘述計程車的移動區域，寫出其遞 移矩陣。 b. 在所有計程車載客一回結束後，找出其新的分布 情形。 c. 在所有計程車載客二回後，找出其新的分布情 形。 Tan/管理數學 第7章 第349頁

21 例題 6 計程車的移動區域（續） 解： 今區域1、區域2 及區域3 分別以馬可夫鏈的狀態1、狀態2及狀態3來代表。 a. 其遞移矩陣為
例題 6 計程車的移動區域（續） 解： 今區域1、區域2 及區域3 分別以馬可夫鏈的狀態1、狀態2及狀態3來代表。 a. 其遞移矩陣為 Tan/管理數學 第7章 第 頁

22 例題 6 計程車的移動區域（續） 解（續）： b. 問題中的初始分布向量為 Tan/管理數學 第7章 第350頁

23 例題 6 計程車的移動區域（續） 解 b（續）： 令X1 代表一次觀察之後(即所有計程車載客一回結束後)的分布向量，則
例題 6 計程車的移動區域（續） 解 b（續）： 令X1 代表一次觀察之後(即所有計程車載客一回結束後)的分布向量，則 亦即會有55.5%的計程車位於區域1，30%的計程車位於區域2，14.5%的計程車位於區域3。 Tan/管理數學 第7章 第350頁

24 例題 6 計程車的移動區域（續） 解（續）： c. 令X2代表二次觀察之後(即所有計程車載客二回後)的分布向量，則
例題 6 計程車的移動區域（續） 解（續）： c. 令X2代表二次觀察之後(即所有計程車載客二回後)的分布向量，則 亦即會有49.65%的計程車位於區域1，30%的計程車位於區域2，20.35%的計程車位於區域3。此結果與利用T2X0 計算出來的一樣。 Tan/管理數學 第7章 第350頁

25 7.2 正規馬可夫鏈 例題1 女性的教育狀況 據調查完成大學教育的母親之中，女兒也完成大學教育的佔70%；未完成大學教育的母親之中，女兒完成大學教育的僅佔20%。已知現在完成大學教育的女性為20%，若照此趨勢發展，最後完成大學教育的女性會有多少比例？ Tan/管理數學 第7章 第355頁

26 例題1 女性的教育狀況（續） 解： 本問題屬於馬可夫鏈，令完成大學教育為狀態1，未完成大學教育為狀態2，則遞移矩陣為 初始分布向量為
例題1 女性的教育狀況（續） 解： 本問題屬於馬可夫鏈，令完成大學教育為狀態1，未完成大學教育為狀態2，則遞移矩陣為 初始分布向量為 Tan/管理數學 第7章 第 頁

27 例題1 女性的教育狀況（續） 解（續）： 利用第7.1節公式(1) 可找出經過一代、二代、三代之後的女性教育狀況的分布向量X1 , X2 及X3 如下： Tan/管理數學 第7章 第356頁

28 例題1 女性的教育狀況（續） 解（續）： 我們亦可繼續計算往後幾代的分布向量： Tan/管理數學 第7章 第356頁

29 例題1 女性的教育狀況（續） 解（續）： 從這裡已經可以看出長期的趨勢為
例題1 女性的教育狀況（續） 解（續）： 從這裡已經可以看出長期的趨勢為 上述的向量稱做系統的極限(limiting) 或穩態分布向量(steady-state distribution vector)。 或 Tan/管理數學 第7章 第356頁

30 例題1 女性的教育狀況（續） 解（續）： 由以上的數據可知，本例的初始分布情形，女性當中有20%完成大學教育，80%未完成大學教育；經過一代之後，女性當中有30%完成大學教育，70%未完成大學教育。若依此趨勢發展，經過許多代以後，女性當中將會有40%完成大學教育，60%未完成大學教育。 Tan/管理數學 第7章 第 頁

31 正規馬可夫鏈 正規馬可夫鏈 若隨機矩陣T的次冪 T, T2, T3, ...
趨近一個穩態矩陣，且符合以下兩個條件者，稱為正規馬可夫鏈(regular Markov chain)： a. 穩態矩陣裡每個元素都是正的。 b. 同一列上的元素，其值均相等。 Tan/管理數學 第7章 第358頁

32 例題 2 判斷下列各矩陣是否為正規隨機矩陣： 解： a. 因矩陣中各元素均為正數，故知其為正規隨機矩 陣。 Tan/管理數學
第7章 第 頁

33 例題 2（續） 解（續）： b. 由於矩陣中有一個元素為0，因此，我們計算它的 次冪： 在二次冪時，所有元素均已是正數，故知其為正
　次冪： 　在二次冪時，所有元素均已是正數，故知其為正 　規隨機矩陣。 Tan/管理數學 第7章 第359頁

34 例題 2（續） 解（續）： c. 令矩陣為A並計算它的次冪：
　由於A3 = A，因此知道A4 = A2, A5 = A, ...，由此判斷，不管 　是A的任何次冪，不可能得到所有元素均為正的結果，故知 　矩陣A不是正規的。 Tan/管理數學 第7章 第359頁

35 正規馬可夫鏈 求穩態分布向量 令T是一個正規隨機矩陣，則其穩態分布向量為下面方 程式的解 TX = X 並需滿足X向量的元素和為1 的條件。
Tan/管理數學 第7章 第359頁

36 例題 3 下面的遞移矩陣T屬於正規馬可夫鏈，試求其穩態分布向量： Tan/管理數學 第7章 第360頁

37 例題 3（續） 解： 本例的T即為例題1 之遞移矩陣。令馬可夫鏈的穩態分布向量X為 則TX = X得 由此列出線性方程組 Tan/管理數學
第7章 第360頁

38 例題 3（續） 解（續）： 但第一式與第二式各自化簡後，會發現它們與下面的方程式是一樣的：
加上x + y = 1 的條件後，便得到以下線性方程組： Tan/管理數學 第7章 第360頁

39 例題 3（續） 解（續）： 由第一式可得 代入第二式後，得到 Tan/管理數學 第7章 第360頁

40 例題 3（續） 解（續）： 因此，解得穩態分布向量為 與例題1 的結果相符。 Tan/管理數學 第7章 第361頁

41 例題 4 計程車的移動區域 在第7.1節的例題6 中，我們找出敘述計程車移動區域的遞移矩陣T，並知T為正規隨機矩陣。試求計程車長時間之後在三個區域的分布情形。 Tan/管理數學 第7章 第361頁

42 例題 4 計程車的移動區域（續） 解： 令穩態分布向量X為 則由TX = X得 Tan/管理數學 第7章 第361頁

43 例題 4 計程車的移動區域（續） 解（續）： 由此寫出線性方程組： 化簡後的線性方程組為 Tan/管理數學 第7章 第361頁

44 例題 4 計程車的移動區域（續） 解（續）： 加上x + y + z = 1的條件後，得到以下四個方程式的線性方程組： Tan/管理數學
例題 4 計程車的移動區域（續） 解（續）： 加上x + y + z = 1的條件後，得到以下四個方程式的線性方程組： Tan/管理數學 第7章 第362頁

45 例題 4 計程車的移動區域（續） 解（續）： 利用第2 章的高斯—喬登消去法，解得
例題 4 計程車的移動區域（續） 解（續）： 利用第2 章的高斯—喬登消去法，解得 即x  0.47, y = 0.30 與z  0.23。因此，最後大約有47%的計程車分布在區域1，30% 的計程車分布在區域2，以及23% 的計程車分布在區域3。 Tan/管理數學 第7章 第362頁

46 7.3 吸收馬可夫鏈 吸收馬可夫鏈 若一馬可夫鏈的遞移矩陣是吸收隨機矩陣，則稱之為吸收馬可夫鏈(absorbing Markov chain)。 吸收隨機矩陣 一個吸收隨機矩陣(absorbing stochastic matrix)必須符合 下面兩個性質： 至少存在一個吸收態。 在任一非吸收態的物體，均有機會經由一個或多個階段來到吸收態。 Tan/管理數學 第7章 第368頁

47 例題 1 判斷下面的矩陣是否為吸收隨機矩陣： Tan/管理數學 第7章 第369頁

48 例題 1（續） 解： a. 由於矩陣的a22=1且第二行的其餘元素均為0，因此知狀態2為吸收態。同理可知，狀態4 亦為吸收態。接下來要問的是，在非吸收態(狀態1 與狀態3) 的物體，是否有機會進入吸收態──狀態2或狀態4？檢視矩陣的第一行，可知在狀態1的物體有0.3的機會可到達狀態3。再由矩陣的第三行元素可知，在狀態3的物體有0.5 的機率可以進到狀態2，有0.2 的機率可以進入狀態4。我們注意到，雖然在狀態1的物體無法經一個階段即到達吸收態，但因有機會進入狀態3，便可由狀態3再到吸收態，只是中間需要經歷多個階段。綜合上述，本矩陣為一吸收隨機矩陣。 Tan/管理數學 第7章 第369頁

49 例題 1（續） 解（續）： b. 狀態1 與狀態2 是吸收態，但處在非吸收態(狀態3 與狀態4) 的物體，都不可能到達狀態1 或狀態2。因此，本矩陣不是吸收隨機矩陣。 Tan/管理數學 第7章 第369頁

50 例題 2 賭徒的毀滅 軍豪決定以本錢 2 元參加賭局。他每次都下 l 元的賭注，每回贏的機率都是0.4 。軍豪將反覆地賭，直到錢輸光或手上擁有 3 元為止。請寫出此吸收馬可夫鏈的遞移矩陣。 解： 本題的馬可夫鏈有 4 個狀態，分別代表軍豪在賭的過程中手上的金額，有 $1、$2 及 $3 。由於 $0 的狀態表示錢輸光，不再玩，因此，這兩個狀態都是吸收態。 Tan/管理數學 第7章 第370頁

51 例題 2 賭徒的毀滅（續） 解（續）： 把吸收態排在前面， $3 也表示達到目標不再寫出遞移矩陣如下，並說解$0 玩明於後：
例題 2 賭徒的毀滅（續） 解（續）： 把吸收態排在前面， $3 也表示達到目標不再寫出遞移矩陣如下，並說解$0 玩明於後： 矩陣的第一、第二行因對應吸收態，故 a11 = a22 = l 且 a21 = a31 = a41 = 0 , a12 = a32 = a42 = 0 。 Tan/管理數學 第7章 第370頁

52 例題 2 賭徒的毀滅（續） 解（續）： 矩陣的第三行因對應非吸收態， $ l ，因此須考慮玩一把的結果：已知贏的機率是 0.4 ，此時將累積到 $2 ，故有 a43 = 0.4 ；且輸的機率是 ，將剩下$ 0 ，故有 a13 = 0.6 。矩陣的第四行因對應非吸收態， $2 ，玩下一把的結果，贏的機率是 0.4 , 此時將累積到 $3 ，故有 a24 = 0.4 ；凡輸的機率是 0.6 ，將剩下$1 ，故有 a34 = 0.6 。 Tan/管理數學 第7章 第370頁

53 吸收馬可夫鏈 求吸收馬可夫鏈的穩態矩陣 假設一吸收隨機矩陣 A 已切割成子矩陣如下 則A 的穩態矩陣為
此處定義(I – R)–1內的單位矩陣 I 與 R 的維度相同。 Tan/管理數學 第7章 第371頁

54 例題 3 賭徒的毀滅 如同例題 2 的敘述，軍豪將反覆地賭，直到錢輸光了或手上擁有 3 元為止。試問軍豪最後贏錢累積到 $3的機率為何？
例題 3 賭徒的毀滅 如同例題 2 的敘述，軍豪將反覆地賭，直到錢輸光了或手上擁有 3 元為止。試問軍豪最後贏錢累積到 $3的機率為何？ 解： 例題 2中，我們已寫出遞移矩陣，予以切割後 Tan/管理數學 第7章 第371頁

55 例題 3 賭徒的毀滅（續） 解（續）： 得到子矩陣R與S 因此 且 Tan/管理數學 第7章 第371頁

56 例題 3 賭徒的毀滅（續） 解（續）： 求其反矩陣（可利用第2.6節的公式）得 與S相乘後 Tan/管理數學 第7章 第 頁

57 例題 3 賭徒的毀滅（續） 解（續）： 得到A的穩態矩陣為
例題 3 賭徒的毀滅（續） 解（續）： 得到A的穩態矩陣為 我們因此知道，軍豪從$2 開始賭，最後累積到 $3 結束賭局的機率為 0.53，亦即贏 $ l 的機率是 53 %。 Tan/管理數學 第7章 第372頁

58 例題 4 遺傳學 有一特殊的玫瑰品種，若具 AA 基因會開出紅色的花，具 Aa 基因會開出粉紅色的花，具 aa 基因會開出白色的花。這裡的 A 為顯性基因， a 為隱性基囚。此外，兩裸母株交配之後，它們的基因會遺傳到子株身上。今假設所有的後代都只與紅色植株交配，試說明經過無數代之後，最終只會剩下紅色的玫塊花。 Tan/管理數學 第7章 第372頁

59 例題 4 遺傳學（續） 解： 本例題的馬可夫鏈共有三種狀態，分別表示三類基因 AA、Aa及aa 。我們寫出遞移矩陣如下，並說明於後：
例題 4 遺傳學（續） 解： 本例題的馬可夫鏈共有三種狀態，分別表示三類基因 AA、Aa及aa 。我們寫出遞移矩陣如下，並說明於後： Tan/管理數學 第7章 第372頁

60 例題 4 遺傳學（續） 解（續）： 因為具 AA 基因的母株與紅色植株（亦為 AA 基因）交配後的 子株，只可能遺傳到 AA 基因（由二母株各取得一個 A 的基因），因此，矩陣的第一行為 a11 = 1 , a21 = a31 = 0。若是具 Aa 基因的母株與紅色植株 交配其子株有 的機會得到A或a的基因，加上來自 紅色植株的 A 基因，因此子株為 AA 或 Aa 基因的機 率各半，故矩陣的第二行為 。 Tan/管理數學 第7章 第 頁

61 例題 4 遺傳學（續） 解（續）： 若是具 aa 基因的母株與紅色植株交配，其子株必然得到 a的基因，加上來自紅色植株的 A 基因，因此子株基因肯定為 Aa ，故矩陣的第三行的a23 = 1 ，其餘為0。 Tan/管理數學 第7章 第373頁

62 例題 4 遺傳學（續） 解（續）： 由遞移矩陣的對角線元素可知狀態 AA 是一個吸收態，且另兩個非吸到達狀態 AA ，因此，本例是一個吸收馬可夫鏈陣求得。其長期的效果，可由 T 的穩態矩陣求得。首先將 T 做個切割。 Tan/管理數學 第7章 第373頁

63 例題 4 遺傳學（續） 解（續）： 得到子矩陣R與S 因此 且 Tan/管理數學 第7章 第373頁

64 例題 4 遺傳學（續） 解（續）： 求其反矩陣（可利用第2.6節的公式）得 與S相乘後 Tan/管理數學 第7章 第373頁

65 例題 4 遺傳學（續） 解（續）： 得到T的穩態矩陣為 由於穩態矩陣第一列的元素均為 l ，因此表示交配到最後，花色將全部變紅。
例題 4 遺傳學（續） 解（續）： 得到T的穩態矩陣為 由於穩態矩陣第一列的元素均為 l ，因此表示交配到最後，花色將全部變紅。 Tan/管理數學 第7章 第373頁

66 7.4 賽局理論與嚴格判定賽局 賽局理論（game theory ）的發展得歸功於約翰 · 馮 · 紐曼（John von Neu-mann , ） ，他是 20 世紀位一位偉大的數學家。之後於 1994 年，約翰 · 哈森義（John Harsanyi ）、約翰 · 納許（ John Nash ）與仁哈德 · 塞頓（ Reinhard Selten ）三人更因在賽局理論上的重大貢獻，而獲得諾貝爾獎。賽局理論結合矩陣方法與機率論，探討在二位或更多對手競爭的情境下，各方可以採取的最佳策略（optimal strategy ) ，原則上以尋求自身的最人穫利（gain ) 或最小損失（loss）為目的。例如，撲克牌的玩家、競爭行號問急欲擴充市場佔有率的管理者、不同黨派的競選總部、或敵我作戰部隊的將領之間），便而臨這類問題的考驗。為簡化起見，我們只討論兩個參賽者（player ）的賽局（game） ，並稱為二人賽局（ two-person game） Tan/管理數學 第7章 第379頁

67 例題 1 錢幣配對 唐先生和聶小姐，一塊兒玩錢幣配對遊戲。在事先不知對方的選擇下，各自選定十元錢幣的一側（正面或反面），爾後同時打開手掌。若兩人都是正面，則唐先生必須付聶小姐 3 元；若聶小姐是正面，唐先生選反面，則聶小姐需付唐先生 6 元；若頗小姐是反面，唐先生選正面，則唐先生需付頗小姐 2 元；若兩人都是反面，則唐先生必須付聶小姐 1 元。在這個遊戲裡，雙方都想找到一個最佳策略，使自己可以贏最多的錢（或者，使自己可以輸得最少）。 Tan/管理數學 第7章 第379頁

68 二人賽局 例題 l 的錢幣配對遊戲是典型的零和賽局（zero-sum game），即一方的收益代表另一方的損失，因此，雙方的付款總和必然為零。例如，當唐先生與聶小姐都出示正面時，若從唐先生（支付）的角度看，因唐先生必須支付 3 元，故記做+3而聶小姐因收入 3 元，故她的支付款記做 3 ，二者的和即為0。 Tan/管理數學 第7章 第379頁

69 二人賽局 以下將錢幣配對遊戲的支付額情形寫成矩陣形式： Tan/管理數學 第7章 第379頁

70 二人賽局 矩陣各行代表唐先生所採取的行動，各列代表聶小姐所採取的行動。炬陣中的元素代表雙方採取的行動之後果，為免混淆，固定以唐先生的支付額登錄。亦即唐先生需付款給聶小姐時（唐先生輸錢的時候），其值為正，而聶小姐需付給唐先生時（唐先生贏錢的時候），其值為負。例如， a22 = 1 表示兩人都出示反面時，唐先生需支付 1 元給聶小姐，而 a12 = 6 則表示聶小姐出示正面，唐先生出示反面時，唐先生將從聶小姐處贏得 6 元。 Tan/管理數學 第7章 第 頁

71 二人賽局 今假設有R與C兩名參賽者的一個二人賽局，參賽者R可採取的行動為R1, R2, …, Rm共m個，而參賽者C可採取的行動為C1, C2, …, Cn共n個。我們可利用一個m × n 大小的矩陣來表示雙方採取的行動組合後果，形式如下 Tan/管理數學 第7章 第380頁

72 二人賽局 其中，第i列第j行的元素aij表示 R 採取 Ri的行動且 C 採取 Cj 的行動時，參賽者 C 的支付額（ payoff ）為aij ，指 C 應付給 R 的款項。注意當 R 需支付給 C 時，則 aij的值為負。上面的矩陣，我們稱為支付額矩陣（ payoff matrix ）。 Tan/管理數學 第7章 第380頁

73 例題 2 一賽局的支付額矩陣如下： 請解釋矩陣內容。 Tan/管理數學 第7章 第380頁

74 例題 2（續） 解： 此二人賽局的參賽者 R 有兩種行動，而參賽者 C 有三種行動。假設支付的單位是元。由支付額矩陣可知，若 R 選擇 R1的行動，則 當 C 採取 C1時， R 贏 1 元。 當 C 採取 C2時， R 輸 2 元。 當 C 採取 C3 時，R 贏 3 元。 若 R 選擇 R2的行動，則 當 C 採取 C1時， R 贏 4 元。 當 C 採取 C2時， R 輸 5 元。 當 C 採取 C3 時，R 輸 1 元。 Tan/管理數學 第7章 第 頁

75 二人賽局 極小值最大化策略 從支付額矩陣的每一列找出最小元素，稱列極小值。 從所有的列極小值中選出最大的，其所在列即參賽者 R 的最佳行動。
Tan/管理數學 第7章 第381頁

76 二人賽局 前述的支付額矩陣運用極小值最大化策略的結果，圈選元素1如下： 因此，聶小姐的最佳行動是採用R2，而圈選的元素1表示她至少會贏1元。
Tan/管理數學 第7章 第381頁

77 二人賽局 極大值最小化策略 從支付額矩陣的每一行找出最大元素，稱行極大值。 從所有的行極大值中選出最小的，其所在行即參賽者 C 的最住行動。
Tan/管理數學 第7章 第382頁

78 二人賽局 承例提1，唐先生運用極大值最小化策略的結果，圈選元素1如下：
因此，唐先生的最佳行動是採用C2，而圈選的元素1代表他最多只會輸掉1元。 Tan/管理數學 第7章 第382頁

79 例題 3 針對下面的支付額矩陣，找出它的極小值最大化策略與極大值最小化策略： 解：
先寫出每一列的極小值與每一行的極大值，再從列極小值中圈選最大者（此處為1，位於第三列），得到極小值最大化策略，表示列參賽者應採取第三列的行動。 Tan/管理數學 第7章 第382頁

80 例題 3（續） 解（續）： 若從行極大值中圈選最小者（此處為 0 ，位於第 2 行），得到極大值最小化策略，表示行參賽者應採取第二行的行動。
Tan/管理數學 第7章 第 頁

81 例題 4 針對下面的支付額矩陣，找出它的極小值最大化策略與極大值最小化策略： 解：
先寫出每一列的極小值與每一行的極大值，再從列極小值中圈選最大者（此處為3，位於第2列），得到極小值最大化策略，表示列參賽者應採取第二列的行動。 Tan/管理數學 第7章 第383頁

82 例題 4（續） 解（續）： 若從行極大值中圈選最小者（此處為 3 ，位於第 3 行），得到極大值最小化策略，表示行參賽者應採取第三行的行動。 Tan/管理數學 第7章 第383頁

83 二人賽局 最佳策略 賽局裡所指的最佳策略（optimal strategy ) ，係對某一名 參賽者最為有利的策略。 Tan/管理數學
第7章 第384頁

84 二人賽局 嚴格判定賽局 一個嚴格判定賽局（ strictly determined game ）具備下 面的性質：
在支付額矩陣中，存在一元素，既是所處列的最小值，也是所處行的最大值。該元素稱為此賽局的鞍點（ saddle point ）。 對列參賽者而言，他的最佳策略是極小值最大化策略，選取的即是鞍點的所在列。對行參賽者而言，他的最佳策略是極大值最小化策略，選取的即是鞍點的所在行。 Tan/管理數學 第7章 第384頁

85 例題 5 一個二人零和賽局的支付額矩陣如下： a. 證明此賽局是一個嚴格判定賽局，並找出它的鞍 點。 b. 分別找出兩位參賽者的最佳策略。
c. 賽局值為何？試問此賽局對誰較有利？ Tan/管理數學 第7章 第 頁

86 例題 5（續） 解： a. 先寫出每一列的極小值與每一行的極大值： 再圈選出元素2 ，它同時為所在列的最小值與所在行的最
　再圈選出元素2 ，它同時為所在列的最小值與所在行的最 　　大值，故此元素a23 = 2 為鞍點。此鞍點的存在，證明這是 　　一個嚴格判定賽局。 Tan/管理數學 第7章 第385頁

87 例題 5（續） 解（續）： b. 因鞍點位於第二列第三行，對列參賽者而言，他 的最佳策略是第二列，對行參賽者而言，他的最 佳策略是第三行。
　　的最佳策略是第二列，對行參賽者而言，他的最 　佳策略是第三行。 c. 我們得到賽局值為2，表示兩位參賽者都採行最 　　佳策略時，行參賽者將贏得2個單位，亦即此賽局 　　對行參賽者較為有利。 Tan/管理數學 第7章 第385頁

88 例題 6 一個二人零和賽局的支付額矩陣如下： a. 證明此賽局是一個嚴格判定賽局，並找出它的鞍 點。 b. 分別找出兩位參賽者的最佳策略。
c. 試問此賽局是否對誰較為有利？ Tan/管理數學 第7章 第385頁

89 例題 6（續） 解： a. 先寫出每一列的極小值與每一行的極大值：
再圈選出元素4，共有兩個，它們都同時為所在列的最小值與所在行的最大值，故本賽局有兩個鞍點，a11 = 4及a31 = 4。這些鞍點的存在，證明這是一個嚴格判定賽局。另外要注意的是，雖然鞍點可能有多個，但其值應相等。 Tan/管理數學 第7章 第 頁

90 例題 6（續） 解（續）： b. 由於鞍點有兩個，都落在第一行，分別位於第一 及第三列。因此，對列參賽者而言，他的最佳策
　及第三列。因此，對列參賽者而言，他的最佳策 　　略是第一及第三列，對行參賽者而言，他的最佳 　　策略只有第一行。 c. 我們得到賽局值為4，表示此賽局對列參賽者較為 　　有利。 Tan/管理數學 第7章 第386頁

91 7.5 混合策略的賽局 混合策略 Tan/管理數學 第7章 第391頁

92 賽局的期望值 賽局的期望值 令 Tan/管理數學 第7章 第393頁

93 賽局的期望值 分別代表列參賽者與行參賽者的混合策略，且知其賽局的支付額矩陣A (維度m × n) 為 Tan/管理數學 第7章 第393頁

94 賽局的期望值 則此賽局的期望值計算如下： Tan/管理數學 第7章 第393頁

95 例題 1 唐先生和聶小姐一起玩錢幣配對遊戲，其支付額矩陣如下(唐先生視為行參賽者，聶小姐視為列參賽者)：
以下若聶小姐採用P的混合策略，而唐先生採用Q的混合策略，試求賽局的期望支付額： 與 Tan/管理數學 第7章 第394頁

96 例題 1（續） 解： a. 由公式計算得 　因此，在重複的賽局下，從長期看，雙方並沒有 　輸贏。 Tan/管理數學 第7章 第394頁

97 例題 1（續） 解（續）： b. 由公式計算得 因此，在重複的賽局下，從長期看，對列參賽者
　因此，在重複的賽局下，從長期看，對列參賽者 　(聶小姐) 而言，每一回比賽平均將輸掉1.06元。 Tan/管理數學 第7章 第394頁

98 例題 2 一賽局的支付額矩陣如下： a. 如果列參賽者採用極小值最大化策略，且行參賽者採用極大值最小化策略，試問對列參賽者而言，期望支付額為多少？ b. 如果列參賽者採用極小值最大化策略的機會為50%，選擇其餘兩列的機會各為25%，且行參賽者選擇各行的機會分別為50%，試問對列參賽者而言，期望支付額為多少？ Tan/管理數學 第7章 第395頁

99 例題 2（續） 解： a. 我們利用第7.4節的方法，尋找極小值最大化策略與極大值最小化策略如下： 　 Tan/管理數學 第7章 第395頁

100 例題 2（續） 解 a（續）： 列參賽者的最佳單一策略是選擇第二列，而行參賽者的最佳單一策略是選擇第二行。如果兩位參賽者都採用上述的最佳單一策略，則從支付額矩陣的第二列第二行元素可知，賽局的期望支付額為支付給列參賽者2元。 Tan/管理數學 第7章 第395頁

101 例題 2（續） 解（續）： b. 根據題意，可寫出列參賽者的混合策略為 　行參賽者的混合策略為 Tan/管理數學 第7章 第395頁

102 例題 2（續） 解 b（續）： 由公式計算，支付給列參賽者的期望支付額為 Tan/管理數學 第7章 第 頁

103 賽局的期望值 2 × 2非嚴格判定賽局的最佳混合策略 令 為一非嚴格判定賽局的支付額矩陣。則對列參賽者而言， 其最佳混合策略是 (2a)
其中 Tan/管理數學 第7章 第 頁

104 賽局的期望值 對行參賽者而言，其最佳混合策略是 (2b) 其中 Tan/管理數學 第7章 第397頁

105 賽局的期望值 此外，當P與Q分別是列與行參賽者的最佳混合策略時，賽局值定義成此賽局的期望值E = PAQ，即 (2c) Tan/管理數學
第7章 第397頁

106 例題 3 錢幣配對遊戲 依照例題1 的支付額矩陣： a. 找出唐先生與聶小姐二人的最佳混合策略。
例題 3 錢幣配對遊戲 依照例題1 的支付額矩陣： a. 找出唐先生與聶小姐二人的最佳混合策略。 b. 計算賽局值，並判斷此賽局是否對誰較為有利？ Tan/管理數學 第7章 第397頁

107 例題 3 錢幣配對遊戲（續） 解： a. 由於此支付額矩陣沒有鞍點，因此這是一個非嚴格判定賽局。將a = 3, b = 2, c = 2 與d = 1 代入公式(2a)： Tan/管理數學 第7章 第397頁

108 例題 3 錢幣配對遊戲（續） 解 a（續）： 故知聶小姐的最佳混合策略為 Tan/管理數學 第7章 第398頁

109 例題 3 錢幣配對遊戲（續） 解 a（續）： 利用公式(2b)： Tan/管理數學 第7章 第398頁

110 例題 3 錢幣配對遊戲（續） 解 a（續）： 得知唐先生的最佳混合策略是 Tan/管理數學 第7章 第398頁

111 例題 3 錢幣配對遊戲（續） 解（續）： b. 利用公式(2c)可計算出賽局值： 由於賽局值為負，所以，此賽局對唐先生較為有利。當唐
例題 3 錢幣配對遊戲（續） 解（續）： b. 利用公式(2c)可計算出賽局值： 　由於賽局值為負，所以，此賽局對唐先生較為有利。當唐 　　先生與聶小姐都採取最佳混合策略，在重複的賽局下，從 　　長期看，平均一回唐先生將贏1/8 元。 Tan/管理數學 第7章 第398頁

112 例題 4 投資策略 連家共有4萬元在股票及貨幣市場進行短期投資，其投資的績效視優惠利率的情況而定。如優惠利率上升，將有利於貨幣市場的投資；如優惠利率下降，則利於股票市場的投資。今將連家視為列參賽者，把不同情形下估算的投資報酬率(%)當作支付額，整理出支付額矩陣如下： Tan/管理數學 第7章 第399頁

113 例題 4 投資策略（續） a. 對於連家這筆4 萬元的短期投資，其最佳投資策 略為何？ b. 連家的這項短期投資，利潤如何？
例題 4 投資策略（續） a. 對於連家這筆4 萬元的短期投資，其最佳投資策 略為何？ b. 連家的這項短期投資，利潤如何？ Tan/管理數學 第7章 第399頁

114 例題 4 投資策略（續） 解： a. 由支付額矩陣可知，此為非嚴格判定賽局。令P = [p1 p2] 代表連家的最佳混合策略，利用公式(2a)，解得 Tan/管理數學 第7章 第399頁

115 例題 4 投資策略（續） 解 a（續）： 故連家宜投資(6/7)(40,000)，即大約34,300元於貨幣市場，以及(1/7)(40,000)，約5700元於股票市場。 Tan/管理數學 第7章 第399頁

116 例題 4 投資策略（續） 解（續）： b. 我們求出賽局值 故知連家這項4 萬元的短期投資，預期會有12.14%的投資
例題 4 投資策略（續） 解（續）： b. 我們求出賽局值 　故知連家這項4 萬元的短期投資，預期會有12.14%的投資 　報酬率，即獲得(0.1214)(40,000) = 4,856元的利潤。 Tan/管理數學 第7章 第 頁