清華姚班本科生及校友獲得第34屆美國(guó)人工智能協(xié)會(huì)年會(huì)最佳學(xué)生論文獎(jiǎng)

清華新聞網(wǎng)2月11日電 2月7日-12日，第34屆美國(guó)人工智能協(xié)會(huì)年會(huì)（National Conference on Artificial Intelligence, AAAI 2020）在美國(guó)紐約召開(kāi)。其中，由姚班2016級(jí)本科生李子豪同學(xué)和姚班2004級(jí)校友、新加坡南洋理工大學(xué)助理教授貝小輝等合作完成的論文《可分割與不可分割商品混合情況下的公平分配》（Fair Division of Mixed Divisible and Indivisible Goods）獲得大會(huì)最佳學(xué)生論文獎(jiǎng)。

李子豪（左一）與貝小輝（右三）研究組

      公平分配問(wèn)題是博弈論與算法博弈論的經(jīng)典問(wèn)題。該論文研究了當(dāng)資源包含可分割商品及不可分割商品時(shí)的公平分配問(wèn)題?；趥鹘y(tǒng)無(wú)嫉妒性（envy-freeness，EF）與單一商品的無(wú)嫉妒性（envy-freeness up to one good, EF1）的經(jīng)典公平問(wèn)題概念，研究者提出了一個(gè)在可分割與不可分割混合情況下更為有意義的公平性質(zhì)，即混合商品的無(wú)嫉妒性（envy-freeness for mixed goods, EFM）。以往的研究主要都是單獨(dú)考慮可分或不可分情況下的公平分配的問(wèn)題，而缺少對(duì)于兩種商品混合情況下的公平分配的研究，此成果是EF和EF1針對(duì)混合商品集合的直接通用化結(jié)果，在EFM存在性與近似解求解的問(wèn)題上均取得理想結(jié)果。研究者證明了滿(mǎn)足EFM性質(zhì)的分配一定存在，并提出了一個(gè)有效算法，可計(jì)算近似公平 () 的分配方式的復(fù)雜度為poly (n,1/) 。值得一提的是，姚班2010級(jí)本科生王君行，曾憑借公平分配領(lǐng)域單一商品最大最小分配的近似公平方案，獲得第15屆ACM計(jì)算經(jīng)濟(jì)學(xué)國(guó)際學(xué)術(shù)大會(huì)（The Fifteenth ACM Conference on Economics and Computation ，EC'14）的最佳學(xué)生論文獎(jiǎng)。相隔六年，他的學(xué)弟李子豪在同一領(lǐng)域針對(duì)混合商品再獲研究突破。

此項(xiàng)科研工作是李子豪同學(xué)于2019年春季學(xué)期在新加坡南洋理工大學(xué)貝小輝助理教授研究組訪(fǎng)問(wèn)交流時(shí)的合作成果，論文的作者以姓氏首字母排序。自2016年全面推行春研制度以來(lái)，大三春季赴海內(nèi)外頂尖高?？蒲薪粨Q已成為姚班培養(yǎng)方案的重要環(huán)節(jié)，并逐漸形成畢業(yè)校友與在校本科生的學(xué)術(shù)傳承特色，產(chǎn)生了多個(gè)優(yōu)秀合作成果。

AAAI是國(guó)際人工智能領(lǐng)域中最主要的學(xué)術(shù)會(huì)議之一。本屆 AAAI 大會(huì)共收到8800 投稿論文，評(píng)審7737篇，并最終接收1591篇，接收率為 20.6％。

論文原文鏈接：https://arxiv.org/pdf/1911.07048.pdf

供稿：交叉信息研究院

編輯：呂   婷

審核：戚天雷