跳至主要內容

博弈论01

leonhardt...大约 18 分钟blog

博弈论01

形式化工作

博弈的组成

  • 参与人(player): i,ji, j
  • 参与人的策略(strategies): si,sjs_i, s_j
  • 参与人的策略集合: Si,SjS_i,S_j
  • 某一次博弈:s。称为策略组合(a strategy profile)
  • 收益(payoffs): Ui(s)U_i(s)
  • 除了i之外其他参与人的策略: sis_{-i}

严格优势策略的定义:对参与人i,其策略sis_i严格优于策略sis_i',如果对于任何sis_{-i}都有U(si,si)>U(si,si)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)

lr
u5,10,2
m1,34,1
d4,22,3

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

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

点球博弈

lr
L4,-49,-9
M6,-66,-6
R9,-94,-4

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


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

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

卡的强度

  1. 任何时候都强
  2. 在特定卡组中强
  3. 针对特定boss
  4. 针对特定小怪,对群
  5. 任何时候都不强

最佳对策的定义

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

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

合作博弈

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

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

参与人 1 的收益 U1=(s1,s2)=0.5×[4×(s1+s2+bs1s2)]s12U_1 = (s_1, s_2)= 0.5 × [4 × (s_1 + s_2 + bs_1s_2)] − s_1^2

0.5 <= 50%股份,
s12s_1^2 <= 自身投入

考虑参与人1的最佳策略,即U1U_1的最大值。求导可得
s^1=1+bs2=BR(s2)\hat s_1=1+bs_2=BR(s_2) =>在s2s_2下,参与人1的最优反应
s^2=1+bs1=BR(s1)\hat s_2=1+bs_1=BR(s_1)


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

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

投资博弈

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

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

纳什均衡(Nash Equilibrium)

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

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

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

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

约会博弈


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

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

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

f(q1)=a𝑞1b𝑞12+𝑞1𝑞2cq1f(q_1) =a𝑞_1 − b𝑞_1^2 + 𝑞_1𝑞_2 - cq_1
当对手策略为q2q_2时,我的策略收益最大值为f(q1)f(q_1^*)q1q_1^*为满足f(q1)=0f'(q_1)=0q1q_1取值。BR1(q2)=q1=ac2bq22BR_1(q_2)=q_1^*=\cfrac{a-c}{2b}-\cfrac{q_2}{2}BR2(q1)BR_2(q_1)类似。

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

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

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

伯川德模型--价格竞争

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

q1={1p1(p1>p2)0(p1>p2)1p12(p1=p2) 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}

收益=q1(p1c)q_1(p_1-c)

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

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

这个结果叫做伯川德悖论(Bertrand Paradox)

线性城市模型

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

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

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

候选人选民模型

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

例如:三种可能的情况

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

分析

  1. 最中间的选民参选:此时,对其他选民来说,不参选是最优策略。=>NE

  2. 两个对称点的选民参选(不能超过1/6|5/6,否则,中间的人会获胜):此时,对两端的选民来说,参选不仅不会当选,且会让当选者的立场离自己更远。对中间的选民来说,如果选正中间不能获胜,则情形类似。

  3. 两个对称点和两个极端点的选民参选,则对称点的人需要向中间靠一点,否则中间人会获胜。

  4. 此模型可能存在多个 NE

  5. 如果左派有一个新的候选人加入,可能会导致右派获胜的概率增大,反之 亦然。

  6. 如果候选人太极端就会有新的中间候选人参选。

选址模型(Location model)

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

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

  1. 两个 NE: 一个是种族隔离;一个 NE 是每个城镇中不同人种均匀分布;两者皆为严格均衡,后者稳定性差,“弱均衡”。 ==这两种情况下参与人都无法通过改变策略来取得更高的收益 ==。后者之所以弱,是因为,改变策略的损失极低。而且,只要有一个人改变策略,则很快很形成另一个NE。(因为右边曲线下降的慢,一个高个走了,则它和高个去的地方收益降低了,但它原来的地方收益降低更多,因此,高个跟着走成为了一个优势策略,从而导致种族隔离。)

  2. 临界点(Tipping Point)

  3. 另一个不太现实的均衡,所有人都选择同一个城镇而被随机分配。

  4. 模型中种族隔离的结果,不能作为人们喜欢种族隔离的论据。 虽然是人们个人的选择的结果导致种族隔离,但不能说人们喜欢种族隔离。=>不要根据现象武断地下结论。

  5. 随机分配(randomization);校车现象(bussing)

  6. 可以通过自下而上的方式实现随机分配,每个人都考投硬币决定自己去哪。个体策略随机化(混合策略)。

  7. 社会随机分配,其结果要比所谓的自主选择要好。

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

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

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

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

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

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

一些相关的心理学知识

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

猜拳

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

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

混合策略

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

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

纯策略(Pure Strategy): Pi(si)=1P_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。(审计员可能认为,逃税的收益降低了这么多,那逃税的人应该更少,所以倾向选择不审查)