Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Cut your cake and eat it (eventually)

      26 October, 2016

      Two computer scientists have made a breakthrough in the theory of cake cutting. They have found a new method to divide a cake between any number of people so that nobody is left envious of someone else. The result isn't only relevant to birthday parties: the cake can represent any continuous object, be it a piece of land, broadcasting time, or oil. Cake cutting theory is inspired by problems that come up in all sorts of contexts, from divorce proceedings to political conflicts.

      Cake

      Which piece do you want?

      The problem of dividing the cake is quite simple when there are only two people involved. Get the first person to cut the cake and the second to choose the piece they want. The first person will make sure they cut the cake so that he or she is content with either of the two pieces. Depending on preference, and what's on the cake, he or she might cut it into two equal halves, or into a smaller piece that comes with a particular bonus (a strawberry, say) and a larger one. Whatever piece the second person chooses, the first won't be left envious. The second person might not like the way the cake was cut, but, since he or she got to pick first, also won't be envious of the other person's piece. Generally, a division method is called envy-free if no person would prefer another person's allocation to their own.

      The method for two people has been known for a long time, but it wasn't until the 1960s that the mathematician John L. Selfridge devised an elegant and efficient method (later independently discovered by John H. Conway) that works for three people (see below). In 1995 Steven J. Brams (who has written several Plus articles) and Alan D. Taylor came up with a breakthrough method that works for any number of people, but has a drawback. Even when only four cake eaters are involved, the number of cuts required to make the fair division could be arbitrarily large. The number of questions you need to ask cake eaters in order to find the division — which relates to the time it takes the method to complete — could also be arbitrarily large. Just how large these numbers will be depends on the preferences of the players (if you're lucky, they could be small), but the point is that you can't from the outset put a limit on how long the algorithm would run and how many cuts would need to be made. This is particularly frustrating because mathematicians know for sure that for n cake eaters there is an envy-free division that requires only n−1 cuts. It's finding that division which is the problem.

      One variation is to allow a moving knife: this involves a referee moving the knife (or several knives) across the cake and players shouting "stop" when they think a cut should be made. For four cake eaters at least, this brings the number of cuts needed down to five. But it involves cake eaters making an infinite number of decisions. For each point of the axis along which the knife moves they need to decide whether to shout stop or not. And since what we would really like is a discrete step-by-step algorithm that could be run on a computer, such moving knife methods aren't entirely satisfactory.

      The new method, devised by Haris Aziz and Simon MacKenzie, is discrete and comes with a bound on the number of cuts needed and the number of questions you need to ask of the cake eaters to find the division. Brams, co-inventor of the unbounded method, is pleased with the result. "I believe that the Aziz-MacKenzie algorithm is an important theoretical result and certainly improves on my earlier result with Taylor — by bounding the number of steps (or cuts) that the algorithm requires — which we showed was finite but for which we could not fix an upper bound."

      Does this mean that conflicts over cake-like goods can now be solved in a flash? Not quite — Aziz and MacKenzie's result is of purely theoretical interest. The bound on the number of questions you need to ask when there are n cake eaters involved is nnnnnn. No matter what the cake eaters' preferences are, you never need to ask more than that number of questions. But this still leads to unimaginably large numbers: even for n=2 standard calculators will give up. "It remains a challenge to reduce this bound, with or without the use of a moving knife," says Brams. "However, I don't think this number will ever be such that any of these algorithms will have any practical value."

      Cake eaters

      There are many ways to eat a cake.

      There is another problem too. Aziz and MacKenzie's method guarantees that nobody is left envious of another person's piece of cake. But this doesn't guarantee that everybody is as satisfied as possible. There may be another division of the cake that leaves one or more of the cake eaters better off without making anyone worse off — in maths jargon, envy-free divisions are not generally pareto-optimal. This may leave cake eaters grumbling: they may not be jealous of another person's piece, but they may well be unhappy knowing they could have done better with a different division. It is often impossible to satisfy both envy-freeness and pareto-optimality at the same time. So while theorists are hard at work reducing the bound on their algorithms, practitioners on the ground need to think hard about what sort of division is best in a particular conflict: envy-free, pareto-optimal, or perhaps some other criterion.


      Further reading

      There is a lovely article about the new result in Quanta Magazine.


      How to divide a cake between three people so that nobody is envious

      Let's suppose our three people are called A, B and C, and since we're gender neutral, we refer to all of them as "it". The procedure starts by C cutting the cake into three pieces it considers equally valuable. A and B then take their pick. If they choose two different pieces we are done.

      Suppose A and B want the same piece. In that case B trims a bit off the piece it considers most valuable so that it matches B's second most-valuable piece. Put the trimming to one side and let A take its pick. Next, B chooses its piece, with the limitation that if A didn't choose the piece that had something trimmed off, then B must choose it. Lastly, C takes its pick. Now A is not envious because it got the first choice. B is not envious, because its two first choices are equally valuable: whatever A picks, there's an equally-valuable piece left for B. C isn't envious because the three initial pieces were equally valuable to it. The only piece that has reduced in value, from C's point of view, is the one that had something trimmed off it, but that will have been taken by either A or B.

      This leaves the trimming to be divided up. Suppose the piece that had something trimmed off it was chosen by A in the previous round. Let B divide the trimming into three pieces it considers equally valuable. Let the A take the first pick, C the second pick, and B the last pick. Now A isn't envious because it got to pick first. If C were envious, it would have to be envious of A. That's because it wasn't envious in the first round, and in the second it's not envious of B because it got to pick ahead of B. Could C be envious of A? Well, in the first round A chose the piece that had something trimmed off it, that is, A picked the piece in the first round that was less valuable to C than the other two. Let's write V for the value, to C, of the three pieces it initially cut the cake into. Let's write W for the value, to C, of the trimming. Now the total value, to C, of C's allocation is V plus some fraction of W. The total value, to C, of A's allocation is V-W plus some fraction of W. Clearly, V-W plus some fraction of W is always going to be less than V. That is, the value of A's allocation, to C, is less than its own allocation, hence C is not envious of A.

      What if it was B who chose the piece that had something trimmed off it in the first round? In that case, simply swap the roles of A and B in the previous paragraph.

      Read more about...
      fair division
      • Log in or register to post comments

      Comments

      Lew Baxter

      26 October 2016

      Permalink

      2^2^2^2^2^2 does not mean ((((2^2)^2)^2)^2)^2. It means 2^(2^(2^(2^(2^2)))).

      • Log in or register to post comments

      Pontons

      28 October 2016

      Permalink

      2^2^2^2^2 is not the same as (((2^2)^2)^2)^2!!!!!!

      • Log in or register to post comments

      JT

      12 November 2016

      Permalink

      2^2^2^2^2^2 is about 6.03 * 10^19727 according to http://www.wolframalpha.com/input/?i=2^2^2^2^2^2

      • Log in or register to post comments

      Rachel

      14 November 2016

      Permalink

      Thanks everyone for spotting this - corrected now. We're sorry we missed that as we're quite keen on power towers here - see Too big to write, but not too big for Graham and Writing the unwritable!

      • Log in or register to post comments

      Read more about...

      fair division
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms