剪刀石头布与博弈论

图片

“石头剪刀布”游戏非常适合决定谁必须将垃圾扔掉。 但是您是否注意到,如果游戏一局接一局地进行,而不是三杆,会发生什么情况? 首先,您选择一种可以给您带来好处的原则,但是随后,对手很快就会理解它并转而对其有利。 在更改策略的过程中,您逐渐达到双方都无法继续改善的地步。 为什么会这样呢?

在1950年代,数学家约翰·纳什(John Nash)证明,在任何类型的游戏中,只有有限数量的玩家和有限数量的选项(例如“剪刀石头布”),总会有多种策略混合在一起,其中没有玩家可以通过改变来显示更好的结果只有你自己的策略。 这种稳定策略的理论被称为“ 纳什均衡 ”,彻底改变了博弈论领域,改变了经济发展的方向以及研究和分析从政治契约到网络流量的一切事物的方式。 她还让纳什获得了1994年诺贝尔奖

那么,纳什平衡在石头剪刀布游戏中是什么样的呢? 让我们模拟一下您(玩家A)和对手(玩家B)一次又一次地玩游戏的情况。 在每个回合中,获胜者获得一个点,失败者失去一个点,平局计算为零点。

假设玩家B在每一轮论文中都选择了(愚蠢的)选择策略。 经过几轮胜利,败局和平局之后,您很可能会注意到他的系统并制定了制胜法宝,每轮都选择剪刀。 让我们称这套策略(剪刀,纸)。 如果每一轮都用剪刀剪纸,那么您将为理想的胜利铺平道路。

但是玩家B很快注意到了这套策略的远见。 当他看到您正在选择剪刀时,他转向了不断选择石头的策略。 这套策略(剪刀,石头)开始为玩家B赢得胜利。但是,当然,现在您要付诸实践。 在游戏的这些阶段中,玩家A和B使用所谓的“清洁”策略-唯一不断被选择和实施的策略。

显然,这里无法达到平衡:对于每个纯策略,例如“总是选择一块石头”,您可以制定一种反策略,例如“总是选择一张纸”,这将使您再次更改策略。 您和您的对手将在策略圈中不断追求彼此。

但您也可以尝试“混合”策略。 假设无需选择一种策略,而是可以在每一轮中随机选择一种纯策略。 混合策略似乎不是“总是选择一块石头”,而是“一半情况下选择一块石头,另一半情况下选择剪刀”。 纳什证明,当这种混合策略可以接受时,每个此类博弈中至少应有一个平衡点。 找她吧

什么是“剪刀石头布”的合理混合策略? 从直觉上讲,“以相等的概率选择石头,纸或剪刀”似乎是合理的。 这样的策略写为  frac13 frac13 frac13。 这意味着石头,剪刀和纸的选择概率  frac13。 这个策略好吗?

假设对手的策略是“总是捡石头”。 这是一个纯策略,可以描述为 1,0,0。 招募策略时游戏的结果是什么  frac13 frac13 frac13对于玩家A和 1,0,0给玩家B?

为了更清楚地了解游戏,我们将构建一个表格,其中将显示每轮九个可能结果中每个结果的概率:A处为石头,B处为石头; A处为石头,B处为石头。 石头在A,纸在B; 等等。 在下表中,第一行表示选择播放器B,左列表示选择播放器A。

A | 乙^ h
 frac1300
 frac1300
^ h frac1300

表格的每个元素表示每一轮选择一对选项的可能性。 这只是每个玩家做出适当选择的概率的乘积。 例如,玩家A选择纸牌的概率等于  frac13,玩家B选择一块石头的概率为1,即概率(A处的石头,B处的石头)为  frac13\乘1= frac13。 但是概率(纸在A,剪刀在B)是相等的  frac13\乘0=0,因为玩家B选择剪刀的概率为零。

玩家A将如何证明自己的策略? 玩家A会赢得三分之一的时间(纸,石头),输掉三分之一的时间(剪刀,石子),而三分之一的时间是平局(石头,石子)。 通过计算每个结果乘以相应概率的乘积之和,我们可以计算出玩家A在每个回合中平均获得的点数:

 frac131+ frac130+ frac131=0


因此,平均而言,玩家A每回合将获得0分。 您将以相等的概率赢,输和抽奖。 平均而言,获胜和失败的数量会相互平衡,实际上,两个玩家都会平局。

但是正如我们已经说过的那样,假设敌人不会改变其策略,则可以通过更改策略来改善结果。 如果您选择策略(0,1,0)(“每次选择纸张”),那么概率表将如下所示:
A | 乙^ h
01个0
000
^ h000

在每一回合中,您都将对手的石头包裹在纸上,每回合得1分。

也就是说,这对策略-  frac13 frac13 frac13对于A和 1,0,0对于B而言,这不是纳什均衡:作为玩家A,您可以通过更改策略来改善自己的成绩。

正如我们所看到的,纯粹的策略似乎并不能导致均衡。 但是,如果您的对手尝试使用混合策略,例如  frac12 frac14 frac14? 这就是“在一半情况下,选择一块石头; 纸和剪刀占案件的四分之一。“ 概率表如下所示:
A | 乙^ h
 frac16 frac112 frac112
 frac16 frac112 frac112
^ h frac16 frac112 frac112

这是从玩家A的角度来看的“奖励”表; 这是玩家A在每个结果中获得的积分数。
A | 乙^ h
0-11个
1个0-1
^ h-11个0

使用乘法,我们将两个表合并以计算玩家A在每一回合中获得的平均点数。

 frac160+ frac1121+ frac1121+ frac161+ frac1120+ frac1121+ frac161+ frac1121+ frac1120=0


平均而言,玩家A每回合再次获得0分。 和以前一样,这套策略  frac13 frac13 frac13对于A和  frac12 frac14 frac14B,导致平局。

但是像以前一样,您作为玩家A可以通过更改策略来改善您的结果:反对玩家B的策略  frac12 frac14 frac14玩家A必须选择  frac14 frac12 frac14。 这是概率表:

A | 乙^ h
 frac18 frac116 frac116
 frac14 frac18 frac18
^ h frac18 frac116 frac116

这是A的最终结果:

 frac180+ frac1161+ frac1161+ frac141+ frac180+ frac181+ frac181+ frac1161+ frac1160= frac116


也就是说,这套策略-  frac14 frac12 frac14对于A和  frac12 frac14 frac14对于B-通过  frac116每轮积分。 经过100场比赛,玩家A将领先6.25分。 玩家A有很大的动机来改变策略。 那是一套策略  frac13 frac13 frac13对于A和  frac12 frac14 frac14因为B也不是纳什均衡。

但是现在让我们看一些策略  frac13 frac13 frac13对于A和  frac13 frac13 frac13对于B。这是对应的概率表:
A | 乙^ h
 frac19 frac19 frac19
 frac19 frac19 frac19
^ h frac19 frac19 frac19

由于对称性,我们可以快速计算出总体结果:

 frac190+ frac191+ frac191+ frac191+ frac190+ frac191+ frac191+ frac191+ frac190=0


你和你的对手又一次平局。 但是这里的区别在于,没有一个参与者有改变策略的动机! 如果玩家B会采取任何不平衡的策略,其中一个选项(例如,石头)的选择比其他选项更多,那么玩家A只需更改其策略并更频繁地选择纸张。 最终,这将使玩家A在每轮比赛中都取得积极的总体结果。 这正是玩家A选择策略时发生的情况  frac14 frac12 frac14反对玩家B的策略  frac12 frac14 frac14

当然,如果玩家A从  frac13 frac13 frac13对于不平衡的策略,玩家B同样可以利用。 因此,没有任何一个玩家可以通过改变自己的策略来改善他们的成绩。 游戏达到了纳什的平衡。

Nash证明,此类游戏具有相似的平衡性这一事实非常重要,原因有几个。 原因之一是现实生活中的许多情况都可以建模为游戏。 当一群人被迫在个人利益和集体利益之间进行选择时(例如,在谈判中或在争夺公共资源的过程中),您会看到使用了策略并评估了赢利。 纳什的工作产生了如此巨大的影响,部分原因是这种数学模型无处不在。

另一个原因是,纳什均衡在某种意义上对所有参与者都是积极的结果。 当达到这种平衡时,任何玩家都无法通过改变自己的策略来改善自己的成绩。 当所有参与者完美合作时,可能会获得集体的结果,但是如果您只能控制自己,那么纳什均衡将是您可以实现的最好结果。

因此,人们可以希望,诸如经济刺激方案,税法,合同条款和网络设计之类的“游戏”将导致纳什均衡,在纳什均衡中,个人为了自己的利益行事会产生适合所有人的结果,并使系统变得稳定。 但是,在玩此类游戏时,是否合理地假设玩家自然达到了纳什的平衡?

有这样一种诱惑。 在我们的“剪刀石头布”游戏中,我们可以立即猜测没有一个玩家可以玩得更好,除非是偶然玩。 但是部分地发生这种情况是因为所有其他玩家都知道所有玩家的偏好:每个人都知道彼此在每个结果中会赢多少输。 但是,如果偏好更加隐蔽和复杂怎么办?

想象一下一个新游戏,其中玩家B在与剪刀的比赛中获胜时获得3分,而其他胜利则获得1分。 这将改变混合策略:玩家B通常会选择石头,希望当玩家A选择剪刀时获得三倍奖励。 尽管积分上的差异并没有直接影响玩家A的回报,但是玩家B策略的最终变化将导致新的反战略A。

并且如果玩家B的每个奖励都是不同的并且是隐藏的,那么玩家A将需要一些时间来找出玩家B的策略。在玩家A猜测之前必须进行很多回合,比方说,玩家B多久选择一块石头来理解他需要多久选择一次纸张。

现在想象一下,有100个人在玩剪刀石头布,每个人都有不同的秘密奖励,每个奖励取决于他们用石头,剪刀或纸赢得的99个对手中有多少人。 要选择正确的频率来选择达到平衡点所需的石头,剪刀或纸张,需要花费多少时间? 很可能很多。 也许比游戏本身更持久。 也许比宇宙本身的寿命更长!

至少,即使是选择合理策略并为自己的利益行事的绝对理性和体贴的玩家,也不会在游戏中达到平衡。 这个想法是2016年在线发表文章的基础。 事实证明,没有通用的解决方案可以在所有博弈中至少导致近似的纳什均衡。 这并不是说理想的玩家从不为游戏中的平衡而奋斗-通常他们确实会为之奋斗。 这仅意味着没有理由相信,如果完美的玩家玩游戏,那么平衡就可以实现。

当我们建立交通网络时,我们可以希望所有寻求最快最快回家方式的参与者,即驾驶员和行人,集体达到一种平衡,在这种平衡下,选择不同的路线将无法赢得任何收益。 我们可以希望,约翰​​·纳什(John Nash)的无形之手将以一种引导他们的竞争和共同利益的方式引导他们-选择尽可能短的路线,同时避免交通拥堵-将创造平衡。

但是,我们的剪刀布游戏越来越复杂,这表明这种希望可能不会实现。 看不见的手可能会控制其中一些游戏,但其他游戏却会拒绝它,使玩家陷入无尽的竞争中,从而不断取得胜利。

练习题


  1. 假设玩家B正在采取混合策略  frac12 frac120。 从长远来看,A应该选择哪种混合策略以最大化其获利?
  2. 假设玩家B正在采取混合策略  frac16 frac26 frac36。 从长远来看,A应该选择哪种混合策略以最大化其获利?
  3. 如果每个玩家获得平局,游戏的动力如何改变?

Source: https://habr.com/ru/post/zh-CN411523/


All Articles