title: 博弈论 斯坦福 game theory stanford week 2-0
tags: note
notebook: 6- 英文课程 - 15-game theory
---
混合策略和纳什均衡
一个例子
我们从一个例子说起, 我们说美国人为了保护自己的利益, 在索马里设卡安检, 我们不妨考虑这样的博弈问题, 说在索马里有很多的路段, 安检者和恐怖袭击者是博弈者如果袭击和安检发生在同一地点, 那么袭击者会受到损失, 如果不是, 袭击者会得到好处对于检查者问题正好相反
但是由于没有相应的情报支持, 两者的决策只能依靠随机进行, 并不会产生固定的决策, 这样的策略称为混合策略
混合策略,
Kv
就像上面的例子一样, 我们考虑这个决策问题:
两个人的利益看起来并不能通过固定的选择方式进行分割, 只能通过随机的选择, 这样就是混合策略
下面我们定义下这种决策,
决策:, 决策是行动 的一个随机变量
纯策略: 在概率中只有一个行为可以采用
混合策略: 在我们的策略中, 可以采用多种策略
在这些策略中, 所有的行为称为策略的支撑
我们还要定义所有的策略
我们还要定义所有策略的收益
在上述的情况下, 我们可以对我们的收益和支出进行概率性的讨论
我们可以定义期望的收益如下:
第一行的公式是说, 当前的收益是所有的行为带来的利益的加权平均值, 第二行说我们可以使用贝叶斯公式来计算每一个的可能性
最优响应和纳什均衡
借助最优相应的概率, 我们将上述的概率化思想融入进来,
得到一个定理:
每一个完整的博弈都有一个纳什均衡
完整的博弈的定义是什么: 只要一个博弈, 拥有一定的数量的博弈者, 有着一定的行为, 有着完整的收益矩阵, 那么就是一个完整的博弈
做一个说明: 我们之前说的没有纳什均衡是说没有纯粹的纳什均衡, 但是它可以有混合的纳什均衡
比如我们前面提到的例子, 如下图:
我们的混合的纳什均衡就是:
这个样子的
要强调混合的概率是随着不同的问题决定的, 那么混合的概率是如何决定的呢, 我们可以认为当所有的博弈者都不愿意再改变他们的概率的时候, 就陷入了纳什均衡
纳什均衡的计算
一个例子
通过这样的一个示例我们讨论纳什均衡的计算方法:
我们不得不说再一般的条件下, 纳什均衡是十分难以计算的, 不过如果你合一对支持进行猜测的情况下, 我们可以相对容易的计算纳什均衡
再上图情况下, 我们假设让一个人选 b 的概率为, 选 F 的概率就是
再这个情况下, 另外一个决策者用混合策略来考虑这个问题, 他需要保证对方这两种博弈行为对自己来说是一种平衡的收益, 因为只有这样, 另外一个博弈者的收益才不会因为对方的选择而发生改变因此我们采用如下的策略列出方程:
使用混合策略的原因
通过随机性来迷惑你的对手
通过随机性来应对不确定性
多方博弈问题
两个例子
线性补充问题(linear complementarity problem)
支持计数方法(support enumeration method)
PPAD 问题
美国加州大学伯克利分校的克里斯托斯. 帕帕迪米特里欧 (Christos Papadimitriou) 教授定义了 PPAD(polynomial parity arguments on directed graphs, 有向图的多项式校验参数) 计算复杂类来描述经济学中的计算问题并与其合作者一起证明了在 4 人及以上的博弈中, 纳什均衡的计算是属于 PPAD-Complete 的
通过上述的图片可以看到, PPAD 问题是一类 NP 问题
简要的发展历史
1928:von 提出两个人的零和博弈的均衡问题
1950:nash 再所有博弈种类提出多人博弈的均衡问题
lemke-howson 算法
LCP 问题, 线性补充方程问题
其中 代表了第 i 个人使用方案 k 的概率
Ai 代表了每一个博弈者的行为, 那么
就表达当博弈者 1 采用 j 策略的平均获得
代表了纳什均衡中的获得, 从而 代表了两者的差距
好吧这里我们先跳过去
~~
纳什均衡的用例
点球问题
我们可以将点球问题当作是一个博弈的问题, 对于一个点球来说, 守门员扑球的方向和球员踢球的方向是一种博弈, 如果两者方向相同, 那么球有更大的几率被扑出
问题简化成上述图片
上述问题是我们已经讨论过的了, 概率是 0.5 0.5, 不过如果问题编程了这个样子呢, 如图:
我们将其中一个, 也就是我们认为踢球者的右脚水平比较差, 可能不会百分百进球, 那么博弈的纳什均衡会发生什么呢?
我, 我们发现纳什均衡点发生了移动, 守门员倾向于扑向右边而球员倾向于扑向左边
分别是 3/7 4/7 和 4/7 3/7
来源: http://www.bubuko.com/infodetail-2515325.html