The Fink protocol (also known as Successive Pairs or Lone Chooser
) is a protocol for
proportional division
A proportional division is a kind of fair division in which a resource is divided among ''n'' partners with subjective valuations, giving each partner at least 1/''n'' of the resource by his/her own subjective valuation.
Proportionality was the f ...
of a
cake
Cake is a flour confection made from flour, sugar, and other ingredients, and is usually baked. In their oldest forms, cakes were modifications of bread, but cakes now cover a wide range of preparations that can be simple or elaborate, ...
.
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".
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
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
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 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. 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
pieces, but in fact only about
are needed as each partner only really needs to do
cuts when the
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 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 p ...
, giving each partner a piece that he values as exactly
of the total.
References
{{reflist
Fair division protocols
Cake-cutting