沃顿商学院的 MBA 选修课分配原本采用积分竞价拍卖,而据研究团队的评估,各校实际使用的机制要么低效、要么不公平,或两者兼有。学生要猜测哪些出价能够中标,从而对冲自己的真实偏好;超额认购的课程让同学被困在糟糕的课表上;这套游戏奖励的是策略型选手。Eric Budish 在 2011 年《政治经济学杂志》的论文中提出了一个理论上的解决方案——等收入近似竞争均衡(A-CEEI)——但指出了实际障碍:偏好报告的复杂性、计算复杂性以及容量约束违反。

Course Match 由 Budish 与 Gerard Cachon、Judd Kessler 和 Abraham Othman 共同构建,弥合了这些缺口。学生报告的是对整份课表的偏好,而非逐门课程的出价;引擎运行大规模并行启发式搜索,求解数十亿个混合整数规划,以在虚拟货币的席位经济中达到近似竞争均衡;并且容量约束得到满足。在全面使用中,它为约 1,700 名沃顿学生分配课程,每学期面对多达 350 门课程,两个学期的汇总统计显示结果既公平又高效。

该方案的采用通过沃顿一项新颖的实验室实验降低了风险:Budish 和 Kessler 采用基于二元选择构建的“引出偏好”方法,发现参与者更偏好 A-CEEI 分配给他们的课表,而非现行积分竞价拍卖产生的课表,且嫉妒程度可测量地更低。他们报告称,该实验帮助说服沃顿商学院采用这一机制,并影响了产品中偏好报告的工作方式。2017 年,沃顿将该实现分拆为一家初创公司 Cognomos,Budish 担任创始董事。

以均衡价格清算整份课表,而非逐个席位

平等预算使分配在构造上减少嫉妒:没有人因为起始积分更少而被挤出,他们被挤出是因为该席位对别人更有价值。

对整份课表竞价消除了暴露问题——学生不再出现赢下一门课却失去那门使第一门课值得选的课的情况。

均衡价格取代了猜测:超额认购的课程价格上涨,学生转向划算的选择,因此需求得以分散,无需午夜抢课竞赛。

计算技巧——并行搜索中数十亿个小型混合整数规划——正是将 2011 年的存在性结果转变为能够为 1,700 名学生对照 350 门课程完成清算的系统的关键。

团队在全面推广前在真实沃顿学生身上测试了该机制,因此学校在采用时知道参与者能够足够准确地报告复杂偏好。

任何稀缺的多物品分配,如果逐项清算就会崩溃:人们会采取策略,诚实的出价者会吃亏。以均衡价格清算所有组合,诚实就几乎变得最优。

该机制设计与计算程序属于公有领域,沃顿拥有生产实现并为其提供了资金;NBER 工作论文中的披露说明,学校于 2017 年将该知识产权分拆至 Cognomos,Budish 作为创始董事持有股权。该案例已成为将组合分配机制从理论——A-CEEI 的公平与效率性质在其中得到证明——推向每学期清算数千份课表的实际市场的标准参考。

从这里,追溯依据

参考来源

  1. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation SSRN / Chicago Booth Research Paper No. 15-28 (Budish, Cachon, Kessler, Othman) · ssrn.com ·
  2. Can Market Participants Report their Preferences Accurately (Enough)? — NBER Working Paper 22448 NBER (Budish & Kessler) · nber.org
  3. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes Journal of Political Economy 119(6):1061–1103 (Budish) · journals.uchicago.edu