13-boyi.Rmd

# 博弈论 {#game}

## 术语

- 博弈论说白了就是讲两方势力在一件事上为了自己的最大利益所采取的行动或决策的理论
- 参与者（players） $N= {1,...,n}$
- 参与者 $i$ 有一组行动（Actions），行动的集合 $a=(a_1,...,a_n) \in A=A_1 \times A_2 \times ... \times A_n$
- 参与者 $i$ 的每个行为的收益（Payoffs）都可以用 $u_i:A \rightarrow \Re$ 这个函数表示 $u_i(a)$ 表示某个行为产生的收益，$u = (u_i,...,u_n)$是效用函数的集合
- n个参与者的标准博弈（normal form） $\langle N,A,u \rangle$
- 两人博弈可以用矩阵（matrix）来描述，行代表选手1，列代表选手2，行对应选手1的行动 $a_1 \in A_1$，列对应选手2的行动 $a_2 \in A_2$，每个单元列出每个参与者的收益，先行选手，后列选手
- 纯竞争博弈（Games of Pure competition）：两个参与者收益对立且对于所有行动集合 $a \in A, u_1(a)+u_2(a) = c$，$c$是常数，零和博弈是一个常数为0的纯竞争博弈，此时我们只用考虑一个参与者的收益函数就可以了

## 支配策略（dominate strategy）

- 行动单一称为纯策略（pure strategies）有一定概率分布的行动策略称为混合策略（mixed strategies）
- 对于一个参与者，不论其它参与者采取任何策略，某策略都会得到最大的收益
- $a_i \in a_i$ 为强支配策略当且仅当参与者$i$ 的收益 $u_i(a_i,a_{-i}) > u_i(a'_i,a_{-i})$，如果 $a'_i = a_i$，那么为弱支配策略

## 最佳回应（Best respinse）

- 对于一个参与者，当已知其他参与者的行为后，收益最大的策略
- 参与者$i$，对于其它参与者的策略$a_{-i} \in a_{-i}$ 的策略如果$u_i(a_i,a_{-i}) \geqslant u_i(a'_i,a_{-i})$

## 纳什均衡（Nash Equilibrium）

- $a = \langle a_1,...,a_n\rangle$ 是一个纯策略纳什均衡当且仅当对于任何一个行为i，有$a_i \in BR(a_{-i})$
- 如果任何参与者改变行为的收益都不会增加，那么此时进入纳什均衡
- 纳什均衡是一系列行为的列表，这些行为都是稳定的
- 支配策略是纳什均衡但反过来不一定对
- 任何有限博弈都存在一个纳什均衡（纳什1950年提出）

## 帕累托最优（Pareto Optimality）

- 某个结果是帕累托最优当且仅当没有其他结果可以全局帕累托支配这个结果
- 帕累托最优表示某个博弈结果不差于其他博弈结果
- 纳什均衡不一定是帕累托最优（囚徒困境）

## 混合策略（Mixed stratergies）

- 策略$S_i$指对于每个参与者行动的概率分布集合
- 概率 $Pr(a|s) = \prod_{j \in N}s_j(a_j)$
- 期望收益函数 $u_i(s) = \sum_{a \in A} u_i(a)Pr(a|s)$
- 随机策略会使对手混乱进入动态，很多博弈只存在混合策略纳什均衡而没有纯策略纳什均衡（石头剪子布）
- 混合策略的目的在于不论你使用哪一种行动，对方的收益都不变

选手   |甲     |乙      
-------|-------|-------
丙     |a,b    |c,d
丁     |e,f    |g,h

- 对于选手1而言，采取丙行动的收益是$aq+c(1-q)$，采取丁行动的收益是$eq+g(1-q)$，q代表选手2采取甲行动概率
- 如果要达到双方均衡，那么不论采取什么行动收益应该一致，不会因为对方概率的变化而偏离，那么我们就可以求解均衡时选手2的行动概率：

$$aq+c(1-q) = eq+g(1-q)$$

$$q = \frac{g-c}{a+g-c-e}$$

- 这个结果表明选手2采取行动主要要参考选手1的行动收益差
- 同理，对选手2而言，采取甲行动收益是$bp+f(1-p)$，采取乙行动收益是$dp+h(1-p)$，p为选手1采取丙行动的概率，求解的到：

$$p=\frac{h-f}{b+h-d-f}$$
- 要达到混合策略纳什均衡，博弈双方的行动概率主要参考对方的行动收益差；同时因为概率已知，我们也可以给出纳什均衡时双方的期望收益
- 应用：守门员博弈，当攻守双方达到纳什均衡时，其概率分布十分接近现实的统计数据，通过策略调整，博弈双方收益会逐渐收敛到纳什均衡，然后就不再变化

## 寻找纳什均衡

- 两人博弈可以用线性互补算法（Linear Complementarity）求解
- 严格说因为一定存在纳什均衡，寻找它不是NPC问题，但是是PPAD问题，后来人证明纳什均衡是PPAD问题
- PPAD问题包括P问题的同时属于NP问题，指存在多项式的解，但不好找
- P问题指多项式时间可解决的问题
- NP问题指多项式时间可验证一个解的问题
- NPC问题指NP问题的归约问题，同时也是NP问题，复杂度不断提高，NPC问题的存在让$P = NP$ 问题很难有答案
- NP-hard问题指NP问题的归约问题，但不一定是NP问题

## 被支配策略（dominated strategy）

- 指不论其他参与者采取任何策略，该策略劣于其他策略
- 被支配策略永远不会是最佳回应
- 排除法：把被支配策略删除，从剩下的行动方案中选择，交互地去除掉每个选手的被支配策略

## 最大最小策略（Maxmin strategies）

- 指其他参与者对某参与者最小收益策略下的最大收益策略$arg max_{s_i}min_{s_{-i}}u_i(s_1,s_2)$
- 最小最大策略指让对方收益最大而自己收益最小的策略$arg min_{s_i}max_{s_{-i}}u_{-i}i(s_1,s_2)$
- 在有限两人零和博弈的纳什均衡中，参与者的最大最小值与最小最大值一致
- 最大最小可用来线性求解纳什均衡

## 扩展形式博弈

- 正常形式博弈不涉及行动顺序与时间
- 扩展形式博弈考虑时序影响，是一个层级结构，双方根据对方已经使用的策略来使用自己的策略，包括信息对称与不对称两种
- 有限信息对称博弈用（N, A, H, Z, χ, ρ, σ, u）来表示
- N代表n个参与者
- A代表一组行动
- H代表一组非终点的选择节点
- 行动函数 $\chi:H \rightarrow 2^A$ 表示每个选择节点的可能行动
- 参与者函数 $\rho:H \rightarrow N$ 表示在节点h上采取行动的选手 $i\in N$
- Z代表终止节点
- 后继者函数 $\sigma:H\times A\rightarrow H \cup Z$映射一个选择节点和一个行动对于所有的节点与行动，如果后继者函数相同，那么节点与行动相同
- 效用函数$u=(u_1,...,u_n);u_i:Z\rightarrow R$ 表示在终止节点上参与者的效用
- 信息对称扩展形式博弈里参与者的纯策略是行动函数的乘积$\prod_{h\in H,\rho(h)=i}\chi(h)$
- 扩展形式博弈可以转为正常形式博弈，但是有大量冗余，正常形式博弈不一定可转化为扩展形式博弈
- 信息对称扩展形式博弈都有纯策略纳什均衡
- 求解扩展形式博弈要从完美子博弈开始，从最小的分支倒推，记录策略，实际上也是最小最大值的求解

## 完美子博弈

- 在节点h的子博弈G是节点集合H对博弈G的限制
- 完美子博弈均衡也是纳什均衡，但不考虑无信用恐吓
- 倒推法：从最低层寻找纳什均衡，逐层反推排除掉其他选择得到策略
- 对于零和博弈，倒推法实际就是最小最大算法

## 信息不对称扩展形式博弈

- 参与者选择节点被分配到不同信息集合里，个体无法区分选择节点
- 信息不对称博弈用（N, A, H, Z, χ, ρ, σ, u, I）来表示
- 对于 $I = (I_1,...,I_n)$，$I_i = (I_{i,1},...,I_{i,k_i})$ 是依赖于 ${h\in H: \phi (h) = i}$ 的平衡，具有当存在j在节点 $h\in I_{i,j}$与$h'\in I_{i,j}$ 时，有 $\chi(h) = \chi(h')$ 与 $\rho(h) = \rho(h')$ 的属性

## 混合与行为策略

- 混合策略随机化纯策略
- 行为策略是遇到每个信息集后的抛硬币

## 重复博弈

- 参与者$i$给定一个无限序列$r_1,r_2,...$，其平均回报是$\lim_{k\rightarrow\infty}\sum_{j=1}^k\frac{r_j}{k}$
- 考虑折扣因子$\beta$，未来折扣回报是$\sum_{j=1}^{\infty}\beta^jr_j$，一般人会更关注当下，对未来关注不会超过当下，但以$1-\beta$的概率终止博弈
- 重复博弈中，当前收益跟未来收益权重不一致，未来收益一般小于当前收益权重：
$$U = U_1 + \sigma U_2+ ...$$
- $\sigma$介于0，1之间
- 有限重复博弈可以用倒推法得到解，基本收敛于子博弈均衡
- 无限重复博弈要分别计算不同策略下收益，当无限重复博弈概率不断增加，有可能打破子博弈均衡，此时会发生偏移

## 随机博弈（stochastic game）

- 随机博弈是重复博弈的泛化，每一次都取决于上一次博弈结果
- 用(Q, N, A, P, R)来表示
- Q代表有限状态集
- N代表有限参与者集合
- $A = A_1 \times ... \times A_n$ 其中$A_i$是参与者i的有限行动集
- $P:Q \times A \times Q \rightarrow[0,1]$表示转移概率函数，从状态Q采取行动A变化另一个状态Q
- $R = r_1,...,r_n$中$r_i:Q\times A\rightarrow R$ 表示参与者i的效用函数

## 虚拟行动（fictitious play）

- 对于行动$a\in A$，用$w(a)$表示对手行动次数，可以非零初始化
- 用这个数字评价对手策略 $\sigma(a) = \frac{w(a)}{\sum_{a' \in A}w(a')}$
- 在虚拟行动中每一个参与者的策略经验分布收敛，那么一定收敛到纳什均衡

## 无悔学习（No-regret learning）

- 后悔表示参与者在时间t上没有采用策略s$R^t(s) = max(\alpha^t(s)-\alpha^t,0)$
- 无悔学习表现出对任何纯策略有$Pr([\lim \inf R^t(s)]\leq0)$
- 在每一步每个行为正比于其后悔$\sigma_i^{t+1}(s) = \frac{R^t(s)}{\sum_{s'\in S_i}R^t(s')}$
- 对有限博弈收敛到均衡

## 无限重复博弈的平衡

- 著名的策略包括以牙还牙（tit-for-tat）跟扳机（trigger）
- 纳什均衡只适用于有限博弈
- 无限策略里有无限个纯策略均衡
- 对于n个参与者的博弈$G = (N,A,u)$其收益向量$r = (r_1,r_2,...,r_n)$，让$v_i = min_{s_{-i} \in S_{-i}max_{s_i \in S_i}} u_i(s_{-i},s_i)$ i的最小最大值是对方使用最小最大策略时其收益
- 一个收益向量r是增强的如果$r_i\geq v_i$
- 一个收益向量是可行的当存在非负值$\alpha_a$对于所有i，有$\sum_{a\in A}\alpha_au_i(a)$且$\sum_{a\in A}\alpha_a = 1$
- 无名氏定理（folk theorem）：如果收益向量对无限博弈的纳什均衡是平均回报，那么对每个参与者都是增强的，如果可行且增强，收益向量就是有平均回报的无限纳什均衡

## 贝叶斯博弈

- 贝叶斯博弈$(N,G,P,I)$里，N代表参与者集合，G代表博弈集合，P代表对某个博弈集合的先验概率，I代表G里面对每个参与者的组成部分
- 也可以用认知类型来定义$N,A,\Theta,p,u$，A表示行为集合，$\Theta$表示对参与者i的类型空间，p表示没中类型的先验概率，u表示某类型某行动对参与者i的收益
- 贝叶斯纳什均衡：最大化每个参与者每种行动类型收益的策略，可以是纯策略，也可以是混合策略
- 三种类型：对自己对方都不知道（现存），知道自己不知道对方(过渡)，都知道（过后）
- 过渡态期望收益：$EU_i(s|\theta_i) = \sum_{\theta_{-i}\in\Theta_{-i}}p(\theta_{-i}|\theta_i)\sum_{a\in A}(\prod_{j\in N}s_j(a_j|\theta_j))u_i(a,\theta_i,\theta_{-i})$
- 现存期望收益：$EU_i(s) = \sum_{\theta_i\in \Theta_i}p(\theta_i)EU_i(s|\theta_i)$
- 贝叶斯均衡混合策略$s_i\in arg max_{s'_i}EU_i(s'_i,s_{-i}|\theta_i)$
- 给定一方行为，考虑先验概率另一方收益最大时的博弈平衡
- 双方信息不对称，一方知道结果，另一方只能通过概率猜测是否对方是某种类型
- 计算不同行动的收益期望，求解概率，如果认为概率高于某个值，则选择对应行动，此时达到收益与概率的均衡

## 联盟博弈

- 收益可转移的联盟博弈（N,v）N代表有限的参与者，$v:2^N \rightarrow R$ 里每个联盟 $S\subseteq N$ 里的能够分配的收益，假定$v(\varnothing)=0$
- 联盟博弈解决的问题是哪些联盟会生成及收益如何分配
- 超加性博弈$G=(N,v)$表示对于所有的$S,T\subset N$，如果$S\cap T = \varnothing$，那么有$v(S\cup T\geq v(S)+v(T))$，这种情况下整体绑定为一个联盟收益最高

## 夏普利值（Shapley Value）

- 如何公平分割收益，Lloyd Shapley认为参与者要按照边际贡献的比例获得收益
- 公理
        - 对于每一种收益方法如果两个人可相互交换$v(S\cup \{i\}) = v(S\cup \{j\}))$，那么其收益相等$\psi_i(N,v)=\psi_j(N,v)$
        - 如果某个人不产生收益$v(S\cup \{i\} = v(S))$，那么不分成$\psi_i(N,v)=0$
        - 对于$v_1$和$v_2$，博弈$(N,v_1+v_2)$用$(v_1+v_2)(S)=v_1(S)+v_2(S)$定义，有$\psi_i(N,v_1+v_2)=\psi_i(N,v_1)+\psi_i(N,v2)$

- 夏普利值按照 $\psi_i(N,v) = \frac{1}{N!}\sum_{S\subseteq N_i} |S|!(|N|-|S|-1![v(S\cup \{i\})-v(S)])$ 分配收益，也就是满足上面三个公理的分配方式

## 核心

- 夏普利值分配比较公平，但不一定稳定，不容易形成大联盟
- 核心指对于$S\subseteq N$，有$\sum_{i\in S} x_i \geq v(S)$ ，总和收益至少不低于内部小联盟收益
- 核心可能是空的且不唯一
- 对于简单博弈核心是空的当且仅当没有否决参与者，如果有否决参与者，核心包括所有非否决参与者收益0的收益向量
- 凸博弈：$v(S\cup T)\geq v(S)+v(T)-v(S\cap T)$，每个凸博弈有一个非空核心且是夏普利值

## 选举

- 选举结果$O$
- 参与者的选择 $\succ$
- 线性排序 $L$ 选择顺序，可传递；非强制选择$L_{NS}$ $\succeq$ 可传递
- 社会选择函数 $C:L_{NS}^n \rightarrow O$，期中L是非强制选择偏好
- 社会福利函数 $W:L_{NS}^n \rightarrow L_{NS}$
- 多数票制：选择大多数人选最多的
- 累计投票：每个人多张票，可以重复投给一个人
- 同意投票：每个人可随意投，投多个人或不投都可以
- 淘汰制多数票：得票最多获胜，否则淘汰得票少的重新投直到有结果
- 波达投票：每个结果分配一个有排序的数字，最后选择总和最高的那个
- 连续消除：设定顺序，然后前两个投票，输的淘汰，之后赢的跟第三个再投票直到出结果
- 孔多塞连续性：如果有个结果在所有对比中都胜出，那么这个候选人可以当选（不一定总是有这样的人，有时会出现循环）
- 不同投票方法结果可能不一样
- 帕累托有效（PE）如果所有参与者都同意某两个结果的顺序，那么社会福利函数也会使用那个顺序
- 无关选择独立性（IIA）两个结果间顺序指依赖于参与者给出的相对顺序
- 独裁者（dictator）某可决定社会排序的参与者
- Arrow理论 任何超过三人的具有PE与IIA的社会福利函数都是独裁的 [证明](https://www.douban.com/group/topic/46208753/)
- 弱帕累托有效：没有出现过被支配的结果
- 单调：一个获胜的结果再拿到更高的排序也是获胜者
- 独裁：存在某参与者的选择与总体选择顺序一致
- 弱帕累托有效且单调的社会选择函数是独裁的
- 单峰选择：每个投票的人都有最想选跟最不想选的候选人，选择上会避免极端

## 机制设计

- 直接形式：参与者同时传递信息到中心
- 间接形式：参与者传递一系列信息，这些信息前后相关
- 启示原则（Revelation Principle）：任何社会选择函数都可以用真实直接的机制来实施
- Gibbard-Satterthwaite 理论：有限选择空间里三个元素以上的支配策略都是独裁的，非独裁策略需要转移函数
- 转移函数：集体对个体的税收或补贴，个人私人收益与转移函数之和是个体的整体结果收益，个人私人收益不考虑其他人的选择
- 真实性：对于每个参与者平衡策略里转移收益机制是真实的党是直接的且个体接受个人收益函数
- 有效性：有效的机制会选择最大化个体的收益，转移函数的和小于等于0
- 预算平衡：所有人转移函数的和为0，大于等于0是弱预算平衡
- 个体理性：没有人会因为参与某个机制得到负收益
- 可处理：收益与转移函数的计算可在多项式时间内完成
- 税收最大化：满足所有限制条件下最大化转移函数总和期望的机制
- 税收最小化：满足所有限制条件下最小化转移函数总和期望的机制
- 公平性：让最不开心的参与者也开心最大化
- 设计政策时要考虑支出补贴税收对所有人都无害或达到均衡

## VCG机制

- 存在货币补偿时自私参与者选择社会福利最大化的通用方法
- 一个直接机制包括选择规则跟补偿规则，VCG作为支配策略是真实有效的，在额外假设下可以满足弱预算平衡跟个体理性
- Groves机制 $(\chi,p)$
$$\chi (\hat v) \in arg max_x \sum_i \hat v_i(x)$$

$$p_i(\hat v) = h_i(\hat v_{-i}) - \sum_{j\neq i} \hat v_j(\chi(\hat v))$$

- VCG机制 $(\chi,p)$
$$\chi (\hat v) \in arg max_x \sum_i \hat v_i(x)$$

$$p_i(\hat v) = max_x\sum_{j\neq i} \hat v_j(x) - \sum_{j\neq i} \hat v_j(\chi(\hat v))$$

- 在VCG机制下，计算你自己存在时社会受益最大时其他人收益总和，然后计算没有你且社会收益最大时其他人收益总和，你的补偿是它们的差值
- 不影响最后结果的人不需要补偿，其存在导致他人收益减少的要付出，其存在导致他人收益增加的要补偿
- 其真实性有效性可以数学证明
- VCG需要个体真实汇报个人信息，但个体间的勾结可以消除补偿，同时VCG会导致开支暴涨，增加参与人也会增加财政支出，个人可能伪装多个人，同时返还机制也不允许所有人返还所有收益
- 价值隐私信息需要损失效率，是动机效率的平衡

## 拍卖

- 自私参与者分配资源的机制
- 英国人拍卖：从保留值开始拍卖，参与人喊价，价高的得到物品并付出对应价格
- 日本人拍卖：所有参与者先站着，价格提升，当价格不合适就坐下，最后一个站着的人得到物品
- 荷兰人拍卖：设定一个高价然后开始逐渐降低，当有人说我接受时拍卖结束，价格就是当时价格
- 第一价格拍卖：参与者将价格写好封装，然后拍卖人开封，价高的人得到物品，付对应价格
- 第二价格拍卖：同上，但付第二高的价格
- 付费拍卖：同上，但所有人都要支出自己写的价格，彩票？
- 拍卖三种规则：竞拍规则，信息释放规则，清场规则
- 在第二价格拍卖里，讲真话是支配策略，符合VCG机制，也可以直观证明
- 在英国人日本人拍卖里，独立私有价值模型下的支配策略是用真实值
- 在第一价格拍卖与荷兰人拍卖实质等同，前者可以异步进行，后者交流快，参与者竞拍价要低于价值，无支配策略
- 两个中等风险的参与者参与第一价格竞拍，分布是均匀分布，贝叶斯纳什均衡是各自价格的一半
- 更多的参与人参加后，价格会不断提升接近真实价格，如果是均匀分布，系数是$\frac{n-1}{n}$
- 收益均等理论：n个风险中等的参与者对于单一物品有独立私有价值，参与竞拍时每个人都从风险分布F里报价，当均衡时分配总是一样的，价值为0其期望也是0，所有有效拍卖产生的收益是一样的
- 最优化拍卖，参与人的虚拟价值$\psi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$在保留价格处为0，并非VCG