Pakistani makes major breakthrough in longstanding mathematics problem

Published: May 27, 2016
Email
LUMS alumnus Haris Aziz along with Simon Mackenzie has come up with solution to problem plaguing scientists for years PHOTO COURTESY: lums.edu.pk

LUMS alumnus Haris Aziz along with Simon Mackenzie has come up with solution to problem plaguing scientists for years PHOTO COURTESY: lums.edu.pk

Lahore University of Management Sciences (LUMS) alumnus Haris Aziz, along with co-author Simon Mackenzie, has come up with a solution to a problem that has been plaguing scientists for 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, while speaking to The Express Tribune.

LUMS alumni named among top AI researchers to watch

“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.”

Pakistani scientist develops device to diagnose cancer rapidly

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.”

Facebook Conversations

Reader Comments (20)

  • leela4fun
    May 27, 2016 - 2:11PM

    Congratulations! Good job!

    Just wondering how the cake cutting would work if the army took the lion’s share and the leaders gobbled up the rest leaving 200 million to lick the crumbs or forced to eat grass.Recommend

  • Baloch
    May 27, 2016 - 3:07PM

    Pakistani Tujhe Salam. :)Recommend

  • Umar
    May 27, 2016 - 3:09PM

    Nice! Congratulations! Recommend

  • bharat
    May 27, 2016 - 4:53PM

    Congrats young man.You made your country proudRecommend

  • Raj - USA
    May 27, 2016 - 8:20PM

    This is nothing new. The problematic issue is
    “how to allocate resources fairly to any number of people so that each is left satisfied with his/her share.”

    Dr. Zardari found a solution and made breakthrough years ago. He named it “NRO”.Recommend

  • hamza khan
    May 28, 2016 - 1:24AM

    @leela4fun:
    only an indian with a inferiority complex could make that statement. hahahaRecommend

  • Naveed
    May 28, 2016 - 2:28AM

    Nothing new in this work. LUMS promo 101Recommend

  • Mehran
    May 28, 2016 - 5:37AM

    Oh boy, now a college paper on resource distribution is MAJOR break through? No one else seems to be saying that except in Pakistan..Recommend

  • Ali khan
    May 28, 2016 - 10:36AM

    @mehran
    If you had only read the article, the original story is from Sydney morning herald. Also experts have called it a breakthrough. Why are people always so negative?Recommend

  • Hassan
    May 28, 2016 - 1:51PM

    Guys please, do not cloud scientific research with typical political rhetoric. Research is a long term process. Better to contribute than criticize. As they say, Rome wasn’t built in a day. Recommend

  • Luminite
    May 28, 2016 - 4:32PM

    Proud to be a Luminite<3 LUMS The Most Prestigious Institution of Pakistan<3Recommend

  • Hashk03
    May 28, 2016 - 4:58PM

    @Ali khan: @mehran If you had only read the article, the original story is from Sydney morning herald. Also experts have called it a breakthrough. Why are people always so negative?

    Because they are indian trolls disguised under many names. There only job is to leave comments negative against pakistan.Recommend

  • hoshiar singh gill
    May 28, 2016 - 9:19PM

    If a Pakistani youngman or woman does something unique he/she owed to be congratulated just like the rest. Well done ! God bless!Recommend

  • Sid
    May 29, 2016 - 1:10AM

    What was the breakthrough ? To realize 1 + 1 = 2 ? Haha. Pakistanis take credit for stale researches. Recommend

  • Shah
    May 29, 2016 - 12:14PM

    @Sid:
    Jealosy has no limits indeed.Recommend

  • Shah
    May 29, 2016 - 12:29PM

    @Sid:
    Yes I Am Sure Indian Research Is Far Ahead Of Us After All Your Gods Invested Spaceships and Atom Bombs Millions Of Years Ago lolRecommend

  • Ahmer
    May 29, 2016 - 3:32PM

    @Shah

    Let’s not making it a mud-slinging match. We should simply appreciate scientific progress wherever it comes from and not feed the trolls. Recommend

  • Mehran
    May 30, 2016 - 12:13AM

    @Ali khan: Sir, I did read the article as well as read the original solution provided by Marvin Stern in 1950’s or Selfridge Conway bounded method in 1960… or Procaccia method in 2009. Yes, it solves a problem but it wasn’t called a “Major Break Through” anywhere nor was it called “Major Breakthrough” by the Sydney Morning Herald.Recommend

  • Ahmer
    May 30, 2016 - 8:00AM

    @Mehran please search for “breakthrough” in the following article: http://www.smh.com.au/technology/sci-tech/fair-allocation-algorithm-that-cuts-cakes-and-may-settle-trump-divorces-20160502-gokmwt.html

    If you are not blind, you will find it.Recommend

  • G. Ali
    May 31, 2016 - 5:31AM

    The moment I saw the heading, I knew some Indian idiot would be here posting their idiotic comments, so thanks for living up to the expectations.Recommend

More in Pakistan