计算n人博弈均衡点4.doc

计算N人推广到连续的各相关k衡1≦k≦N，为找到一个N人衡提供了一个建设性的程序1.引言 本文的目的是论证来蒙克豪恩算法，这个算法最初是作为一个建设性程序寻找双人博弈均衡，现在也常被延伸拓展直接用来建立N人博弈的均衡。当然，在此过程中需要求解多线性方程的通解，而不仅仅是在两人情况下的特解，但总有适合该问题的计算方法。Nash给出了一个采用有理数和无理数间的平衡下的三人博弈的例子。 本文中心思想是在一般情况下，一个几乎互补的路径，导致一个平衡，的情况。此外，人们可以几乎互补的路径，通过构建一个（n-1人的平衡启动程序。因此，可以通过k人博弈的平衡的n人平衡，1≦k≦N。 2.N人非合作博弈的情况。P表示有限个博弈的人数的集合，给出P的子集n, Sn表示一般情况下对应于人数n的有限个纯策略。表示局中人的可能存在的组合情况。对于任意n, w，定义假定不考虑下总体的损失，定义n阶矩阵，其中每个元素都为正。 混合策略对于博弈论的参与者n(P是一个概率分布，也就是说公式 超过了他在Sn 中的单纯策略。也即(i( Sn)(ni(0且( i( Sn(ni=1。因此，(n是(Sn(维单纯形(n的一个元素，而且(ni是参与者n在其第i个纯策略中的概率。定义(=(n(P(n是该博弈的混合组合策略集。同样，对于每一个参与者v(P和(((，令(v（(）=((((((，n(v，(，是参与者v的混合策略变量子集合。一般来说，对于任意x((( 欧式空间 特别是，对于参与者n混合策略 在他的纯策略i的条件上产生预期效用 ，无条件的期望效用 。很容易验证均衡的定义就是 。而且，一个人可以通过改变一下变量来消除限制 ： 定义 然后，对于一个均衡，我们可以而且能够找到这样的x，y，使得 显式（3）平行的推导出莱蒙克和霍森两人博弈的结论。通常，如果我们给定x(((，我们假设y通过 来定义。 我们可以从一个解决方案到（3）式，通过反向转换获得一个均衡 。因此，寻找（3）式的解决方案是我们直接的调查对象。 3.几何特性。对于任意的参与者n(P，令 ，令 。显然，每个(n是非空且封闭的，由于An(0，且每个(n和Z*包含了（3）式的所有解。纳什[3]给出了一个定点证明了均衡的存在，因此Z*是非空的，尽管稍后我们会提供一个创造性的证明来说明这个事实。 他满足必须考虑相关子集Z*，也即，集合Z从子集Z*点出发 均衡是指混合策略组合，且没有一个参与者希望单独改变他自己的策略。由于 可以分配给n个参与者任意一人的概率为1， 但是，为了确保这一点，我们以下限制。非退化假设：E非负随机变量满足K边界条件，满足K边界条件，Z是一维图，值得区分它的节点和弧 Z中的节点一个点，Z *的一个极值点，也就是说，它满足（恰恰）K的边界条件。显然，Z只有有限数目的节点Zx当且仅当它是一个互补的节点同样地，Z一个弧，对应于开边缘Z*，集满足（精确）K一1的边界条件一些指定的参数变化x或y在开区间Z*一个极如果有的话从零遇到的第一个值显然，弧极值点“离开”Z*，也就是说，在Z一个节点处。，对于N 3的弧是非线性的，实际上，多线性。最初于莱姆克和豪森一个建设性的程序的想法进行从一个几乎互补节点到另一个直到互补节点被发现并产生一个平衡。 4几乎互补的路径。对于固定的m，S中任一个纯策略j，令Z（m，j）Z中几乎互补m，j的子集很明显，对于每一对（m，j）当且仅当x是Z（m，j）一个补节点，x（3）（m，j）的选择可是任意1. Z（m，j）一节点，几乎互补弧当且仅当节点证明节点X Z（m，j）恰恰满足边界条件K互补或几乎互补。如果x是互补的，那么正零是（x，y），只有该弧从xmj或yjmx出发，才是几乎互补（m，j。，x不互补，但xmj和yjm的，并且有唯一的一对（n，i），x和y是零。在这种情况下，两个圆弧只有从x开始xmj和yjm 各自参数化才是（m，j几乎互补这些都。结论证明。类似的论点表明，KZ的一个互补节点而互补的节点恰恰有属于一个Z（m，j）。几乎互补的节点（m，j）和弧一个最大连接组被称为（m，j）的路径。显然，Z（，）有限（m,j）的路径m以概率使用策略j。使成为这些参与者中的N-1人博弈。 引理2：一个均衡相当于上一个几互补的节点。 证明：令为的一个均衡。我们分两种情况讨论：或,如果，则令人博弈中的变形（2）为，所以满足关于的（3）。这可以通过定义[如果，，如果，转变为N-1人博弈。则在除了n=m的情况以外满足关于的（3）。定义，。令我们得到： （当时，等号成立）因此，由于只有时满足（3），所以中x是的几乎互补，并且x是一个节点。当N=2时，证明，暗含与lemke和howson的阐述中，相当的不同，对于，为一个均衡需要[当，，当，]的条