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 of the cake. This is in contrast to proportional division procedures, which give each partner at least of the cake, but may give more to some of the partners.

When , 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 , the division is neither exact nor envy-free, since each partner only values his own piece as , but may value other pieces differently.

The main mathematical tool used by Austin's procedure is the intermediate value theorem (IVT).[1][2][3]: 66 

Two partners and half-cakes

edit

The basic procedures involve   partners who want to divide a cake such that each of them gets exactly one half.

Two knives procedure

edit

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. How can we be sure that George can say "stop" at some point? Because 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

edit

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

edit

As noted by Austin, the two partners can find a single piece of cake that both of them value as exactly  , for any integer  .[2] Call the above procedure  :

  • Alice makes   parallel marks on the cake such that   pieces so determined have a value of exactly  .
  • If there is a piece that George also values as  , then we are done.
  • Otherwise, there must be a piece that George values as less than  , and an adjacent piece that George values as more than  .
  • Let Alice place two knives on the two marks of one of these pieces, and move them in parallel, keeping the value between them at exactly  , until they meet the marks of the other piece. By the IVT, there must be a point at which George agrees that the value between the knives is exactly  .

By recursively applying  , the two partners can divide the entire cake to   pieces, each of which is worth exactly   for both of them:[2]

  • Use   to cut a piece which is worth exactly   for both partners.
  • Now the remaining cake is worth exactly   for both partners; use   to cut another piece worth exactly   for both partners.
  • Continue like this until there are   pieces.

Two partners can achieve an exact division with any rational ratio of entitlements by a slightly more complicated procedure.[3]: 71 

Many partners

edit

By combining   with the Fink protocol, it is possible to divide a cake to   partners, such that each partner receives a piece worth exactly   for him:[1][4]

  • Partners #1 and #2 use   to give each one of them a piece worth exactly 1/2 for them.
  • Partner #3 uses   with partner #1 to get exactly 1/3 of his share and then   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  , the generated division is not exact, since a piece is worth   only to its owner and not necessarily to the other partners. As of 2015, there is no known exact division procedure for   partners; only near-exact division procedures are known.

See also

edit

References

edit
  1. ^ a b Austin, A. K. (1982). "Sharing a Cake". The Mathematical Gazette. 66 (437): 212–215. doi:10.2307/3616548. JSTOR 3616548. S2CID 158398839.
  2. ^ a b c Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. pp. 22–27. ISBN 978-0-521-55644-6.
  3. ^ a b Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
  4. ^ Brams, Steven J.; Taylor, Alan D. Fair Division [From cake-cutting to dispute resolution]. pp. 43–44. ISBN 978-0-521-55644-6.
edit