知乎日报:猜对我手里有几枚硬币我就把它们都给你

  这就是一道博弈论的题目。

  如果按照题目的描述,我们可能会画出这样一棵博弈树(也被称为博弈的拓展形式 extended form)

  从上往下,首先由甲选择藏起来的硬币是 10 还是 20,再由乙猜测硬币,最后的收益,前一个是甲的收益,后一个是乙的收益。

  但是这棵树是有问题的:乙在决策的时候,其实不知道甲到底藏的是 10 还是 20,所以其实正确的博弈树是这样的:

  连上虚线的两个点,表示在同一信息集中(掌握了同样多的信息),这时候,我们可以把它等价地画成支付矩阵(也被称为博弈的标准形式或战略形式 strategic form)

  拓展形式的博弈树,通常用于表示博弈策略选择有前后顺序的情况(我们称为 sequential game),而战略形式的支付矩阵,则表示博弈策略选择是同时进行的情况(我们称为 simultaneous game)。在这个问题中,由于乙猜测时不知道甲藏的硬币是多少,可以认为乙是在甲藏硬币的同时进行猜测,因而可以写成战略形式的支付矩阵。

  接下来我们来求解这个博弈的解,这里就是它的纳什均衡。

  纳什均衡的定义是,在均衡下,参与者不会单方面地改变自己的选择。

  首先考察纯策略纳什均衡(双方都只用一种策略),由于格子少, 所以我们可以逐格按照定义进行检查,当然也可以用经典的划线法:给定甲的策略,选出乙的最佳选择,再给定乙的策略,选出甲的最佳选择,如下图:

  我们可以说,这时候不存在纯策略纳什均衡,任何一种结果下,都会有一方觉得自己本应有更好的选择。

  我们转而寻求混合策略纳什均衡,就是双方混合采取多种策略。

  混合策略纳什均衡的求解办法,如题主所做的那种是可以的,但这比较复杂,我们通常采用的是利用对手无差异性。

  对手无差异性的含义是,如果甲要混合选择 10 和 20,那乙无论选择 10 还是选择 20,得到的收益应该是一样的。否则,如果甲选择混合策略之后,乙发现自己选择 10 的收益更高,那么甲应当预见到这一点,并转而选择 20,这说明甲有更好的策略;反之乙如果发现选择 20 的收益更高也是同理。

  这样一来,我们假定甲以 p 的概率选择 10,1-p 的概率选择 20,那么由对手无差异性

  10p-15(1-p)=-15p+20(1-p)

  25p-15=20-35p

  解得 p=35/60=7/12

  同理可得乙以 q=7/12 的概率选择 10,5/12 的概率选择 20。计算结果和题主是一样的~

  以上解答了题主提到的 Vladimir Arnold 提出的问题。

  接下来解答题主的问题。

  1. 此解法有一个假设,即『在游戏开始后策略不改变』。在该假设下,此解法是否正确?

  答:并不需要这个假设,因为原题说的是甲乙双方进行一次游戏的情况,尽管这其中涉及概率,但不代表这个游戏要进行很多次来统计频率,而是参与人每一轮都根据概率进行选择。

  题主想说的,其实是游戏进行多轮的状况,这种状况被称为重复博弈(repeated game)。

  重复博弈下,策略就更像是一种战略,而不是战术,它代表了玩家在每一轮如何选择的一整套规则,这个规则可以是“根据上一回合的结果决定下一回合的选择”,也可以是“在游戏开始后策略不改变”。

  我用最经典的囚徒困境博弈来做个说明。

  囚徒困境进行一轮的时候,囚犯的策略是合作(C)或者背叛(D);

  囚徒困境重复进行时,囚徒的策略可以是永远合作 ALLC,永远背叛 ALLD,以牙还牙 Tit For Tat,冷酷策略 Grim Trigger 等等,这些策略是单轮博弈的策略(合作或者背叛)的有机组合。这里“永远合作”或者“永远背叛”就是“在游戏开始后策略不改变”的策略的例子,而“以牙还牙”和“冷酷策略”都是“根据上一回合的结果决定下一回合的选择”的例子。

  2. 是否有一种『根据上一回合的结果决定下一回合的选择』的策略,使得甲或者乙收益更多?如果有,是什么?如果没有,如何证明?

  答:这时候我们就要进一步划分重复博弈。

  1)如果重复博弈进行有限轮,在最后一轮,双方一定会选择纳什均衡。

  如果有多个纳什均衡,而且各个纳什均衡的收益不同,那么可以通过威胁对方说,我会在最后一轮强制选择较差的纳什均衡,来逼迫对方在最后一轮之前选择非纳什均衡。

  然而,这道题中只有一个纳什均衡(就是混合策略纳什均衡),因此最后一轮双方无论如何都只有这一种选择,倒推到倒数第二轮,则双方都无法威胁对方,那么倒数第二轮也只能都选择纳什均衡,依此类推,我们就得到了一个定理:

  定理:若单轮博弈只有唯一纳什均衡,则有限重复博弈中每一轮博弈双方均选择该纳什均衡。

  这个定理用在囚徒困境上,就可以知道有限次囚徒困境中,双方都永远会选择背叛。

  2)如果重复博弈进行无限轮,这时候就没有“最后一轮”了,我们就不能从最后一轮来进行倒推了。这时候,我们就只好利用另一个定理(证明略),即无名氏定理(Folk Theorem)。

  在介绍定理之前,先来了解一下折现率(discount rate)的概念。简单地说,就是没到手的钱没有已经到手的钱值钱,在今天看未来的收益,要打个折扣。这个也很好理解,比如我今天给你 100 块和明年的今天给你 100 块,肯定是今天拿到手合算,因为我可以拿去投资啊,最起码可以多拿一年的利息,所以明年的 100 块钱,在今天就要少一些,我们用折现率δ

  如果我们进行无限轮博弈,最后我们会得到一个总折现收益,这个总折现收益等价于每年固定拿一定量的钱的总折现收益,我们称为平均折现收益。比如说,如果我今年拿 2 块,从明年开始每年拿 1 块,折现率是 1/2,那么我的总折现收益是

  2+1/2+(1/2)2+...=3

  平均折现收益假设是 x,那么有

  x+x*(1/2)+x*(1/2)2+...=3

  解得 x=3/2

  也就是说,“我今年拿 2 块,从明年开始每年拿 1 块,折现率是 1/2”,就相当于我每年拿 3/2 块,折现率是 1/2。

  好了,我们回到无名氏定理。无名氏定理说的是,对于双方高于其最小最大值(minimax)的收益,在折现率充分高的情况下,存在策略,使得双方的平均折现收益达到该值。

  在零和博弈中(比如本题),最小最大值的收益就是纳什均衡下的收益。而零和游戏意味着提升一方的收益必然降低另一方收益,所以无法用无名氏定理证明存在这样的策略。(= =!一个大写的懵逼)

  (然而证明不存在的定理我们没学过……)

  3. 此题让我联想到 Evolutionarily Stable Strategy(虽然只有两个人),现实中(如生物、经济等领域)是否有符合此题模型的现象?

  我还是想说这个问题本身只是一轮,不是多轮……所以本身并没有 Evolutionary 的成分……不过如果放在演化博弈的视角下,这确实是一个 ESS。

版权声明:本文源自 网络, 于,由 楠木轩 整理发布,共 3200 字。

转载请注明: 知乎日报:猜对我手里有几枚硬币我就把它们都给你 - 楠木轩