记Joseph Halpern“21世纪计算”大会主题演讲
转自：微软亚洲研究院的博客
http://blog.sina.com.cn/msra
如涉版权请加编辑微信iwish89联系
编者按：2011年10月26日，由微软亚洲研究院和清华大学联合举办的第13届“21世纪的计算”大会在清华大学隆重举行。本届大会以“计算之本，创新之源”（Back to Basics–Fundamental Research Fuels Innovation) 为主题，探讨计算科学基础研究在21世纪快速发展过程所发挥的重要作用。通过精彩的主题演讲，来自国内外计算机领域的大师们与中国学生及学者分享了计算科学领域的最新成果。
Joseph Halpern现任康奈尔大学计算机科学系主任、教授，美国人工智能协会(AAAI)美国计算机学会(ACM)及美国科学发展协会(AAAS) 院士。Halpern于1981年获得哈佛大学的博士学位，1982年加入IBM阿尔马登研究中心，一直到1996年；而且他还是斯坦福大学的咨询教授。他于1996年加入康奈尔大学的计算机科学系，现在是系主任。Halpern博士的研究兴趣是对知识、不确定性、安全性的推理，分布式计算，以及决策理论和游戏理论。他与他的学生Yoram Moses开创了将知识推理应用于分析分布式协议和多代理系统。他拥有6项专利，出版了两本书（Reasoning about Knowledge和Reasoning about Uncertainty）并发表了300多篇技术文章。
我们经常谈论计算科学家和物理科学家之间的联系。今天我想说一下计算科学家和社会科学家之间的联系。在过去十年，社交网络、网上拍卖等发展迅速，Google赚的所有钱都来自于拍卖和竞价。所以就需要我们具有战略的思维，也就是博弈论（Game Theory）。而博弈学和计算科学有什么联系呢？这就是我今天要谈的内容。
在博弈论中，人们专注于策略的概念，这就需要大家能够去预计这场博弈。其中最著名的策略概念就是纳什均衡（Nash Equilibrium）——纳什因此而获得诺贝尔经济学奖。每一个对手都有自己的策略，把局中所有人的策略构成一个策略组合。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡，因为每个人都不能只通过改变自己的策略而收获更多。所以直觉上看，纳什均衡是一个不动点、一个稳定状态。纳什均衡好处就是有时候能够预测人们将要做什么，并且纳什证明了每一个有限的博弈，都会有这样的现象出现。所以经济学家喜欢这个结论，他们会说，我们知道这就是最终将要发生的。
纳什均衡也有很多的问题，它常常给出不合理的答案。正如我刚刚提到的，它假设这个玩家在知道所有别人的策略的前提下做出最优的策略，但如果他以前没有碰到这些对手，没有跟他们玩过游戏，怎么知道他们会做什么。如何知道别人会做什么，这是一个背景。
即使我知道别人会怎么做，他们做过什么，但是我怎么知道他们会按照纳什均衡来做。纳什均衡假设玩家都是理智的，但我们知道人不总是理智的。所以有很多的替代性的策略概念，比如说序列均衡（sequential equilibrium）、完美均衡（perfect equilibrium）、合适均衡（proper equilibrium）。（见图1）你会看到很多相关的概念，但是没有一个是计算科学家所一致认可的。其实，计算科学在意计算的健壮性，能处理错误。而纳什均衡假设每个人都是完美的，每个人都是理智的，也没有合作。很多公司，他们都去给一个产品做招投标的话，就会有合作。纳什均衡不能处理这种情况，它至假设每一个公司不能通过改变自己的策略而收获更多，但可能他们合作而同时改变可以做得更好。另一个甚至对计算科学家更重要的是纳什均衡假设计算是免费的，有可能很难算出最优的决策，但是纳什均衡假设你可以做到最优。
图1 替代性的策略概念
纳什均衡认为每个人都非常清楚博弈的结构，每个人在每种情况之下会做什么，有哪些参赛者。但是平时生活中有很多复杂的博弈，不会知道有哪些选手会在。比如说eBay上的拍卖品，不知道还有什么其他的拍卖品。当我们进入战略性的博弈的时候，大家不知道一开始的举动。纳什均衡认为，每一个参赛选手都知道对方要做什么。可你怎么一开始就知道其他的人会怎么做呢？这些都是我和我同事一直在讨论的问题。在这次讲座里我主要讲前两个问题，有时间我简要介绍下第三个问题。
我想说的是，纳什均衡是非常好的经济学理论，但是从计算科学角度来说，还有一些问题需要考虑。我们下面来谈一下K-韧性均衡（K-resilient equilibrium）。纳什均衡处理的是但只有一个玩家改变时不能收获更多，所以如果我们说一个均衡是K韧性的，是指任意至多K个选手不能通过合作改变策略而使他们收获更多。举个例子，假设我们所有的人要不就是0，要不就是1。如果全是0就每人得到1。如果是恰好两个人玩1的话，他们会得到2，其他的人只得到0。否则的话，每一个人都得到0。如果每一个人都出0的话，这就是纳什均衡。因为如果有一个人做的不一样，那么每个人都得0。但是如果一个人和我同时出1的话，我们俩都能得到2，所以这个纳什均衡不是2-韧性均衡，因为两个人合作改变时可以受益更多。（见图2）
图2 K-韧性均衡
所以，对于纳什均衡就是说，这个K的韧性值就不太好。纳什均衡可以说是等于1的韧性均衡。1990年鲍勃·沃尔伦获得了诺贝尔奖，也考虑到了韧性均衡。但是没有人真正仔细思考这个问题。我想这种韧性和弹性，其实是非常关键的一个关联。
纳什均衡就是假定每一个人都是理智的，但实际上并不是这样。比如说某些博弈中，我们对有些人的受益假设是错误的，他们可能对整个情况不了解。可能是因为他们打游戏的时候，是通过网上来做的，他们的电脑出了问题，也就是说他们使用的工具出了问题。或者说我的母亲，她是理智的，但是她却不太会用电脑，所以她应该知道怎么做，但是却无法这样去做。还有一个例子，比如说，我教我的学生学数学，我跟他说，必须好好做家庭作业，因为占了总分数的20%，如果这种情况下，不做家庭作业的话，就是不理智的。但是每年我的课堂上，都有学生出现不理智的行为。我相信你们都是理智的，也许不是，也许你们会想，昨天晚上开了一个派对，这个派对对你们来说更加重要，他们的受益函数不是我所想的受益函数。
我们无法假设人们按照我们对理性的理解来做出理性的行为。我们必须设计出健壮的功能系统做这样的事情。你们不理智的行为，其实是经常发生的。比如说，人们在分享文件的时候，在BT上上载种子，让其他人下载。在美国这样做是犯罪的，但是仍然有很多人这样做，难道他们是不理智的吗？但是也可能他们就是非常喜欢这种方式，因为别人下载了他们的种子，他们感到非常骄傲。我们讲的类似中国的电驴，愿意在上面上传种子，为什么喜欢这样做？因为他们需要这样的骄傲感。所以，这种不理智的行为，对于很多系统奏效的话，是非常关键的因素，就是依赖于人们不理智的行为电驴能够存在。
假设有N个讨价还价的经纪人，他们都在那里待着，然后开始讨价还价，这个时候，所有的人都得到2。如果有任何一个人回家，就会得到1，这时任何留下来的人得到0。如果一部分人走，一部分人待着，待着的人就得到了0。这个博弈里有两个纳什均衡，第一个是最好的，所有人都留下，每个人得到2；第二个是所有人都回去，每个人得到1。第一个均衡里任何K个人合作改变都不能更好，所以对所有K都是韧性的，同样第二个也是。
我们说，第一个纳什均衡是脆弱的，只要一个人回家，那么剩下的几千个人都得0了。所以，所有的人都待下来，这就是K韧性，但并不健壮。为什么？只要有一个人做得不一样的话，所有的人都要遭受损失。但是我感兴趣的是健壮的均衡，我们说一个均衡是t免疫（t-immune）的是指如果均衡中好的经纪人的受益不会受到其他至多t个人的决策的影响。这里的健壮的概念是指能够容忍出错的经纪人。我们可以综合韧性和免疫的概念，得到（k,t）-健壮均衡，这意味着能容忍最多k个人的合作，以及最多t个人的错误。从而纳什均衡是（1,0）-健壮的。一般来讲，我们得不到（k,t）-健壮的均衡，但是有时在有一个可信的第三方的情况下却可以。（见图3）
图3 t免疫（t-immune）与（k,t）-健壮均衡
经济学里有所谓的调停者，调停者是指可信的第三方。比如说我们做一个拍卖的话，我们的拍卖师就是要给予合适的机制。事实上，公司并不希望揭示自己的标的。所以我们有可信的第三方，他能告诉谁是最终的赢家而不会揭示私人的信息。
有趣的是，通过第三方才能完成的能不能在没有第三方时也能完成？经济学和计算科学在寻找第三方这一方面做了很多的事情。能不能省略第三方，就是所谓的叫“空谈”博弈（Cheap Talk），谷歌和百度搜索这词的话，会得到很多的信息。一些非常知名的诺贝尔获得者，他们认为，如果使用一个调停者获得纳什均衡的话，其实也可以通过无调停者的安排获得。为什么叫“空谈”博弈，因为它就是个谈话，而且便宜，便宜的谈话。不管怎么说，没有人逼着我们做口头的承诺。而麦尔森就是建立了，你使用“空谈”博弈，就能够实现纳什均衡的结果。同时还有一个叫做多方计算，也是属于计算机科学里的。这些科学家做的是不同的，如果选择可信的第三方做能够实现的话，即使有一些坏的对手，不按规矩来做，仍然可以经过不适用第三方而实现承诺。就是自己多方进行的讨价还价，也能够达到可信第三方，调停带来的结果。
假设我们有足够多的玩家，重要的是理性玩家与不理性玩家的比例。我们看一下(k,t)-健壮的意义，然后把经济学和计算机科学结合在一起。我们就可以对纳什均衡做出一般性的结论。我们可以预计所有的对手都是理智的行为，或者说出现不理智行为的时候。我记得安迪在1987年，有关多方计算的研究的一篇论文，第一篇论文是在1981年。在这二十年中，这两个人研究的是一样的，一个是1987年的论文，一个是1989年的论文，计算机科学领域同样的研究，但是当时他们都不知道，他们同事也在做同样的工作。所以你看到在计算机科学方面，确实有很多的研究，但是并没有应用到经济学当中，比经济学自身的研究还要更深入。
我们再来看一下技术的细节，N就是总得对手的数量，K是指容忍度，或者弹性，T是指坏的选手。我们看一下如果N大于3K+3T，如果有这样的战略，通过一个斡旋者，那么它也能通过“空谈”博弈来实现，意思就是不通过第三方执行的话，只要你告诉我有第三方斡旋者的协议，就可以通过协议，不经第三方也可以执行。不需要知道理性玩家的受益函数，可以使用随机化。这个协议本身有一个运行时间的束缚。
如果N小于3K+3T，就做不成了。另外一个结果是说，假设你实际上知道每个玩家的收益函数，也知道作用多大，尤其这些参赛者都是理性的。假设我们有一个惩罚的措施，还有欺骗性，理性的玩家被抓到欺骗要被惩罚。这种情况可以实施调停，或者调解人在我们之间进行交流。再是2K+3T的情况，可以惩罚不好的代理人，可以进行2K+2T，有这样的资源和公共设施的话，能够通过我们的技术，超过2K+2T，细节并不重要。我们一直想强调的是，这个里面有问题，包括经济学感兴趣的问题，能够找到一个均衡，找到一个解决办法。但是稍微进一步延伸一点，我们可以处理强健壮，就是计算机科学非常在意，而经济学方面应该很在意。更多的假设，我们总是在计算机科学里面做假设。
我们假设有这样的密码技术，公共密钥的基础设施，是我们需要的。能够证明我们在实施调解的时候，需要的环节。真正的底线，经济方面跟科技方面结合在一起，找到一些概念，能够解决共存，包括容错方面的情况。
第一，如果我们现在非常在意计算复杂度的问题。举个例子，我给你一个很大的整数，你来猜它是素数还是不是，你可以说是，不是，或者放弃，如果猜测正确的话，给十美元，如果猜错的话，就是损失十美元，如果放弃的话，就得到一个美元。并假设你没有非常好的计算机，没有办法为你做这样的计算。
我给予你们一个很大的数字，你可能会说放弃，给我一美元吧。做这样博弈的话，就是有一个纳什均衡，那就是给予一个正确的答案，如果不给予正确的答案的话，就可以改变决策选正确的答案，如果可以得到答案的话，就有十美元。纳什均衡就错过了重要的地方，关于计算的成本。可以给予一个很大的数字，从原则来说，可以花一个小时找出数字，可以到网上查和下载，做一些测试，但可能不值得这样做，也不值得这样的成本。
所以，我们想把这个观念，关于纳什均衡进一步延伸，明智的考虑到成本的因素。这并不是全新的。我们让计算成本成为纳什均衡的一部分。回到1985年的研究当中，当时确定下来，找出一个办法，是基于这个状态的，能够按照状态数量做。我们还有一个一般性的框架，你们可以了解我们所做的，理解起来很容易。细节的注意并不是很重要。假设每一个玩家有一个类型，代表着隐私的信息，比如是否是一个懒惰的人，一个勤奋的人，都是一个人的类型，都是你们自己的信息，而别人是不知道的隐私信息。怎么做建模，每一个代理人选一个图灵机器。这个图灵机器会做一个输入，根据输入的你的类型进行计算，并带来一个输出。输出就是一个博弈的行动，在行动当中怎么做，之后会有一个回报，取决于什么？所有人的这些类型的状况，会取决于最终每个人的输入，并不是自己的输出而是最终所有的输出。回报多大，取决于你做什么，和其他对手怎么做的，获得拍卖，需要取得其他投标人的情况。
我的意思是把每一个图灵机器连起来，还有每一个类型，还有复杂性。运行图灵机器的话，在M2T，复杂性意味着什么？我们就是有意识，都有很多的解释，可以是我们的数字，也可以是我们运行时间。让图灵机器运营M2T多长时间，以及M2T占多大的空间，图灵机器有多少的复杂性和状态在里面。也可以是有多少的随机化，概率多大，最起码是比较困难的。他们同意随机化的工作。我想建议一个好的使用图灵机器，如果使用图灵机器是免费的，可能会找到一个更好的图灵机器，但是收费了，有一个搜索的收费。这时候提供一个模型，人们找到了认为比较好的东西，很难进行切换，进行转换的话，成本就很大。所以可以使用复杂性，定出很多的模式。
我们有了之后，我们可以做一个通常的纳什均衡定义，每个人有一个图灵机，你不能通过交换图灵机而受益更多，好消息是我们增加了复杂因素之后，就可以得到很重要的特性。我们还在测试的游戏当中，可以看到是安全的，因为有这样的竞争的成本，还有效用，包括运行图灵机器，从一个战略转到另外一个战略营销，以及很多的观察结果。
下面讲一下，囚徒困境的问题怎么解决？每一个，他们是相互的合作呢，看这个C，收益为33，都可以得到这样一个回报。如果其中一个协作，一个不愿意协作，就会得到惩罚，还有既成事实的情况。这个博弈最有趣的是是一个主导的战略，不管做什么，如果招认的话，会有更好的回报。如果是不招认的话，也是可以得到-5.5的回报，招认比不招认更好一些，这是难题的一个方面。
对于一个玩一百次的游戏，另外一个观点会怎么说最好的战略呢？因为我们要玩一百次，游戏只玩一次的话，就没有前途了。我们可以做成招认的，就是看99次的情况，都是招认的话，玩一百次，一开始就是相互不招认。真正的问题，如果一时的不招认，如何停止这个不招认，到第95次，停止不招认的话，想在第94开始，或者93次形成合作。现在的问题就是说，如果不招认的话，怎么往前更进一步，会有一个均衡的平等的方面，就是永远不去合作。另外还有一个，就是小的成本，看起来很容易，我们希望可以合作，就是有很多的建模方式。举个例子，首先讲一下以牙还牙的战略，一开始不招认的话，我们也会继续的不招认，只要能不招认。不招认是第一步，不管是做什么。只要能不招认，前一步还是继续不招认，如果你有不好的情况，我们也不合作了，你上一步怎么做，我也会怎么做。这是一种直观的，如果你违背的话，我会去惩罚你，以牙还牙就是以同样的方式做同样的事情。
还是图灵的机器，玩了100次之后离开，如果你知道了我会这样做，以其人之道还之其人之身。你最好的办法就是一直合作下去，直到最后一步。因为你最后一步再违背的话我来不及惩罚你。看起来很容易，是以牙换还牙的方式。我们知道响应到最后一步，再去违背。
现在的问题就是博弈，要玩长久的博弈，比如说有100个步骤。这是一个难题，大家都是最后一步违背，要计算你玩了多少次，差不多玩了100轮的时候，情况就更复杂了。如果我们要去向你进行跟踪的话，不考虑到其他的优惠折扣的话，就会进行收费，会感觉计算的成本更加的昂贵了。我们一直合作到最后一步，再去违背，跟我们一直合作到底更加简单一些。我们开始对竞争进行收费，包括技艺的收费，最好就是一直进行合作。但也不见得可以一直合作下去。
所以，我们能够考虑到竞争因素是好的，也可以解释很多的现象。总体来说，竞争考虑进去，纳什均衡就不存在了。简单的一个例子，这样的博弈，就是锤子剪子布的游戏，纳什均衡叫随机化，差不多1/3，1/3，1/3。假设可以稍微收一点费，就是要给予随机化的做法以微小的惩罚，而确定性的策略是免费的，这样就没有纳什均衡存在了。
首先，看一下没有纳什均衡，所有都是随机化的情况下。如果随机化了，不管我做什么，你都有最好的可确定的响应。很容易能够看到最确定的响应，不管提供的概率多大，都是一样的。如果我随机出，给一个锤子，或者给一个剪子，如果我最大的可能性就是锤子，那你最优的就是总是用布包锤子。如果使用随机化的战略，会决定自己最好的战略，最好的响应，不管最大的概率放在什么地方。如果1/3、1/3都是随机化的，任何想做的事情都是随机的。必须预先确定是什么样的响应，给予一个方案，就是随机化。严格来讲，所以这个游戏中确定性的策略总是严格优于随机的策略，所以随机的策略不可能是一个纳什均衡，因为我总是可以选择某个确定的策略来做的更好。但是也很容易看到每个人出一个确定策略最后也不可能是纳什均衡，所以结论就是没有纳什均衡。
也许都是按照我们预先的确定来做的，结论就没有纳什均衡的存在了，也并不太坏。理论角度来说，我们可以展示一个情况，这就是唯一的一个案例里面，没有这样的概念在里面，就是纳什均衡，是一种叫做随机化。实际上我们的结果可以能够证明在可计算战略里面有纳什均衡存在，比我们的纳什均衡更加复杂一点。在此之上想强调一个现实的地方，也许没有纳什均衡，也并不太坏。有意思的一点，就是到亚马逊上看一下，有一些书是关于讲锤子剪子布理论的书，实际上并没有战略性探讨的，都需要1/3的概率，在石头剪子布里面。每年有一个锦标赛，如果都按照1/3的概率的话，就不会获得冠军了。我们还有相当的定义，在我们博弈的理论定义上，关于安全来说，还有多方的安全，使用叫做博弈的，或者比赛的纳什均衡，能够提出多方的安全。
第三个内容，涉及到一个问题，就是过去四五年当中认为是理所当然的，是基于我们做的工作，他们想摆脱这一点。假设的博弈理论，博弈是一个常识性的，所有人都知道和理解。到底有哪些是我们可采取的行动，但是这个没有道理。比如在一次战争中，并不知道另外一方使用的武器，比如说有新的武器等。在我们的金融市场上，我们并不知道创新的产品，但是这本书在2007年出版了，在金融危机之前。
图4 缺乏意识性的例子
其实金融危机的发生主要是出现了所谓的信用违约，CDS出现的。大多数人不知道CDS到底怎么做的。我想强调的是，所谓的意识性、知晓性非常重要，如果缺乏知晓性的话，就像在自己的雷达上都看不到，这就意味着走这条路的概率非常低。不知道实际上这是一种移动，这是一种措施的话，如果能感知的话，就能采取措施，但是现在根本就不知道它的存在。因此再给大家举一个简单的例子，我们可以看到纳什均衡的一个可能，就是只要A往下走那么A,B就同时得到1，如果A穿过，则B往下走时A获得2，B获得3，B穿过时A获得0，B获得2。这里有一个均衡是A穿过，B往下走，但是如果A根本都不知道B可以往下走，那么A就肯定是往下走，就无法达到这样的均衡了。（见图4）所以，我们可以找很多的工具，找到逻辑，当大家没有意识到这种举动的时候，可能会带来什么样的效果。我们还可以更进一步，就是希望能够让大家意识到可能自己不知道什么事情。你们就可以意识到，可能有一些事情，你们是不知道的。这就是我们想要谈的内容。也就是无法计算出一个回答的时候，要知道有可能性的存在。也知道有可能把答案计算出来。我建议的方案就是所谓的计算能力，建立这种意识。这只是浅谈，当我们谈计算的时候，帮助人们做，有时候，我们有行为不规范的对手，他们企图破坏游戏规则，有一般的选手，还有超级的选手，所以我们一定要考虑到博弈理论中。知道有些选手会按照所推荐的规矩来做，但是计算系统是一个对称的系统。同时，也会探讨不对称的情况的发生。而博弈论中总是探讨对称的情形，不对称在计算机中有很大的不同。（见图5）
图5 作者建议方案
我非常高兴我们能够做出一些结论。就是如果你知道有人会偏离规矩，不遵守规矩，我们可以有模式进行模拟。我想说的就是说，经济学家和计算科学家，他们双方都可以交叉，都可以互相影响。谢谢！
责任编辑：
