《算法博弈论、布雷斯悖论与流量分配的无秩序代价》各章定量结论

多修一条路,为什么每个人都更慢了?本书用算法博弈论考察自私的选择与集体最优之间的差距:它从哪里来、最坏有多大、什么价格或规则能消除它,以及同样的结构在注意力市场、推荐系统与撮合市场中以什么形式出现。依次讨论:瓦德罗普用户均衡与系统最优,布雷斯菱形网络中零延迟捷径使通行时间从 1.5 增至 2.0(捷径是弱占优而非严格占优,悖论只在需求介于 2/3 与 2 之间时出现),以及同一组方程在弹簧—绳子网络与直流电路中的同构;无秩序代价的定义与来历,非原子用户、线性延迟下的 4/3 上界与 d 次多项式延迟下的上界(d = 4 时 2.151,按 Θ(d/ln d) 增长,与拓扑无关的结论出自拉夫加登 2003),随机网络中的数值检验,以及有限人数博弈中最坏情形为 5/2;边际成本通行费使自私均衡与最优重合,但不退还收入时用户的「时间 + 费用」未必下降,有限人数的拥堵博弈是势博弈,6 人布雷斯博弈的改进过程停在「全走桥」;霍特林线性城市及达斯普勒蒙等人 1979 年的修正、热门赛道的拥堵博弈与只在非串并联结构中才可能出现的「数字布雷斯悖论」;多臂老虎机中贪婪、ε-贪婪、UCB1 与汤普森采样的比较,富者愈富的曝光与学习质量的区别,以及一个示意的三级流量池的筛选信噪比;盖尔—沙普利延迟接受算法、提议方最优与提议方说真话的占优性(接受方不成立)。

DOI 10.5281/zenodo.23782094 · 阅读本章所在专著 · English version

模型示意算例,非实时报价