乾明 魚羊 發自 凹非寺
量子位 報道 | 公眾號 QbitAI
江湖英雄輩出，又是姚班少年郎。
第34屆美國人工智能協會年會AAAI 2020現場，又一重要獎項揭曉。
最佳學生論文獎，頒向《可分割與不可分割商品混合情況下的公平分配》（Fair Division of Mixed Divisible and Indivisible Goods）。
論文作者：李子豪、貝小輝，都出自清華姚班。
貝小輝是姚班首屆弟子、樓教主鬲融的同班同學，而李子豪更是姚班2016級本科生——目前在讀。
AAAI 2020最佳學生論文
這篇獲得最佳學生論文獎的論文，研究了當資源同時包含可分割商品及不可分割商品時的公平分配問題。
公平分配問題是博弈論與算法博弈論的經典問題。是指為若干個分配者分配有限數量的資源時的博弈。
當資源為一種物質又可分割時，分配將會很容易進行。但資源種類複雜、不可分，而分配者的喜好各不相同時，分配將會難以進行。比如將17頭品種不同的活牛分給3個人。
基於傳統無嫉妒性（envy-freeness，EF）與單一商品的無嫉妒性（envy-freeness up to one good, EF1）的經典公平問題概念，研究者提出了一個在可分割與不可分割混合情況下更為有意義的公平性質，即混合商品的無嫉妒性（envy-freeness for mixed goods, EFM）。
以往的研究主要都是單獨考慮可分或不可分情況下的公平分配的問題，而缺少對於兩種商品混合情況下的公平分配的研究，該研究成果將EF和EF1都推廣到了混合環境中。
研究人員證明了，對於任意數量的智能體（agents）而言，滿足EFM性質的分配一定存在，並提出了一個有效算法，以計算2個智能體和n個智能體的EFM分配問題，並對可分割商品進行分段化線性評估。
在放寬對無嫉妒性的要求，轉而要求針對混合商品的ǫ-無嫉妒性（ǫ-EFM）後，研究人員提出ǫ-EFM算法，使其在一定的智能體數量、一定的不可分割商品數量和的 1 /ǫ的情況下，找到時間多項式的ǫ-EFM 分配。
研究人員認為，混合商品環境中的公平分配編碼了一個豐富的結構，並創造了一個新的研究方向，非常值得後續探索。
姚班畢業生與姚班本科生的聯手
這篇論文雖然署名有三個機構：新加坡南洋理工、清華大學和香港大學，但清華、清華姚班顯然是最大贏家。
論文第一作者貝小輝，現在是新加坡南洋理工大學助理教授，但他還有另外一個身份：清華姚班2008屆校友，也是姚班的開山弟子。
貝小輝是遼寧人，高中就讀於競賽名校東北育才學校，作為當年的全國信息學競賽金牌選手，貝小輝於2004年保送至清華計算機系。
2005年，姚班第一次在校內招生的時候，貝小輝與樓天城、鬲融等人一併被錄取，他畢業之後繼續選擇了研究，師從姚期智攻讀博士學位，曾獲得微軟亞洲研究院2011年度“微軟學者”獎學金。
2012年獲得博士學位之後，先後在南洋理工大學、Max Planck Institute for Informatics擔任研究員。
主要研究興趣是計算經濟學、社交網絡分析和通用算法設計等主題，在各大頂級會議與期刊上發表了超過20多篇論文。
第二位作者，是貝小輝的直系學弟——姚班2016級的在讀本科生李子豪，同樣也是一名信息學競賽高手。
李子豪是廣東佛山人，高中就讀於南海石門中學。2015年拿下全國信息學競賽金牌之後，獲得2016年高考直接保送清華大學的資格。
清華大學叉院介紹稱，這次的科研工作，是他2019年春季學期在新加坡南洋理工大學貝小輝助理教授研究組訪問交流時的合作成果，論文的作者以姓氏首字母排序。
△ 李子豪（左一）與貝小輝（右三）研究組，圖片來自清華叉院公眾號
這背後，是姚班自2016年全面推行春研製度，要求本科生在大三的春季，赴海內外頂尖高校科研交流，現在已經是姚班培養方案的重要環節。
從這篇頂會論文成果來看，也逐漸形成了畢業校友與在校本科生的傳幫帶的學術傳承。
值得一提的是，這並不是姚班學生第一次在公平分配領域拿下頂會最佳論文。
根據清華叉院報道，姚班2010級本科生王君行，曾憑藉公平分配領域單一商品最大最小分配的近似公平方案，獲得第15屆ACM計算經濟學國際學術大會的最佳學生論文獎。
“清華姚班”已經形成和正在探索的諸多機制。
或許也能為更多優秀人才的培養提供借鑑。可謂開風氣之先，又利在千秋。
你說呢？
論文地址：https://arxiv.org/pdf/1911.07048.pdf
— 完 —
量子位 QbitAI · 頭條號簽約
關注我們，第一時間獲知前沿科技動態
閱讀更多 量子位 的文章
