UMD Team Led by Hajiaghayi Designs New Algorithm for "Envy-Free" Task Division

Mon Feb 12, 2018

A team of University of Maryland researchers has come up with a new algorithm designed to fairly divide tasks amongst any number of individuals in a group.

Led by Mohammad T. Hajiaghayi (in photo), the Jack and Rita G. Minker Professor of Computer Science, the UMD team solved a 40-year-old challenge first proposed by famed mathematician Martin Gardner in his influential 1978 book, "Aha! Insight."

Gardner's problem is the dual variant of a well-known cake-cutting problem, where the goal is to divide a desirable cake amongst individuals. The challenge is to have each person accept the piece they receive, even if the sizes vary.

"Envy-free Chore Division for An Arbitrary Number of Agents"—co-authored by Hajiaghayi and UMD computer science doctoral students Sina Dehghani, Alireza Farhadi and Hadi Yami—offers the first bounded algorithm able to allocate a task between an arbitrary number of individuals in an envy-free manner.

The researchers recently unveiled their work at the ACM-SIAM Symposium on Discrete Algorithms 2018 (SODA '18), which was held in January in New Orleans, Louisiana.

Hajiaghayi says that envy-free task division is an important problem to address because the topic has become an integral issue in professional life, and also applicable in local and regional governance issues.

In any large public project such as building a new Metro line, a road, or an oil pipeline system—all of which may pass through several cities, counties, states or even countries—there is always discussion about what the fair division of costs will be considering the benefits that each entity receives, Hajiaghayi explains.

"In any real-life problem, cost versus benefits is usually the most important measure to consider for each entity involved—whether it's a contractor, worker, or computer," he says. "Of course, when there is more than one entity involved, the fair division of costs and benefits among these entities is the most essential problem."

In solving the task-division problem, the UMD team took into account that each individual might have different preferences over different parts of the task. Their objective was to find an allocation that divides the task into the smallest possible number of parts such that no envy arises between individuals.

Yami, a third-year doctoral student advised by Hajiaghayi, says solving this problem was challenging in part due to its complexity, and also because prior studies on this subject to reference were very limited.

While the main objective of the team's research is in managing and assigning small, defined tasks involving complex projects, their findings could also be applied to dividing various computational tasks amongst computers with different processing powers, says Farhadi, a second-year doctoral student advised by Hajiaghayi.

"We anticipated using our results in dividing a task between selfish individuals," he says. "But we also think our tools could be very useful in solving other allocation problems that are computing related."

-Story by Melissa Brachfeld