Fink protocol

The Fink protocol (also known as Successive Pairs or Lone Chooser ) 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 newcomer, 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".

The Fink protocol (also known as Successive Pairs or Lone Chooser ) 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 newcomer, 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". When partner #3 joins, both partners #1 and #2 cut their share to 3 pieces that are equal in their eyes. The new partner chooses 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. Partner #3 values the shares of partner #1 and #2 at v_1 , v_2 , where v_1 + v_2 = 1 . The value of partner #3 is at least \frac{v_1}{3} from the piece of #1 and at least \frac{v_2}{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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1323047843 under CC BY-SA 4.0; modifications have been made.