机器博弈 (一) 入门简介

2020-01-31 本文已影响0人小小何先生

现代博弈论建立

现代博弈论的建立得从1944年算起，1944年冯·诺依曼的《博弈论与经济行为》以数学形式来阐述博弈论及其应用，标志着现代系统博弈理论的初步形成。冯·诺依曼被称为现代博弈论之父。

博弈论(game theory)，也被称为对策论。博弈者在博弈过程中的行为(action)被称作博弈行为。

博弈行为解释：带有相互竞争性质的主体，为了达到各自目标和利益，采取的带有对抗性质的行为。

博弈论主要研究博弈行为中最优的对抗策略及其稳定局势，协助人们在一定规则范围内寻求最合理的行为方式。

参与者或玩家(player)：指的是参与博弈的决策主体。
策略(strategy)：参与者可以采取的行动方案，是一整套在采取行动之前就已经准备好的完整方案。
- 某个参与者可采纳策略的全体组合形成了策略集(strategy set)。
- 所有参与者各自采取行动后形成的状态被称为局势(outcome)。
- 如果参与者可以通过一定概率分布来选择若干不同的策略，这样的策略被称为混合策略(mixed strategy)。
- 若参与者每次行动都选择某个确定的策略，这样的策略称为纯策略(pure strategy)。
收益(pay off)：各个参与者在不同局势下得到的收益。
- 混合策略参与者采取的策略是按概率分布出现的，所以混合策略意义下的收益应为期望收益(expected payoff)。
规则(rule)：指的是对参与者行动的先后顺序、参与者获得信息多少等内容的规定。

博弈论研究的基本范式：建模者对参与者(player)规定两样东西：1.可采取的策略集(strategy sets)；2. 取得的收益。观察：当参与者选择若干策略以最大化其收益时会产生什么结果。最终要实现：两害相权取其轻，两利相权取其重。

警方逮捕了共同犯罪的甲、乙两人，由于警方没有掌握充分证据，所以将两人分开审讯。假定条件：

参与者：甲、乙。

规则：甲、乙两人分别决策，无法得知对方的选择。

策略集：认罪、沉默(纯策略)。

	乙沉默	乙认罪
甲沉默	二人各服刑半年	乙被释放，甲服刑10年
甲认罪	甲被释放，乙服刑10年	二人各服刑5年

囚徒困境均衡解产生的原因：对两人而言认罪的收益在任何情况下都比沉默的收益高，所以两人同时认罪是一个稳定的局势。

囚徒困境表明稳定局势并不一定是最优局势。

合作博弈与非合作博弈
- 合作博弈(cooperative game)：部分参与者可以组成联盟以获得更大的收益。
- 非合作博弈(non-cooperative game)：参与者在决策中都彼此独立，不事先达成合作意向。

静态博弈与动态博弈
- 静态博弈(static game)：所有参与者同时决策，或参与者互相不知道对方决策。
- 动态博弈(dynamic game)：参与者所采取行为的先后顺序由规则决定，且后行动者知道先行动者采取的行为。
完全信息博弈与不完全信息博弈：
- 完全信息(complete information)：所有参与者均了解其他参与者的策略集、收益等信息。
- 不完全信息(incomplete information)：并非所有参与者均掌握了所有信息。

囚徒困境是一种非合作、不完全信息的静态博弈。

在博弈论中有一个重要的概念：纳什均衡。

博弈的稳定局势即为纳什均衡(Nash equilibrium)：指的是参与者所作出的这样一种策略组合，在该策略组合上，任何参与者单独改变策略都不会得到好处。换句话说，如果在一个策略组合上，当所有其他人都不改变策略时，没有人会改变自己的策略，则该策略组合就是一个纳什均衡。
Nash定理：若参与者有限，每位参与者的策略集有限，收益函数为实值函数，则博弈必存在混合策略意义下的纳什均衡。
囚徒困境中两人同时认罪就是这一问题的纳什均衡。

纳什均衡的本质就是不后悔。