The School of Computing at NUS is set in tranquil surroundings — buildings atop gentle hills are connected by breezy walkways, and research labs and classrooms look out onto lush tropical vegetation. In recent months, however, the views have been tainted by an eyesore: a monstrous construction site.
When completed, the site will transform into the school’s new wing, a curved building in calming hues of cream and brown, topped off with an inspiring name: Computing 3 (COM3) @ Imagination Ridge. As students and faculty members pass by the construction boards, they imagine multipurpose halls, sun-lit offices, a high-ceilinged foyer, a terrace canteen, and other gleaming new facilities.
But Warut Suksompong sees the site and thinks of something else: how can we allocate the newly available office space in a manner that’s fair to all?
“It’s desirable that those in the same research group be situated close to one another for convenience and to facilitate communication,” says Suksompong, an assistant professor at NUS Computing and an NUS Presidential Young Professor, whose research includes algorithmic game theory and computational social choice theory.
“It matters that each research group should get a contiguous block of offices, rather than someone getting an office at one end of the corridor and another at the opposite end or one group getting all the cubicles on the border of a big room,” he says. “It’s not just about being connected, but being well-connected in an intuitive sense.”
This resource allocation problem (called ‘fair division’) is something that researchers — economists, mathematicians, and now computer scientists such as Suksompong — have been studying for decades. He summarises the problem as such: “You have a resource that you want to allocate to interested parties. How can you do this in a fair way?”
But it’s only in recent years that academics have approached the problem in a new light. “Most of the literature doesn’t take into account the constraints that arise in practical applications,” says Suksompong. “They assume that you can allocate the resource in whatever way you want.”
The real world, unfortunately, isn’t quite as straightforward. Not everyone can have a corner office or enjoy one with great views that’s close to both the elevator and pantry.
But if that’s the case, how can resources best be divided when there are real-world constraints? Such restrictions may include requirements that the resource be divided in such a way that the parts remain well-connected (like in the office scenario above). Or that the parts have to be separated from one another under certain criteria (think Covid social distancing guidelines). These are known as connectivity and separation constraints, respectively.
It’s all about connection
“Different constraints require different tools to tackle them,” says Suksompong, who first began studying the topic while pursuing a PhD at Stanford University more than 6 years ago.
He was drawn to cake cutting because “there are so many real-world applications out there.” Another attraction was that the “mathematical side of things is also very interesting — it involves many elegant tools,” he says.
“It’s about how you tie together and apply mathematical tools, technical tools etc. to these problems that appear in the real world,” he explains. “That’s what I find attractive about this area.”
Suksompong explored the office allocation problem in a recent paper that was presented at the 35th AAAI Conference on Artificial Intelligence in February. The problem is one of connectivity constraints.
Suksompong and his collaborators — from Singapore’s Nanyang Technological University and the Japan’s National Institute of Informatics — used graphs to estimate the fairness of a particular allocation. To do so, they studied floor plans and modelled them as graphs.
“The vertices of the graph are offices. If two offices are adjacent to each other, then we add an edge between them,” he explains.
The researchers then analysed how well-connected each point was to the others — the greater the number of lines emanating from each point, the better its connection. For instance, 10 offices placed in a single row (represented as 10 points on a straight line) will have fewer connections than if they were arranged in a circle.
“The graph depends on how well-connected your topology or floor plan is,” says Suksompong. “The more connected a graph is, the stronger the fairness guarantee we can provide.”
Give me space, please
For another paper, presented at the same conference, Suksompong studied the fair allocation of divisible items — also known as ‘cake cutting’, this time considering separation constraints. The problem can be found in many real-world scenarios: for example, vendors at an exhibition post-Covid setting up their stalls at a safe distance apart, a farmer looking to maintain some space between his crops to prevent cross-fertilisation, or a lab researcher having to wait while a machine cleans itself or erases data from a previous session.
A key aspect of cake cutting lies with the idea of proportionality, where each agent can expect to receive her proportionally fair share of cake. But when separation constraints are imposed, proportionality cannot always be satisfied.
In such instances, the next best thing is to apply the ‘maximin share fairness’ concept to cake cutting, argue Suksompong and his collaborators (this time from the University of Oxford). “With maximin share fairness, we’re trying to answer the question of how to make the least valuable part as valuable as possible,” explains Suksompong.
“Maximin share fairness provides a robust version of proportionality that can be adjusted to fit the separation constraint in cake cutting,” he says.
Since then, Suksompong and his collaborators have written two follow-up papers, which will be presented at the 30th International Joint Conference on Artificial Intelligence (IJCAI) in August. A new aspect the researchers explored is two-dimensional resources, for example the area of a particular land.
“The area matters because it makes a difference whether the land you get is nice and round, or long and thin,” says Suksompong. This is quite different from analysing one-dimensional resources such as dividing a road network among construction companies, where size and shape doesn’t matter too much.
Suksompong remains passionate about his chosen area of research. “I believe fair division has a lot of potential to resolve conflicts and improve equitability,” he says. “I look forward to continuing to bridge the gap between theory and practice in my research.”
Papers:
The Price of Connectivity in Fair Division
Mind the Gap: Cake Cutting With Separation
