【博弈论】基础知识
【博弈论】基础知识
博弈论是研究决策制定者在竞争和合作情境中如何做出最优决策的理论。本文将从策略式博弈、扩展式博弈以及纳什均衡三个维度，为您详细介绍博弈论的基础知识。
1 策略式博弈
策略式博弈又称静态博弈，它是一次博弈。策略式博弈G GG形式化表示为：
G = { N , { A i } i = 1 N , { u i } i = 1 N } G=\left{N,\left{A_{i}\right}{i=1}^{N},\left{u{i}\right}_{i=1}^{N}\right}G={N,{Ai }i=1N ,{ui }i=1N }
其中：
- N NN：玩家集，所有玩家的有限集合；
- A i A_{i}Ai ：玩家i ii的策略集：表示玩家i ii可选择的策略的集合；
- u i u_iui ：玩家i ii的收益函数：A 1 × A 2 × … A N → R A_{1} \times A_{2} \times \ldots A_{N} \rightarrow RA1 ×A2 ×…AN →R表示在一组策略下的收益。
完全信息静态博弈具有以下特点：
- 非合作博弈
- 同时行动（simultaneous move）：所有玩家同时做出策略选择。在选择策略时不知道其他玩家的策略选择
- 完全信息（complete information）：每个玩家的的策略和收益函数都是所有玩家的共同知识（common knowledge）
非完全信息静态博弈（也称静态贝叶斯博弈）具有以下特点：
- 非合作博弈
- 同时行动（simultaneous move）：所有玩家同时做出策略选择。在选择策略时不知道其他玩家的策略选择
- 非完全信息（incomplete information）：至少有一个玩家不能准确地知道其他某个玩家的收益函数。
以囚徒困境为例：
完全信息静态博弈：
两名犯罪嫌疑人被抓捕，被关到不同的牢房，但警方无充足证据，两名嫌疑人被告知：
- 若双方都不坦白，则均被判一个月；
- 若双方都坦白，则均被判六个月；
- 若一方坦白而另一方不坦白，则坦白一方释放，不坦白一方被判九个月。
可以使用双变量矩阵来表示二者的收益：
非完全信息静态博弈：
两名犯罪嫌疑人被抓捕，被关到不同的牢房，但警方无充足证据，两名嫌疑人被告知：
- 若双方都不坦白，则均被判一个月；
- 若双方都坦白，则均被判六个月；
- 若一方坦白而另一方不坦白，则坦白一方释放，不坦白一方被判九个月。
除此之外，还有额外需要注意的：
- Prisoner 1 总是理性的，即自私的
- Prisoner 2 可能是理性的，也可能是利他的，取决于他的心情
- 当 Prisoner 2 是利他时，那么他更偏好不坦白，他认为坦白等于“额外入狱四个月”
- Prisoner 1 不能准确地判断 Prisoner 2 是利己的还是利他的，但他能推断 Prisoner 2 理性的概率为 0.8，利他的概率为 0.2。
2 扩展式博弈
扩展式博弈，也称动态博弈，它与策略博弈相对应。在扩展式博弈中，玩家是轮流进行决策的，通常可用博弈树将其刻画。
博弈树由结点(node)和边(edge)组成，对应博弈玩家、策略和收益。
- 非叶子结点：代表博弈玩家，表示这个时候哪个博弈玩家做出决策。每个非叶子结点有且仅有一个博弈玩家。
- 叶子结点：代表每个玩家在此时的收益。收益只存在于叶子结点。
- 边：表示策略
扩展式博弈G GG形式化表示为：
G = { N , H , P , { u i } } G=\left{N, H, P,\left{u_{i}\right}\right}G={N,H,P,{ui }}
其中：
- N NN为玩家集合；
- H HH为“策略的序列”构成的集合，可以是有限集或者无限集。H HH中的元素称为历史(history)。性质包括：
- ∅ ∈ H \emptyset \in H∅∈H，表示博弈树的根结点。
- 如果策略序列a 1 a 2 … a k ∈ H a^{1} a^{2} \ldots a^{k} \in Ha1a2…ak∈H并且s < k s<ks<k，那么a 1 a 2 … a s ∈ H a^{1} a^{2} \ldots a^{s} \in Ha1a2…as∈H
- 如果无穷策略序列( a k ) k = 1 ∞ \left(a^{k}\right){k=1}^{\infty}(ak)k=1∞ 满足对于任意的k kk，a 1 a 2 … a k ∈ H a^{1} a^{2} \ldots a^{k} \in Ha1a2…ak∈H，那么( a k ) k = 1 ∞ ∈ H \left(a^{k}\right){k=1}^{\infty} \in H(ak)k=1∞ ∈H
- 每一条历史序列都对应博弈树的一个结点，对应历史序列末端到达的结点
- 在完全信息扩展式博弈中，历史集大小=结点个数
- 最终历史集(Terminal history set)：Z ZZ= {All Terminal history}，在这些结点上是收益
- P PP为博弈玩家函数(Player Function)：
- P : H \ Z → N P: H \backslash Z \rightarrow NP:H\Z→N给每一个非终结历史分配玩家集N NN中的一个元素
- P ( h ) P(h)P(h)表示在历史h hh后，轮到哪个玩家做决策
- u i u_iui 为收益函数，表示第i ii个玩家的收益
3 纳什均衡
继续上面
完全信息静态博弈
的囚徒困境的例子。我们先站在犯人1的角度思考：
- 如果2坦白了，我选择坦白，则收益为-6；如果我不选择坦白，则收益为-9。因此我会选择坦白；
- 如果2不坦白，我选择坦白，则收益为0；如果我不选择坦白，则收益为-9，因此我会选择坦白。
同时，犯人2也会这么想。因此二者都会坦白。
最优反应：当对手策略选定的时候，玩家会调整自己的策略，使得自己的收益在几种策略选择中是最大的。
纳什均衡：任何一位玩家在此策略组合下单方面改变自己的策略（其他玩家策略不变）都不会提高自身的收益。
也就是每个玩家的策略都是最佳反应的时候，就会形成一个稳定的局面，即达到纳什均衡。
纳什均衡的形式化定义如下：
纳什均衡是博弈结果a ∗ = ( a 1 ∗ , a 2 ∗ , … , a N ∗ ) a^{}=\left(a_{1}^{}, a_{2}^{}, \ldots, a_{N}^{}\right)a∗=(a1∗ ,a2∗ ,…,aN∗ )，即对每个玩家i ii都有：
u i ( a i ∗ , a − i ∗ ) ≥ u i ( a i , a − i ∗ ) u_{i}\left(a_{i}^{}, a_{-i}^{}\right) \geq u_{i}\left(a_{i}, a_{-i}^{*}\right)ui (ai∗ ,a−i∗ )≥ui (ai ,a−i∗ )
因此，我们可以通过寻找同时满足所有人的最佳反应的博弈结果，来求解纳什均衡。