Protocolo Fink

El protocolo Fink ^[1] (también conocido como Pares Sucesivos ^[2] o Elector Solitario ^[3] ) es un protocolo para la división proporcional de un pastel .

Su principal ventaja es que puede funcionar de forma online, sin conocer de antemano el número de socios. Cuando se incorpora un nuevo socio, se ajusta la división existente para darle una parte justa al recién llegado, con un efecto mínimo sobre los socios existentes.

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

Protocolo

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

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

Cuando llega el compañero n.° 2, el compañero n.° 1 corta la torta en dos pedazos que a su juicio son iguales. El nuevo compañero elige el pedazo que a su juicio es mejor. El valor de cada compañero es, por lo tanto, al menos 1/2 (como en el protocolo de dividir y elegir ).

Cuando se une el compañero n.° 3, tanto el n.° 1 como el n.° 2 dividen su parte en 3 trozos que son iguales a sus ojos. El nuevo compañero elige un trozo de cada compañero. El valor de cada uno de los compañeros 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 valor del compañero n.° 3 es al menos 1/3 del trozo del n.° 1 y 1/3 del trozo del n.° 2, lo que le da al menos 1/3 del total de la tarta.

En general, cuando el compañero n.° i entra a la fiesta, los i -1 compañeros anteriores dividen su parte en i porciones iguales y el nuevo compañero toma una porción de cada montón. Nuevamente, es posible demostrar que el valor de cada compañero es al menos 1/ n del total, por lo que la división es proporcional.

Número de cortes

El uso directo del algoritmo generaría piezas, pero en realidad solo se necesitan unas cuantas, ya que cada socio realmente solo necesita hacer cortes cuando llega el socio ^{número uno.} ${\displaystyle n!}$ ${\displaystyle n^{3}/3}$ ${\displaystyle n-1}$ ${\displaystyle n}$

Aplicaciones

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

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

Referencias

1. Fink, AM (1964). "Una nota sobre el problema de la división justa". Revista de matemáticas . 37 (5): 341–342. doi :10.2307/2689255. JSTOR  2689255.
2. Optimización en números enteros y problemas extremos relacionados. TLSaaty. McGraw-Hill 1970
3. Brams, Steven J.; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . p. 40. ISBN 0521556449.