A Lahore University of Management Sciences (LUMS) alumnus Haris Aziz, along with co-author Simon Mackenzie, has finally come up with a solution to a problem that has been plaguing scientists for many years: how to allocate resources fairly to any number of people so that each is left satisfied with his/her share.
“My co-author Simon Mackenzie and I started working on this particular problem around 18 months ago. We are both based at Data61 and UNSW in Sydney. The problem for four or more persons was unresolved for years. We first came up with an algorithm for the case of four persons,” Haris Aziz said.
“The paper has been accepted at STOC (a prominent theoretical computer science conference) and will be presented in Boston this June. Our latest algorithm is more general and was shared with experts a few weeks ago,” he added.
Their paper, titled, A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents, was published on the Cornell University Library archive site in April.
Dividing a thing in two fairly is easy enough, but when there are more people involved, that’s when the task becomes more difficult. In the 20th century, John Selfridge and John Conway independently developed a solution for envy-free cake cutting for three people.
The cake is only a metaphor for any kind of divisible good, be it time, property settlement, or computing resources. “As technology improves, many problems will arise and be solved on electronic platforms. One interesting application area of fair division algorithms is allocating access to cloud computing resources. Fair allocation algorithms also have the potential to identify desirable solutions in complex automated negotiation settings,” Aziz said.
Earlier this year, Aziz, a senior research scientist, was named among ‘AI’s 10 to Watch’ by the IEEE Intelligent Systems magazine. ‘AI’s 10 to Watch’ acknowledges 10 researchers who are upcoming professionals in the field of artificial intelligence (AI), an official statement said.
Aziz shares that cake cutting is just one of the problems within the wider field of multi-agent resource allocation. “Other problems include assigning credit in a joint project and sharing supply chain costs. Another important application of allocation algorithms is efficient exchange of donated organs such as kidneys to save lives.”
Their solution has been described as a “major breakthrough” by Professor Steven Brams at New York University, who has worked on such problems for more than 20 years. Although the paper is yet to be peer reviewed, Professor Brams told the Sydney Morning Herald the “results look solid”.
However, he also said that the Aziz-Mackenzie protocol is too complex for practical application and Aziz agrees with him. “Not only is the algorithm complex but the number of steps it takes to get the job done can be too high in the worst case. So our result should be viewed as a mathematical result rather than a practical engineering result.”
“Having said that, many experts previously thought that there was no algorithm that takes a bounded number of steps or cuts even for four persons. Now that we have a bounded algorithm, it provides hope to refine the ideas to get better bounds. Some of the mathematical ideas and algorithmic techniques may be useful for other problems,” he added.
Another researcher in this field Ariel Procaccia at Carnegie Mellon University in Pittsburgh told the Herald, “I was convinced that a bounded, envy-free cake-cutting algorithm [did] not exist. So the breakthrough result of Aziz and Mackenzie is nothing short of amazing. It is a beautiful piece of mathematics.”
 alumnus Haris Aziz, along with co-author Simon Mackenzie, has finally come up with a solution to){kind=link}