logo资料库

纳什均衡的存在性与多重性.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.41M 资料格式：doc 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    第四章 纳什均衡的存在性与多重性
    4.1 纳什均衡的存在性定理
    4.1.1 纳什均衡与不动点定理
    4.1.2 纳什存在性定理及其证明
    4.1.3 其它的纳什均衡存在性定理
    第四章 纳什均衡的存在性与多重性 对于数学家来说，一个数学概念的存在性与唯一性是特别需要加以关注的。这是因 为，从形式逻辑角度看，如果某个事物并不存在，那么关于这个杜撰中的事物所给出的 任何陈述或判断都可认为是正确的或错误的，因为对于不存在的事物来说，任何关于它 的陈述或判断都不可能加以证伪。所以，倘若某个概念所对应的事物并不存在。那么， 关于这个概念所给出的研究结论都必然不存在被证伪的可能。因而根据波普尔的证伪主 义观点，这样的研究不具备科学上的意义。所以，我们在对任何新提出来的数学概念加 以系统研究之前，首先需要弄清楚所研究的对象事物是否存在。 有许多被称为伪科学的东西，它们之所以被人们认为是“伪科学”的原因就是它们 大肆谈论的东西并不存在或并未被证实其存在性。譬如，所谓的特异功能或“超灵学” 并未得到证实，而 UFO 研究迷们至今也未能拿出一件存在球外生命的证据，所以，特 异功能学或“超灵学”或“不明飞行物学”实际上都可被归入伪科学。除了存在性之外， 概念事物的唯一性也是数学家们所关心的问题。从纯理论的兴趣上看，数学家们更多地 是从审美的角度上看待概念的唯一性，但从波普尔的证伪主义哲学看，模型均衡解的唯 一性关系到模型的预测功能，从而是科学理论应基本具有的特征。我们在第二章中曾指 出，理论的预测功能是判别理论的科学性的准绳，而在第三章中，我们提出用纳什均衡 作为模型的预测结果。按照这样的逻辑，一个自然的推论就是：模型能否具有科学意义 取决于纳什均衡的唯一性。因为倘若纳什均衡不是唯一的，那么就难以根据模型对即将 出现的结果加以预测，这种不确定性对于科学理论来说是不存在的。再加上前面谈到的 存在性问题，我们可以这样说，模型能否具有科学意义取决于纳什均衡的存在性和唯一 性，因为这正是科学理论所具有的基本性质。 博弈论目前发展的情况是这样的：已经证明在非常一般的情况下，纳什均衡是存在 的，这是一个好的结果；但是，在许多情形，模型的纳什均衡解不是唯一的，这被称为 纳什均衡的多重性问题。 纳什在 1950 年代证明了纳什均衡的存在性定理，为非合作博弈打下了重要基础。 纳什的工作不仅解决了存在性问题，而且还为其后的博弈论研究提供了一整套方法论工 具，即运用不动点定理(fixed point theorem)这一强有力的数学工具进行博弈论数学分析， 这对后来的博弈论甚至数理经济学的发展产生了很大的影响。纳什均衡的多重性问题至 今仍是困扰博弈论学者的一个主要问题。为了攻克这一问题，博弈论专家已经做出了许 多贡献，如聚点均衡、相关均衡，子博弈精炼纳什均衡，颤抖手均衡，序贯均衡等概念 的提出。但不幸的是，这类努力还未使得多重均衡问题完全得到解决，许多博弈论专家 正在这一领域进行着不懈的工作。 本章将给出纳什均衡的存在性定理和讨论存在多重均衡情况下的均衡选择问题。 115
    4.1 纳什均衡的存在性定理 自从纳什(1950)首先给出存在性定理及其证明之后，许多学者又相继提出了不同表 述下的存在性定理和不同的证明方法。这里，我们介绍 Myerson(1991)给出的存在性定 理和证明。 4.1.1 纳什均衡与不动点定理 所有的存在性定理证明都采用了不动点定理，这是因为，纳什均衡的概念在数学上 就是一个不动点的概念。在给出存在性定理及其证明之前，我们先来说明不动点的概念 和给出不动点定理。 x x 什么是“不动点”呢？考虑一个方程   xf  xf 为一种“变换”，即  f 是将 x 对应为 y  YX  ，则方程   的两个元素， x ， Yy  。如果 xf x 变为自己，即 x 在  f 变换下是不变的，故称   xf  ，其中 x 为方程的解。我们将  f 视 的变换，其中 x 和 y 分别是属于集合 X 和Y  的几何意义就是：变换  f 将 x 一般地，我们可以将所有的方程都写为如下形式：   0xy 在式(4.1)两端加上一个 x ，则变为   xy 令   xf   xf  所以，一般地，方程求解的问题本质上是寻找变换的不动点问题。  的解为变换  f 的不动点。   xy (4.1)  x  x 则有 x 。  x 对于这样一种非常一般地的问题，数学家们感到十分高兴的是居然在不太严格的条 件下式(4.1)存在解，即不动点是较为广泛地存在的。 譬如，图 4.1 表明不动点是曲线  f 与 45o 线的交点。当函数  xf 定义在  1,0x 区 1,0 区间时，如果  xf 是连续的，则必然存在不动点。 间上且因变量 y   xf 的值域也为 )(xf 1 x* f(x) 45o 0 图 4.1 x* 1 [0,1]区间上的自变换函数的不动点 x 116
    那么，这种现象到底具有多大的一般性意义呢？ 数学家 Brouwer 在很久以前就注意到这一现象，他得出了如下的一般性定理，即著 名的 Brouwer 不动点定理。 定理 4.1(Brouwer……) 设  xf 是定义在集合 X 上的实函数，且   xf 如 果  xf 是 连 续 的 ，  为 一 非 空 的 有 界 凸 闭 集 ， 则 至 少 存 在 一 个   。即  xf 至少存在一个不动点[1]。 有意思的是，Brouwer 不动点定理存在很强的几何直观[2]，但其数学证明却十分艰 x 。  xf x * ， 使 X x * * 深，需要动用代数拓扑这类就是职业数学家也感到望而生畏的超级抽象数学工具[3]。 在此，我们不给出 Brouwer 不动点定理的证明。 直接用来证明纳什存在性定理的不动点定理还不是 Brouwer 不动点定理，而是角谷 静夫(Kakutani)不动点定理，而后者的证明只是前者的一个相对简单的运用。 我们所以要引用角谷静夫不动点定理，是因为在纳什均衡存在性证明中所遇到的反 应函数一般是多个因变量函数，即所谓对应(correspondence)，而角谷静夫不动点定理正 好描述的是对应的一种性质。角谷静夫不动点定理是 Brouwer 不动点定理的推广，但其 自身的证明要用到 Brouwer 不动点定理。我们在这里不打算给出这两个不动点定理的证 明，因为这类证明只是一种纯数学过程，但我们将给出纳什存在性定理的一种证明，因 为了解存在性定理的证明过程有助于我们更好地理解纳什均衡。 为了解读角谷静夫不动点定理，我们先来准备一下一些有关的数学概念。 对于任一有限集 M，我们用 RM 表示形如   的所有向量组成的集合，其中 对 M 中每一个 m，第 m 个分量 mx 是实数域 R 的一个元素。为方便计，我们也可将 RM 等价地理解为 M 到 R 上的所有函数组成的集合，这时 RM 中 x 的 m 分量 mx 也可被记为  mx 。  Mmmx x  令 S 是 RM 中的一个子集，我们有如下定义： 定义 4.1 S 是凸的(Convex)当且仅当对任意的 只要 S x  和 S y  ，则有    1 x y    这里，   , x  定义 4.2，S 是闭的(Closed)当且仅当对每个收敛的序列    jx  ，则有 S  Mmm  x   Mmm  1   1  Ry  Rx  x    y y x , y M ,   m  ,  S   S jx  有   lim j  定义 4.3，RM 中的子集 S 是开的(open)当且仅当它的补集 RM/S 是闭的。 定义 4.4，S 是有界的(bounded)当且仅当存在某个正数 K 使得对 S 中的每个元素 x 都 M 及满足 0   的，  1   Mmy  m  jx  1j ，如果对每个 j 都 有 117
     x m  K Mm  定义 4.5，一个点到集合的“对应”(correspondence) X 中的每个点 x ，  xG 是与 x 相对应的 Y 中的一个子集。 XG : Y 是任何一个规定了对 如果 X 和 Y 都是度量空间，则 X 和 Y 上的收敛和极限概念已经定义，这时有： 定义 4.6 ，一个对应 G:X→Y 是上半连续的(upper—hemicontinuous)，当且仅当对每 收 ，如果对于每个 j 有   X ，而且序列     jx   jxG     jyjx 个序列   , 敛于某个点 Xx  ，又序列     jy 1 j jx  和  jy  收敛于某个点 Yy  ，则有 1j 1j )(xGy  定理 4.2，对应 XG : Y  是上半连续的当且仅当集合  xGyXxyx   ,  ,   是集合 YX  中的一个闭子集。 . ,    故 A Zj   lim j  显然有    jx  证明：必要性。记集合 lim j  lim A  j Z j 设   jy  由上半连续性知      , xGyXxyx YX      jyjx  为 A 中一收敛序列，其中   X jx  , ,    ( ,1 ), , jXg j      lim Gjy   j    X jx ，所以 A 为 YX  中一闭子集。 充分性。假设 A 为 YX  上的一个闭子集。 如果序列       中每个  jx 和  jy 都有 , jyjx   X jx  ，      jxGjy  收敛于 x 和    且      jy jx  A 由 A 的闭性知 yx , ，即 故 G 为上半连续。 证毕！ 收敛于 y ，则  xGy  Z j j 1 1j 1j       jyjx , 收敛于 yx, 。 上半连续性是我们熟知的连续函数概念的一种推广，而函数的连续性比上半连续性 要强一些，于是有 定理 4.3，如果 ，那么   xG  xy    证明： 设序列   ,     jy     jyjx 收敛于 y 。 j 1j Xy : Y XG : Y 是一个从 X 到 Y 的连续函数，且对 X 中的每一个 X 都有 是一个点到集的上半连续对应。 1 ，且对每个 j 有   X jx  和   jxGjy     ，     jx 1j 收敛于 x ， 118
     xy y   xGy  由 y 的连续性知 故 于是 G 是上半连续的。 下面，我们将不动点概念扩充到对应的情形。 定义 4.7，一个对应 F： 角谷静夫得出如下被广泛应用的一个重要定理。 定理 4.4 （角谷不动点定理）令 S 是一个有限维向量空间中任一非空有界闭凸子集。 都是 S 的一个非 设 F： S  是任一上半连续的点到集对应，且对 S 中每个  xFx, S  的一个不动点是 S 中任一满足  xFx  的 x 。 S S 空凸子集。那么，S 中一定存在某个 x 使得 (Kakutani, 1941)  xFx  角谷不动点定理说的是对于有限维向量空间中任一非空有界闭凸子集上的上半连 续自对应来说，在一定条件下都至少存在一个不动点。角谷不动点定理及其它的一系列 相关定理的证明还可参见 Burger(1963), Franklin (1980)和 Border(1985)。数理经济学家 Scarf(1973)曾通过一种计算不动点的算法而提供了一个构造性证明，其中不动点的存在 性是由这个定理所保证的。关于角谷不动点定理的推广，可参见 Glicksberg (1952)。 4.1.2 纳什存在性定理及其证明 下面，我们来证明纳什存在性定理，该定理最早由纳什得出，这里的证明由 Myerson(1991)给出[5]。 定理 4.5 (Nash , 1950)，任何一个战略式表述的有限博弈都至少存在一个混合博弈纳 什均衡。  S 证明：令  是任—战略式表述有限博弈，即 ; uS  1 n n 显然，  n 是一个有限维向量空间的一个非空有界闭凸子集(注意  是有限博    u , 1 i i 1  弈，即局中人数和每个 iS 中的元素个数都是有限数)[6]。 任给    arg R    i  i 即  i  是局中人 i 在 i 中对其余局中人独立混合战略组合 i 的最优反应混合 iR 和任一局中人 i，令 max     i V , i i i i 战略。 S i i i  sV i    i 根据定理 3.2，  iR i , max arg   Ss  i   ,   ik k   ' , R  i i    i 1     任给 i   i V '' i i i i i  0i ，由定理 3.2 的证明过程知道，  是 iS 上所有的概率分布 i 组成的集，且使得对每一个满足 的 iS 有  i s   sV i  , ,        令,1,0  R ki i i  i 119
    ， 因 为 iS 是 有 限 集 ， 故 存 在 某 个 k 使  ,1  il  ,0 l  k ，则 i     非空。  即 i 故  iR 下面构造对应 R，它将 中的点映射于 中的子集，满足：   R     , n ，  iR  都是非空凸集，显然  R 也是非空凸集。下面我 i ,    i i i i i i i i k k  ik ik ik  ''  ik ,    sV i i '' 显然 ， i      '' , SV V    i i i       ' 1 , sV     ik ik i  k ,~ ,~  i     1 V v     i i i   ,~ ~,   ) ( R V     i i i i  i ，所以   i '' iR R  是凸的。   故 i i   根 据    , V sV     i i ik R  i   , sV  i   i i sV i  max     i i il , 是非空的。令 V ,  ik l 即 argmax  V   i  R i      i max ,    ik i  , , ik i i i i i i i i  sV i i   iR   , n 们来证明 R 是上半连续的。 由于对每一个 ,1  1  i i 假设  k 和  k 都是收敛序列 1k 1k k   , k k R     ,2,1k lim 且 k   lim k  k     , k  R~  i i i i , , k  k i  V  , 。       i 为了证明 R 是上半连续的，我们将需要证明 因为有：   k V  i i  ,2,1k 显然期望效用函数 iV 是  上的连续函数，故有  , V 因此，对于每一个i 有   R 所以 R 是 到自身上的一个上半连续对应。 根据角谷不动点定理，存在 中的某个混合战略组合使  i    i i     i  ，因此就是  的一个（混合）纳什均衡。     故,i i 。 V R R    , ,  i i i i i i i i 个i 有 证毕！ 120  R  ，即对于每一
    4.1.3 其它的纳什均衡存在性定理 在纳什存在性定理中，我们只谈及到包括混合战略均衡在内的纳什均衡存在性问 题，除此之外，我们自然会对纯战略纳什均衡的存在性感到特别的兴趣。另外，许多博 弈不一定是有限博弈，一些常见的博弈的纯战略空间通常都是无限集。在纳什定理之后， 其他研究者还得到许多进一步的结果，这些结果中与上述问题相关的有如下几个定理。 定 理 4.6(Debreu, 1952; clicksberg, 1952, Fan, 1952) 在 n 人 战 略 式 表 述 博 弈  中，如果纯战略空间 Si 是欧氏空间上的非空有界闭凸子集，支付 S  u , n , ; uS n G 函数 iu 是连续的且对 iS 是拟凹的 , 1  , i ,1 n ，则 G 存在一个纯战略纳什均衡。  x  1 一般地，当函数  xf 满足下述性质时，我们称其为凹的：   1 f x   1,0 如果当  凸的当且仅定函数-  时上面的不等式严格成立，则称  xf 为严格凹的。一个函数  xf 是  xf 是凹的；  xf 为严格凸函数当且仅当-  xf 为严格凹函数。  xf  1  1    1,0 , xx 1  xf     nR   ,   2 2 2 拟凹函数是凹函数概念的一种推广，它包括了凹函数在内的一大类函数，而这类函 数在经济学中有着广泛应用，关于拟凹函数的定义如下： 定义 4.8，函数  xf 定义在 Rn 中的子集 D 上，当且仅当  xf 满足如下性质时，  xf 是拟凹的：  x  1   1 x   f 显然，凹函数是拟凹的，但反过来并不成立，即拟凹函数不一定是凹函数。在图 3.2  [0,1] min  2   xf 1  ,  xf  2  中，函数  xf 是拟凹的，但不是凹的。 y  xf 0 x1 x2 x 图 4.2 不是凹函数的拟凹函数 在定理 4.6 中，与定理 4.5 相比，我们增强了对支付函数 iu 性质的假设，于是获得 更进一步的结论，即保证了存在的纳什均衡还是纯战略博弈纳什均衡。在有限博弈场合， 即使纯战略空间可能是非凸的，支付函数也可能是非连续的，但混合战略空间是欧氏空 间上的非空有界闭凸集，期望支付函数是连续的，拟凹的。当纯战略空间本身是欧氏空 121
    间上一个非空的，闭的，有界的凸集且支付函数在纯战略空间上是连续的，拟凹的时， 就没有必要引入混合战略了。 如果放松定理 4.6 中关于支付函数的拟凹性假设，则只能保证混合战略均衡的存在 性，这就是下面的定理 4.7。 定理 4.7 (Glicksberg, 1952) ，在 n 人战略式表述博弈  S  中，如 果纯战略空间 iS 是欧氏空间上一个非空有界闭凸集，支付函数 iu 是连续的，则 G 存在 一个混合战略纳什均衡。 ; uS 1 u n ,  ,  u G 1 122
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料