Fink protocol

The Fink protocol^[1] (also known as Successive Pairs^[2] or Lone Chooser^[3]) is a protocol for proportional division of a cake.

Its main advantage is that it can work in an online fashion, without knowing the number of partners in advance. When a new partner joins the party, the existing division is adjusted to give a fair share to the new comer, with minimal effect on existing partners.

Its main disadvantage is that, instead of giving each partner a single connected piece, it gives each partner a large number of "crumbs".

Protocol

We describe the protocol inductively for an increasing number of partners.

When partner #1 enters the party, he just takes the entire cake. His value is thus 1.

When partner #2 comes, partner #1 cuts the cake to two pieces that are equal in his eyes. The new partner chooses the piece that is better in his eyes. The value of each partner is thus at least 1/2 (just like in the divide and choose protocol).

When partner #3 joins, both partners #1 and #2 cut their share to 3 pieces that are equal in their eyes. The new partner choose one piece from each partner. The value of each of partners #1 and #2 is at least 2/3 of their previous value, which was 1/2. Hence their new value is at least 1/3. The value of partner #3 is at least 1/3 from the piece of #1 and 1/3 from the piece of 2, which gives him at least 1/3 of the total cake.

In general, when partner #i enters the party, the previous i-1 partners divide their share to i equal pieces and the new partner picks a piece from each pile. Again it is possible to prove that the value of each partner is at least 1/n of the total, so the division is proportional.

Number of cuts

Straightforward use of the algorithm would generate $n!$ pieces, but in fact only about $n^3/3$ are needed as each partner only really needs to do $n-1$ cuts when the $n$ ^th partner comes along.

Applications

Fink's protocol is used in a subroutine in other cake-cutting protocols:

Woodall's protocol for super-proportional division for n players.
Austin moving-knife procedure, giving each partner a piece that he values as exactly $1/n$ of the total.

References

↑ Fink, A. M. (1964). "A Note on the Fair Division Problem". Mathematics Magazine 37 (5): 341. doi:10.2307/2689255. JSTOR 2689255.
↑ Optimization in Integers and Related Extremal Problems. T.L.Saaty. McGraw-Hill 1970
↑ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division: From cake-cutting to dispute resolution. p. 40. ISBN 0521556449.

This article is issued from Wikipedia - version of the Saturday, August 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.