Austin moving-knife procedures

The Austin moving-knife procedures are procedures for equitable division of a cake. They allocate each of n partners, a piece of the cake which this partner values as exactly $1/n$ of the cake. This is in contrast to proportional division procedures, which give each partner at least $1/n$ of the cake, but may give more to some of the partners.

When $n=2$ , 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 $n>2$ , the division is neither exact nor envy-free, since each partner only values his own piece as $1/n$ , 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

The basic procedures involve $n=2$ 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. 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

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 $1/k$ , for any integer $k\geq 2$ .^[2] Call the above procedure ${\mathrm {Cut}}_{2}(1/k)$ :

Alice makes $k-1$ parallel marks on the cake such that $k$ pieces so determined have a value of exactly $1/k$ .
If there is a piece that George also values as $1/k$ , then we are done.
Otherwise, there must be a piece that George values as less than $1/k$ , and an adjacent piece that George values as more than $1/k$ .
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 $1/k$ , 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 $1/k$ .

By recursively applying ${\mathrm {Cut}}_{2}$ , the two partners can divide the entire cake to $k$ pieces, each of which is worth exactly $1/k$ for both of them:^[2]

Use ${\mathrm {Cut}}_{2}(1/k)$ to cut a piece which is worth exactly $1/k$ for both partners.
Now the remaining cake is worth exactly $(k-1)/k$ for both partners; use ${\mathrm {Cut}}_{2}(1/(k-1))$ to cut another piece worth exactly $1/k$ for both partners.
Continue like this until there are $k$ pieces.

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

Many partners

By combining ${\mathrm {Cut}}_{2}$ with the Fink protocol, it is possible to divide a cake to $n$ partners, such that each partner receives a piece worth exactly $1/n$ for him:^[1]^[4]

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

References

1 2 Austin, A. K. (1982). "Sharing a Cake". The Mathematical Gazette. 66 (437): 212. doi:10.2307/3616548. JSTOR 3616548.
1 2 3 Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. pp. 22–27. ISBN 0-521-55644-9.
1 2 Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 1-568-81076-8.
↑ Brams, Steven J.; Taylor, Alan D. Fair Division [From cake-cutting to dispute resolution]. pp. 43–44. ISBN 0-521-55644-9.

External links

Fischer, Daniel. "Consensus division of a cake to two people in arbitrary ratios". Math.SE. Retrieved 23 June 2015.

This article is issued from Wikipedia - version of the 5/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.