Austin moving-knife procedures
Austin moving-knife procedures
The Austin moving-knife procedures are procedures for equitable division of a cake. To each of n partners, they allocate a piece of the cake which this partner values as exactly <math>1/n</math> of the cake. This is in contrast to proportional-division procedures, which give each partner at least <math>1/n</math> of the cake, but may give more to some of the partners.
When <math>n=2</math>, the division generated by Austin's procedure is an exact division and it is also envy-free. Moreover, it is possible to divide the cake to any number k of pieces which both partners value as exactly 1/k. Hence, it is possible to divide the cake between the partners in any fraction (e.g. give 1/3 to Alice and 2/3 to George).
When <math>n>2</math>, the division is neither exact nor envy-free, since each partner only values his own piece as <math>1/n</math>, but may value other pieces differently.
The main mathematical tool used by Austin's procedure is the intermediate value theorem (IVT).
Two partners and half-cakes The basic procedures involve <math>n=2</math> partners who want to divide a cake such that each of them gets exactly one half.
Two knives procedure For the sake of description, call the two players Alice and George, and assume the cake is rectangular. * Alice places one knife on the left of the cake and a second parallel to it on the right where she judges it splits the cake in two. * Alice moves both knives to the right in a way that the part between the two knives always contains half of the cake's value in her eyes (while the physical distance between the knives may change). George says "stop!" when he* thinks that half the cake is between the knives. We can be sure that George would "stop" at some point, since if Alice reaches the end, she must have her left knife positioned where the right knife started. The IVT establishes that George must be satisfied the cake is halved at some point. * A coin is tossed to select between two options: either George receives the piece between the knives and Alice receives the two pieces at the flanks, or vice versa. If partners are truthful, then they agree that the piece between the knives has a value of exactly 1/2, and so the division is exact.
One knife procedure A single knife can be used to achieve the same effect. * Alice rotates the knife over the cake through 180° keeping a half on either side. * George says "stop!" when he agrees. Alice must of course end the turn with the knife on the same line as where it started. Again, by the IVT, there must be a point in which George feels that the two halves are equal.
Two partners and general fractions As noted by Austin, the two partners can find a single piece of cake that both of them value as exactly <math>1/k</math>, for any integer <math>k\geq 2</math>. * Partners #1 and #2 use <math>\mathrm{Cut}_2(1/2)</math> to give each one of them a piece worth exactly 1/2 for them. * Partner #3 uses <math>\mathrm{Cut}_2(1/3)</math> with partner #1 to get exactly 1/3 of his share and then <math>\mathrm{Cut}_2(1/3)</math> with partner #2 to get exactly 1/3 of her share. The first piece is worth exactly 1/6 for partner #1 and so partner #1 remains with exactly 1/3; the same is true for partner #2. As for partner #3, while each piece can be more or less than 1/6, the sum of the two pieces must be exactly 1/3 of the entire cake.
Note that for <math>n>2</math>, the generated division is not exact, since a piece is worth <math>1/n</math> only to its owner and not necessarily to the other partners. As of 2015, there is no known exact division procedure for <math>n>2</math> partners; only near-exact division procedures are known.