OR12 对策论博弈论.ppt

运筹学第12讲——对策论(博弈论)简介
广州大学地理科学学院蔡砥
10/9/2017
内容
对策现象及其三个要素
对策问题举例及对策的分类
矩阵对策(矩对策)的基本理论
关于纯策略与混合策略
10/9/2017
对策现象及其三个要素
10/9/2017
经典案例:囚徒困境
两个犯罪嫌疑人被捕并受到指控,但除非至少一个人招认犯罪,警方并无充足证据将他们按罪判刑。
警方把他们关入不同牢房,并对他们说明不同行动带来的后果:
如果两人都不坦白,将均被判为轻度犯罪,入狱一个月;如果双方都坦白招认,都将被判入狱6个月;最后,如果一人招认而另一人拒不坦白,招认的一方将马上获释,而另一人将判入狱9个月(所犯罪行6个月,干扰司法加判3个月)。
前提:两囚犯是非合作的。
10/9/2017
囚徒困境的双变量矩阵表示
囚徒面临的问题可用上图的双变量矩阵表来描述。( “双变量”指的是在两个参与者的博奔中,每一单元格有两个数字——分别表示两个参与者的收益)
习惯上,横行代表的参与者(囚徒1)的收益在两个数字中放前面;列代表的参与者(囚徒2)的收益置于其后。
无论囚徒1选择沉默(不坦白),或者招认,囚徒2都会选择招认;反之也然。
10/9/2017
对策现象的三个要素
局中人
策略(集)
赢得函数
一般,当局中人、策略集和赢得函数这3个要素确定后,一个对策模型也就给定。
10/9/2017
局中人(players)
一个对策中,有权决定自己行动方案的对策参与者称为局中人,通常用I表示局中人的集合。一个对策中至少有两个局中人。
局中人是广义的,可以是单个个人,也可以是一个集体,利益完全一致的参与者只能看成一个局中人。
局中人都是“理性的”:遵从博弈(game)的规则并总是采取最利己的策略。
10/9/2017
关于理性局中人的一个有趣例子
海盗分宝石:
5个海盗抢到了100颗宝石,每一颗都一样的大小和价值连城。他们决定这么分:
1. 抽签决定自己的号码(1,2,3,4,5)
2. 首先,由1号提出分配方案,然后大家5人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则提案人将被扔入大海喂鲨鱼。
3. 如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
4. 依次类推
问:最终的方案为如何?
前提:海盗们非常遵守规则,并谋求利益最大化
命不能丢
宝石要尽量多
10/9/2017
理性的破坏
照《三国》,1命刀斧手埋伏于帐侧,到时候一声令下,将其他4个统统剁成肉泥!!!
照《水浒》,1奋起一脚掀掉桌子,挑一个最有主见的,抽刀砍了~~来个林冲刀砍王伦!!!其他几个立马跪地告饶:“哥哥息怒!!!哥哥但要独得~尽管拿去就是了!!!”
引自网易科技论坛,码帖人:乱话三千
10/9/2017
策略(strategies)
博弈中,可供局中人选择的一个实际可行的完整的行动方案称为一个策略。局中人i的策略集记为Si,一般的,每一个局中人的策略集中至少应包括2个策略。
囚徒困境问题中,囚徒的策略有2个:沉默或招认;
海盗问题中
提出方案的海盗有多个策略:各种可能的分配方案
其它海盗的策略有2个:支持或否决。
10/9/2017