New AI framework introduced for cutting a 'multi-layered cake'

Jessica Hallman
April 14, 2021

UNIVERSITY PARK, Pa. — Imagine two students, Alice and Bob, who would each like to reserve multiple facilities at Penn State — such as a conference room in which to study and a room at the gym where they can exercise. Each facility can only be used by one student at a time, and these students may wish to access each room at different times of the day.

Many organizations use software driven by artificial intelligence to allocate resources among their constituents, for example, to schedule facilities among students, faculty and staff at a university. The algorithms in these tools are designed to give optimal results to maximize resources. But are they fair? Will Alice and Bob be happy with the rooms and times that are assigned to them?

To find out, a team of researchers, including Hadi Hosseini, assistant professor at the Penn State College of Information Sciences and Technology, explored if fair division of time could be achieved across multiple resources in a recent study.

“In many such scenarios, what is crucial to consider is fairness of the solution,” said Hosseini. “Obviously, you can develop algorithms to optimally utilize the available resources, but these solutions could be very unfair to some stakeholders.

Expanding on an established problem in mathematics and computer science known as fair cake-cutting — a metaphor for cutting a cake in a way that each participant receives a slice that they believes to be fair — Hosseini and his team introduce a novel concept of "multi-layered cake-cutting" to achieve fairness when distributing access time over multiple resources. In the hypothetical multi-layer cake, each layer represents an allocable resource.

The researchers enforced the concepts of feasibility, which ensures that overlapping resources are not assigned to one individual, and contiguity, which ensures that the resource is allocated to everyone for a continuous time and not split into multiple sections of time throughout the day. Under these conditions, they wanted to learn if they could achieve fairness guarantees of envy-freeness, in which no person envies another, or the slightly weaker concept of proportionality, the concept in which the partition that an individual can receive by assuming that everyone else’s preferences are identical to their own.

“It turns out, when we introduce these constraints and model these problems in multi-layer cake-cutting with these types of natural constraints, the problem actually becomes very difficult,” said Hosseini. “It requires its own subtle protocols and additional algorithmic techniques to be able to guarantee fairness when time-sharing the available resources.”

In their study, the researchers enhanced the existing concept of "cut-and-choose," where one person cuts the “cake” into two pieces and the other chooses a piece first. The researchers expanded the cake to two layers to represent two resources and introduced the concept of making diagonal cuts over those two layers. They found that their method can achieve proportional allocations for any number of individuals when enforcing the constraints of feasibility and contiguity as long as the number of divisible resources is an even number.

“That was one of the interesting things that we found, so we can break the problem into smaller problems that way and solve those using the solutions we developed for the case with only two layers,” said Hosseini.

They further expanded their methods when introducing a third person seeking a fair share of two divisible resources. To accommodate, they applied the "moving-knife procedure" — an existing type of solution to fair division used in game theory — to multiple layers. This introduced a multi-knife approach with a short knife moving over the top layer from left to right, and a long knife pointing to the spot on the cake that would cut the across all layers in an envy-free manner.

“That guarantees a solution that is envy-free for all three agents under some assumptions,” said Hosseini.

They found, however, that contiguity is a strong requirement. But once that condition is removed, they were able to show positive results for any number of individuals or layers.

“My overall goal in research is to try to develop algorithmic solutions with provable fairness or provable societal guarantees,” said Hosseini. “In this work, we proposed a new mathematical framework through which we solved some of the open problems, but we also introduced several new problems in this field that are open for further studies, from mathematical and algorithmic perspectives,” said Hosseini.

Hosseini collaborated with Ayumi Igarashi, assistant professor at the National Institute of Informatics, and Andrew Searns, research associate at the College of IST. They presented their work at the International Joint Conference on Artificial Intelligence – Pacific Rim International Conference on Artificial Intelligence in January. Hosseini’s work was funded by the National Science Foundation.

Last Updated June 28, 2021