区块链安全►博弈论

博弈论

ps：声明！！！该内容为本人从公选课途径获取，如有错误，轻喷！！!

引言

博弈三要素

  1. 谁参与这个博弈
    参与这个博弈的，叫做这个博弈的参与人或者局中人 (player)。
    n 个参与人的博弈，叫做 n 人博弈 (n—person game)。
  2. 可供参与人选择的行动 (action) 或者策略 (strategy)
    对局 (strategy profile)
    策略组合 (strategy combination)
  3. 支付
    在博弈的各种对局下各参与人的赢利或者得益，叫做参与人的支付 (payoff)

囚徒困境

1
设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑8年；如果另一个犯罪嫌人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑2年，而坦白者有功被减刑8年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1年。

智猪博弈

1
猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有个踏板，每踩一下踏板，在远离踏板的猪圈的另一边的投食口就会落下少量的食物。如果有一只猪去踩踏板，另一只猪就有机会抢先吃到另一边落下的食物。当小猪踩动踏板时，大猪会在小猪跑到食槽之前刚好吃光所有的食物；若是大猪踩动了踏板，则还有机会在小猪吃完落下的食物之前跑到食槽，争吃到另一半残羹。

博弈树

1 序贯决策博弈采用 “树型” 表示方法。

1
2
3
1. 根和分枝点是决策节点(decision nodes)，
2. 树梢即各枝梢是末端节点(terminal nodes)。
3. 每个末端节点标示出博弈如果走到这里每个参与人的得益。
  1. 每一博弈树都有一个根 (root)，并且只有一个根


博弈的基本分类

  1. 最基本的分类：
    按照博弈各方是否同时决策，分为静态博弈和动态博弈。
    按照大家是否都清楚各种对局情况下每个局中人的得益，分为完全信息博弈和不完全信息博弈。
  • 完全信息：
    各种对局情况下每个局中人的得益多少是所有局中人的共同知识 (common knowledge)。
  1. 完美信息博弈 (games with perfect information) 和不完美信息博弈 (games with imperfect information)
  • 完美性：
    如果在博弈进行过程的每一时刻，面临决策或者行动的参与人，对于博弈进行到这个时刻为止所有参与人曾经采取的决策或者行动完全清楚，这样的博弈叫做完美信息博弈。
    只有动态博弈才考虑完美或不完美信息。
  1. 零和博弈，常和博弈，非常和博弈
  • 零和博弈
    如果一个博弈在所有各种对局下全体参与人之得益的总和总是保持为 0，博弈就叫做零和博弈 (zero-sum game)，也称 “严格竞争博弈”。
    猜硬币，田忌赛马，石头 - 剪刀 - 布
  • 常和博弈
    博弈方之间利益的总和为常数。博弈方之间的利益是对立的且是竞争关系。
    分配固定数额的奖金、利润，遗产官司
  • 非常和博弈
    零和博弈和常和博弈以外的所有博弈。合作利益存在，博弈效率问题的重要性。
    囚徒困境、产量博弈等
  1. 合作博弈和非合作博弈
    两者的区别在于参与人在博弈过程中是否能够达成一个具有约束力的协议。倘若不能，则称非合作博弈
  • 合作博弈
    合作博弈强调的是集体主义，团体理性，是效率、公平、公正
  • 非合作博弈
    非合作博弈则主要研究人们在利益相互影响的局势中如何选择策略使得自己的收益最大，强调个人理性、个人最优决策，其结果是有时有效率，有时则不然

同时决策博弈

二人同时博弈的三要素

  1. 局中人
  2. 策略 / 行动
  3. 支付 / 得益
  • 局中人
  1. 根据局中人的个数博弈可分为 “二人博弈” 和 “多人博弈”
  • 策略
  1. 参与博弈的各局中人在进行决策时，可以选择的方法、做法或经济活动的水平、量值等。
  • 支付
  1. 在每一个博弈中，给定一个策略组合，参与博弈的每一个局中人都会有相应的支付
  2. 是指每个局中人从博弈中获得的利益，它体现每个参与博弈的局中人的追求，也是他们行为和决策的主要依据。
  3. 支付本身可以是利润、收入、量化的效用、社会效益、福利等。
  4. 支付可取正值，也可取负值，取正值表示得益。

支付矩阵

  • 例子
    石头，剪刀，布
    策略集
    策略组合
    支付向量（1 赢，0 平，-1 输）
  • “石头，剪刀，布” 支付矩阵
  • 有限博弈
  1. 局中人数目有限并且每个局中人可以选择的 (纯) 策略的数目也有限的博弈，叫做有限博弈 (finite games)。
  • 三人博弈
  1. 例子
    例子
    局中人：A、B 和 C
    每个局中人有三种策略：数字 1，2，3
    支付：每个局中人得到 4 乘以三人中所选的数字中的最小者，再减去自己所选的数字。
  2. 支付矩阵


  • 正规型 (策略型) 博弈
  1. 例子

优势策略

  1. 在某个博弈中，如果不管其他局中人选择什么策略，一个局中人的某个策略选择给他带来的支付始终高于其他策略选择，或者至少不低于其他策略选择，这样，只要这个局中人是一个理性的局中人，那么他必定愿意选择这个策略。
  2. 优势策略可分为：
    整体的严格优势（劣势）策略 (strictly dominant strategy) 如：囚徒困境
    弱优势策略 (weakly dominant strategy)
  3. 例子囚徒困境

相对优势策略和纳什均衡

  • 相对优势策略
  • 纳什均衡
  1. 局中人单独改变策略不会得到好处的对局即策略组合，就叫做纳什均衡
  2. 检验纳什均衡
    盯住一个格子，如果这个格子里面__右上方的数字向右或者向左移动都不变大、这个格子里面左下方的数字向上或者向下移动也都不变大__，那么这个格子代表的策略组合，就是这个二人博弈的一个纳什均衡。
    ps：箭头的方法感觉更好
  3. 相对优势策略划线法

    原则上，相对优势策略标记法适用于任何有限博弈，即可用于多人有限博弈。
  4. 箭头指向法
    依次考察矩阵型博弈的每个策略组合，如果在这个策略组合某个局中人能够通过单独改变策略选择增加自己的支付，则从所分析的策略组合下他所对应的支付处引一箭头，指向他单独改变策略后新的策略组合下他所对应的支付。当所有策略组合都这样处理完了以后，没有箭头指出去的那些格子表征的策略组合，就是博弈的纳什均衡。

    纳什均衡：（-3，-3）

    纳什均衡：（2，1）（1，2）

混合策略纳什均衡

混合策略与期望支付

扯到概率论了… 不太会捏

反应函数法

  • 例子






    纳什均衡之间的取舍

多重纳什均衡及其筛选

当博弈出现多重纳什均衡时，哪个纳什均衡最有可能成为最终的博弈结果？

1
2
1. 取决于某种能使局中人产生一致性预测的机制或判断标淮。
2. 在现实生活中，人们往往可以通过一些约定俗成的观念或者某种具有一定合理性的机制，引导博弈的结果朝着比较有利于局中人的方向发展。
  • 帕累托优势标准
    按照支付大小筛选出来的纳什均衡，比其他纳什均衡具有帕累托优势。这种标准，称为帕累托优势标准。
  1. 例子
1
设想在古代的一个地方，有两个猎人，那时候，狩猎是人们的主要生计。为了简单起见，假设主要的猎物只有两种，鹿和兔子。在古代，人类的狩猎手段越是比较落后，弓箭的威力也有限。在这样的条件下，进一步假设，两个猎人一起去猎鹿，才能猎获一只鹿，如果一个猎人单兵作战，他只能打到四只兔子。从填饱肚子的角度来说，4只兔子能管4天，一只鹿却差不多能够解决一个月的问题。
  1. 帕累托优势
  • 风险优势标准
    考虑不同纳什均衡之间的风险状况，风险小的优先
  1. 期望赢利比较法
  2. 偏离损失比较法
  • 帕累托标准与风险优势的关系
    如果在一个博弈中，按照帕累托效率的标准筛选出的纳什均衡，与按照风险优势标准筛选出来的纳什均衡不一致时，应当选择哪一个呢？
1
2
3
4
5
6
7
8
9
10
帕累托优势标准:   
A  
风险优势:  
期望赢利比较法：  
B  
损失偏离比较法：  
B  
很多人会选择B。
理由一：人是会犯错误的；
理由二：人不喜欢冒大的风险（风险厌恶）。

聚点均衡

1
2
基本思想：在现实生活中，局中人可能会使用某些被博弈模型抽象掉的信息来达到一个均衡，这些信息往往跟社会文化习惯、局中人过去博弈的历史和经历有关。
对于一些既不存在帕累托优劣关系，也不存在风险优劣关系的博弈，人们往往都是利用聚点均衡的思想来指导自己的决策行动。
  1. 例子
  • 情侣博弈
1
如果今天是男的生日，  (足球，足球)可能是一个聚点均衡；而如果是女的生日，(芭蕾，芭蕾)可能是一个聚点均衡。这里，出现聚点均衡背后的原因是，在女的生日时，男的可能认为应该讨女的欢心，而女的也认为男的会认为应该讨自己欢心，结果，他们都出现在芭蕾舞厅。

相关均衡

关均衡是局中人主动设计某种形式的选择机制形成制度安排从而确定对局结果的一种均衡选择。

抗共谋均衡

如果局中人多于两个，有可能会发生部分局中人联合起来追求小团体利益的共谋行为，从而导致均衡情况的变化。

强均衡

如果在其他局中人的策略选择给定的条件下，不存在局中人集合的任意一个子集所构成的联盟，能够通过联合偏离当前的策略选择而增加联盟中所有成员的支付，那么这个策略组合就叫作强均衡。

1
2
1. 强均衡一定是抗共谋均衡,但是抗共谋均衡未必是强均衡。
2. 强均衡不一定是帕累托最优的。

颤抖的手精炼均衡

泽尔滕在 1975 提出了颤抖手精炼均衡或者简称颤抖手均衡的概念。
基本思想：在任何一个博弈中，每一个局中人都有一定的犯错误的可能性。
博弈的均衡是否经得起颤抖呢？局中人所选择的一个策略组合，只有当它在允许每个局中人都可能犯小小的错误时仍是所有局中人的最优策略组合时，才是一个足够稳定的均衡。

序贯决策博弈

序贯决策博弈与博弈树

  • 例子
1
2
3
4
以房地产开发为例
参与人是A、B
A先行，然后是自然选择市场大小，最后B行动
自然选择的概率分布为：市场需求大的概率为1/2，需求小的概率1/2。

  1. 博弈树由节点 (nodes) 和棱 (edges) 组成，节点又分为决策节点 (decision nodes) 和末端节点 (terminal nodes)。
  2. 决策节点是局中人作出决策的地方。每个决策节点都与一个在该决策节点上进行决策的局中人相对应。
  3. 每棵博弈树都有一个初始决策节点，初始决策节点也叫做博弈树的根 (root)，是博弈开始的地方。

序贯博弈的纳什均衡






倒推法（逆向推导法）

  • 一般步骤
    从序贯博弈的最后一个决策阶段开始分析，每一次确定出所分析阶段局中人的行动选择和路径。然后再确定前一阶段决策的局中人的行动选择和路径。

同时博弈与序贯博弈

完美信息博弈

如果一个序贯博弈的每个信息集都是一个单点集，那么么该序贯博弈就是完美信息博弈。 否则，它就是不完美信息博弈。

零和博弈

  • 零和博弈
    每一局博弈的总支付，即双方得失之和总是 0。
  • 二人 “常和” 博弈
    每局双方得失之和虽然不是零，却是一个常数。

感想

1
2
3
4
博弈论是这样一个过程：它是个人或团体在一定规则约束下，依据各自掌握的关于别人选择的行为或策略，决定自身选择的行为或策略的收益过程。  
通过本次公选课收获了很多知识，博弈论的一些专业术语；还有博弈的分类：合作博弈和非合作博弈，静态博弈和动态博弈，完全信息博弈与不完全信息博弈，纯策略和混合策略；并且学会了找纳什均衡的各种方法，通过各种有趣的事例，详细清晰的明白各种策略，以及利用一些数学方法和哲学理论进行解决。其中我觉得对我个人收获最大了是拓宽了我的知识面，我结合最近火爆的区块链知识和博弈论进行一个理解。 
区块链和博弈论是两个不同的领域，乍一看似乎并没有太大的关联性，但事实并非如此。几乎所有的博弈论经典案例都可以借助区块链构建出新的博弈关系
区块链本质上是一个去中心化数据库。是一种分布式数据存储，点对点传输，共识机制，加密算法等计算机技术的新型应用模式。那么，一个无序的、去中心化的点对点系统是如何保持其诚信的呢？矿工权利很大，且很容易作恶并逃脱。这就是先前尝试构建去中心化系统失败的地方。毕竟，用户是人类，而人类就有作恶的倾向。因此，如何建立一个有人类诚信的去中心化系统？答案就在一个最基本的经济学概念中：博弈论。
访问量次 | 访客人 |