分类：
2010-11-25 19:57:20
上篇我们说到 Tit for Tat 的策略有一个极大的漏洞, 是什么样的漏洞呢? 我们不妨先用通俗的例子理解一下.
假如现实生活中有两个人 A 和 B, 都是认为自己非常理智, 而且严格执行”以牙还牙”策略的人遇到了一起, 会发生什么样的事情呢? 我们按照他们初始的策略, 分三种情况讨论.
1. 假如 A 某次不小心招惹了一下 B (执行了被 B 解读为 D 的策略), 按照 B 的策略, 必然会在下一轮执行 D 策略 (报复). 而 A 对 B 初始是执行 C 策略 (合作) 的. 在 B 报复之后, A 下一轮就会采用报复. 而相反的, B 在本轮看到 A 合作之后, 下一轮就会报复. 如此往返. 不难看出, A 和 B 会陷入彼此报复的怪圈当中, 用大白话说, 就是所谓的冤冤相报何时了. 更加糟糕的是, 博弈的双方都认为自己是完全理智而且愿意合作的, 但是就是因为正好彼此差了一步, 因此从A的角度看B, A 会认为 B 是一个完全不懂得合作的蠢货 (A 提出合作的时候B正好报复). B 看 A 也一样. 现实生活中我们也能发现这种例子, 比如两个性格很强的人遇到了, 在某件事情上不投合, 结果成了一辈子的仇人, 还互相认为对方是傻X. 此时, 双方都得不到期望的最大受益.
2. 如果一开始双方都采用 D 策略, 则可以遇见, 这样的 D 策略将持续下去, 没有一方会主动的让步, 因为先让步的一方必然吃亏. 现实中, 我们也能观察到这样的事情, 即博弈双方仇怨越积越深, 最后到了不可化解的地步. 此时, 双方都陷入了囚徒困境.
3. 如果博弈的双方一开始都采取 C(合作)策略. 那么, 博弈双方则能够永远的友好合作下去, 获得最大的受益. 此时, 双方获取的受益都最大化了.
从上面的分析我们可以看到, 在多轮囚徒困境的情况下, 如果有多个 Tit-for-Tat 策略参与, 那么每个的受益, 极端的依赖于初始状态的设定. 在数学和计算机科学中, 这样的系统, 叫做”初值敏感系统”. 一般认为, “初值敏感系统”是非常不好的系统, 原因在于缺乏”鲁棒性”. 这里我走一下题, 解释一下初值敏感系统和鲁棒性这两个概念.
大家都知道有一个叫做”蝴蝶效应”的东西, 大体是说, 一只蝴蝶在巴西扇动翅膀，有可能会在美国的德克萨斯引起一场龙卷风. 原因在于, 这只蝴蝶翅膀扇动的气流, 引起的一个小小的搅动, 可能会在系统中被各种各样的因素放大, 最后演变成一个非常显著的效应. 中国也有一句古话, 叫做差之毫厘, 谬以千里, 说的都是, 初始的微小变化, 都能引起最后结果的显著不同. 我们这里的初值敏感系统, 和蝴蝶效应也是类似的, 能从小的摄动引发出显著的后果的. 比如大家都知道, 在”一只馒头引发的血案”中, A 在很不经意的情况下, 对B 采用了 D 策略(抢了馒头), B 由此产生了报复, 搞得 A 国破家亡.
显然, 面对这样的系统, 人类即使有模型, 也是很难预测未来的, 因为初值条件在测量上的一点点微小的误差, 都能造成预测的结果的巨大不同. 为了表征这个特性, 我们把”不对初值敏感”的特性成为鲁棒性 (Robustness). (这个鲁棒, 您可以直接理解为山东大棒, 结实, 抗得住外界的一些摄动).
聪明的读者要说了, 即使系统不鲁棒, 我们能不能设计好初值, 使得系统沿着最好的方向演化呢? 答案是不能. 因为任何一个客户端拥有的上传和下载的带宽都是有限的, 有限的资源必然会导致资源的竞争, 从而导致必然某些请求不能满足. 在这种情况下, D 策略是不可避免的. 况且, 网络情况复杂多变, 即使双方都有意采取 C 策略, 很可能因为网络的复杂性, 双发获得的受益不对等, 从而引发一方采取 D 策略. 所以, 如果 Tit for Tat 这种初值敏感策略放到 P2P 客户端中, 结果是不可想像的, 因为这时候每个客户端都是碰不得的刺猬, 一旦在某个时间点某个节点出现了差错, 很可能整个系统都陷入”冤冤相报”的死结, 让整个网络没法完成文件的传输, 反而忙着互相报复和自我保护.
从上面的分析我们看出, 靠精心设计初值来维护这个系统是不现实的, 我们需要设计的, 是一个好的策略, 使得不管初值怎么变, 系统中每个个体依然能够获得较大的收益. 那么, 怎样设计这个鲁棒的系统呢? 我们从极端的两个例子开始, 一种是不管别人怎么出牌, 永远合作的; 另一种是或者不管别人怎么策略, 永远背叛的. 这两个都很鲁棒, 都很”彪悍”. 但是毫无疑问, 效用不见得最大化.
从这两个极端的例子表现不怎么好来看, 我们的确应该要根据对手的策略选择自己的策略, 同时又不能非常的依赖于对手的策略(否则就初值敏感了). 那么, 最简单的方法就是: 我们以一定的概率去执行以牙还牙, 但是也允许以一定的概率不管上次选什么, 这次和对手选择合作(跳出怪圈). 这样, 因为随机性的引入, 对初值的依赖就随着时间的流逝越来越小了.
在多个人的环境中, 我们的确愿意和对手选择随机合作, 但是因为资源的限制, D 是不可避免的. 但是我们不会让 D 永远下去, 我们每轮和随机的对手选择一次随机的合作, 这样就不会被怪圈所左右. 这个就是 bt 协议跳出冤冤相报的精髓. 一旦知道了这个, 本文思想就差不多介绍完了. 下面就是程序员的编码工作了. 下面的内容完全是基于 Bram Cohen (bt 协议创始人) 的经典论文 “Incentives Build Robustness in BitTorrent” ( ) 里面的内容展开的. 我只介绍和博弈论有关的部分. 读英文更加习惯的读者直接看原论文比读下面的文章更加好.
首先说点背景知识, bt 把文件看成一块一块的, 并且用一定的排序算法决定现在能够下载哪一块. 其次, bt 协议同时和多个机器之间建立 TCP 连接, 但是采用堵塞的方法控制传输. 因为建立连接代价比较大, 所以 bt 协议维持连接不变, 在其上采用 choking (堵塞) 的方法来执行 D 策略, 采用 un-choking 的方法 来执行 C 策略, 而不是每次都重新建立和取消连接. IP 协议在这方面有天然的优势.
每次, BT 协议选择 k (通常为7, 限速的情况下为2, 3, 或 4) 个其他的客户端来执行 C 策略(即给上传). 在上一轮中给出最多下载的那些节点, 在本轮将被执行 C 策略(注意到有的节点上一轮并没有给上传, 即从C 到 D). 同时, 为了避免其他的更加好的节点被忽视, 每 m 轮, BT 客户端选择一个随机的 choke 了的节点执行 C 策略 (即从 D 到 C. 同时, 因为资源限制, 必然有一个被 choke 了, 即从 C 到 D).
那么, 什么时候执行 D 呢? 在 BT 协议中, 假如连续 n 轮, 都没有从一个节点收到任何下载, 在 bt 术语中, 这个叫做 snubbed. 这时候, 则该节点认为自己被那个结点执行D策略了. 作为报复, 自己也停止对该节点的上传(即以牙还牙, 从 C 到 D. ). 除非等到下次随机的选到了那个节点(再次到 C ).
这就是 bt 的协议关于博弈论的全部. 其中, 一轮持续时间在现在的实现中是 10 秒. m 为 3, n 为 6. 目前暂不清楚 Bram Cohen 是否通过实验得到这些参数, 有兴趣的读者可以自己查阅 bt 源代码, 改一下, 看看哪个更加好. 同时, 因为其他客户端采用的是 Tit for Tat, 想把自己的客户端改成 吸血bt 是不可行的, 也占不到别人便宜.
PS: 有兴趣的读者可阅读 bt 源代码中的 Choker.py. BT 源代码用 Python 写成, 比较好懂.
