清华姚班本科生及校友获得第34届美国人工智能协会年会最佳学生论文奖
清华新闻网2月11日电 2月7日-12日，第34届美国人工智能协会年会（National Conference on Artificial Intelligence, AAAI 2020）在美国纽约召开。其中，由姚班2016级本科生李子豪同学和姚班2004级校友、新加坡南洋理工大学助理教授贝小辉等合作完成的论文《可分割与不可分割商品混合情况下的公平分配》（Fair Division of Mixed Divisible and Indivisible Goods）获得大会最佳学生论文奖。
李子豪（左一）与贝小辉（右三）研究组
公平分配问题是博弈论与算法博弈论的经典问题。该论文研究了当资源包含可分割商品及不可分割商品时的公平分配问题。基于传统无嫉妒性（envy-freeness，EF）与单一商品的无嫉妒性（envy-freeness up to one good, EF1）的经典公平问题概念，研究者提出了一个在可分割与不可分割混合情况下更为有意义的公平性质，即混合商品的无嫉妒性（envy-freeness for mixed goods, EFM）。以往的研究主要都是单独考虑可分或不可分情况下的公平分配的问题，而缺少对于两种商品混合情况下的公平分配的研究，此成果是EF和EF1针对混合商品集合的直接通用化结果，在EFM存在性与近似解求解的问题上均取得理想结果。研究者证明了满足EFM性质的分配一定存在，并提出了一个有效算法，可计算近似公平 (
) 的分配方式的复杂度为poly (n,1/
) 。值得一提的是，姚班2010级本科生王君行，曾凭借公平分配领域单一商品最大最小分配的近似公平方案，获得第15届ACM计算经济学国际学术大会（The Fifteenth ACM Conference on Economics and Computation ，EC'14）的最佳学生论文奖。相隔六年，他的学弟李子豪在同一领域针对混合商品再获研究突破。此项科研工作是李子豪同学于2019年春季学期在新加坡南洋理工大学贝小辉助理教授研究组访问交流时的合作成果，论文的作者以姓氏首字母排序。自2016年全面推行春研制度以来，大三春季赴海内外顶尖高校科研交换已成为姚班培养方案的重要环节，并逐渐形成毕业校友与在校本科生的学术传承特色，产生了多个优秀合作成果。
AAAI是国际人工智能领域中最主要的学术会议之一。本届 AAAI 大会共收到8800 投稿论文，评审7737篇，并最终接收1591篇，接收率为 20.6％。
论文原文链接：https://arxiv.org/pdf/1911.07048.pdf
供稿：交叉信息研究院
编辑：吕婷
审核：戚天雷
2020年02月11日 13:19:34 清华新闻网
