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

Slides:



Advertisements
Similar presentations
课程:博弈论 教材:《经济博弈论》 《经济博弈论习题指南》 复旦大学出版社. 第一章 导论 博弈论定义 经典博弈模型 博弈结构与分类 博弈论历史与发展 博弈论在中国的发展.
Advertisements

2009 套读自考本科简介 —— 抓住机遇,用知识改变命运 目 录 二、提升学历、提升自身素质的途径选择 三、高教自考和套读自考本科介绍 四、我校自考套读本科情况介绍 一、就业状况 五、我校今年招生专业介绍.
组长 : 章莹莹 组员 : 陆文嫣 舒翼 钱悠舜 谢瑞 婷. 东方明珠塔位于上海蒲东, 1991 年 7 月 30 日动 工, 1994 年 10 月 1 日建成。塔高 468 米,与外滩 的 “ 万国建筑博览群 ” 隔江相望,建设完成时, 列亚洲第一,世界第三高塔。 东方明珠塔由三根直径为 9 米的立柱、塔座、下.
我的家乡我的家乡 河北迁安河北迁安. 迁安市隶属于河北省, 位于河北省东北部,燕 山南麓,滦河岸边,地 理坐标为:东经 118°37′ ~ 118°55′ ,北 纬 39°51′ ~ 40°15′ 之间, 辖 12 个镇、 7 个乡、 1 个 街道,总面积 1208 平方 公里,截至 2011 年,总.
旅游景点分布介绍.  1 、自然景观  2 、人文景观  3 、展馆  4 、休闲度假.
小组成员 : 陈佳 张美蓉 边疆 吴程 阮宇博 郭聪. 仙都 ,位于缙云县境内,是一 处以峰岩奇绝、山水神秀为特色、 融田园风光与人文史迹为一体, 以观光、休闲、度假和科普为主 的国家级重点风景名胜区、国家 首批 AAAA 级旅游区。境内九 曲练溪、十里画廊;山水飘逸、 云雾缭绕。有奇峰一百六、异洞.
1 债券融资业务拓展交流 债券业务部 二 O 一二年二月. 2 目 录  第一部分 债券融资业务概述  第二部分 东兴证券债券融资业务情况介绍及前景展望  第三部分 什么样的企业适合发债  第四部分 债券融资业务合作开发方式及激励探讨.
轴对称(一) 课堂引入 仔细观察下列图片,思考这些图片有什么样 的特点.
邵阳. 史称 “ 宝庆 ” 。位于湖南省 西南部,南接广西壮族自治 区桂林市。总面积 平 方公里,全市辖 3 个市辖区、 7 个县、 1 个自治县,代管 1 个 县级市。市人民政府驻大祥 区。是一座拥有 2500 多年历 史的古城 。 宝庆湖南桂林 有娄邵铁路与湘黔、京广 线相接,沪昆高速、
博弈论与经济学思维.
我的家乡我塑造 制作者:韩树涛.
创意鄱阳湖— 一种基于无形资源理念开发鄱阳湖的思考 以传奇背景音乐作为开场,体现创意创造传奇 南昌大学 黄细嘉
防盜裝置  學生科技探究.
饮食中的平衡 酸 性 食 物 与 碱 性 食 物.
期末書面報告指定書籍 王鼎鈞回憶錄---昨天的雲
举国上下抗击风雪灾害专刊 温暖行动 灾情告急年关近 万众一心齐抗灾 可歌可泣留千古 温暖行动遍人间 导读提示 阳关雨露出版社
川信-丰盛系列集合资金信托计划 2016年3月.
古文選讀.
賽局理論 Game Theory.
农信社信贷产品实务技能提升培训.
“三生教育”专题 生命·生存·生活.
作文选刊 作文之窗
高齡者道路交通事故特性與道安防制措施 研究計畫報告
统一刊号:CN44–0181/02 旅游报刊 出版日期:2006﹒12﹒8 深圳旅游报社出版 华东旅游 泰州旅游 苏州旅游.
结合崇明建设生态岛和开发旅游景点开发的现状与问题
是重要的感觉器官,有许多感觉器,具触觉、嗅觉功能,还能感受异性的性信息素。 触角由柄节、梗节和鞭节三部分组成。
快乐假期 2010年第6期 总第54期 贝尔芬 主编 暑期作文专刊 《快乐假期》杂志社 出版.
项目亮点 融资方为AA级发债主体,是当地唯一的综合平台公司
以賽局角度探討企業經營策略 張宮熊 中華民國青年企業研究社2009理事長; 青年企業管理評論總編輯; 國立屏東科技大學企管系暨財金所教授;
复习 什么是结构? 结构是指事物的各个组成部分之间的有序搭配和排列。
美丽麻城.
神奇的宇宙 我们的太阳系 宇宙中天体有哪些类型? 刊号:CN77-87 编辑: 施雅苑 今日一叠4版 第1期 认识宇宙 16岁的哈勃
植物辨識及分類 呂春森 基隆市立暖暖高級中學 植物辨識及分類 呂春森 基隆市立暖暖高級中學.
老师:如何撰写教研文章? 主讲:石修银 谨以此赠与孜孜追求的老师 谨以此赠与改变人生的老师.
依“标”据“本”,命制考题 发表于《数学教学》2006年第9期 (华东师大核心“CN”刊物)
第九章 寡头垄断市场的价格与产量决定.
第三课 闲话“家”常 1.
肇庆七星岩.
12星座 对于星座,你又知道多少呢? 第一刊.
“华东师大数学系部分老同事活动”(辛卯聚会)记事
第五节 读图表述.
財團法人中華民國證券櫃檯買賣中心 交 易 部 中華民國101年8月
定风波.
管理好种公鸡提高雏鸡质量.
走进 莱 芜 制作人:楠楠.
美丽青浦,古韵水乡 青浦一中 六(4)班 庄歆怡.
数学通报简介 ——如何写稿及投稿 数学通报 郑亚利 2014年8月.
腾冲叠水河瀑布 和来凤山公园 音乐:贝多芬——F大调浪漫曲 摄影、制作:曹珏 陈晓芬.
邵阳文化.
口腔衞生.
凤凰古城 公共管理学院李靖涛 学号
推进《玻璃钢制品工》 国家职业资格证书制度的建设
企业所得税年度申报表讲解 —— 特别行业.
本期导读: 1版 习 惯 2版 的 十个做人的好习惯 3版 力 4版 量 5版 6版 7版 8版
第三部分 博弈论 §3.1实验二:双方信任博弈 例如:一厂商支付给一名工人高于均衡水平的工资,并且期望这名工人能够回报以相应的更多的劳动。主动方厂商出于对被动方的信任,率先背离了标准的不合作博弈论所阐述的最优选择,若工人也提供了回报,则双方得到一个合作的结果。在现实中,这样的例子很多,比如酒店会给熟客赊账,而客人也不会赖账,我们将这一类建立在信任基础上的合作波已称为双方信任博弈。
中国古代史中考复习方略 石城二中 黄北京.
马克思主义基本原理概论 第三章 人类社会及其发展规律.
口腔卫生.
人无信不立 业无信不兴 公路建设市场信用体系 建设综述 交通运输部公路局 交通运输部公路局
The Effects of Exogenous and Endogenous Uncertainty in Static Games
第十六章 賽局理論 Game Theory 作業研究 二版 2009 © 廖慶榮.
第六章 完全信息静态博弈 博弈的基本概念 纳什均衡 纳什均衡应用 混合策略和混合策略纳什均衡.
Introduction to Game Theory
第七章 機率與賽局理論.
政治大學公企中心財經學分班 課程名稱:管理經濟學 MANAGERIAL ECONOMICS
學習目標 瞭解什麼是賽局 知道賽局是如何發展成一們重要的學科 瞭解賽局的本質 熟悉賽局組成的要素 OBJECTIVES.
Topic 8 賽局理論(Ch5).
06 无形资产投资环节的会计处理.
職業學校課程綱要發展指導委員會第2次會議 職業學校課程綱要總綱 修訂說明報告 計畫主持人:國立臺灣科技大學 蔡顯榮主任.
知识点:交流接触器的结构和工作原理 主讲教师:冯泽虎.
Presentation transcript:

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

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

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

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

遞移機率 敘述馬可夫過程中由某個狀態到達下一個狀態的機率(如例題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頁

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

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

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

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

例題 3(續) 解(續): 以此類推,故用矩陣表示則為 Tan/管理數學 第7章 第346頁

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

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

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

例題 4 都市與郊區間的人口流動(續) 解(續): Tan/管理數學 第7章 第347頁

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

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

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

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

例題 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頁

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例題 3(續) 解(續): 由第一式可得 代入第二式後,得到 Tan/管理數學 第7章 第360頁

例題 3(續) 解(續): 因此,解得穩態分布向量為 與例題1 的結果相符。 Tan/管理數學 第7章 第361頁

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

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

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

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

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

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

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

例題 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頁

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

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

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

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

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

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

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

例題 3 賭徒的毀滅(續) 解(續): 求其反矩陣(可利用第2.6節的公式)得 與S相乘後 Tan/管理數學 第7章 第371-372頁

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例題 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章 第380-381頁

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例題 2(續) 解(續): b. 根據題意,可寫出列參賽者的混合策略為  行參賽者的混合策略為 Tan/管理數學 第7章 第395頁

例題 2(續) 解 b(續): 由公式計算,支付給列參賽者的期望支付額為 Tan/管理數學 第7章 第395-396頁

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

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

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

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

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

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

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

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

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

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

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

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

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

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