基于连续同伦的多方对策之N...sh均衡点的机械化求解方法_熊贝贝.pdf

（）（，），基于连续同伦的多方对策之均衡点的机械化求解方法熊贝 贝杨争 峰武斌曾振柄（湖北大学数学与统计学 学院，武汉 ；华东师范大学软件工程学院，上海 ；上海财经大学浙江学院，金华；中国科学院成都 计 算机 应用研究所，成都）摘 要定理证明非合 作人矩阵对策一定有混合 平衡解，现有文献多讨论时混合 平衡解的求法，一般用优化或逼近的方法文章给出了一种机械化求解方法，通过构造非合 作多人矩阵对策的混合 平衡局势所 满足的多项式方程组，应用方程组求解 软 件由此可直接求出多人对策的问题的各 种混合 平衡解关键词定理，混合 平衡策 略，数学机械化，多项式方程，连续同伦方法（）主题分类号，（，；，；，；，），国家自然科学基金（）资助课题收稿日期：，收到修改稿日期：通信作者：武斌，：编 委：袁 春明熊贝 贝等：基于连续同伦的多方对策之均衡点的机槭化求解方法 ，引言和预备知识对策和博弈是一个古老的问题，例 如我国战国时期的“齐王赛马对策论的科学研究，源于近 年前 等人的工作其中，多方 对策（也称多人对策）是国际国内经济政治中经常出现的一个实 际问题，参见文献其数学模型中，假 设 有个 行为 主体（即局中人）参与博弈，每个局中人的有 有限多个策 略用氐表示 第个局中人的策 略集合（？），则 笛卡尔积负的就 是方 对策的所有局势的集合设函数：，（，？，？）（，？），是局中人，的收益函数（文献中也称为赢得函数）假设（氐）屯则每个函数払可以看成为一个山实张量上面定义的方 对策可记为（，）；（，）；（两人对策中，收益函数用矩阵表示，最基本的模型是零和对策，即场等于零矩阵的情况，通常简单表示为？而的多方对策的研究中，一般假定对策不是 零和博弈，即，）在 最简单的多方对策中，还假设 各局中人在同一时刻选择策 略，而且不允 许与其 他局中人订立联盟，称之 为 非合 作对策多人非合作对策中一个重要的研究问题是其平衡局势的存在性一个局势（，）负的称为是一个纯策 略意义下的平衡局势，如果 这个局势对于每一个局中人都是有利的，即对于每一个，？，下面的不等式 成立（），）（）：，：，），：即，对于 任一局中人，若其 他局中人不改变策 略，则当前的局势对于此局中人来 说是最优的图显示的是一个三方对策，三个局中人的纯策 略集分别为，负氏高是一个格点经过局势（，）可作三条直线，分别平行于：，轴方向，与私的交集分另为（，），（，），（，）设历（：，）（，）：？分别是局中人，的收益张量，则按照 系统科学与数学卷平衡局势的定义，局势（，）是这 个三方对策的平？衡点，当且仅当私（，）分别是函数迅丑（？，：，场私迅供？（，）的最大值闬贫方对策錄，个例子，局中人，分别有个纯策略二个势乎集旮，都 包 含（，），其所在直线分别平行于？轴方向（，（，）两人对策和 多人对策可能有多个平衡局势：也可能没 有纯策略意义下的衡局势引入混合对策的概念设第（？）个局中人的纯策略 集为民，成，在不合作对策中按照概率），使用这些策略，其中，之）令？；表示妒中 的单形：（，；）？），？，则；中的每一个点对应着混合对策的一个局势局中人（？）在这一局势下的 收益的数学期望是（，（），（）：）（，）为记号简便，下面 设？，？，以及（，：？，）？，），（，）并直接用払（）表示瓦这 时，一个混合局势；讲十净称为一个衡局势（或衡点），如果下面的不等式组成立（，），（，），），（），）（，）熊贝 贝等：基于连续同伦的多方对策之均衡点的机械化求解方法 如果平衡局势（，）是点集，的内点，则称它是一个完全混合平衡局势（）对于二人零和决策，设局中人的收益矩阵 为则两个局中人在混合决策下的收益函数可以写成二次型（，），）（，），），），），（）（，？，）（，），）对局中人，最小 收益期望值（最 差情况下的最 有利者）分别是，（）根据的如下 最小最大定理（，见文 献）：如果是紧致凸集，函数：？关于第一个 分董￥是连 续凸函数，关于第二个 分是连 续凹函数，那么（，）（，），；立即可以证明，对任意矩阵和二人零和对策（，），（，）；，总有满足（）从而列（），巧（），即局势是？私，氏；，在混合意义下的平 衡局势（见）上面结论保证了二人零和矩阵对策的混合平 衡局势的存在性给定 局中人的收益 矩阵（叫），文献将 对策？知 祝乂的混合平 衡局势的计算问题转化为如下的对偶 线性规划问题的求解原问题：，：对偶问题：，办，非零和的二人和 多人（非合 作）对策问题，世纪年代，证明如下定理，定理非合 作（）人对策（，），（氏，），（迅，丑，），其中，一定存在混合策 略意义下的平 衡局势，即存在 系统科学与数学卷使不等式组，）之邮，心，），（，），、？（，）（，），对所有（，；成立应用紧凸集上的不动点定理证明了混合平均局势的存在性理论上可以通过所构造的压 缩映像和数 值 计算求解定理所 保证的混合平 衡局势可 参见文 献，有大量文 献（参见文 献，）研究二人非合 作对策问题？的混合平衡点 的直 接计算问题以下我们简要解 释这一问题可以转化为双线性不等式组的求解问题设卜（），（）是矩阵此时，定理的结论可表述为：存在（，），（，；）；，使 得 下面的不等式（，）（，）（）对一切；（，；）成立，同时 不等式（，），），（）对一切，成立注意到对于 任意确 定的，），（，），一次不等式（），（）对一切（，）（，切）丨成立，当旦仅当它们在 单形，的所有 顶点处 成立换言之，（），（）的正确性等价于，），（“，）是否满足方程，以及下面的十个不等式（，念，（丄），这样，双矩阵对策问题的混合平衡局势的计算，转化为双线性不等式组的求解问题例 如，对于下面双矩阵对策（）有（），（）（）（）？，熊贝 贝等：基于连续同伦的多方对策之均衡点的机槭化求解方法）因此，混合平 衡局势（的，的），（，）由如下方程和不等式组确 定十，（，），（：）（，），（：）：（，），（：），（，）：，）（，）：，）（，）：令！，则这个不等式组可以转化为，（，）（，），（，），（，），（，），（，），（，）局中人在三个 平衡局势下的收益分别为，？注意到，上面这个例子中，两个局中人在两个纯策 略平衡局势的收益值，都大于 完全混合平衡局势的收益，但由于 局中人在选择策 略前不允 许协商，所以他们不 能保证达到（，），（，）或（，），（，）文献，研究了一些特殊的双矩阵（例 如反对称阵）对策存在完全混合平衡局势的充要条 件就我们所知，文 献中关于的非合 作多人对策，直接 计算其混合平 衡局势的工作尚不多年，文献卩研究了三人对策？（，），（乳的，），（，）在三个局中人有或个纯策 略（即，为或张量）情况下的混合平衡局势的计算方法设（叫开），（讲），（）？用和软件求解以下三个非线性规划问题（）（）（），（）（）（），易验证，这个不等式组的解 是，对应得到原双矩阵对策的三个混合平衡局势 系统科学与数学卷其约束条件均为以下的不等式约束，、，）二，工，？，；，？根 据定理，的混合平衡局势满足约束条 件（）然而，由于平 衡局势可能 不唯一，数值优化 軟件一般不 能 求出问题的所有局部极值，这 使 得三个非线性规划问题在同一约束条 件（）的（局部）极 值点可能 不同，因此，用非线性规划优化 軟件求解 对策问题的平 衡局势，难以直接得到原问题的解其 它通过 迭 代求 混合平衡局势的方 法，也存在不 能 求出所有解的困难本文第节介绍一种新的方法，把多方不合 作 矩阵对策的完全混合平衡局势的求解，转换为求解一组代数 方程组的 实根的问题这样，利用目前业已成熟的方程数值軟件（例 如连续同伦 算法），或更为精密但 计算 董较大的数 值 符 号混合计算軟件，就可以得到一个 对策的所有完全混合平衡局势我们将给出一个三方 对策实例和一个四方对策的 实例第节简要讨论部分局中人的最优策 略是部分混合策 略的平 衡局势的计算方法第节是一个简要总结，同时我们将 提出两个进一步研究的问题完全混合平衡局势的方程根据定义，一个局势（，），？叫十十？称为 完全混合局势，如果，分别是单形，的内点本节我们证明，（？）方矩阵对策的完全混合平衡局势，满足一组代数方程，其中有个是线性 方程，其余？个是次方程方程组的变量个数 是：定理设（，（奶，奶，坊），（斗勿，），之）是方非合 作 矩阵对策？（，），（私，的，），（，）的一个混合平 衡局势，？，（是维张量，满足，？，？，则尤，巧，识，满足以下方程组？：，之，（）熊贝 贝等：基于连续同伦的多方对策之均衡点的机械化求解方法？：（）勿？：？：（）定理的证明依赖于下面的引理引理设，心）：？是线性函数，是一单形，其顶点为（，？，），（，？，），？，（，？，）若的一内点（，）满足，），）（），？，（，）（），（）则！）（）证如果是常值函数，则结论已经成立故假 设不是常数显然中的任何一点（，抑）满足（，？，？）由于是线性映射，有（，）（）设），），？，（），则（，）（）（）？）？因此（，）（），？，（），（，）设（，）是的内点，即；，如果引理的结论）不 成立，则这一点满足（，）（）？），），），与（）矛盾引理得证 系统科学与数学定 理的证明设（：，）是局中人的收益函数，则此函数可以写成其中的求和 范围是若（，），（；，）构 成？的混合平均局势，则（，）中代入此混合平均局势中的坐标分量，视为：（，）的线性函数，坐标值的，；，：对于一切变量（，）满足 不等式（，；）（，？，；），从而，；）；），；）（；），这 里凡，是的顶点根据引理即得，）（，），）此即定理结论中的公式（）完全相同的方法可证明公式（），（）定理得证下面以一个三方 对策为例演示上面的混合平 衡 方程构造 方 法设局中人，各 有个纯策 略，于是他们 的收益函数，都 可以用一个张量来表示为节省 空间，我们将，按照格 式安 排在同一个分块矩阵里，其中；（，）是一个实数矩阵我们用随机数发生器生成，的元素，为避免计算误差，取所有元素为整数例 如，应用定理，由上面这个张量 可构造如下个二次方程注 意上面矩阵中黑 色 加粗 数字 在熊贝 贝等：基于连续同伦的多方对策之均衡点的机槭化求解方法 多项式中的相应位置？，；！；！；？十￥？十？十￥加上如下三个线性 方程，讥十奶十，构 成该三方对策的完全混合平衡局势方程组同伦方 法能够 可靠 而旦髙 效计算多项式方程组的数 值解基于同伦的多项式方程组求解主要思想是利用多项式系统的结构以及解的数目，构造一个初 始系统，通过跟踪解的路径从而 能够快速求解多项式方程组的解目前，基于同伦方法的多项式方程组求解已经有若千个相对应的工具，如，和在 这 里我们采用工具求解多项式方程组本文采用连 续同伦方法的主要 程序见 附录在配置（）（）的机器上，用了 秒，求出上述 方程组在（，）中有如下解，：，別 ，之 二注 意，并非 任意 随机生成的三方 对策都 有完全混合平 衡局势下面这个实例，构造其完全混合平 衡局势方程之后，用连 续同伦 算法 未找 到（，）中的 实零点系统科学与数学卷下面是一个四方 对策的例子每个局中人有个纯策 略因此局中人，的收益函数都是张董本文约定用分块矩阵表示，格 式 如下乂乂）乂乂 乂 乂乂 乂 其中每个矩阵，是一个数字 矩阵 用隨机数发生器生成局中人，的收益张，尽实例 如下其中的元素取到之间的整数丄丄丄熊贝 贝等：基于连续同伦的多方对策之均衡点的机械化求解方法这一非合 作四方矩阵对策的变量为（；，；，；），（，奶，），（別，），（，），所有分量 在，取值，满足，根据定理，由以上张量，生成个三次方程，每个方程最多有个单项式下面给出第一个方程（）？（）？（）系统科学与数学卷其中，之，之这 些三次方程与四个线性方程联立，用软件求解，得到（，）中的如下实根，之 ，之，之 ，部分混合平衡局势在定理（定理）中，混合平 衡局势，）的存在范围是，定理建立了完全混合平 衡局势（要求的每个坐标分量严格大于零的局势）满足的代数 方程组若应用高次方程组数 值求根软件求解（），（），（）和线性 方程，坊，？，（）所构 成的方程组，没有 得到每个坐