The 34th AAAI Conference on Artificial Intelligence (AAAI-20) now underway in New York, USA from Feb. 7-12, just announced the Best Papers of 2020, and the Outstanding Student Paper Award was granted to Fair Division of Mixed Divisible and Indivisible Goods, jointly written by Zihao Li, Yao Class undergraduate, Xiaohui Bei, assistant professor at Nanyang Technological University & Yao Class alumnus, and other scholars from HKU and NTU.
The paper studies the classical problem of fair division in game theory when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, they propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. Finally, they relax the envy-free requirement, instead asking for ǫ-envy-freeness for mixed goods (ǫ-EFM), and present an algorithm that finds an ǫ-EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and 1/ǫ. Previously, a former Yao Class student Junxing Wang also won a Best Student Paper Award in this field for the paper Fair Enough: Guaranteeing Approximate Maximin Share on the Fifteenth ACM Conference on Economics and Computation, EC'14.
This work was conducted during Zihao Li’s visit to Prof. Xiaohui Bei at Nanyang Technological University in the spring semester of 2019. The visit was supported by an Overseas Visit Program of Yao Class, which was initiated in 2016 to facilitate the research collaborations between Yao Class students and the scientists including Yao Class alumni in the world-renowned universities.
AAAI is a premier conference in artificial intelligence. This year, 1591 papers were selected from 8800 submissions for the conference with a paper acceptance rate of 20.6 percent.
The full paper is available at https://arxiv.org/pdf/1911.07048.pdf
(By Yuying Chang)
