Protocolo Fink

El protocolo Fink ^{[ 1 ]} (también conocido como pares sucesivos ^{[ 2 ]} o elegido solitario ^{[ 3 ]} ) es un protocolo para la división proporcional de un pastel .

Su principal ventaja es que puede funcionar en línea, sin necesidad de conocer de antemano el número de socios. Cuando un nuevo socio se une al grupo, el reparto existente se ajusta para darle una parte justa, con un impacto mínimo en los socios ya existentes.

Su principal desventaja es que, en lugar de dar a cada socio una sola pieza conectada, les da a cada socio una gran cantidad de "migajas".

Describimos el protocolo de forma inductiva para un número creciente de socios.

Cuando el socio n.º 1 entra en la fiesta, se lleva todo el pastel. Por lo tanto, su valor es 1.

Cuando llega el segundo participante, el primero corta el pastel en dos trozos que, a su juicio, son iguales. El nuevo participante elige el trozo que considera mejor. De esta forma, el valor de cada participante es al menos la mitad (igual que en el protocolo de dividir y elegir ).

Cuando se une el socio n.° 3, los socios n.° 1 y n.° 2 dividen su participación en 3 partes iguales a su parecer. El nuevo socio elige una parte de cada socio. El valor de cada uno de los socios n.° 1 y n.° 2 es al menos 2/3 de su valor anterior, que era 1/2. Por lo tanto, su nuevo valor es al menos 1/3. El socio n.° 3 valora las participaciones de los socios n.° 1 y n.° 2 en${\displaystyle v_{1}}$,${\displaystyle v_{2}}$, dónde${\displaystyle v_{1}+v_{2}=1}$. El valor del socio n.º 3 es al menos${\displaystyle {\frac {v_{1}}{3}}}$de la pieza del #1 y al menos${\displaystyle {\frac {v_{2}}{3}}}$del trozo número 2, lo que le da al menos 1/3 del pastel total.

En general, cuando el socio i se une a la fiesta, los socios anteriores (i -1) dividen su parte en i partes iguales, y el nuevo socio elige una parte de cada montón. De nuevo, es posible demostrar que el valor de cada socio es al menos 1/ n del total, por lo que la división es proporcional.

El uso directo del algoritmo generaría${\displaystyle n!}$piezas, pero de hecho solo unas pocas${\displaystyle n^{3}/3}$son necesarios ya que cada socio solo necesita hacerlo${\displaystyle n-1}$cortes cuando el${\displaystyle n}$^El socio aparece.

El protocolo de Fink se utiliza en una subrutina en otros protocolos de corte de pasteles:

• Protocolo de Woodall para la división superproporcional para n jugadores .
• Procedimiento de Austin de cuchillo móvil , dando a cada socio una pieza que valora exactamente${\displaystyle 1/n}$del total.