乾明魚羊發(fā)自凹非寺
　　量子位報(bào)道公眾號(hào) QbitAI

　　江湖英雄輩出，又是姚班少年郎。

　　第 34 屆美國人工智能協(xié)會(huì)年會(huì) AAAI 2020 現(xiàn)場(chǎng)，又一重要獎(jiǎng)項(xiàng)揭曉。

　　最佳學(xué)生論文獎(jiǎng)，頒向《可分割與不可分割商品混合情況下的公平分配》（Fair Division of Mixed Divisible and Indivisible Goods）。

　　論文作者：李子豪、貝小輝，都出自清華姚班。

　　貝小輝是姚班首屆弟子、樓教主鬲融的同班同學(xué)，而李子豪更是姚班 2016 級(jí)本科生——目前在讀。

　　AAAI 2020 最佳學(xué)生論文

　　這篇獲得最佳學(xué)生論文獎(jiǎng)的論文，研究了當(dāng)資源同時(shí)包含可分割商品及不可分割商品時(shí)的公平分配問題。

　　公平分配問題是博弈論與算法博弈論的經(jīng)典問題。是指為若干個(gè)分配者分配有限數(shù)量的資源時(shí)的博弈。

　　當(dāng)資源為一種物質(zhì)又可分割時(shí)，分配將會(huì)很容易進(jìn)行。但資源種類復(fù)雜、不可分，而分配者的喜好各不相同時(shí)，分配將會(huì)難以進(jìn)行。比如將 17 頭品種不同的活牛分給 3 個(gè)人。

　　基于傳統(tǒng)無嫉妒性（envy-freeness，EF）與單一商品的無嫉妒性（envy-freeness up to one good, EF1）的經(jīng)典公平問題概念，研究者提出了一個(gè)在可分割與不可分割混合情況下更為有意義的公平性質(zhì)，即混合商品的無嫉妒性（envy-freeness for mixed goods, EFM）。

　　以往的研究主要都是單獨(dú)考慮可分或不可分情況下的公平分配的問題，而缺少對(duì)于兩種商品混合情況下的公平分配的研究，該研究成果將 EF 和 EF1 都推廣到了混合環(huán)境中。

　　研究人員證明了，對(duì)于任意數(shù)量的智能體（agents）而言，滿足 EFM 性質(zhì)的分配一定存在，并提出了一個(gè)有效算法，以計(jì)算 2 個(gè)智能體和n個(gè)智能體的 EFM 分配問題，并對(duì)可分割商品進(jìn)行分段化線性評(píng)估。

　　在放寬對(duì)無嫉妒性的要求，轉(zhuǎn)而要求針對(duì)混合商品的?-無嫉妒性（?-EFM）后，研究人員提出?-EFM 算法，使其在一定的智能體數(shù)量、一定的不可分割商品數(shù)量和的 1 /?的情況下，找到時(shí)間多項(xiàng)式的?-EFM 分配。

　　研究人員認(rèn)為，混合商品環(huán)境中的公平分配編碼了一個(gè)豐富的結(jié)構(gòu)，并創(chuàng)造了一個(gè)新的研究方向，非常值得后續(xù)探索。

　　姚班畢業(yè)生與姚班本科生的聯(lián)手

　　這篇論文雖然署名有三個(gè)機(jī)構(gòu)：新加坡南洋理工、清華大學(xué)和香港大學(xué)，但清華、清華姚班顯然是最大贏家。

　　論文第一作者貝小輝，現(xiàn)在是新加坡南洋理工大學(xué)助理教授，但他還有另外一個(gè)身份：清華姚班 2008 屆校友，也是姚班的開山弟子。

　　貝小輝是遼寧人，高中就讀于競(jìng)賽名校東北育才學(xué)校，作為當(dāng)年的全國信息學(xué)競(jìng)賽金牌選手，貝小輝于 2004 年保送至清華計(jì)算機(jī)系。

　　2005 年，姚班第一次在校內(nèi)招生的時(shí)候，貝小輝與樓天城、鬲融等人一并被錄取，但與樓天城不同的是，他畢業(yè)之后繼續(xù)選擇了研究，師從姚期智攻讀博士學(xué)位，曾獲得微軟亞洲研究院 2011 年度“微軟學(xué)者”獎(jiǎng)學(xué)金。

　　2012 年獲得博士學(xué)位之后，先后在南洋理工大學(xué)、Max Planck Institute for Informatics 擔(dān)任研究員。

　　主要研究興趣是計(jì)算經(jīng)濟(jì)學(xué)、社交網(wǎng)絡(luò)分析和通用算法設(shè)計(jì)等主題，在各大頂級(jí)會(huì)議與期刊上發(fā)表了超過 20 多篇論文。

　　第二位作者，是貝小輝的直系學(xué)弟——姚班 2016 級(jí)的在讀本科生李子豪，同樣也是一名信息學(xué)競(jìng)賽高手。

　　李子豪是廣東佛山人，高中就讀于南海石門中學(xué)。2015 年拿下全國信息學(xué)競(jìng)賽金牌之后，獲得 2016 年高考直接保送清華大學(xué)的資格。

　　清華大學(xué)叉院介紹稱，這次的科研工作，是他 2019 年春季學(xué)期在新加坡南洋理工大學(xué)貝小輝助理教授研究組訪問交流時(shí)的合作成果，論文的作者以姓氏首字母排序。

李子豪（左一）與貝小輝（右三）研究組，圖片來自清華叉院公眾號(hào)

　　這背后，是姚班自 2016 年全面推行春研制度，要求本科生在大三的春季，赴海內(nèi)外頂尖高校科研交流，現(xiàn)在已經(jīng)是姚班培養(yǎng)方案的重要環(huán)節(jié)。

　　從這篇頂會(huì)論文成果來看，也逐漸形成了畢業(yè)校友與在校本科生的傳幫帶的學(xué)術(shù)傳承。

　　值得一提的是，這并不是姚班學(xué)生第一次在公平分配領(lǐng)域拿下頂會(huì)最佳論文。

　　根據(jù)清華叉院報(bào)道，姚班 2010 級(jí)本科生王君行，曾憑借公平分配領(lǐng)域單一商品最大最小分配的近似公平方案，獲得第 15 屆 ACM 計(jì)算經(jīng)濟(jì)學(xué)國際學(xué)術(shù)大會(huì)的最佳學(xué)生論文獎(jiǎng)。

　　“清華姚班”已經(jīng)形成和正在探索的諸多機(jī)制。

　　或許也能為更多優(yōu)秀人才的培養(yǎng)提供借鑒。可謂開風(fēng)氣之先，又利在千秋。

　　你說呢？

　　論文地址：

　　https://arxiv.org/pdf/1911.07048.pdf

總結(jié)

以上是生活随笔為你收集整理的清华姚班“斩获”AAAI 2020最佳学生论文的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。