1700497110
1700497111
博弈论有一个开创性的结果，数学家约翰·纳什在1951年证明了每一个双人游戏至少有一种均衡。这一重大发现使纳什获得了1994年的诺贝尔经济学奖（并由此产生了关于纳什的名为“美丽心灵”的书和电影）。这种均衡现在被称为“纳什均衡”，即丹·史密斯一直试图追踪的“纳什”。
1700497112
1700497113
从表面上看，纳什均衡总是存在于两个玩家的游戏中，这似乎让我们稍稍从那些描述扑克和许多其他熟悉比赛的镜像递归中解脱出来。当我们感觉自己掉进了递归的兔子洞时，我们总是有办法跳出对手的脑袋，寻找均衡，直接进入最佳策略，设想这是一场理性的游戏。在石头剪刀布里，仔细观察对手的脸，看看他们可能会出什么，这也许是不值得的，如果你知道长远来看，随便乱出才是一个不可战胜的策略。
1700497114
1700497115
更通俗地说，纳什均衡可以帮助人们预测任何一套规则或激励制度的长期稳定结果。因此，它是预测和制定经济政策以及总体社会政策的宝贵工具。正如诺贝尔奖得主经济学家罗杰·迈尔森所说，纳什均衡“对经济学和社会科学产生了根本性和普遍的影响，与生物科学中DNA（脱氧核糖核酸）双螺旋结构的发现具有可比性。”
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
算法之美：指导工作与生活的算法 公地悲剧
[
上一页 ]
[ :1.70049711e+09 ]
[
下一页 ]