Protocolo Fink
El Protocolo Fink [1] (también conocido como Pares Consecutivos [2] o Selector Único [3] ) es un protocolo de reparto de pasteles proporcional .
La principal ventaja del protocolo es que funciona en línea, incluso si no se conoce de antemano el número de participantes en la división. Cuando un nuevo miembro se une a una división, la división existente se reconstruye para dar una división justa para el recién llegado con un efecto mínimo en los miembros existentes.
El principal inconveniente del protocolo es que, en lugar de una pieza coherente, el protocolo asigna una gran cantidad de "migajas" al participante.
Protocolo
Describimos el protocolo de forma inductiva aumentando el número de participantes.
Cuando el concursante #1 se une a la fiesta, simplemente se lleva todo el pastel. Su valor de acción es 1.
Cuando llega el concursante n.º 2, el concursante n.º 1 corta el pastel en dos partes iguales a sus ojos. El nuevo participante elige la pieza que le parece mejor. El valor para cada participante ahora es al menos 1/2 (como en el protocolo divide y elige ).
Cuando el participante n.° 3 se une, ambos participantes n.° 1 y n.° 2 cortan sus porciones en 3 partes iguales a la vista. El nuevo participante elige una pieza de cada participante. Los valores para los participantes #1 y #2 son al menos 2/3 de su valor anterior, que era 1/2. Por tanto, su nuevo valor no es inferior a 1/3. El valor para el concursante n.° 3 es al menos 1/3 de la rebanada n.° 1 y 1/3 de la rebanada 2, lo que le otorga al menos 1/3 del pastel completo.
En general, cuando el participante #i se une al grupo, los i -1 participantes anteriores dividen sus acciones en i partes iguales y el nuevo participante elige una pieza de cada pila. De nuevo, se puede demostrar que el valor para cada participante es al menos 1/ n del valor total, por lo que el recorte es proporcional.
Número de cortes
La aplicación sencilla del algoritmo dará piezas, aunque de hecho solo alrededor de , ya que cada participante necesita cortes cuando llega el -ésimo participante.
Aplicaciones
El protocolo Fink se usa como algoritmo auxiliar en otros protocolos para una división justa del pastel:
- Protocolo de Woodall de división superproporcional para n participantes .
- Procedimientos de "Moving Knife" de Austin , asignando a cada participante una pieza cuyo valor es exactamente igual a un pastel completo.
Notas
- ↑ Fink, 1964 , pág. 341.
- ↑ Saaty, 1970 .
- ↑ Brams y Taylor 1996 , pág. 40
Literatura
- Fink AM Una nota sobre el problema de la división justa // Revista de matemáticas. - 1964. - T. 37 , núm. 5 . -doi : 10.2307/ 2689255 . — .
- Saaty TL Optimización en Números Enteros y Problemas Extremos Relacionados. - McGraw-Hill, 1970. - ISBN 0070543690 .
- Steven J. Brams, Alan D. Taylor. División justa: desde el corte del pastel hasta la resolución de disputas. - 1996. - ISBN 0521556449 .