Highlight: Fair Division of Resources

Posted 19/02/2020

Prof. Bei Xiaohui and his team
The team that won the AAAI Outstanding Student Paper Award for their work on “Fair Division of Mixed Divisible and Indivisible Goods”. From left: Nanyang Asst. Prof. Xiaohui Bei, Jinyan Liu, Dr Shengxin Liu, and Xinhang Lu.

The equitable distribution of limited resources is one of the most pressing problems in the world today. For instance, how should greenhouse gas emission limits be divided between developed and developing countries? How should housing units be distributed among eligible households, who might have different needs and preferences? Such questions have long preoccupied thinkers in numerous fields, including political scientists, economists, computer scientists, and mathematicians.

A team from Nanyang Technological University (NTU), led by Nanyang Assistant Professor Xiaohui Bei, has developed a new mathematical framework for approaching such “fair division” problems. Their paper, “Fair Division of Mixed Divisible and Indivisible Goods”, was awarded the Outstanding Student Paper Award at the AAAI Conference at Artificial Intelligence held from February 7—12, 2020 in New York, USA.

In the past, the literature on fair division has focused on two classes: (i) the allocation of divisible resources, such as land or time, and (ii) the allocation of indivisible resources, such as housing units or vehicle licenses. These two classes have always been treated as completely separate. In their paper, Prof. Bei and his team propose a new mathematical definition that captures the notion of fair division for both divisible and indivisible resources.

“This is the first unified solution that merges the two classes of goods into a single coherent setting,” says Prof. Bei. “Moreover, we managed to prove that there exists an efficient method for finding what mathematicians call an ‘envy-free’ allocation of these mixed goods — an allocation that makes every participant feel sufficiently satisfied.”

The AAAI Outstanding Student Paper Award acknowledges the contributions of Xinhang Lu, a third year PhD student in Prof. Bei's group at NTU, as well as Dr Shengxin Liu, a research fellow at NTU, and two visiting undergraduate students Zihao Li (Tsinghua University) and Jinyan Liu (University of Hong Kong). The AAAI conference is the world's largest scientific conference in the emerging field of Artificial Intelligence (AI). This year's conference received almost 8000 paper submissions, and only one Outstanding Student Paper award is given out each year.

Xiaohui Bei, Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu, Fair Division of Mixed Divisible and Indivisible Goods, arxiv:arXiv:1911.07048