博弈论知识点总结 |
您所在的位置:网站首页 › 博弈论中的纳什均衡 › 博弈论知识点总结 |
系列文章目录
提示:国科大其他课程资料整理 国科大高级AI——强化学习(格子问题) 国科大高级AI——博弈论以及相关考题 国科大高级AI——一阶谓词逻辑 国科大高级AI——证明题历年考题 国科大高级AI——深度学习整理 国科大高级AI——野人和传教士问题 国科大模式识别——历年考题以及课后题整理 文章目录 系列文章目录前言一、纳什均衡与帕累托均衡1.纳什均衡2.帕累托最优与社会最优 二、讨价还价问题三、maxmin策略和minmax策略四、最优匹配问题1.如何找到最优匹配?——穷举法2.如何找到最优匹配?—— 引入价格机制 五、网络交换博弈网络交换博弈基本概念纳什议价解备选项 均衡结局 前言主要是国科大高级AI课程的博弈论相关的考点,纳什均衡和帕累托均衡、讨价还价问题、maxmin和minmax策略、最优匹配问题以及网络交换博弈问题都是重要的选择题考点、maxmin策略和minmax策略的计算应该不会考,价格机制的最优匹配也不会考,但是也是很有意思的知识点。 一、纳什均衡与帕累托均衡首先先回顾上课讲到的三种模型,囚徒困境、性别之战和石头剪刀布: 定义:如果一个局势下,每个局中人的策略都是相对其他局中人当前策略的最佳应对,则称该局势是一个纳什均衡 注意:我们在分析纳什均衡的时候一定要充分考虑到每一个局中人,同时我们在分析问题的过程中也可以使用固定一方去观察其他局中人来完成分析。 囚徒困境:对于囚徒1而言,囚徒1的最优策略是坦白,而囚徒2的最优策略也是坦白,双方坦白即是囚徒策略的纳什均衡。 性别大战:1.对于妻子来说,他的最优策略是看韩剧,那我们就先将该策略固定住,看在妻子看韩剧策略下,丈夫采取什么方式是最优的(即:丈夫也看韩剧),2.我们将丈夫固定住,丈夫最优策略是看体育,那在丈夫看体育的情况下,妻子也看体育是最优的。所以性别大战有两个纳什均衡(双方都看体育或者双方都看韩剧) 石头剪刀布:没有纯策略的纳什均衡,可以通过上面的分析分析得出。 纳什定理: 1.任何有限博弈都至少存在一个纳什均衡,不一定是纯策略纳什均衡,例如剪刀-石头-布。 2.寻找博弈的纳什均衡是困难的 2.帕累托最优与社会最优帕累托最优:对于一组策略选择(局势),若不存在其他策略选择使所有参与者得到至少和目前一样高的回报,且至少一个参与者会得到严格较高的回报,则这组策略选择为帕累托最优。 如何理解帕累托最优呢?对于一组决策,我不管别人怎么选,作为局中人的我就是要选择对我最有利的决策从而得到这个“较高”的回报。 拿囚徒困境来说,对于囚徒A,囚徒B无论选坦白还是抗拒,囚徒A选择坦白的收益是最高的。而对于B也一样,我不要去管A选什么,我只管选择坦白来让我的收益是最高的。所以囚徒困境的帕累托最优是:(抗拒,抗拒)、(抗拒,坦白)、(坦白,抗拒)。 为什么(坦白,坦白)不是帕累托最优呢,注意后半就行“至少一个参与者会得到严格较高的回报”,双方都坦白的话,有一方的抗拒可以使得另一个局中人获得所谓“较高的”收益。 社会最优:1.使参与者的回报之和最大的策略选择(局势)2.社会最优的结果一定也是帕累托最优的结果. 3.帕累托最优不一定是社会最优。 帕累托最优的决策组合一共有3个,分别是(坦白,抗拒),(抗拒,坦白) 和(抗拒,抗拒), 纳什均衡策略组合(坦白,坦白)不是帕累托最优 社会最优策略组合是(抗拒,抗拒) 二、讨价还价问题
好好搞复习…后面的以后来补… 三、maxmin策略和minmax策略
以性别之战为例子: 首先你得先得到一个关于妻子和丈夫的一个收益表
还是这样的一个收益表 在零和博弈中,maxmin策略和minmax策略是等价的。(因为收益总和为0,此消彼长,削弱对手和增强自己的效果一致) 四、最优匹配问题匹配的效用:成功匹配的估价之和,称为匹配的效用 最优匹配:效用最大的匹配 最优匹配对于个体而言不一定是最优的,但是对社会而言一定是最好的。 1.如何找到最优匹配?——穷举法就类似于该题:xin对于Room1、Room2、Room3估价为12,2,4,其他人估价如图所示: 不是考点,以后有时间补吧。 五、网络交换博弈 网络交换博弈基本概念网络交换博弈的一些概念和知识点 对于两个在交易的节点A和B来说,他们分别存在备选项收益分别为x、y。(备选项怎么计算后面会有) 在这里x+y1 A和B就不会交易(如果x+y>1,那么A、B双方就会更加倾向于和备选项去进行交易) 在下图中A只能和B交易,所以A备选项是B,B目前在和A交易(一般粗线相连的 节点之间达成交易)但是B和C由浅线相连,那么我们可以说B、C互为对方的备选项,备选项的值为:1减去潜在交易对象的值(即1-2/3=1/3) 给定一个结局,如果结局中的任意一个参与配对的边都满足纳什议价解的条件,则称该结局是均衡结局。 均衡结局一定是稳定结局。 因此,在寻找均衡结局时,可以先寻找稳定结局,进而确定均衡结局。 如何去说均衡结局呢?均衡结局是一种交易上的折衷,举个例子商人A和商人B一直在交易,交易的次数变多了,他们的交易价格最后也趋于一个稳定。他们就会不由自主的放弃自己的一些利益做折衷,以保持交易的稳定性。 均衡是交易出来的,我们也可以管这一次次的交易叫迭代。 举例子 我们可以声明,框出来的第二个网络交易的结局是稳定的。 当然我们可以拿其他网络试试,拿第三个网络为例子: 只计算A、B,我们令A初始备选项为x(0),B初始备选项为y(0),其中x(0)=0,y(0)=1/4,A、B剩余成本 s = 1-0-1/4 = 3/4: 进行迭代: A 新一轮收益为: x(0) + s/2 = 3/8 B 新一轮收益为: y(0) + s/2 = 5/8 x(1) = 0 y(1) = 3/8 没事干可以迭代算一下,你会发现,A的收益最后在不断向1/3靠近、B的收益在不断向2/3靠近。 这就是为了保证交易稳定性而不断进行的折衷。但是无论怎么说:此时的A、B还没有达到稳定。该网络交易模型结局不是均衡结局 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |