Math 版 (精华区)

发信人: freely (* 星星风铃 *), 信区: Math
标  题: Nash演讲稿中文版(转载)
发信站: 哈工大紫丁香 (2002年09月04日23:53:07 星期三), 站内信件

【 以下文字转载自 Management 讨论区 】
【 原文由 freely 所发表 】
发信人: Serenading (吉他好难学。。。), 信区: Mathematics
标  题: Nash演讲稿中文版
发信站: 北大未名站 (2002年09月04日22:47:04 星期三), 转信

                              通过代理来研究博弈中的合作


    在一九六六年的“科学夏令营”上，我曾经从重
复与进化策略的角度，针对那些致力于合作适应的自
然进化研究的理论生物学家对“  徒困境”博弈的应
用作了一个演讲。自此之后，我更多地思考这样一个
理念，即把博弈看作重复博拜来研究。由此，我得到
了解决如何消除在联盟以及联盟形成中所涉及的“言
辞上的”复杂性的思路。
    原则上说，联盟以及冯·诺依曼和摩根斯坦恩在
《博弈论与经济行为》中考虑的联盟，可以通过类似
罗马法中的契约来实现。由于契约能够并且理应用语
言表达出来，契约本质上是一个“语言”的事物。
    我的想法是，在重复博弈的角度，参与者对他们
之中的“代理关系”或“代理人”的选择具有投票权。
这样，在博弈的第一阶段，

参与者（比如，参与者A）可以选择是否接受参与者
B作为他的代理人。其结果可能导致联盟（A，B）的
形成（就象一个B作主席的委员会）， 并且形成中不
需要A与B之间的任何言语的过程。进一步，这个过
程也适用于下一阶段联盟的形成。因为如果进行下一
阶段的选举，参与者B可以作为联盟（A，B）的代理
人接受参与者C的代理关系，从而C就成为代表联盟
  （A，B，C）的代理人。
      通过这种方式，如果广义的“代理关系”可以由
选举产生，“大联盟”总可以形成（对于有限参与者的
博弈）；这样的结果是，“ Pareto效率”的必要条件将
得到满足。
                           代理关系进一步讨论
       联盟形成、解散以及重新形成的方式不是无限
的，我们必须制定一个特定的选举程序，以构成由被
转化的最初博弈的参与者参与的非合作形式博拜的基
础。对重复博弈的研究，我们能够制定一个选举过程，
使得选举出的代理人可以完全独立决策，

并且在每个特定的博弈中，代理人一经选举不得改变。
（当然，因为博弈是重复的，选举结果会发生变化）。
        我们需要设定一套规则，以便使在每一选举阶段
中仍保持独立的参与者（没有接受其他参与者作为自
己的代理人）均可以选择其他参与者作为可接受的代
理人。这些规则产生的结果理应是收敛的，则n个参
与者的博弈最多需要( n-1)阶段的选举。
    选举规则需要解决选举中可能出现的“僵局”问
题，即在A选择B作为代理人的同时，B也选择A作
为代理人。对于哪些选举规则能够以最优的方式处理
此类情形，我们事先并不是非常清晰。我们已经研究
过多种情况。近来我们在应用特定博弈模型进行计算
中发现，当选举不能形成任何的代理权，允许重新进
行选举可能是一个解决的方法。这个发现使我们认识
到，在任何选举阶段中，能够使至多一个代理人被选
中的选举规则是最适宜的（另外，计算的实际结果似
乎暗示：这种选举规则是“渐进无偏见的”。因为“成
功选举”的概率趋向于1时，“同时选举”的概率趋向
于0）。

    对于一般的CF博弈，如果博弈要求所有联盟的
收益必须通过其代理人的行为决策来实现，该代理人
有权代表联盟的所有成员，那么由此形成的“代理博
弈”仍然同最初的博弈具有同样的可导出的特征函数。
本质上说，联盟具有同以前一样的潜能，然而，在规
范的意义上，要挖掘这些潜能，联盟的成员需要共同
策划一个可操作程序，用以成功选举出代理人，并且
最终选出的能够代表联盟全体成员的代理人的行动是
联盟最终的有效行动。
                            模型的目前形式
       我们已经发现，在两人或者三人的博弈中应用此
类模型，有可能找到“讨价还价均衡”。出现的一些问
题和复杂的细节使我们关注模型的精炼。
    理想的情况是，能够开发一个类似于应用在天气
预报中的数学方法（用偏微分方程描述气流的研究
等）。在注重物质利益商业层面，这种模型可以自然地应用
于公司合并的具体交易细节（就象最近的Pfizer公司
和 Pharmacia公司的合并）。或者，我们希望能够由此
更深层次的认识已经存在的价值与价值评估概念，例
如，Shapley值、核。
    联系应用代理模型研究联盟和合作的方法，本研
究将涉及以下内容：关于重复博弈中的参与者如何对
自己喜爱和不喜爱的、其他参与者的行为出“反应”
的各种模型；研究关于参与者如何选择能够规范他们
反应行为的“需求”的各种概念。例如，一个类似的
研究领域是，理论生物学家在PD类型的重复博弈下
研究合作进化的可能性。该研究发现了不同类型的有
利于形成合作的“反应本能”。除了最简单“针锋相对”
的本能反应之外，还存在更复杂的变型。这些变型需
要更多的记忆（关于最近一系列重复博弈的经验）。代
理选举模型的一个类似的情形是，参与者被允许做出
的“需求”可能或多或少地被精巧构造。
    因为去年的简单模型中用以减少方程个数和变量
个数的做法似乎产生了一些问题，我现在正在考虑一
个更为复杂的模型（三个参与者的博弈模型）。

               去年模型和当前工作的公共特征
    这些模型均有一个产生代理权的选举程序。较早
的模型中，在第一阶段选举生效之后，采用一个简单
的程序将剩余的活跃参与者数量减少至2个。我们使
用了一类简单自然的讨价还价机制，通过这个机制，
剩余参与者竞争选择的效用配置是合理的。然而，这
种简化方法并不是直接遵循象博弈开始时所有参与者
进行同一类的相互博弈产生代理关系的那些基本概念。
    两个版本的模型均从第一阶段的选举开始，在第
一阶段的选举中，三个参与者都可以投票（或者选择）
其他任一个参与者作为自己的代理人。两个版本中的
投票或选择行为（象在重复博弈中反复采用的）均用
数字来描述。这些数字能有效表示所涉及的行为或者
机会出现时采取行动的概率。
      这样我们就有一个包含六个数字的矩阵（和三个“隐
含数字”），描述为：
       参与者1          参与者2               参与者3
      a1f2＆ a1f3      a2f1＆ a2f3        a3f1＆ a3f2

       这些数字描述了每一个特定投票的概率。例如，a2f1
是参与者2（在第一阶段博弈中）选择参与者1作为
自己授权代理人（就像“代理权”）的概率，也就是“ P2
接受  P1的比率”。
    其他aifj形式的变量具有类似的含义。有时可以
利用另一类方便的符号，例如，n3=1-a3f1-a3f2表示参
与者3既没有接受参与者1也没有接受参与者2作为
其代理的概率；或者表示参与者3没有投票或投票给
自己的概率。
      既然三个参与者同时作出他们的第一次投票，就可能
产生不同的结果。我们制定一个简化过程的规则，使
投票产生一个合适的结果。如果在第一次投票机会中
可接受的投票数目超过1个，我们从中随机的选择一
个作为结果。

        那么，选举只有两种结果：（1）其中一个参与者选择
其他参与者作为自己的代理人；（2）没有任何一个参
与者选择其他参与者作为代理人代表他的利益。
       我们又引入一个约定，如果参与者没有达成一致
以至于没有选出任何代理关系，第一阶段选举在某一
概率下可以重复进行。在前一个模型中也用到了这个
思想。参与者被赋予再次投票的概率设为(1-e4)或
(1-E4)， 我们希望研究的是当e4趋向于0的计算结
果。（我们发现，在较早的模型中，当的趋向于0时，
象a1f2所表示概率也趋向于0，但是这样代理人产生
的概率将增大。因为不断地给联盟的基本行动（选举
代理）提供“第二次机会”）。
                       代理选举的第二个阶段
    在我们以前的模型中，一个代理关系选出之后，
只有两个参与者保持活跃，根据剩下的这两个参与者
的指定效用的损益，已经选为代理人的参与者选择两
个数，而余下的单个人选择一个数字。

       当前模型的研究方法是，在某种意义上，更多的关于
代理关系思想的“传统”和所有一般合作的可能性简
化为最终选举一个“一般性的代理人”。这样当一个参
与者已经接受另一个参与者作为他的代理人，那么剩
下两个自由行动的参与者，而适合“大联盟”的合作
层次没有实现直至他们中的一个被另一个选为代理
人。
    但是如果最后的代理关系选举失败，那我们可以
允许现有的代理关系去使用由两个参与者形成的2人
联盟的资源。（在一个简单的情形，正如我们所考虑的，
这会导致简单的使用由一对参与者形成的联盟的特征
函数决定的资源）。
    类似的想法适用于选举的第一阶段，我们允许第
二阶段可以重复，其概率为(1-e5)，如果没有一方推举
另一方有代理资格，我们的思路是要研究当e5渐进趋
近于0时极限形式的结果。
    一旦一个“一般性代理”选出来，那么他／她有特
权能够分配收益，将所有可获得的收益效用资源分配
给包括他自己在内的所有参与者。我们的模型将整个
可获得的资源简化为1，这也对应于博弈的Pareto边
界。
    每一个参与者有四种可能的方式被选为最终的代
理人。两个参与者之一可能一开始就选举他，这有两
种情形；或者其他两个参与者有两种方式产生最初联
盟，任一种方式接下来都是他被选为两人联盟的代理
人。作为最终的代理人他要在一个2维空间中选择一
个点来决定他的可达的Pareto效用配置。
    这样每个参与者有8个维度，共3个参与者，当
他们在被选为“最终代理人”之后，指定的效用配置
就总共有24个选择维度。在39个“策略变量”中24
个选择变量被看作个人的目标和参与者个人最优选
择。
    其他15个参与者的策略选择的维度对应于他们
与反应性行为（在重复博弈中）相关联的选项。参与
者由他们反应性策略选择所影响或控制的行为一般是他们的
“接受行为”。

                       博弃的第三步：效用的配置
    当代理选举的前两步完成之后，最初的参与者之
一已经成为所有人的代理，并由他“配置”收益。假
定配置是Pareto有效的，由此我们假设他／她指定三个
特定的非负数，其和为 1。这是由对其他参与者（目
前是两个人）的分配数量决定的。这样对所有的参与
者总共就有24种可选的策略。
    例如，在UjBijRk型的情形，数字i是固定的，
即参与者 i首先由参与者j选举，然后由参与者k选举；
参与者i选择分配ujbijrk给j（分配ukbijrk给参与者
k，但是这是另外一种配置策略的情形)。
    例如，u1b3r21 是由参与者3决定分配给参与者1
的数量，参与者3由参与者2选出，而参与者2在第
一轮由参与者1选出。而u2b3r21 是分配给参与者2
的（他在选举的过程中处于一个不同的地位）。参与者
3将u3b3r21 分配给自己，但是这在我们  42个变量和
42个方程的系统中被化简，因为其他两个参与者的配
置与参与者3的配置之间有个简单的关系。这样就有了
24个“效用配置”的变量（分别对应着参与者选择的策略
人并且分为4类：UjBijRk，UkBijRk，UjBiRjk和 UkBiRjk。

                           博弃第二阶段的“需求”与行为
    当“第二阶段”到来的时候，一个参与者成为了
代理，另一个参与者根据这种代理关系被代表，而第
三个参与者仍然单独的。
    假设现在参与者1代表参与者2，而参与者3是
单独的。我们简单的将   a12f3记为a12，也就是现在参
与者1选择投票给3作为最终代理人的概率。（这在一
个可重复的博弈中是一个可以观察到的行为。）并且我
们用af12表示参与者3愿意投票接受参与者1（他已
经代表参与者2了）作为最后的代理人。这种分类导
致12个数，每种6个。
    然而这12个数不是所有涉及的参与者的“策略”
选择，而是我们设定的他们由需求规范的“反应行为”
所决定的，这是参与者真正的策略选择。
    例如，a12（或 a12f3）指定为 A 12/(1+A12)，其
中A12是一个正数。

这使得a12是一个小于1的正数。而控制a12的A12
是由A12=Exp[(u1b3r12-d12)/e3]得到。这里e3，或者“E3”，
它在我们研究模型的均衡最终变得非常小。由
于非常小，使得A12在d12和u1b3r12相对变化时变
化剧烈。这里的数字“ d12”是参与者1根据环境作出
的“策略性”“需求”选择，他可以投票接受参与者3
作为一般性（最终）的代理人和等着希望参与者3会
接受他作为最终代理人（！）。 这个公式所要考虑的仅
仅是当参与者1已经被选出代表参与者2，即 ul1b3r12
的情形下，参与者3成为一般性代理时，参与者1的
预期收益或支付。
    这里有6个如 d12（它控制着a12）需求策略数字。
同样，这里也有6个非常类似的策略选择，如df23控
制着af3（或a1f23）。所以“df23”是参与者1的一
种选择，因为他控制a1f23也即接受在博弈的第二阶
段作为独立人的参与者1作为参与者2的代理人的概
率，在参与者2已经代表参与者3前提下。
    这样我们有
af23=AF23/(1+AF23)或a1f23=AIF23/(1+A1F23)
其中AF23=Exp[(u1b23r1-df23)/e3]被指定用于控制
（策略性）需求选择的可接受行为。或者用一个更长
的记号：A1F23=Exp[(u1b23r1-d1f23)/e3] 。
                   第一阶段的需求和可接受的行为
    在选举的第一个阶段，即三个参与者都是独立的
时候，我们通常已经做了一个选择，即如何将选举行
为和“需求”联系起来。作出的选择并不是绝对自由
随意的，有时还更加复杂，也需要进行恰当的考虑。
每一个参与者的投票都有选择，例如参与者2，可以
选择投票给参与者1（行为的概率为a2fl），也可以选
择投票给参与者3（行为的概率为a2f3），或者票都不
投给他们（描述为n2=1-a2f1-a2f3）。这个模型，和以
前研究的模型一样，将这些行为描述的数字（或概率）
与一个单独的需求参数相联系，即d2，这涉及参与者
2在博弈的第一阶段所有的策略选择。我们在模型中
假定正数A2f1和 A2f3都是给定的（有d2控制）并
且a2fj=A2fj/(1+A2f1+A2f3)，其中j为1或3。
    A2fj假定为 Exp[(q2j－d2)/e3]，其中 q2j 为参与者
在假定博弈进行到第二阶段，且他成为参与者j的代理
人的前提下计算的期望收益。这样参与者2策略性选
择需求  d2，无论在第二阶段是（q21），即参与者1成
为代表他的代理人，还是（q23），即参与者3成为代表
他的代理人，d2 都可以解释为参与者2他／她应该对期
望收益的要求。
    那么，三个策略变量   d1，d2和 d3控制   6个行为
的概率a1f2，a1f3，a2f1，a2f3，a3f1以及a3f2，它们
完整的描述了真实的（可观察到的）第一阶段参与者
的行为。
                           模型中的变量
    在模型中我们总共有39个“策略”变量，15个
“需求”变量和24个“效用配置”的选择。但是我们
可以通过相关的控制行为概率，如 a23或a1f2和 a1f3，
替换所有的需求变量，如   d23或d1。这样我们可以得
到简化的方程组，绝大部分指数类函数都消除了。
    实际中必须考虑的一个问题是如何找到这些方程
的真实数值解。这是在以前简单模型中就遇到的问题，
然而在目前的模型中，工作还远未完成。不过，在NSF
项目资助（AK）的帮助下，模型已经到了一个推导出
可以解的实际方程的程度（即处于一种好的形式，可
以应用计算机软件进行研究）。进一步，首先对完全对
称博弈然后对一般性的非对称博弈进行的一些数值计
算表明，该模型如预期的那样。至少对2个参与者的
联盟这样的小数据是这样的。但是，目前还不能对解
的渐进形式或对计算的结果妄加评论，这一切都还为
时尚早。
     当对各种形式的非对称博弈进行了足够的计算，
那么通过计算出的收益，推断出的隐含值可以给出与
很多相关概念，如核等，相提并论的数字。
     剩下来的挑战是如何真正地发现足够多的、由均
衡模型的数值解揭示的、有指导意义的结果。
                         结果比较
     模型的设计使得博弈可以分类，其中Shapley值和核
给出博弈不同的“评估”。这些评估，例如“仲裁程序”中所用的指南，是

好是坏（如果这些比较从任何角度都是有效的）？当然，
任何其他可以用于“评价”的规则，都能成为对这些
或其他评价方法的进行比较的一个基础。
    如同以前的模型一样，我们的建模也有三个参数
描述两个参与者联盟可获取的资源。如果它们是小的
正数，例如小于1/3，尽管Shapley值在对博弈评价时
给予它们适度的权重，但标准的核估计容易忽视它们。
    我们以前的模型对这些情形给出了数值结果：根
据两个“E”的比率(相比前面描述的“e3”）这种
评价可以是“上Shapley式”（与处于{1/3，1/3，1/3}
的核相比）或者是“下Shapley式”。
    最后，我做个总结，对于“需求”选择效果的不
规则平滑化中用到的“模糊性”需要一个更加一致的
概念。否则，如同2人模型早期研究所证实的，如果
一个参与者有“精明”的需求，而另一个可能有“迟
钝”的需求，这样有精明需求的参与者会变成一个“精
明”的讨价还价者并会在计算出的博弈结果中占据
优势！


模糊性的引入是出于数学上的考虑，可使得光滑函数
的推导能够计算。但是，在一定的环境下，“不平衡”
的模糊性会“损害”博拜评价的客观性。
                             相关的研究
    这个项目的工作，主要是寻求利用“代理”的概
念，通过简化为非合作博弈均衡的考虑，从而成功的
研究合作博弈，这已经引导我对其他一些问题进行研
究。
    其中之一是核的可计算性，因为如果研究各种各
样的博弈例子，并且如果它们都定义了古典的核和
Shapley值，那么仅对于数值结果的比较，最好有一种
快速的方法找到形成核向量的数字。对我来说，可能
通过蒙特卡罗类型的程序方法，在一个高度近似的水
平，利用随机干扰发现核分量的数值。
    我曾试着用MATHEMATICA编程，发现博弈经
常可以用合理的数字来定义，而一个对真实核的高度
近似可以导致通过找到用于近似的这些简单的合理数
字来发现真实的答案。

      在逐次逼进的方法中，核的确切定义是比较生成
近似向量的各种随机扰动优劣的评判标准的基础。
      后来，我从Sven Klauke在Bielefeld的工作，了
解到这一类的方法已经是有效C＋十编程的基础，并且
已经开发出一套有效的程序，它采用的方法就是将问
题简化为“线性规划”问题。
      在出席去年的 Stony Brook大会之后，我考虑一个
Harsanyi（在1960年左右）计算的一个与发展合作博
奕中的一般解概念有关的特征函数。当时，我认识到
如果这个方法用于改变三人博拜的解释，并且如果对
（常数和）博弈计算出核，那么这将导致与博弈的
Shapley值相同的向量（而它本身不会由于“ Harsanyi
特征函数”而改变）。
     另一方面，如果我们考虑类似的四人博弈，在通
过Harsanyi特征函数转变联盟值的信息之后核计算
一般不会与Shapley值向量相一致。


对我而言，目前恰巧遇到和 1928年 Von Neumann
的相类似的情形3人合作博率在一定程度上可以评
价，但4人博拜从评估的角度看，其困难程度不是
一个级别。

--

--

           Keep Running
   
                      freely


※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 172.16.8.48]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 172.16.8.48]