一点博弈论趣题

回顾快要结束的研究生生活, 发现真正带给我学习快乐的并不是研究. 虽然机器学习, 计算机视觉都是非常有趣的方向, 可是由于自己积累太少, 要想真正体会到研究的快乐还是比较难, 尤其是作学术讲究求新立异, 现在看来一年的确是不够的. 事实上我向来觉得, 如果我们普通人能够掌握到19世纪初左右的数学, 科学知识, 那么也已经相当牛了. 而推进人类认知的任务, 就交给PHD先生/女士们了. 而我本来就没有一颗献身科学的心, 当然如果有的话, 也不会选择计算机科学, 一定是数学或者物理. 所以说学术这条路, 事实上已经在6年前被我亲手斩断了.

总而言之, 自己创新能力还是不够, 更善于接受一些别人做出的成果然后去评判是否有趣有用值得读. 比如说, 研究生阶段80%的课程都是断然的水课. 剩下的不水的课中, 掐指一算, 也就只有Rudolf Fleischer老师的算法博弈论和阚海斌老师的图论课属于有趣的了. 这几天觉得应该把这些内容整理一下积累起来才不算浪费. 这应该是一系列关于博弈论或者图论的文章之一, 记录一些有趣的, 有启示的结论, 证明等等.

相信很多人听说博弈论都是从囚徒困境开始的. 用最简单的话来说, 囚徒A, B分别有承认他们的犯罪或者抵赖两种选择, 而这个“游戏”的设计使得他们中任何一个人, 无论另外一个囚徒的选择是如何的, 对于自己来说, 选择承认犯罪总是更好的选择. 因此这个游戏的最终结果就是, A, B都承认犯罪, 双双入狱坐牢2年, 而如果他们知道合作都不承认犯罪, 那么最好的结果是他们只需坐牢1年.

        A承认    A抵赖


 B承认 都坐牢2年 A坐牢5年


 B抵赖 B坐牢5年 都坐牢1年

事实上, 一种更好的说法是, A,B同时抵赖在这个游戏中并不是一个纳什均衡点, 即在没有合作的情况下, 有参与者会从这个“大家都抵赖”的点选择其他的做法, 因此游戏最终没有停留在这个点上. 而且在囚徒困境中, 每一个参与者都有一个“主导策略”, 也就是说无论对手如何选择, 选择抵赖总是最好的策略. 这种情况下游戏很容易就会到达一个纳什均衡点.

关于纳什均衡点有很多有趣的性质准备在后续的文章中详细说说. 我们再来看一些有趣的博弈论例子.

Braess悖论

考虑A, B两座城市之间的高速公路:

假定走A-X以及Y-B这2条路消耗的时间是T/100 , 其中T是路上的车辆数, 而A-Y和X-B上消耗的时间为常数45分钟. 现在如果有4000辆车, 那么容易得到, 在2条路径A-X-B和A-Y-B上分别有2000辆车时, 这个游戏达到了平衡, 大家都会花费65分钟在路上.

现在我们试图建造一条超高速高架, 连接X-Y, 而且从X到Y的时间可以忽略不计.

这时, 由于司机考虑到, T/100最多为40, 因此他们会毫不犹豫得选择A-X, 而同样的道理, 由于X-Y的时间消耗为0, 他们在到达X之后会选择由超高速高架到达Y, 继而再花40分钟到达B. 因为每一个司机都是如此考虑的, 所以在这种添加了一条超高速公路的情况下, 游戏最终会稳定在所有人都选择A-X-Y-B的路径, 花费80分钟从A到达B. 而我们之前看到, 在没有超高速公路的情况下, 最佳路径花费只需65分钟. 悖论出现了, 额外花钱建造的超高速公路反而使得大家花费在路上的时间增加了!

事实上博弈论出现得比我们想象的更加频繁, 比如google adwords的第二价格竞标, 比如近两年很火的HFT, 股票市场的博弈, 顺便提一下, 计算纳什平衡是非常难的问题(PPAD), 所以这可能也是即使有了计算机, 市场仍然难以把握的原因之一.

关于博弈论的书, <<Algorithmic game theory>>这本书写得的确不错, 内容也适合非数学/经济的同学读.