1700497116
1700497117
然而，计算机科学把这个故事复杂化了。广义而言，数学研究的对象是真理；计算机科学研究的对象是复杂性。正如我们所看到的，如果一个问题是难以解决的，那么要找到问题的解决办法就是不够的。
1700497118
1700497119
在博弈论环境中，知道均衡存在并不会告诉我们它是什么，或者如何实现它。正如加州大学伯克利分校的计算机科学家克里斯托斯·帕帕迪米特里欧所写，博弈论“预测了代理人的均衡行为，又通常不考虑到这样一种状态实现的方式，而这正是计算机科学家最应该关心的问题。斯坦福大学的蒂姆·拉夫加登也认为纳什提出的证明均衡永远存在的证据不充分。“好吧，”他说，“但我们是计算机科学家，对吧？”给我们一些可以用的东西。不要只告诉我它在那里，告诉我怎么找到它。因此，博弈论最初的领域是基于算法的博弈论，也就是说，对游戏理论上的理想策略的研究成为机器（和人）如何为游戏制定策略的研究。
1700497120
1700497121
事实证明，问太多关于纳什均衡的问题会让你很快陷入计算麻烦。到20世纪末，确定一款游戏是否超过一种均衡，或者有一种能给玩家带来一定回报的均衡，或者一种需要采取特定行动的均衡，都被证明是棘手的问题。然后，2005—2008年，帕帕迪米特里欧和他的同事证明，仅仅找到纳什均衡都很棘手。
1700497122
1700497123
像石头剪刀布这样简单的游戏，随意一瞥就可以看到其中的均衡，但是我们现在很清楚，在现实世界的复杂性游戏中，我们不能想当然地认为参与者能够发现或者达到游戏的均衡。反过来，这意味着游戏的设计者不能用均衡来预测玩家的行为。这一发人深省的结果产生了深远的影响：作为一种模拟和预测市场行为的方式，纳什均衡在经济理论中保有一个神圣的地位，但这一地位可能不是应得的。正如帕帕迪米特里欧解释的那样，“如果一个均衡的概念不能被有效地计算，那它作为对理性主体行为的预测的可信度就会失去大半”。麻省理工学院的斯科特·阿伦森对此表示赞同。“在我看来，”他说，“如果纳什均衡成立的定理被认为与自由市场和政府干预之间的争论有关，那么发现这些均衡的确难以处理的定理就也应该被认为是相关的。”纳什均衡的预测能力只有当参与者真正找到均衡时才体现其重要性。引用亿贝网（eBay）前研究主管卡迈勒·杰恩的话：“你的笔记本电脑都无法找到的东西，市场也无法找到。”
1700497124
1700497125
1700497126
1700497127
1700497129
算法之美：指导工作与生活的算法 占优策略，无论好坏
1700497130
1700497131
即使当我们达到平衡时，仅仅因为它是稳定的并不会使它变好。这似乎自相矛盾，但是均衡策略，是没有参与者愿意改变策略的领域，并不一定是为参与者带来最好结果的策略。没有什么比博弈论中最著名、最具煽动性、更有争议的双人游戏“囚徒的困境”更能说明问题了。
1700497132
1700497133
囚徒的困境玩法如下。想象一下，你和一个密谋者在抢劫了一家银行后被逮捕，并被关押在不同的牢房里。现在你必须决定是否要与对方“合作”，是保持沉默，不承认任何事情，还是通过向警方告发对方来“背叛”你的伙伴关系。你们知道，如果你们彼此合作，保持沉默，州政府就没有足够的证据来定你们任何一个人的罪，所以你们都可以重获自由，然后两个人分那笔赃款——每人50万美元。如果其中一方叛变并告发对方，而另一方什么没招供，那名告密者就将得到全部的100万美元，而保持沉默的人则会被判为唯一的犯罪嫌疑人，并被判10年徒刑。如果你们双方都互相告发，那么你们就会分担刑期：每人5年。问题就在这里。
1700497134
1700497135
不管你的同谋做了什么，你最好的选择永远是叛变。
1700497136
1700497137
如果你的帮凶出卖了你，那么反过来，如果你也出卖他们，你将会减少5年的刑期——你将会与同伙共同分担刑期（5年），而不是你自己独自服刑（10年）。如果你的同伙保持沉默，告发他们可以使你得到100万美元——你就不必将赃款拿出一半了。无论如何，不管你的同谋如何决定，对你来说告发总比合作更好。相反的做法则会让你变得更糟，不管怎样。
1700497138
1700497139
事实上，这使叛变不仅仅成为均衡策略，还是所谓的占优策略。一个占优策略避免了递归，因为它是对你对手所有可能策略的最佳反应，所以你甚至不需要麻烦自己了解他们的想法。占优策略是强有力的。
1700497140
1700497141
但现在我们已经到了这个矛盾的地方。如果每个人都做理性的事情，并遵循占优策略，那么故事就会结束，你们都要服刑5年——这与自由和每人50万美元相比，每个人的处境都要糟糕得多。怎么会这样呢？
1700497142
1700497143
这已成为传统博弈论的主要见解之一：一组游戏玩家的均衡，所有人都玩得很理性，这对那些玩家来说可能不是最好的结果。
1700497144
1700497145
与计算机科学原理相一致的算法博弈论，已经接受了这一观点，并对其进行量化，创造了一种叫作“调和率”的度量。调和率衡量合作（集中设计或协调的解决方案）和竞争（每个参与者都各自试图最大化利于自己的结果）之间的差距。在像囚徒的困境这样的游戏中，这个调和率实际上是无限的：增加赃款金额和延长刑期可以使可能的结果之间的差距任意扩大，即使占优策略保持不变。如果参与者不协调的话，那事情的痛苦程度就无止境了。但在其他游戏中，正如算法博弈理论家会发现的那样，调和率并不那么糟糕。
1700497146
1700497147
例如，想想交通。无论是每日试图在各种交通堵塞中通过的个人通勤者，还是在互联网上移动传输控制协议数据包的路由器，系统中的每一个人仅仅想要对他们个人来说最容易的选择。司机只是想走最快的路线，不管路线是什么，而路由器只是想在它们的包里随意地移动，但是在这两种情况下，这可能导致在关键路径上过度拥挤，使大家都堵塞。但这有多大的伤害啊？令人惊讶的是，蒂姆·拉夫加登和康奈尔大学的伊娃·塔多斯在2002年证明了“自私路由”方法的调和率仅仅是4/3。也就是说，完全公开只比组织严密的完美的协调差33%。
1700497148
1700497149
拉夫加登和塔多斯的研究成果对城市规划和网络基础设施都产生了深刻的影响。例如，自私路由的低调和率可以解释为什么因特网的运作和没有任何中央集权管理单个数据包的路由运行效果一样。即使这样的协调是有可能的，但也不会增加太多。
1700497150
1700497151
当涉及人类的交通时，低调和率会在两方面各有利弊。好的方面是，缺乏集中的协调只会使得你的通勤状况变糟33%。另一方面，如果你希望自动驾驶的汽车能为我们带来未来交通的理想状况，那么如果你了解到，现今的自私、不愿协调的司机其实已经相当接近最佳状态时，可能会令你十分沮丧。的确，自动驾驶汽车应该减少交通事故的数量，并且能够使汽车更紧密地往前行驶，实现这两方面都能加快交通速度。但从拥塞的角度来看，调和率只有4/3，而完美的协调意味着完全协调的通勤只能是现在的3/4。这有点儿像詹姆斯·卡贝尔的名言：“乐观主义者宣称，我们生活在有可能是最好的世界里，而悲观主义者则担心这是真的。”交通拥堵永远是一个问题，要由规划者和总需求来解决，而不是由个别司机、人类或计算机、自私或合作的决定来解决。
1700497152
1700497153
量化混乱的价格调和率给了这个领域一种具体而严谨的方法来评估分散系统的利弊，这在很多领域都有广泛的影响，在那些领域里，人们发现自己参与到玩游戏的过程中（不管他们是否意识到）。“低调和率意味着，无论好坏，系统本身就会像它被精心管理的那样良好。另一方面，高调和率意味着在谨慎地协调的情况下，事情有可能会最终变好，但如果没有某种形式的干预，我们就会陷入灾难。囚犯困境的游戏显然是属于后者。不幸的是，许多这个世界必须玩的最关键的游戏也都是这样的。
1700497154
1700497155
1700497156
1700497157
1700497159
算法之美：指导工作与生活的算法 公地悲剧
1700497160
1700497161
1968年，生态学家加勒特·哈丁借鉴了囚徒的困境的想法，并设想将其规模扩大到包括一个农业村的所有成员。哈丁邀请他的读者去描绘公共草坪的“公有地”——每个人都可以来此放牧，但容量有限。从理论上讲，所有的村民放牧的动物数量都应该是自己家的牲畜吃完草后还能给其他人留一些草。然而，实际上，多放牧一些动物的好处要比直接给你的好处多一点儿，而伤害似乎很小，不会有什么后果。然而，如果每一个人都遵循这样的逻辑，大家只会得到少于他们本应得到的公有地，这是一个可怕的均衡结果：一个完全毁坏的草坪，这样一来，所有人的牲畜都没有草吃。
1700497162
1700497163
哈丁称之为“公地悲剧”，这已经成为经济学家、政治学家及环境运动对诸如污染和气候变化等大规模生态危机的主要视角之一。“当我还是个孩子的时候，有一种叫作含铅汽油的东西，”卡内基梅隆大学的计算机科学家、博弈论学家艾弗瑞姆·布卢姆说，“含铅的价格便宜10美分，但它污染了环境……考虑到其他人都在做的事情，如果你给自己的车加含铅汽油，那么你个人（健康）到底有多糟糕？并没有多糟。这就是囚徒的困境。”在企业和国家层面上也是如此。最近的报纸头条简洁地指出：“稳定的气候要求将大多数的化石燃料留在地下，但它们归谁呢？”每个公司（在某种程度上，每个国家）为了竞争优势都比它们的同行更不顾后果。然而，如果它们的行为更加鲁莽，就会导致地球被蹂躏，最终一切都是徒劳：相对于它们开始的阶段，任何人都没有经济上的优势。
1700497164
1700497165
这种游戏的逻辑是如此的普遍，以至于我们甚至不用去看那些错误行径都能知道它在胡作非为。我们也可以很容易地以一种纯净的良心结束这种可怕的平衡。又怎样进行呢？看看你公司的假期政策。在美国，人们的工作时间是世界上最长的，正如《经济学人》杂志所言：“工作价值越高，休闲的价值就越低。”很少有法律规定雇主所应提供的休假时间，甚至美国员工有休假时间，他们也不用。最近的一项研究表明，普通员工只享受了赋予他们的一半的假期，而惊人的是，15%的员工则完全没有假期。
[
上一页 ]
[ :1.700497116e+09 ]
[
下一页 ]