学科课程教师培训班第8章幻灯片.pptVIP

博弈论简单应用之一：网络流量的博弈论模型 （对应第8章） 网络中的博弈 公路交通网 十一长假，是否出门？走哪条路线？ 有意无意中，你会想：别人会怎么样？ 博弈论思想的一个典型应用 回顾博弈问题讨论的核心概念：均衡 给定一个博弈设置（参与人，策略，收益），博弈结果会如何？ “互为最佳应对”的策略组，即“均衡” 每个人，都按照对他人理性行为的预期，决定自己的最佳行动（理性的） 每个人实际采取的行动与其他人的预期一致 该状态下所有参与者的策略互为最佳应对，任何个人都没有理性的理由改变 第8章：网络流量的博弈论模型 布雷斯悖论－如果结构不合理，增加资源可能更糟 网络中的博弈：一个简化的例子 参与人：4000位司机 策略：“走上面”和“走下面” 回报：行驶时间（越小越好），显然也取决于他人的策略 有4000辆车，都要从A到B 均衡？ 一种没人要调整的选择状态 4000辆车，要从A到B 此时，若某人要改变，则他的行驶时间 2001/100 + 45 65，因此没人会改变 均衡：每条路上2000 辆车； 对每辆车而言，对应回报为65 设想政府要改善民生，新修了一条快速路 注意，在没修这条路前，均衡中行驶时间是65 如果某人盘算改变为A?D?B，则他的行驶时间将变为45+4000/10080，于是他不会改变！ 均衡是大家都走： A?C?D?B 每人行驶时间为 4000/100+0+4000/100=80 ！！！ 布雷斯悖论出现！ 会发生什么情况？ 为什么大家不像从前那样？ 你会很合理地想走A?C?D?B。也就是说，从前那样的模式在均衡态是不可能的（不均衡，有人有动机改变） 你会这么想，其他人呢？会不会变成2000人走A?C?D?B，另外2000人走A?D?B？ 若你是决定走上面的 2000人之一，看到了这个局面，此时会不会有什么想法？ 这种问题的一般性如何？ 对于“任意交通网”和“线性通行时间” 函数，是不是总存在一个均衡？ 若在一条边（e）上的通行时间函数可表为： Te(x)=ax+b，其中x为在该边上的车辆数，则称在该边上是线性通行时间函数 均衡：在车辆群所体现的行驶路线（即每人的选择）模式中，没有司机可通过改变线路缩短自己的通行时间 答案是肯定的！如何证明？ 深度学习材料之一 均衡路线模式的存在性证明（1） 思路的出发点： 给定任意初始交通模式，若不是均衡，那么就存在一个司机，能够通过改变路线缩短自己的通行时间 假设他如此做了，于是得到一个新的交通模式，若不是均衡，那么就存在一个司机，能够通过改变路线缩短自己的通行时间 … 如此下去，为什么会停止？（即达到均衡） 均衡路线模式的存在性证明（2） 在网络交通模式上定义一个适当的量，使得当一个司机选择缩短自己行驶时间的路线后，新模式的这个量严格减小 这个量不能是所有车辆的行驶时间之和，因为一辆车的缩短了，其他的可能因此加长了，总时间的变化难以说清楚 Potential Energy（势能） 对于一条边e，Energy(e)=Te(1)+Te(2)+…+Te(x) 对于一个交通模式，ΣEnergy(e) 然后说明，司机的每一次缩短行驶时间的路线改变都使这个模式势能下降－－恰好等于他行驶时间的减少 Te()为边e上的通行时间函数 如何说明司机改换路线的效果？ 放弃原来的路线；走一条新路：时间减少 设e是原来路线上的一条边，放弃意味着在那条边上的车辆数从x变为x-1，对应该边上的势能变化为 Te(1)+Te(2)+…+Te(x) ? Te(1)+Te(2)+…+Te(x-1) 即降低的数值恰好为他当前在该边上的行驶时间 走新路，则在一条边上引起的势能增加等于新的行驶时间（Te(y+1)） 也就是新模式的势能严格小于先前的 因为改变路线的车的新老行驶时间要有： 深度学习内容（之二） 均衡状态下车辆行驶时间之和（社会成本）可能不是最少（社会最优）的，但也不会太差（严格上界为4/3倍） 为简单起见，教材中证明了一个弱一点（不超过2倍）的结果 对于每条边，依然有线性通行时间假设 如何说明？ 以势能做桥梁，建立它与行驶时间之间的关系 均衡态社会成本上界的证明 一辆车在边上的通行时间：Te(x)=aex+be 其中e为边的标识，x 为该边上的车辆数 一条边的势能：Energy(e)=Te(1)+Te(2)+…+Te(x) 一条边的社会成本：Cost(e)=xTe(x) 关键认识： 对边求和就得到一个交通模式的总能量与社会成本的关系 从通行函数的线性性以及Energy和Cost的表达式容易看出这不等式 但我们需要的是均衡模式（Z’）下的社会成本与社会优化模式（Z）下的社会成本之间的关系，即： 关键思路： 从一个社会优化模式开始，不断施行“最佳应对”，直到达到一个均衡模式，看其间势能与社会成本的变化，并