博弈论01

leonhardt...大约 18 分钟

博弈论01

形式化工作

博弈的组成

参与人(player): $i, j$
参与人的策略(strategies): $s_i, s_j$
参与人的策略集合: $S_i,S_j$
某一次博弈：s。称为策略组合(a strategy profile)
收益(payoffs): $U_i(s)$
除了i之外其他参与人的策略: $s_{-i}$

严格优势策略的定义：对参与人i，其策略 $s_i$ 严格优于策略 $s_i'$ ，如果对于任何 $s_{-i}$ 都有 $U(s_i,s_{-i})>U(s_i',s_{-i})$ 。

弱严格优势策略：大于=>大于等于。最差是等于，但某些情况是大于。

选数游戏

从[1, 100]中选一个数，如果你选的数是所有人选的数的平均值的2/3,则你获胜。

剔除[ 68，100]，因为只有当所有人都选 100 时，100 的 2/3——66 又 2/3，才是个合理的答案。剔除劣势策略，剩余的选择[ 1，67 ]，在这样的情况下，同理 [ 45，67 ] 也被剔除了。[ 45，67]策略在原博弈中并不是弱劣势的，可是一旦我们排除掉了[ 68，100 ]，它们就成为了劣势策略，即弱劣势策略。剔除[ 68，100 ]，是一种直接思考；同时作为一个理性参与人的选择。剔除[ 45，67 ]，则是站在别人的角度去思考的结果，因为对手不会选择劣势策略。同时考虑到你的对手也是一个理性的参与人。不断重复这个过程，最终会得到 1 的结果。

考虑worst case，剔除[ 68，100]。
假设其他人是理性的，剔除[45，67]。
假设其他人知道他的其他人是理性的，剔除[30，45]。
以此类推，最终会得到1。

common knowledge：我知道你知道我知道...的东西
mutual knowledge：我知道你不知道的东西。你知道我不知道的东西。

中位选民定理

player：你和你的对手
strategy：政治立场，从极左到极右分10个等级。
payoff：票数。假设每个立场有10%的选民支持，每个选民会支持离自己支持的立场最近的立场，如果距离相同则平分票数。

和选数一样，通过不断剔除劣势策略，最终会收敛到中立立场。

最佳对策(Best Response)

	l	r
u	5,1	0,2
m	1,3	4,1
d	4,2	2,3

当对手选择 l 时，u 是最佳策略。
当对手选择 r 时，m 是最佳策略。

但实际我并不知道对手会选什么，因此我需要猜测对手选择各策略的可能性，并以此计算我的预期收益，作为决策的依据。

点球博弈

	l	r
L	4,-4	9,-9
M	6,-6	6,-6
R	9,-9	4,-4

4 代表进去的概率 $U(L,l)$ 向左射门，向左扑救，进去的概率为 40%

不要选择任何信念下都非最优反应的策略，即蓝色线条。

在卡牌游戏里，如果一张卡在任何情况下都非最优解，那么这张卡的使用率，或者说强度就会很低。比如战逝鸽的斩铁波。

卡的强度
任何时候都强
在特定卡组中强
针对特定boss
针对特定小怪，对群
任何时候都不强

最佳对策的定义

参与者 i 的策略 $\hat s_i$ 是其他参与者的策略 $s_{-i}$ 最佳对策，如果 $U_i(\hat s_i,s_{-i}) \geq U_i(s_i',s_{-i})$ 对于所有的 $s_i' \in S_i$ 都成立，或者说 $\hat s_i$ 是 $\max_{S_i}U_i(s_{i}, s_{-i})$ 的解。

加入预期(对对手选择策略的概率估计，P)后
在参与人持信念 P 的情况下选 $\hat s_i$ 获得的预期收益比在同样的信念P下选其它策略，获得的预期收益都要高，对于可选的 $s_i'$ 均成立。

合作博弈

两个参与人都是公司股东，各持有公司50%的股份，供应合伙关系；每个股东要选择对公司投入精力，以“小时”表示，策略集合 $S_i=[0,4]$ ，即可选择 0 到 4 间任意实数“小时”的投入，这是一个连续区间，不是同于选数游戏中的只能选整数。

利润按以下表达式：
$4[s_1+s_2 + 𝑏s_1s_2], b \in [0 , 1/4]$
b 表示协同程度

参与人 1 的收益 $U_1 = (s_1, s_2)= 0.5 × [4 × (s_1 + s_2 + bs_1s_2)] − s_1^2$

0.5 <= 50%股份，
$s_1^2$ <= 自身投入

考虑参与人1的最佳策略，即 $U_1$ 的最大值。求导可得
$\hat s_1=1+bs_2=BR(s_2)$ =>在 $s_2$ 下，参与人1的最优反应
$\hat s_2=1+bs_1=BR(s_1)$

通过不断剔除非优势策略，最终将收敛到交点。
交点可解得为
$s_1^*=s_2^*=\frac{1}{1-b}$

这个点就是纳什均衡点。参与人们都采用了自己的最优反应
$\frac{1}{1-b}$ 就是边际效应的公式。

投资博弈

参与人：在场的所有人
策略：投资 10 或 0
收益：0=>0, 10 : 如果有90%的人选择投资，则额外赚5。如果没有，则全亏。

博弈会朝着趋向于一个均衡的方向自然发展，结果（self-enforcing）不断趋向一个 NE。初始状态会很大程度上影响趋势，进而影响结果。
寻找 NE 的一个有效方法是猜想与验证（guess and check）
较劣的不投资均衡相当于较优的 NE 处于帕累托劣势
协调之所以能达成在于他不同于囚徒困境，它没有去说服人们采取一个严格劣势策略。因此，通过沟通就可以解决，而不需要通过合同改变收益。

纳什均衡(Nash Equilibrium)

纳什均衡是满足下列条件的策略组合：对于任意一个此集合内的参与人 i ，她所选择的策略 $s_i^*$ 是其它参与人所选择策略的最优反应，其它参与人的策略用 $𝑠_{−𝑖}^∗$ 表示。

简单地说，每个人都选择了最优反应。因此任何参与人都严格不会改变策略，改变策略严格不会使参与人获得增益。其他参与人不改变行为的前提下，自己改变行为并没有任何好处。

严格劣势策略永远不是最优反应，最优反应才可以出现 NE。

不为当时做出的决定后悔，因为已经采取了最优反应。
应该是各个 player 选择 NE 的动机；同样重要的一点是 NE 是自我实现的（self-fulfilling/self-enforcing。

约会博弈

也是协调博弈，但不同的NE下，参与人的相对收益不同。
Battle Of The Sexes。

古诺的双寡头模型(Cournot Duopoly)--产量竞争

参与人：两家公司
策略：某种同质产品产量， $𝑞_1, 𝑞_2$
成本计算： $c × 𝑞$ ，c 为生产一个单位产品的成本；
市场定价的两个参数 a，b ：价格 $p = a − b (𝑞_1 + 𝑞_2 )$ 两家企业生产的越多，该产品的市场价格也就越低
收益=利润-成本 => pq-cq

$f(q_1) =a𝑞_1 − b𝑞_1^2 + 𝑞_1𝑞_2 - cq_1$
当对手策略为 $q_2$ 时，我的策略收益最大值为 $f(q_1^*)$ ， $q_1^*$ 为满足 $f'(q_1)=0$ 的 $q_1$ 取值。 $BR_1(q_2)=q_1^*=\cfrac{a-c}{2b}-\cfrac{q_2}{2}$ 。 $BR_2(q_1)$ 类似。

当参与人2的产量为0，即1垄断时，要取得最大收益需要的产量称垄断产量，为 $\cfrac{a-c}{2b}$ 。
当参与人均采用最佳对策，即达到NE时，此时总产量称古诺产量，为 $2\times \cfrac{a-c}{3b}$
需求曲线和边际成本的交点对应的产量称完全竞争产量，为 $\cfrac{a-c}{b}$ 。
显然
完全竞争产量>古诺产量>垄断产量
完全竞争价格<古诺价格<垄断价格
行业利润递增(垄断时最大)

需求曲线，市场定价对应的需求量
垄断产量，边际收益等于边际成本的那个点
边际收益(Marginal Revenue)曲线等于价格曲线斜率的 2 倍 $-2b$ 。
边际收益指增加一单位产品的销售所增加的收益。利润最大化的一个必要条件是边际收益等于边际成本。(因为边际收益递减)。
“边际”是相对于“固定”的概念，“固定”代表生产设备之类，“边际”和设备制造的产品相关。

不是一个策略互补博弈(BR曲线斜率为正，我选高值，你的应对也是选高值)，而是一个策略替代博弈(BR曲线斜率为负，我选高值，你的最佳应对是选低值)。

伯川德模型--价格竞争

参与人：生产相同的产品的两个公司
策略：定价，本例中用 $p_1$ 代表公司 1 的价格，用 $p_2$ 代表公司 2 的价格
策略集合: 每个公司可以把价格设定在 $0 ≤ p ≤ 1$
产量制定: $Q(p)=1-p$ 。p为两家公司定价较低的价格。
需求量：

q_1=\begin{cases}1-p_1(p_1>p_2) \\ 0(p_1>p-2)\\\frac{1-p_1}{2}(p_1=p_2) \end{cases}

收益= $q_1(p_1-c)$

分析最佳策略
第一段，公司 2 定价低于成本价销售时，公司 1 定价必须高于 𝑝2才能避免销售每件产品都亏损，同时也意味着产品没有销量——退出市场。
第二段，当公司 2 的定价高于成本且低于垄断价格时，公司 1 只需要比该价格低一点点，用 𝜀来表示，才能占领市场。
第三段，当公司 2 的价格高于垄断价格时，公司 1 选择垄断价格以获取最大利润。
第四段，当公司 2 的价格等于边际成本时，公司 1 选择大于或等于边际成本。

$𝑁𝐸 = ( 𝑝_1 = 𝑐, 𝑝_2 = 𝑐 )$
这个结果与完全竞争非常相似，尽管只有两家公司。

这个结果叫做伯川德悖论（Bertrand Paradox）

线性城市模型

一个路贯穿城市，两个公司分别坐落在 0、1 点，消费者 y 到公司 1 的距离为 y，到公司 2 的距离为 1-y，假设每个消费者买且只买一个产品。消费者会选择对他而言成本最小的。

在 y 点的消费者，如果从公司 1 购买则他们支付 $𝑝_1 + 𝑇𝑦^2$ ，产品的价格 $𝑝_1$ ，和交通成本 $𝑇𝑦^2$ ；到公司 2 购买则需要支付 $𝑝_2 + 𝑇(1 − 𝑦)^2$ ，交通成本以距离的平方的速率增长。

$𝑝_1 + 𝑇𝑦^2 = 𝑝_2 + 𝑇(1 − 𝑦)^2$
=> $p_1=p_2+T(1-2y)$
=> $T(1-2y)$ 决定了在成本价之上的定价空间。y<0.5，优势在1。反之，则在2。
价格取决于距离优势，距离优势越大，优势策略空间越大。

候选人选民模型

参与人：选民
策略：是否参选（选民将选票给与最近的候选人，得票最多者当选，平局掷硬币）
收益：获胜赢得奖励 B，参选付出成本 C，且 B>2C；若选民不参选获胜者的立场距离该选民越远，则该选民将承受越重的负面效应，若该选民在线上 X 点，获胜者在 Y 点，则承担−|𝑋 − 𝑌|的成本，两点间距离的负向效应，也就是对方当选后给未参选的选民造成郁闷程度。

例如：三种可能的情况

Mr.x 参选并获胜，他的收益为 𝐵 − 𝐶
Mr.x 参选，但 Mr.y 获胜，Mr.x 的收益为−𝐶 − |𝑋 − 𝑌|
Mr.x 不参选，但 Mr.y 获胜，Mr.x 的收益为−|𝑋 − 𝑌|

分析

最中间的选民参选：此时，对其他选民来说，不参选是最优策略。=>NE
两个对称点的选民参选(不能超过1/6|5/6，否则，中间的人会获胜)：此时，对两端的选民来说，参选不仅不会当选，且会让当选者的立场离自己更远。对中间的选民来说，如果选正中间不能获胜，则情形类似。
两个对称点和两个极端点的选民参选，则对称点的人需要向中间靠一点，否则中间人会获胜。
此模型可能存在多个 NE
如果左派有一个新的候选人加入，可能会导致右派获胜的概率增大，反之亦然。
如果候选人太极端就会有新的中间候选人参选。

选址模型（Location model）

假设两个小镇，东镇和西镇；世界仅有两种人，高个和矮个；每种人都有 10 万，每个城镇都只能容纳 10 万人；
参与人：10万高个、10万矮个
策略：选择东镇还是西镇
收益：如果城镇只有参与人是矮个，其他人都是高个，那么参与人的收益为 0，反之亦然；如果是高个和矮个混居，数量都是城镇人口的一半则收益达到最大；如果城镇全是矮个或高个则收益是最大值的一半。

人们可以自由选择想要居住的城镇，如果选择一个城镇的数量超过了容积，则会从所有选择该城镇的参与人中随机抽取，分配到另一个城镇。例如有 15 万人选择东镇，那么每个人只有 2/3 的概率可以住在这里，另外随机抽取 5 万人，会被分配到西镇去。

两个 NE：一个是种族隔离；一个 NE 是每个城镇中不同人种均匀分布；两者皆为严格均衡，后者稳定性差，“弱均衡”。 ==这两种情况下参与人都无法通过改变策略来取得更高的收益 ==。后者之所以弱，是因为，改变策略的损失极低。而且，只要有一个人改变策略，则很快很形成另一个NE。(因为右边曲线下降的慢，一个高个走了，则它和高个去的地方收益降低了，但它原来的地方收益降低更多，因此，高个跟着走成为了一个优势策略，从而导致种族隔离。)
临界点（Tipping Point）
另一个不太现实的均衡，所有人都选择同一个城镇而被随机分配。
模型中种族隔离的结果，不能作为人们喜欢种族隔离的论据。虽然是人们个人的选择的结果导致种族隔离，但不能说人们喜欢种族隔离。=>不要根据现象武断地下结论。
随机分配（randomization）；校车现象（bussing）
可以通过自下而上的方式实现随机分配，每个人都考投硬币决定自己去哪。个体策略随机化(混合策略)。
社会随机分配，其结果要比所谓的自主选择要好。

注

随机策略与占卦
采取混合策略(随机化策略)存在一个困难，即如何实现随机。常用的方式有抛硬币，掷骰子，占卜(找一朵花，根据其花瓣奇偶数进行选择)。中国古代则“龟为卜，策为筮”，卜用龟甲，筮用蓍草。灼龟观兆(烧灼龟板观察兆纹以定吉凶), 摓策定数(执持蓍草确定其数目以定吉凶)。都可以看做使用随机策略的方式。

在选址模型中，采用随机策略的结果通常是好的，这是各种占卜喜欢的场景。
而在猜拳博弈中，虽然采用混合策略是纳什均衡策略，但根据随机结果，实际收益是有正有负的。这种情况下占卦，则会有失败的风险。对这种情况的处理方式可以是(走为上计)，给个凶险的结果，再给求卦的人一个"护身符"。这样，如果成功了就是占卦者和"护身符"的功劳，失败了就是“命中注定有此一劫”，“有护身符也保不住你”，“要是没有护身符，说不定结果更差”。

所谓三不占原则：不诚不占、不疑不占、不义不占。

不诚不占：拒绝纯随机猜结果。拒绝错误信息。
不疑不占：将场景限定在混合策略纳什均衡下。
不义不占：道德原因。不引祸上身。
占卦的人也要趋吉避凶啊。

通常，会去求卦的人遇到的问题，是自身的知识或信息不够导致的。这时候，如果占卦人的知识或信息可以解决，那就是提高自身声望的机会了，占卦则沦为形式。所以，存在一些“得道高人”可以为人指点迷津，实际流程是

能用科学方法解决的就用科学方法解决。比如看风水。
如果选择的结果收益都为正，则帮人获得一个随机数。或者帮人做出积极的选择(皮格马利翁效应)。
如果选择有失败的风险，则给出差预测，并做好两手准备。一是"护身符"，有"趋吉避凶"的作用。二是跑路准备。

一些相关的心理学知识

巴纳姆效应。
人很容易相信一个笼统的一般性的人格描述，并认为它特别适合自己并准确地揭示了自己的人格特点，即使内容空洞。
皮革马利翁效应。
罗森塔尔和雅各布森认为，高期望会导致更好的表现，而低期望会导致更糟，这两种影响都会导致自我实现的预言。
幸存者偏差。
幸存者偏差，另译为“生存者偏差”或“存活者偏差”，是一种常见的逻辑谬误（“谬误”而不是“偏差”），意思是只能看到经过某种筛选而产生的结果，而没有意识到筛选的过程，因此忽略了被筛选掉的关键信息。

猜拳

Rock, Paper, Scissors
没有纯策略的NE。

混合策略NE：按 1/3 概率选择RPS。

混合策略

混合策略用 $𝑃_𝑖$ 表示， i 表示参与人， $𝑃_𝑖$ 表示采用每个纯策略的概率
用 $𝑃_𝑖( 𝑠_𝑖 )$ 表示在混合策略 $𝑃_𝑖$ 下，参与人 i 采用 $𝑠_𝑖$ 的概率，即 $𝑃_𝑖( 𝑠_𝑖 )$ 是 $𝑃_𝑖$ 赋予纯策略 $𝑠_𝑖$ 的概率。混合策略 $𝑃_𝑖$ 的预期收益，每个纯策略预期收益的加权平均数。

加权平均数一定介于最大值和最小值之间。

纯策略(Pure Strategy): $P_i(s_i)=1$

混合策略NE中每个策略必须是BR，且加权后的收益相同(否则你应该排除它)。
如果混合策略不是NE，那么可以通过改变策略来获得严格增益。

网球博弈

V击球，最好打到S没有防御的地方。
S防御，最好到V击球的方向防御。
S的BR在主对角线，V的BR在副对角线，因此不存在纯策略的NE。

假设S的混合策略NE为(q,1-q)，则根据NE条件，即V的混合策略中每个纯策略的收益一定是相同的。因此可以解出q=0.6。
同理，假设V的混合策略NE为(p,1-p)，则根据NE条件，即S的混合策略中每个纯策略的收益一定是相同的。因此可以解出p=0.7。

寻找我的混合策略NE，需要用对手的收益来计算，让对手的每个纯策略应对我的NE混合策略的期望收益是相同的，从而可以确定具体权值。(既然对手选择了混合策略，说明各策略的期望收益一定是相同的，否则将收益低的策略从混合策略中剔除，就能获得严格增益)
结论：只需要考虑改变纯策略是否严格有利即可。
因为就混合策略本身的定义来说就不会有严格有利的混合策略偏离，两个相同的数怎么加权都是一样的。

如果情况改变了，S更擅长打反手球(l)了。
新的均衡:
p=0.5, q=7/12。

为什么引入混合策略？
理由 1:混合策略可能优于一些纯策略（这些纯策略本身并不劣于其他纯策略）。
理由 2 混合策略的最差情况可能好于所有纯策略的最差情况。
理由 3：如果我们只限于纯策略，那么，我们也许不能找到博弈的纳什均衡。

税收博弈

审计员的收益：

最好的结果，不审查而纳税人如实申报，收益为 4；抓到漏税收益也为 4；
最糟的结果，不审查，但纳税人逃税成功，收益为 0；
审查而纳税人如实申报，因为审查是有成本的，因此收益为 2；

政策试验，提高惩罚，从-10 增加到-20。

审计员的收益没有变化，因此纳税人的策略不会变。
纳税人的收益变化实际导致审计员的策略改变，审计率从2/7降低到1/6。(审计员可能认为，逃税的收益降低了这么多，那逃税的人应该更少，所以倾向选择不审查)