石头-剪刀-布---三人博弈

（一）“石头，剪刀，布”游戏（Rock,Scissor,Paper）思考：双方应该怎么选择才是最优的？是否存在绝对致胜的方法？我们总是在选择自己的战略前试图猜中对手的行动选择；同时，我们又会力图避免自己的选择被对方猜中，还要根据自己对对方行动的事前预测来做出最优的行动选择，即这样的游戏行动选择带有随机性。（二）著名的“囚徒困境”（Prisoners’Dilemma）假设有两个小偷联合犯事，私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行单独审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果两人都认罪，则各被判刑8年。如果一人认罪，另一人不认，则认罪者立即释放，不认罪者加重判刑至10年。如果两人都不认罪，则警方因证据不足不能判两人有罪，但可以因私入民宅的罪名将两人各判入狱一年。并且，每个小偷都被告知，他的同伙也面对着同样的政策。想想:他们会如何选择，最终的决策结果会是什么？分析：这个模型有如下要素：1.两个小偷必须在不知道对方的选择的情况下独立进行自己的决策2.双方都会为自己的利益考虑，即使自己的盈利最大化将双方的具体选择和相应的结果描述如下：-8-80-10-100-1-12认罪不认罪认罪1不认罪对1来说无论2选择什么，他选择‘认罪’总是最优的，根据对称性，对于2，‘认罪’也是最优的，所以模型的最终选择结果是（认罪，认罪）但是，实际上，显然（不认罪，不认罪）是对双方最好的结果。所以，在个人理性与集体理性之间存在不一致性。我们假定两个小偷都只在乎各自的刑期，且盈利等于刑期的相反数博弈与决策：博弈是建立在相互猜测对方的决策过程基础上的决策，即是“互动性”的决策。博弈论是建立在理性人的假设基础之上（理性人一般是指主体所追求的唯一目标是自身经济利益的最大化），博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略，被广泛应用到经济活动和其他社会科学领域当中。上述两个例子，其实都可以被描述为一局博弈，而且都是二人博弈（只有两个参与者），其中隐含了时间的动态性质，被称为静态战略式博弈。下面我们给出博弈模型的战略式数学描述GameTheory定义：一个战略式博弈G=N,(𝑨𝒊),（𝒖𝑖）有如下组成部分：博弈局中人集合：N={1,…,n};每一个局中人𝒊有一行动集𝑨𝒊，行动集合包括其可选择的所有行动，𝒊∈N每个局中人𝑖有一个盈利函数（或效用函数）𝒖𝒊：𝑨→𝑹,其中𝑨=×𝑨𝒊,𝒊∈N局中人（Players）：可以是个人也可以是团体、组织等，在博弈论中假定局中人是理性人。行动空间（Actionspace）：每个局中人都有一行动集，而每个人在自己的行动集当中的选择所构成的一组策略，被称为行动空间，即上述A。盈利函数（效用函数Payofffunction）：指局中人从博弈中获得的效用水平，大多是数值型的，来表示自己在一局博弈当中的盈利。显然，它是A的函数，并且满足线性变换。（Rock,Scissor,Paper）运用这些概念，我们来描述一局“石头，剪刀，布”游戏：N={1，2}𝑨𝒊={石头，剪刀，布}，𝒊=1,2𝒖𝟏（剪刀，布）=𝒖𝟏（布，石头）=𝒖𝟏（石头，剪刀）=1𝒖𝟏（石头，石头）=𝒖𝟏（剪刀，剪刀）=𝒖𝟏（布，布）=0𝒖𝟏（剪刀，石头）=𝒖𝟏（布，剪刀）=𝒖𝟏（石头，布）=-1𝒖𝟐（𝒂𝟏,𝒂𝟐）=−𝒖𝟏（𝒂𝟏,𝒂𝟐），∀𝒂𝒊∈𝑨𝒊（𝒖𝟏+𝒖𝟐=0，零和博弈）支付矩阵为：001-1-11-11001-11-1-11002石头剪刀布石头1剪刀布（Rock,Scissor,Paper）显然，从支付矩阵上看，不存在一个对双方都是最优的决策，但是无论双方的选择是什么，各自的效用函数之和总是为零。这样的博弈称为二人零和博弈那么我们怎么选择才能使自己的盈利最大呢?既然，局中人的行动具有随机性,我们对每一行动选择赋予概率，组成该博弈的混合战略。定义：∆𝑨𝒊=(𝜶𝟏,⋯,𝜶𝒌(𝒊))𝜶𝒋≥𝟎,∀𝒋,𝜶𝒋=𝟏𝒌(𝒊)𝒋=𝟏,称为𝒊的混合战略空间，即𝒊用𝜶𝒊,𝒌的概率去选择他在𝑨𝒊的第𝒌个行动，𝒌(𝒊)为𝑨𝒊中元素的个数，记𝜶𝒊𝝐∆𝑨𝒊为𝒊的一个混合战略，𝜶𝒊=⋯，𝜶𝒊,𝒌，⋯。现在我们用𝜶−𝒊=𝜶𝟏，⋯，𝜶𝒊−𝟏，𝜶𝒊+𝟏，⋯，𝜶𝒏来表示除𝒊以外其他人的混合战略的组合。给定混合战略组合𝜶=𝜶𝒊，𝜶−𝒊，则局中人𝒊的期望盈利为（假定局中人是独立地选择行动）:𝑼𝒊𝜶=𝜶𝒋(𝒂𝒋)𝒖𝒊(𝒂)𝒋𝝐𝑵𝒂∈𝑨,𝜶𝒋𝒋𝝐𝑵(𝒂𝒋)是在混合战略组合𝜶之下行动组合𝒂出现的概率。运用上述概念，我们来对“石头，剪刀，布”完整地建立博弈模型：记双方的混合策略行动集分别为∆𝑨𝟏=𝒑=(𝒑𝟏,𝒑𝟐,𝒑𝟑)𝟎≤𝒑𝒊≤𝟏,𝒑𝒊=𝟏𝟑𝒊=𝟏,∆𝑨𝟐=𝒒=(𝒒𝟏,𝒒𝟐,𝒒𝟑)𝟎≤𝒒𝒊≤𝟏,𝒒𝒊=𝟏𝟑𝒊=𝟏,𝒖𝟏𝒂𝟏,𝒂𝟐可以表示为效用矩阵（𝒖𝟏𝒊,𝒋=𝒎𝒊𝒋）𝑴={𝒎𝒊𝒋}𝟑×𝟑=𝟎𝟏−𝟏−𝟏𝟎𝟏𝟏−𝟏𝟎同理，𝒖𝟐𝒂𝟏,𝒂𝟐的效用矩阵为−𝑴则𝑼𝟏𝜶=𝑼𝟏𝒑,𝒒=𝜶𝒋(𝒂𝒋)𝒖𝟏(𝒂)𝟐𝒋=𝟏𝒂∈𝑨=𝒑𝑴𝒒𝑻=𝒑𝒊𝒎𝒊𝒋𝒒𝒋𝟑𝒋=𝟏𝟑𝒊=𝟏𝑼𝟏𝜶=−𝑼𝟐𝜶局中人1希望最大化自己的期望效用，而局中人2希望最小化1的效用（等价于最大化自己的期望效用，因为是零和博弈），根据二人零和博弈理论，1和2的决策问题变为：对于1:𝑴𝒂𝒙𝒑𝑴𝒊𝒏𝒒(𝒑𝑴𝒒𝑻)；对于2：𝑴𝒊𝒏𝒒𝑴𝒂𝒙𝒑(𝒑𝑴𝒒𝑻)根据零和博弈理论的最小最大定理有：𝑴𝒂𝒙𝒑𝑴𝒊𝒏𝒒𝒑𝑴𝒒𝑻=𝑴𝒊𝒏𝒒𝑴𝒂𝒙𝒑𝒑𝑴𝒒𝑻即此时战略（𝒑,𝒒）对于双方都是最优的，在该战略选择下，每个人都没有动机单方面偏离自己选定的战略，我们说此时达到了平衡的稳定态。这样的一对（𝒑,𝒒）称为该局博弈的混合战略纳什均衡（Nash,1950）在博弈理论中，纳什均衡是一个非常重要的概念，它表达了博弈的基本原理，我们简单地给出它的定义：对于战略式博弈𝑮=𝑵,𝑨𝒊,(𝒖𝒊).行动组合𝒂∗=(𝒂𝟏∗,⋯,𝒂𝒏∗)满足：𝒂𝒊∗∈𝒂𝒓𝒈𝒎𝒂𝒙𝒂𝒊∈𝑨𝒊𝒖𝒊𝒂𝒊,𝒂−𝒊∗,𝒊∈𝑵.即对任意的𝒂𝒊∈𝑨𝒊且𝒂𝒊≠𝒂𝒊∗，都有𝒖𝒊𝒂𝒊∗,𝒂−𝒊∗≥𝒖𝒊𝒂𝒊,𝒂−𝒊∗，则𝒂∗是一个（纯）纳什均衡（Nashequilibrium），同理可类比混合战略纳什均衡。𝑚𝑖𝑗𝑞𝑗≤𝑝𝑀𝑞𝑇,∀𝑖∈𝐴1(𝑚)𝑛𝑗=1𝑝𝑖𝑚𝑖𝑗≤𝑝𝑀𝑞𝑇,𝑚𝑖=1∀𝑗∈𝐴2(𝑛)显然，满足上式的（𝒑,𝒒）就是所求的均衡，这样问题就转变为规划问题，可以用LINGO求解。对二人博弈，用计算机求解纳什均衡常用的Lemke-Howson算法主要运用下述定理：LINGO程序如下：model:sets:k/1..3/:p;n/1..3/:q;pay(k,n):Ma,Mb;endsetsdata:Ma=01-1-1011-10;Mb=0-1110-1-110;enddatava=@sum(pay(i,j):Ma(i,j)*p(i)*q(j));vb=@sum(pay(i,j):Mb(i,j)*p(i)*q(j));@for(k(i):@sum(n(j):Ma(i,j)*q(j))=va);@for(n(j):@sum(k(i):Mb(i,j)*p(i))=vb);@sum(k:p)=1;@sum(n:q)=1;@free(va);@free(vb);End运行结果：VariableValueVA0.000000VB0.000000P(1)0.3333333P(2)0.3333333P(3)0.3333333Q(1)0.3333333Q(2)0.3333333Q(3)0.3333333即符合要求的概率行动为：𝒑𝟏=𝒑𝟐=𝒑𝟑=𝟏𝟑𝒒𝟏=𝒒𝟐=𝒒𝟑=𝟏𝟑表明当局中人分别以同样的概率随机的去选择石头、剪刀、布中的任一个时，对双方来说此时是最优的，而且此时双方的期望盈利达到最大，可以验证，最大盈利都为01.我们可以这么理解该游戏的混合战略，当每个人以同等的概率随机的选择时，他们认为这三个行动一样好，即没有对哪个的偏好，此时对于对方的选择，你选择哪一个行动所获得的期望效用是相同的，所以你选择哪个是无差别的。2.对于该游戏，我们选取的效用函数构成了零和博弈（Zero-SumGame），但是如果局中人的效用之和不为零，我们不能根据最小最大定理简单地去分析和计算，但是我们可以根据纳什均衡的定义去求解。我现在要求是三个人玩呢？（”Rock,Scissor,Paper”forthreepeople）拆分成三个二维矩阵：对于某一局中人1有23石头剪刀布石头0,0,01,1,-1-1,-1,1剪刀1,-1,11,-1,-10,0,0布-1,1,-10,0,0-1,1,1石头：23石头剪刀布石头-1,1,1-1,1,-10,0,0剪刀-1,-1,10,0,01,1,-1布0,0,01,-1,11,-1,-1剪刀：23石头剪刀布石头1,-1,-10,0,01,-1,1剪刀0,0,0-1,1,1-1,1,-1布1,1,-1-1,-1,10,0,0布：容易验证：该博弈不存在纯纳什均衡，考虑混合战略:∆𝐴1=𝒎=(𝑚1,𝑚2,𝑚3)0≤𝑚𝑖≤1,𝑚𝑖=13𝑖=1,∆𝐴2=𝒑=(𝑝1,𝑝2,𝑝3)0≤𝑝𝑗≤1,𝑝𝑗=13𝑖=1,∆𝐴3=𝒒=(𝑞1,𝑞2,𝑞3)0≤𝑞𝑘≤1,𝑞𝑘=13𝑖=1,𝑈1𝛼=𝑈1𝒎,𝒑,𝒒=𝛼𝑗(𝑎𝑗)𝑢1(𝑎)3𝑎∈𝐴=𝑚𝑖𝑝𝑗𝑞𝑘𝑀1𝑖,𝑗,𝑘3𝑘=13𝑗=13𝑖=1𝜕𝑈1𝛼𝜕𝑚𝑖=0,𝜕𝑈1𝛼𝜕𝑝𝑗=0,𝜕𝑈1𝛼𝜕𝑞𝑘=0𝑚𝑖=13𝑖=1,𝑝𝑗=13𝑖=1,𝑞𝑘=13𝑖=1𝑚𝑖,𝑝𝑗,𝑞𝑘≥0根据纳什均衡，均衡点𝑚,𝑝,𝑞是使得𝑈1𝛼取最大值，不妨看作一多元函数求极值的问题：进一步分析：局中人的选择和盈利是对称的，所以我们考虑的局中人1怎么选让自己的盈利最大，对于2和3也是一样的𝒎=(13,13,13)𝒑=(13,13,13)𝒒=(13,13,13)我们加入对称条件去简化上述方程的求解：𝑚𝑖=𝑝𝑖=𝑞𝑖,𝑖=1,2,3最后得出：当然，也可以用MATLAB去求解，运行结果跟前面的理论分析是一样的，截图如下：M文件主函数及结果总结：我们根据博弈的理念，对这个小游戏作了一下关于最优战略的讨论和分析，可以看出当限定一些条件之时，无论二人还是三人“石头，剪刀，布”，每个参与者以相等的概率随机选择三个行动时是最优的，我们可以根据对称性解得，即使是𝒏人参与的游戏，在与之相同的规则下博弈的均衡解应是一样的。拓展问题：假定三人游戏中，任意两人可以组成联盟呢，如果是多人呢？给出一种情况：23石头剪刀布石头0,0,01,-𝟏𝟐,-𝟏𝟐-1,𝟏𝟐,𝟏𝟐剪刀1,-𝟏𝟐,-𝟏𝟐2,-1,-10,0,0布-1,𝟏𝟐,𝟏𝟐0,0,0-2,1,11.石头：