马尔科夫链在非完全信息动态博弈中的应用.doc

马尔科夫链在非完全信息动态博弈中的应用类别：社会科学类社会调查报告和学术论文马尔科夫链在非完全信息动态博弈中的应用摘要：对于信用博弈困境这样个人理性和团体理性冲突的案例，已经通过严密的论证，说明了无限次重复博弈的可以使出现皆大欢喜的合作均衡解，而且通过无名氏定理知道无限重复信用博弈得出的结论可以使用与一般性的重复博弈。本文基于随机过程中的马尔科夫性和转移矩阵，论证了即使是在有限次重复博弈之中，信用博弈是可以出现一直（诚信，诚信）这一策略的。关键词：信用博弈困境 时齐的马尔科夫链 Markov转移矩阵 Logit函数1.前言在现代的博弈理论之下，认为无限次重复的囚徒博弈之所以可以避免陷入囚徒困境，是因为人们对未来收益和当期收益之间的完全互补性，但是实验数据并不能有力的支持这一观点。而且在过去的博弈论发展史中，关于均衡是如何产生的问题在很大程度上被避而不谈，均衡概念暗含的假设是，参与者要么听从虚构的外界仲裁者的建议，通过推理算出均衡的位置，要么是通过学习或者演化而趋近均衡。重复博弈有多少个解？有无数个。在数学上没有任何理由认为某个解比另外的解更有可能出现，但用语言可以做这种暗示。汪丁丁说，合作有可能出现。这个说法既不和数学结论冲突，又可以暗示合作就是重复博弈的均衡。克莱帕斯关于重复博弈有两个解的论断也和这个结果兼容。而“重复博弈的结果就是合作”根本没有任何数学基础，只不过是一个愿望而已。奥斯本和鲁宾斯坦强调说，重复博弈理论的贡献是“证明了产生这种组合的均衡的存在性”（1994，p134）。这个数学工具虽然论证了合作确是“一个”均衡解，但同一个数学工具也告诉了我们这个均衡解发生的概率有多大。无论博弈理论家如何偏爱无数均衡解中的某一个，这种偏爱都得不到数学逻辑的支持。有人很温婉地指出，重复博弈模型预言了合作就是纳什均衡这种说法太过了8。宾默尔说的就很不客气。对于博弈论数学家来说，如何继续求助于数学变换，将这个解的范围进一步缩小，是一个重要的工作。如果数学家可以解开不确定性重复博弈，证明“合作”是重复博弈的均衡解，就证明了一个关键的博弈其纳什均衡也是合作，同时也可以证明守约就是博弈均衡，于是就证明了经济学中非常流行的一个命题：一切法律规范都是和纳什均衡一致的（张维迎，2000）；同时也证明了另外一个命题：契约可以自我实施。本文基于实验中调整收益可以改变博弈结论的这一事实，在学习理论中选择一种博弈学习的规律，通过计算更新概率，从转移概率、转移矩阵的角度，证明了正仿射变化没变法实现（合作，合作）的均衡解，以及通过马尔科夫矩阵和转移概率来分析和探讨怎么通过学习或者演化而趋近均衡的。周蓉5研究了具有学习效应的寡头厂商重复博弈，认为在实际博弈中，当参与者有经验时，博弈的结果和纳什均衡有很大的不同，参与者的策略有明显的合作趋势。并且其所做的实验得到的结论是：在重复博弈的阶段数不多的情况下，尽管参与者初始的策略不一致，但经过博弈，参与者策略的平均水平将趋向纳什均衡解。表明参与者在初始阶段缺乏必要的知识或者由于没有历史博弈可以参考的情况下，会作出不理性的决定，但随着博弈的进行，参与者之间会有一定程度上的知识共享，参与者会分析其他人的决策来调整自己的策略。张秀英6通过研究考试作弊行为，认为学生和老师都是基于自身利益最大化的做出决策的，认为博弈的最终结果受监考力度的直接影响，博弈可能出现的结果并不是唯一的。张汉江7等探析了信贷行为中的不完全信息动态博弈，认为参与者发送的信号不同，对重复博弈的最终均衡会产生很大的影响，因此在考虑均衡的时候需要考虑参与者的行为，以便分析参与者发送不同信号的原因。从博弈论的精髓分析中不难看到，博弈论能够解决的问题是比较有限的。只有那些在博弈论框架下的问题能够通过某种分析方法得到均衡的解析解，才是博弈论的解。尽管在近百年的研究中，可以列出许许多多博弈论解决的问题，如囚徒困境、智猪博弈、手雷问题等，数不胜数，但想通过数学分析的方法能够对博弈的结果给出一致预测的情况却是十分有限的。此外，在一个动态博弈中，如果参与者的策略集和对弈回合数比较庞大，如数以十计，由于采用扩展式模型的节点数接近天文数字而难以建模，用回溯的方法更是无法在时间和空间上应对，现有的博弈论模式依然显得无能为力。因此，博弈论无论从它的目标上，还是从它求解问题的方法上，都需要极大的拓展。虽然博弈论能够解释无限次重复博弈，例如信用合作博弈等重复博弈可能可以达到（合作，合作）的最优解，但是这是基于贴现因素的影响，导致人们对现在和未来的收益有不同的感受，只有在合作的情况下预期收益的现值大于不合作的预期收益的现值情况下，才会出现（合作，合作）的均衡解。但是，人们是有限理性的，没办法完全预期未来的收益，基于大多数的实验表明，人们普遍只能预期未来两期的收益，而这样就会造成无限次博弈很可能达不到（合作，合作）的均衡。本文使用马尔科夫链来解决收益对重复博弈最优均衡的影响，解决对弈回数比较庞大的不完全信息动态博弈，以及基于有限理性的假设，解决了两期预测拓展到无限期预测下的均衡问题。马尔科夫链，简称马氏链，最主要的特征是无后效性，当期的状态至于前一期的状态有关，而与其他前期的状态无关，这并不是说其他前期的状态对本期没有影响，而是说明其他前期的影响已经都转移到前一期之中，即Markov链的定义为：从Markov过程转为研究马氏链，会更加便于研究。因为一旦Markov链的初始分布给定，其统计特性就完全由条件概率决定。而如何确定这个条件概率，也正是Markov链理论和应用中的重要问题之一。基于马氏链来分析对弈回数很庞大的博弈，可以将离散时间的马氏链的状态空间看成是每次对弈可能出现的结果的集合，对每次可能出现的结果进行分类来统计转移矩阵，计算从不同的状态出发最终可能在有限次或者无限次重复博弈可能出现的结果进行预测。2.学习理论在Markov链中的体现2.1学习理论3学习模型主要研究的是哪类模型在一般情况下更符合学习的过程，以及为什么更符合这个过程。学习也被定义为由于经验而发生的行为方面被观察到的变化，因此学习的统计模型预测了历史的信息如何影响未来选择的概率。博弈论中关于学习的理论很多：演化动态、强化学习、信念学习、老练（预期性）学习、经验加权吸引力（EWA）学习、模仿、方向学习和规则学习。在此，我们并不是致力于探讨到底哪一种学习理论更加准确的描述事实，而是在前人的基础之上，研究在这些学习理论之下，对于一些问题的博弈策略在此种理论之下的更新概率，并将这个更新概率运用到Markov链之中，探讨重复博弈可能存在的均衡。但是在对混合策略均衡博弈进行分析和预测的时候，所有的基本模型大体上预测得一样的准确。此外，对于EWA，需要对灵敏度、及机会成本的权重、由于在学习环境不断变化时，遗忘或者对旧经验的故意放弃而导致的前一期吸引力的衰减参数、吸引力的增长率进行拟合这些参数。由于缺乏数据，因此，考虑使用强化理论来计算更新概率，并预测重复博弈的结果。信念学习大概的思想是，参与者利用关于其他参与者过去的策略选择与获得收益的信息来更新当前博弈阶段他们对其他参与者策略选择的偏好信念。这样他们可以根据对其他参与者策略选择的预期来决定自己的最优策略。与路径学习以及模仿学习不同的是，信念学习对博弈参与人只有间接的影响，过去的经验强化或削弱参与人的信念。这样，他们可以依据对其他参与人的选择的预期来决定自己的最优反应。2.2.根据学习理论建模（1） 符号说明（2）转移概率的计算1）.每个策略都有一个分支，它是每个参与者i的 个策略的吸引力的加权线性组合。T使其策略的分值3是，表示第i个参与者在时间t选择策略j的期望收益：2）.每种策略被采纳的概率是Logit形式，表第i个参与者在时间t选择策略j的概率：如果需要考虑其他因素的时候，需要提出一个满足一系列条件的概率函数，在此为了便于分析，假定影响参与者决策的依据只有支付函数。3）.转移概率的计算：由条件概率公式可知：表示参与者从前一个状态转移到后面一个状态的概率，也就是说参与者前一次选择策略B到参与者下一步选择策略的概率。因此在知道前后发生的概率的基础之上，求出在B发生的条件下A发生的概率，这个概率也就是状态之间的转移概率。(3)一步转移矩阵在计算转移矩阵的时候，需要说明的问题是，所涉及的经济问题是不是具有时齐的马尔科夫链性质。时齐的马尔科夫链，就是说Markov链的转移概率P(Xn+1=j|Xn=i)只与状态i，j有关，而与时刻n无关。也就是不论什么时候发生在状态i到状态j的转移概率，与具体什么时候到达状态i，j是无关的，只与当前状态和未来状态有关。学习博弈的一个重要假定就是博弈的参与者是有限理性的，因而随着博弈的进行，不同的参与者之间的互动产生了一个学习的动态过程，其和子女在于不同类型的博弈在相应的学习过程中如何人导致长期博弈收敛于某一个纳什均衡。在学习过程中，参与者可能强化已有的信念、或者模仿或者更新信念等，从而变得越来越老练和理性。在此基础之上，可以认为存在学习过程的博弈是一个马尔科夫链，其转移概率具有时齐的马尔科夫性质。2.3案例分析信用博弈 给出信用博弈的阶段博弈矩阵，如下所示：商人2诚信欺骗商人1诚信4，40，5欺骗5，01，1此博弈的一次博弈也可以用博弈树（扩展式）来等价表示，如下所示：商人1欺骗(1-p1)诚信p1欺骗(1-p2)欺骗(1-p2)诚信p2诚信p2商人2商人21 15 00 54 4假设给定商人2认为商人1诚信的概率为p1，则商人2认为商人1欺骗的概率是为1-p1，在此时商人2选择诚信的期望收益就是商人2选择欺骗的期望收益就是因此商人1认为商人2诚信的概率p2为：则商人1认为商人2欺骗的概率为1-p2(1)。现在商人1和2都根据对方所属类型来进行决策，选择自己的策略。通过观察可以知道，对于任意的p1，都有也就是说在进行第一次博弈的时候，不论商人1诚信的概率有多大，商人1认为商人2在这样的报酬情况下，都会选择欺骗，因为商人1认为商人2的选择诚信这一策略的概率小于0.5，因此商人1必然选择欺骗这一策略，而在商人1选择欺骗的时候，商人2基于这样的认识，将会在后面的博弈中改变对商人1的类型的评价，也就是说将改变商人1是诚信还是欺骗的概率。将上面的信用博弈扩展到两期，则其博弈矩阵就变为：商人2（诚信，诚信）（诚信，欺骗）（欺骗，诚信）（欺骗，欺骗）商人1（诚信，诚信） （8 8） （4 9）（4 9）（0 10）（诚信，欺骗） （9 4） （5 5）（5 5）（1 6）（欺骗，诚信） （9 4） （5 5）（5 5）（1 6）（欺骗，欺骗） （10 0） （6 1）（6 1）（2 2）在第二期的时候，商人1认为商人2选择欺骗策略的概率是1-p2，选择诚信的概率是p2.基于这样的认识，则商人1在第一期选择诚信的条件下，第二期选择诚信的期望收益就会变为：商人1在第一期选择诚信的条件下，第二期选择欺骗的期望收益是：商人1在第一期选择欺骗的条件下，第二期选择诚信的期望收益是：商人1第一期选择欺骗的条件下，第二期选择欺骗的期望收益是：按照信念理论，引入信念更新函数，如下所示：也就是说，商人1在第二期选择诚信或者欺骗的时候，都对于其收益施加一个信念，使得具有加强的效应，于是按照前面由收益得到的概率就可以有如下几个： 由于，因此有因此也就是说由上期诚信转移到下一期继续保持诚信的概率是小于0.5的，由上期欺骗转移到下期诚信的概率也小于0.5，也就是说由上期欺骗转移到下期欺骗的概率是大于0.5的。也就是说当商人2对商人1在决策的时选择诚信和期望概率的转移矩阵是：此时在这样的转移矩阵下，商人2认为商人1在第二期选择诚信和欺骗策略的概率分别为：此时，即使在p1=1的时候，商人2认为商人1在第二期选择诚信和欺骗策略的概率也会是选择欺骗的概率大于选择诚信的概率。也就是说商人2会认为商人1在第二期选择欺骗，因此，不管将上述博弈重复多少次，总会出现（欺骗，欺骗）的均衡解，而不是团体最优解（合作，合作）。综上所述，在两期博弈的时候，按照逆序求解博弈的均衡，知道商人2认为商人1在第二期将选择欺骗，此时，商人2也将选择欺骗，再回到第一期，商人1不知道商人2对其初始的评价，认为商人2将选择欺骗，则商人1在第一期将选择欺骗，而商人2在第一期选择诚信还是欺骗的概率按照其既定的对商人1的诚信概率p1来决定，因此两期信用博弈的结论都是商人1都选择欺骗，而商人2第二期开始也将选择欺骗，因此最终必将陷入信用博弈的困境，达不到两者的最优。按照上述的方法，如果假设商人2将一直按照上述的转移矩阵来修正商人1对策略诚信和欺骗的概率，在商人1和商人2重复博弈次数趋于无穷次得时候，将会发现不论开始的时候商人2对商人1的诚信的概率是多大，最后商人2认为商人1选择诚信的概率都是0.2689，选择欺骗的概率达到0.7311.因为：因此在这种支付下的信用博弈将无法在无穷次重复博弈下走出囚徒困境。唯一的均衡结果只能是每一阶段都为（欺骗，欺骗），因而人类社会所谓的合作根本就不可能产生，人与人之间的诚信只能是一种奢望。然而，现实并非如此，虽然人与人之间存在着利益冲突，但也确实存在着合作的行动和结果，否则人类社会早就终结了。这种合作不仅仅在人类社会存在，实际上在动物的行为中同样存在，莎士比亚笔下的夏洛克虽然歹毒，但是不可否认他是诚信的。那么如何解释这种合作行动呢？3.信用博弈困境的解决对于信用博弈困境，一种观点认为，合作解在有限重复博弈中出现要求阶段博弈必须存在多重纳什均衡，但在无限重复博弈中，这一条件并不是必需的，因为在重复博弈无限次的情况下，贴现因子充分接近于1，即人们有足够的耐心，那么考虑长远的利益也就要好于短视。因为如果当前参与者选择合作，那么他将得到的好报（选择高收益的均衡结果）；如果选择欺骗，那么将来他将得到报应（选择低收益的均衡结果）。“两害相权取其轻，两利相权取其重”，从而使得合作在信用博弈中出现4。现在从另一个角度对这个问题进行描述3，因为在Camerer and Hogarth，1999年的实验中，有进行增加奖金的最后通牒实验，表明通常多付一单位的奖金通常并不会改变参与者思考的难度，因为行为本来就是简单的，但是奖金较高可能会改变参与者赋予在自身所得和他人所得上的相对权重。虽然奖金效应在实验研究中确实得到一定程度上的证实，但是这种效应是微乎其微的。在美国最早的关于这方面的研究显示拒绝比例没有显著性的变化（Roth et al.，1991；Forsythe et al.，1994；Hoffman，McCabe and Smith，1996a；Straub and Murnighan，1995）。然而这些研究都收到了限制，因为应用了特定的出价法并且低出价很少出现，因此统计学上对拒绝比例如何变化很难进行研究。后来人们对其他国家进行了一些有创见的实验，其中所定的奖金具有相应的足够购买力。斯洛伐克，斯洛尼姆和罗思（1998）发现在中等和高水平的奖金条件下（集中进行十次实验）拒绝行为显著的减少（每次遇到的对手都不同）。里斯特和凯瑞（2000）在佛罗里达州进行实验，针对不同额度的不同拒绝行为以及跨时期的变化进行了有力的统计观察，实际结果表明，对于400美元的额度，拒绝比例的确要较小一些，并且随着时间的推移有某种程度上的下降。在这种观点之下，认为支付对博弈均衡结果有重要的影响。由纳什均衡的不变性可以知道，纳什均衡在支付函数的正仿射变换下是不变的2。因此考虑对支付函数进行正仿射变换，即对任意的参与者i，有因此上述的信用博弈矩阵可以表示为（a0,b0)：商人2诚信欺骗商人1诚信4a+c，4b+dc，5b+d欺骗5a+c，da+c，b+d此时商人2在认为商人1诚信的概率是p1的情况下，商人2选择诚信的期望收益是：商人2选择诚信的期望收益是：因此商人1认为在商人2诚信的概率是：可见商人1认为商人2选择诚信的概率是与商人2支付函数的放大倍数b有关的，放大倍数越大，参与者选择欺骗的概率也就越大，也就越不可能选择诚信来达到都合作。而且，在b非负的情况下，有从另个一个角度论证了纳什均衡在支付函数的正仿射变换下是不变的。在一定程度上也说明，利用马尔科夫转移矩阵来说明纳什均衡存在性是可行的。因此，考虑两期有限信息博弈，存在强化信息时候的重复博弈的均衡情况。再将上面的信用博弈扩展到两期，则其博弈矩阵就变为：商人2（诚信，诚信）（诚信，欺骗）（欺骗，诚信）（欺骗，欺骗）商人1（诚信，诚信）8a+2c，8b+2d4a+2c，9b+2d4a+2c ，9b+2d2c ，10b+2d（诚信，欺骗）9a+2c，4b+2d5a+2c ，5b+2d5a+2c ，5b+2da+2c ，6b+2d（欺骗，诚信）9a+2c，4b+2d5a+2c ，5b+2d 5a+2c ，5b+2da+2c，6b+2d（欺骗，欺骗） 10a+2c ，2d 6a+2c ，b+2d6a+2c ，b+2d2a+2c ，2b+2d在第二期的时候，商人1认为商人2选择欺骗策略的概率是1-p2，选择诚信的概率是p2.基于这样的认识，则商人1在第一期选择诚信的条件下，第二期选择诚信的期望收益就会变为： 商人1在第一期选择诚信的条件下，第二期选择欺骗的期望收益、第一期选择欺骗的条件下，第二期选择诚信的期望收益、第一期选择欺骗的条件下，第二期选择欺骗的期望收益分别是：考虑信念的作用，可以得到：于是按照前面由收益得到的概率就可以有如下几个： 也就是说商人2对商人1在决策的时选择诚信和期望概率的转移矩阵就是：因此在这样的转移矩阵下，商人2认为商人1在第二期选择诚信和欺骗策略的概率分别为： 给定p1以及a，b，c，d可以求出第二期博弈时商人2对商人1诚信的概率，通过Matlab计算可以得到下列模拟的结果：（1） 此次模拟的含义就是在初始商人2认为商人1诚信的概率是0.95，且商人1的支付按照的正仿射变化，商人2按照来变化，得到的第一次转移概率分别是由诚信到诚信的概率是1，由欺骗到欺骗的概率是1，这也就是说会出现两种可能的均衡，一种是（诚信，诚信），另外一种是（欺骗，欺骗），而到底会出现这两者之中的那种，取决于初始的商人2认为商人1诚信的概率，在诚信概率是0.95的时候，第二期商人2认为商人1诚信的概率还是0.95，那么此时商人2两期都会选择诚信这一策略，同理，商人1也会选择诚信这一策略，因此，最终出现的是（诚信，诚信）的团体最优解。当商人2认为商人1诚信的概率小于0.5的时候，此时出现的不再是（诚信，诚信）的最优解，而是（欺骗，欺骗）的纳什均衡。因为一旦两个商人之间有一方选择欺骗这一策略，就会在转移矩阵的作用下，最终两者都选择欺骗，只要两者都选择欺骗的时候，那么，只可能出现（欺骗，欺骗）的均衡，不管怎样，都不可能使得选择诚信这一策略的概率大于0.5。（2）类似上面的分析，当商人2认为商人1选择诚信的概率大于0.5的时候，都会出现（诚信，诚信）的均衡，而当商人2认为商人1选择欺骗的概率较大的时候，就会出现（欺骗，欺骗）的均衡。而且，还可以发现，增加在保持商人2认为商人1诚信的初始概率不变的时候，增大c，也就是增大商人1的支付，会使得无限次重复博弈的转移矩阵变为只有两个选择的均衡，即只会出现（诚信，诚信）或者（欺骗，欺骗）。也就是说，如果在增大商人1的收益的时候，如果商人2认为商人1诚信，那么博弈的最终结果只可能是实现（诚信，诚信），也就是说在减少商人1选择诚信和欺骗之间收益的差额的时候，商人1更可能的按照期望和强化信息，选择唯一的策略。（3） 此时模拟的是在减少商人1获得支付的倍数的时候的转移矩阵，可以发现，在无限次重复博弈的时候，商人1最终只会选择欺骗策略，尽管前面几期是选择诚信的策略，但是基于收益放大倍数不够明显，使得最终滑向（欺骗，欺骗）的均衡策略。在减少商人2认为商人1初始选择诚信概率的时候，例如在p1=0.45的时候，因此第二期就会滑向（欺骗，欺骗）的纳什均衡。（4）在这次的模拟中，改变了商人2的支付的放大倍数，虽然不改变第一次转移矩阵，但是在无限次重复博弈的转移概率发生了改变。由于d在无限次重复博弈的转移概率之中并没有这一项，因此不考虑d的变化的影响。4.小结由上面的分析计算可以知道，不论商人2初始认为商人1诚信的概率是多少，最终会出现三种情形：（1） 商人2认为商人1是诚信的概率都大于0.5，此时商人2将一直选择诚信这一策略，因此说明存在合作的可能性；（2） 商人2在前面几期认为商人1选择诚信的概率大于0.5，此时商人2会选择诚信，但是在几期之后，商人2会认为商人1欺骗的概率更大，大于0,5，这时候商人2将不在选择诚信这一策略，而改为选择欺骗，这也和实际之中人们在有限期合作之后将最终回归到（欺骗，欺骗）这一策略；（3） 商