【TD精选】博弈论-走向平衡的路并不清晰（连载2）

2017 年 8 月 16 日 TalkingData锐眼 路瑶

本文预计阅读时间10分钟，Enjoy your reading！

多人游戏

在一些简单的游戏中，很容易发现纳什均衡。例如，如果我喜欢中国菜，而你更喜欢意大利菜，但是我们最强烈的喜好是一起吃饭，两个明显的均衡是我们两个人去中国餐馆或我们两个人去意大利餐厅。即使我们开始只知道自己的喜好而且不能在比赛之前交流策略，我们也并不会因为花太多时间去深入了解彼此的偏好而导致错过联系的机会从而只能孤独的晚餐，我们很有希望找到一个，或者另一个均衡。

但是想象一下，如果晚餐计划涉及100人，每个人都决定了他喜欢和什么人共进晚餐，同时没有人知道其他任何人的喜好。纳什在1950年证明，即使像这样的大型复杂的游戏，也总是存在一个均衡（至少在策略的概念被扩大以允许随机选择，比如你有60％概率选择中国餐馆，的情况下是成立的）。可惜纳什在2015年因车祸而死亡，他没有给出达到均衡的计算方法。

阿维亚·鲁宾斯坦（Aviad Rubinstein）帮助表明，玩家不一定会发现纳什均衡。

Tselil Schramm通过潜入Nash的证明过程，Babichenko和Rubinstein能够表明，一般来说，玩家无法找到近似纳什均衡的路径，除非他们表达了几乎所有关于他们各自的喜好。随着游戏中玩家的数量的增加，这种沟通所有需求的时间迅速增长到足以令人望而却步。

例如，在100人的餐厅游戏中，有2^100种可能的结果，因此每个玩家必须共享2^100种偏好。相比之下，自大爆炸以来已经过去的秒数只有2^59。

这种通信瓶颈意味着，任意方法都不可能通过从一轮到另一轮的适应策略来指导玩家有效地达到纳什均衡，至少对于一些复杂游戏的这样的（例如具有复杂偏好的100人玩家餐厅游戏）。毕竟，在每一轮中，玩家只会学到一点新信息：其他玩家对某种晚餐安排有多满意。因此，他们需要2^100轮游戏来知道彼此价值观（而在此之前中国和意大利餐馆可能都已经关门了）。

耶路撒冷希伯来大学游戏理论家塞尔古·哈特（Sergiu Hart）说：“如果这将比宇宙演化花费更长的时间，那当然完全没有用。”

玩家为找出纳什均衡，有时候需要知道对方所有的价值观，这看起来很自然。然而在现实中，这往往是难以实现的一点，即使玩家愿意达到一个接近纳什均衡且已经足够好的近似纳什均衡。这是新的论文提出的一个重要的发现。

亚科布·巴布奇琴科（Yakov Babichenko）表明达成纳什均衡可能需要比宇宙的时代更长的时间。

Babichenko和Rubinstein的结果并不意味着所有（甚至大部分）的游戏都将受到这个限制，也就是说，只有一些游戏会。经济学家用来建模现实世界的许多游戏都有额外的构架，从而大大减少了每个玩家必须沟通的信息量。例如，如果我们每个人都选择我们早上通勤的两条路线之一，那么你可能不在乎每个路线上有哪些车手 - 你只需要路线上有多少车。这意味着你的收藏偏好将具有很高的对称性，你可以将其全部内容转换成两个选择好的句子，而不是2^100个。

经济学家可以使用这样的论据来证明为什么特定的游戏是可以达到纳什均衡的。但本文介绍的新的成果，意味着这种判定必须在一个个具体案例中分别作出，即不存在一个完美论据证明对于所有游戏，达到纳什均衡都是可实现的。