7 September 2021 – NUS Computing Assistant Professor Warut Suksompong and his research collaborators won the Distinguished Paper Award at the 2021 International Joint Conference on Artificial Intelligence (IJCAI 2021), held online from 19 to 26 August 2021.
Founded in 1969, IJCAI gathers artificial intelligence (AI) researchers and practitioners from all over the world to communicate advances and achievements in AI research.
Of the 587 papers accepted for the conference (from a total of 4,204 that were submitted), only three received the Distinguished Paper Award.
Dr Suksompong and his collaborators, Dr Edith Elkind (University of Oxford) and Dr Erel Segal-Halevi (Ariel University), won the award for their paper titled ‘Keep Your Distance: Land Division With Separation’.
Straddling the research areas of algorithmic game theory and computational social choice, the paper explores ways in which land can be allocated fairly among interested parties (or ‘agents’) – especially when there are real-world constraints.
“An important constraint that we handle is separation: where the parts are separated from each other under certain criteria,” said Dr Suksompong, “for example, we may want to leave sufficient space between adjacent pieces of land to prevent dispute between different owners, avoid cross‐fertilisation of different crops, and provide separate access to the plots.”
This resource allocation problem, also known as fair division, has been studied by Dr Suksompong for many years.
While this IJCAI paper explores fair division of land, which is a ‘two-dimensional’ resource, earlier this year, Dr Suksompong investigated separation constraints in the allocation of ‘one-dimensional’ resources in a paper published at 35th AAAI Conference on Artificial Intelligence.
According to Dr Suksompong, there are a couple of new challenges to handle in the fair division of two-dimensional resources.
“We can think of a one-dimensional resource (such as space along a street) as a line, while a two-dimensional resource (such as land) can be represented as a shape,” said Dr Suksompong.
“When dividing a one-dimensional resource, the shape of the resource does not matter, because each agent simply gets an interval of the line. On the other hand, for two-dimensional resources, the shape of the resource that each agent gets matters – a 5 metre × 500 metre piece of land is unlikely to be very useful even though its area is large,” he added.
Therefore, several common ways to divide the resources that work in one-dimensional situations will not yield meaningful results (or fairness guarantees) in two-dimensional situations.
To combat this, Dr Suksompong and his collaborators came up with a solution that involves the fair division notion known as ‘maximin share fairness’.
“With the maximin share fairness notion, we’re trying to answer the question of how to make the least valuable part as valuable as possible,” said Dr Suksompong, “and we found that using an approximate version of maximin share fairness provides meaningful fairness guarantees.”
“This works by dividing the resource among a larger number of agents than the actual number – resulting in a lower agent ‘satisfaction bar’ than the standard maximin share fairness, and we showed in our paper that this bar can be met,” he added.
