Let them cut cake!
Dr Haris Aziz, from Computer Science Engineering and CSIRO research group Data61, and collaborator Simon Mackenzie have followed in the footsteps of mathematical giants to solve the age-old problem of how to cut cake fairly.
We caught up with Aziz to congratulate him and hear about his plans to use algorithms to help refugees.
What is the cake-cutting problem?
It’s an abstract mathematical problem concerning the division of resources in a fair manner. One famous and well-established notion of fairness is called “envy-freeness”, which means you shouldn’t prefer somebody else’s allocation over yours. As a fundamental philosophical question, it has been studied for many years across a variety of disciplines.
The cake-cutting problem can be phrased in a very succinct manner: you’re given a divisible resource, you don’t know what people value about different parts of that resource, so you want to elicit enough preference information to allocate the resource in an envy-free manner. What is particularly nice about this problem is that an envy-free allocation is guaranteed to exist because it has been proven in various mathematical theorems.
When did mathematicians start examining it?
Dividing a cake (or resource) fairly between two people has been around since at least biblical times: it’s called the “divide and choose” algorithm. Basically, one person cuts the cake and the other person chooses which slice they want. But dividing a resource fairly between three or more people gets much more complex.
Famous Polish mathematician Hugo Steinhaus popularised it as the “cake cutting” problem after World War II, and mathematicians since have advanced it. For example John Conway, and John Selfridge in the 1960s, independently devised envy-free “bounded” algorithms for three people, and in the 1990s political scientist Steven Brams and mathematician Alan Taylor devised a protocol guaranteed to produce an “unbounded” envy-free division for four or more people.
However, an unbounded algorithm means that you never know when it’s going to finish – it could take days, years, decades, more – which is highly undesirable in computer science. So for the last 20 years, people have been actively trying to come up with a bounded algorithm for four or more people. This is the breakthrough that my co-author Simon Mackenzie (now a postdoctoral researcher at Carnegie Mellon) and I managed to achieve.
Did you have a eureka moment or was it a gradual step-by-step progress?
We’re working on a model as well as algorithms to help allocate refugees in a more methodical and fair manner. This will lead to much better social outcomes for everyone
Dr. Haris Aziz, UNSW Computer Scientist
There were a few moments when we were pretty excited but there were also weeks that were very frustrating. Our method was to take baby steps. We started by trying to find a bounded envy-free algorithm for four people and when we achieved that it took another year to devise one that can fairly divide a cake among any number of people.
The algorithm is extremely complicated and we are still really far from understanding the real complexity of finding an envy-free allocation, but at least now we know that it’s bounded. That’s the biggest breakthrough.
Are you going to continue working on the problem?
I’m not working on it at the moment but we do have some ideas about how to explore it further. Rather than try to speed the algorithm up, I’d like to simplify it to make it easier for more people to understand. There are other interesting extensions of this problem that are worth looking into, too. For example, this algorithm wouldn’t work for the division of things people don’t want – like tasks at work or chores in a share-house, for example.
Has there been much interest in your success?
An article about us in Scientific American was a highlight and we also made it into the main national German newspaper. We’ve also appeared in a few local news and radio venues, such as The Sydney Morning Herald. Peer recognition is obviously very important and in the theoretical computer science community there is a famous blog called Computational Complexity. It awarded us the Best Paper of the Year last year, which was great. We’ve given invited talks and my co-author, Simon, got his postdoc Carnegie Mellon position because of this. We wrote these results while he was a PhD student in our group, so it was a nice collaboration.
You were recently named in the IEEE Intelligent Systems top 10 AI Scientists to watch. What else are you working on?
My background is at the intersection of game theory and computer science. Whenever you’re trying to build algorithms or systems where you want to reason about rationality or fairness or stability, you can fuse ideas from game theory and computer science, and the interplay of these ideas can help come up with a lot of interesting applications.
For example, one problem we’re working on concerns the fair placement of refugees with hosts. Matching algorithms are already being used in a wide variety of applications (like matching students to universities, for example) and it’s a field that has actually won a Nobel Prize in economics. We’re looking at a new but related matching problem that was formalised in the literature recently. It’s called the “refugee-allocation problem” and it’s been motivated by recent events in Syria.
In the current system, refugees are often accommodated in a completely ad hoc manner even though they might have real preferences over where they’d like to go – to a country where they already have an established network of family or friends, for example. From a host’s perspective, they also have preferences over which refugees they’d prefer to take – people who speak a common language, for example, may find social integration easier.
We’re working on a model, as well as algorithms, to help allocate refugees in a more methodical and fair manner. This kind of allocation system has obvious social and economic benefits and is similar to the cake-cutting problem in a way, where you want to achieve a win-win social outcome and people feel like their opinions have been heard and they’ve been treated fairly.
Why do you love what you do? Where does your drive come from?
Firstly, I feel that my interests and skills are suitable for this kind of work. Secondly, I love the timeless nature of mathematics. But, more importantly, I just feel excited to be part of the story of ideas in this discipline. Even if the things I do are just footnotes to this greater story, it is still really exciting to be part of it.