《算法博弈论、布雷斯悖论与流量分配的无秩序代价》各章定量结论
多修一条路,为什么每个人都更慢了?本书用算法博弈论考察自私的选择与集体最优之间的差距:它从哪里来、最坏有多大、什么价格或规则能消除它,以及同样的结构在注意力市场、推荐系统与撮合市场中以什么形式出现。依次讨论:瓦德罗普用户均衡与系统最优,布雷斯菱形网络中零延迟捷径使通行时间从 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
- 第 1 章 · 布雷斯悖论:多修一条路,所有人更慢
用户均衡要求被使用的路线一样快,系统最优要求总成本最低,两者相差每个人给别人增加的边际延迟。在布雷斯网络中,对每个人都弱占优的零延迟捷径使通行时间从 1.5 增至 2.0,而最优根本不用它;悖论只在一段需求范围内出现。同一组条件也描述弹簧—绳子网络与直流电路。下一章问:自私最多比最优差多少? - 第 2 章 · 无秩序代价:自私最多让我们损失多少
无秩序代价是最坏的自私均衡与最优之比。在线性延迟、非原子用户的网络中,它不超过 4/3,而且最坏情形就是庇古的两条路网络,与拓扑无关;$d$ 次多项式延迟下上界为 $[1 - d(d+1)^{-(d+1)/d}]{-1}$,$d = 4$ 时为 2.151,按 $\Theta(d/\ln d)$ 增长。随机网络中的 PoA 通常远低于上界,并随需求先升后降;BPR 型道路只有在严重超载时才接近最坏情形。上界不适用于有限人数的博弈,后者… - 第 3 章 · 庇古税与势博弈:给看不见的延迟定价
在最优处按 $x^c'(x)$ 收费,自私均衡就与最优重合,但不退还收入时用户的「时间 + 费用」未必下降;斯德哥尔摩的拥堵费显示价格能显著改变出行。有限人数的拥堵博弈是势博弈,6 人布雷斯网络中的改进停在「全走桥、每人 120」;按外部性收取积分后,势函数变成总成本,全走桥不再是均衡。下一章把这一结构搬到注意力市场。 - 第 4 章 · 注意力的拥堵:热门赛道、霍特林与数字布雷斯悖论
霍特林的线性城市在价格固定时预测卖家扎堆,但在价格竞争下这个结论不成立:线性成本下靠得太近时没有价格均衡,平方成本下卖家会尽量远离,因为靠近对手只会引来价格战。在热门赛道的拥堵博弈中,均衡把过多的卖家挤进热门赛道,总收益比最优低约 4%;进入热门赛道给他人造成的损失是进入边缘赛道的两倍,按这一损失收费可以使均衡变成最优。「数字布雷斯悖论」只在注意力的流动经过两个相连的拥堵环节时才可能出现,是一个有待检验的类比。下一章讨论推荐系统怎样分… - 第 5 章 · 探索与利用:推荐中的老虎机、马太效应与流量池
只利用不探索会把曝光锁定在早期运气好的内容上;汤普森采样与 $\varepsilon$-贪婪的平均损失只有贪婪的三分之一,前者更稳定,UCB1 在点击率很低时探索过度。「富者愈富」的曝光使结果部分取决于运气,汤普森采样使曝光的集中与质量一致,但不使曝光平均。在示意的三级流量池中,选对第一级指标比增加级数更重要。「信息茧房」的经验证据有争议。下一章讨论双边匹配。 - 第 6 章 · 稳定匹配:延迟接受、提前签约与说真话
程序在 500 个随机的 6 × 6 市场上逐一检查了这些性质:结果全部稳定;每个提议者得到的都是他在全部稳定匹配(用穷举 720 种配对找出)中最好的伴侣;每个接受者得到的都是他最差的;随机打乱申请次序 5 次,结果都不变。稳定匹配常常不止一个:500 个市场中只有 183 个是唯一的,204 个有两个,最多的一个市场有 8 个。 - 第 8 章 · 实践与预注册试验
所以样本量按保守得多的假设计算:对照组陷入 60%,A 组 30%,双侧 $\alpha = 0.05$,把握度 90%:每组需要 56 个可分析的小组;考虑约 10% 的小组因有人中途退出而不完整,每组招募 63 个小组,即每组 378 人,共 756 人;模拟检验的把握度为 0.89。若真实差距只有 25 个百分点(60% 对 35%),每组需要 82 个小组。这些参数都是假设值,正式实施前应当用预试验的数据核对。
模型示意算例,非实时报价