華頓商學院的 MBA 選修課分配原本採用點數競標拍賣,而依研究團隊的評估,各校實際採用的機制不是效率低落、不公平,就是兩者兼具。學生得猜測哪些出價會成交,因而對自己的真實偏好有所保留;超額登記的課程讓同學被卡在糟糕的課表上;這套遊戲獎勵的是策略高手。Eric Budish 於 2011 年發表在《Journal of Political Economy》的論文提出了一套理論上的修正方案——等收入下的近似競爭均衡(approximate competitive equilibrium from equal incomes, A-CEEI)——但也點出了實務上的障礙:偏好回報的複雜度、計算複雜度,以及容量違規。

由 Budish 與 Gerard Cachon、Judd Kessler 及 Abraham Othman 共同打造的 Course Match 補上了這些缺口。學生回報的是對整份課表的偏好,而非逐門課的出價;引擎執行大規模的平行啟發式搜尋,求解數十億個混合整數規劃,以在一個為座位而設的假想貨幣經濟中達成近似競爭均衡;而且容量限制得以維持。在全面規模的實際使用中,它為約 1,700 名華頓學生分配課程,這些學生每學期面對多達 350 門課;橫跨兩個學期的彙總統計顯示,結果既公平又有效率。

這套機制的採用,是先透過華頓一項新穎的實驗室實驗來降低風險:Budish 與 Kessler 採用一種由二元選擇建構而成的「引導式偏好」(elicited preferences)方法,發現參與者偏好 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