Procedimientos para mover cuchillos de Austin

Los procedimientos de "cuchillo móvil" de Austin son procedimientos imparciales para dividir tortas . Los procedimientos reparten a cada uno de los n participantes un trozo de tarta, que este participante evalúa exactamente en la tarta entera. Esto contrasta con los procedimientos de división proporcional , que le dan a cada participante al menos un pastel completo, pero pueden darle más a cada participante. $1/n$ $1/n$

Si , el corte obtenido por el procedimiento de Austin es una división exacta y no hay envidia en ello . Además, es posible cortar el pastel en cualquier número k de piezas, que cada uno de los socios evalúa exactamente en 1/ k . Por lo tanto, es posible dividir el pastel entre los participantes en cualquier proporción (por ejemplo, dar 1/3 a Alicia y 2/3 a Jorge). $n=2$

Si , la división no será ni exacta ni libre de envidia, ya que solo evalúa su propia pieza a , pero la evaluación de otras piezas puede diferir de este valor. $n>2$ $1/n$

La principal herramienta matemática utilizada por el procedimiento de Austin es el teorema del valor intermedio [1] [2] [3] .

Dos miembros y mitades de pastel

Los procedimientos básicos implican que los participantes compartan el pastel para que ambos obtengan exactamente la mitad. $n=2$

Procedimiento de dos cuchillos

Para facilitar la descripción, llamemos a los dos jugadores Alice y George y supongamos que el pastel es rectangular.

Alice coloca un cuchillo a la izquierda del pastel y el otro paralelo a este a la derecha, donde está a punto de cortar el pastel en dos.
Alice mueve ambos cuchillos a la derecha para que la parte entre los cuchillos sea siempre la mitad del pastel (en su estimación, aunque la distancia física entre los cuchillos puede cambiar).
George dice "¡Alto!" cuando cree que hay medio pastel entre los cuchillos. ¿Cómo podemos estar seguros de que George dirá la palabra "¡alto!" ¿en algún momento? El hecho es que si Alicia llega al borde con el cuchillo derecho, la posición del cuchillo izquierdo debería estar en el mismo punto desde el que comenzó el cuchillo derecho. El teorema del valor intermedio establece que George debería estar satisfecho con cortar el pastel por la mitad en algún momento.
Lanzar una moneda determina dos opciones: George obtiene una pieza entre los cuchillos y Alice obtiene dos piezas extremas, o viceversa. Si los participantes son honestos, estarán de acuerdo en que la parte entre los cuchillos es exactamente la mitad, por lo que el corte será preciso.

Procedimiento de un cuchillo

Se puede usar un cuchillo para lograr el mismo efecto.

Alice gira el cuchillo sobre el pastel a 180°, manteniendo iguales las mitades a ambos lados del cuchillo.
George dice "¡para!" cuando está de acuerdo.

Alice debe, por supuesto, completar el giro del cuchillo en la misma línea en la que comenzó. Nuevamente, según el teorema del valor intermedio, debe haber un punto en el que George piense que las dos mitades son iguales.

Dos participantes y partes de la vista general

Como señaló Austin, dos participantes pueden encontrar un trozo de pastel que ambos valoren exactamente para cualquier número entero [2] . Llamemos al procedimiento anterior como : $1/k$ $k \ geqslant 2$ $\mathrm {Cortar} _{2}(1/k)$

Alicia hace marcas paralelas en el pastel para que las piezas sean exactamente iguales . $k-1$ $k$ $1/k$
Si hay un trozo que George cree que también es igual a , hemos terminado de extraer ese trozo. $1/k$
De lo contrario, debe haber un fragmento que George evalúe como menor que at y un fragmento adyacente que George evalúe como mayor que . $1/k$ $1/k$
Deje que Alice coloque dos cuchillos en las dos marcas de una de estas piezas y que mueva los cuchillos en paralelo, manteniendo el valor entre los cuchillos exactamente hasta que los cuchillos aterricen en las marcas de la segunda pieza. Por el teorema del valor intermedio, debe haber un punto en el que George debe aceptar que el valor entre los cuchillos es exactamente . $1/k$ $1/k$

Al aplicar recursivamente a dos participantes, pueden dividir todo el pastel en partes, cada una de las cuales ambos participantes evalúan exactamente [2] : ${\displaystyle \mathrm {Cortar} _{2))$ $k$ $1/k$

Usamos el procedimiento para cortar una pieza que ambos jugadores valoran exactamente en . $\mathrm {Cortar} _{2}(1/k)$ $1/k$
Ahora ambos jugadores evalúan el resto del pastel exactamente en . Úsalo para cortar una pieza que ambos jugadores calculen exactamente en . ${\ estilo de visualización (k-1)/k}$ $\mathrm {Cortar} _{2}(1/(k-1))$ $1/k$
Seguimos hasta conseguir todas las piezas. $k$

Dos partes pueden llegar a una división exacta con cualquier proporción racional de acciones adeudadas mediante un procedimiento un poco más complicado [4] .

Muchos miembros

Al combinar el procedimiento con el protocolo Fink , es posible dividir el pastel entre los participantes, de modo que cada participante reciba una porción que evalúe exactamente [1] [5] : ${\displaystyle \mathrm {Cortar} _{2))$ $norte$ $1/n$

Los participantes #1 y #2 usan , para dar a cada uno exactamente la mitad, en su opinión. $\mathrm {Cortar} _{2}(1/2)$
El participante n.° 3 usa con el participante n.° 1 para obtener exactamente 1/3 de su parte y luego con el participante n.° 2 para obtener exactamente 1/3 de su parte. La parte asignada de la pieza al participante n.° 1 es valorada por ambos participantes en exactamente 1/6, por lo que el participante n.° 1 se queda con exactamente 1/3. Lo mismo es cierto para el concursante n.° 2. Para el concursante n.° 3, aunque puede calificar las piezas por encima o por debajo de 1/6, la suma de las dos piezas debe ser exactamente 1/3 de todo el pastel. $\mathrm {Cortar} _{2}(1/3)$ $\mathrm {Cortar} _{2}(1/3)$

Tenga en cuenta que para el corte resultante no es exacto, ya que la pieza se evalúa en solo el propietario de la pieza, pero no necesariamente en la misma cantidad por otros participantes. A partir de 2015, no se conocía el procedimiento de división exacto de los participantes, solo se conocen procedimientos de división casi exactos . $n>2$ $1/n$ $n>2$

Véase también

El procedimiento de Austin es utilizado por el procedimiento de Brahms-Taylor-Zwicker .
Otros procedimientos y resultados de división justa y división exacta .

Notas

↑ 1 2 Austin, 1982 , pág. 212.
↑ 1 2 3 Brams y Taylor, 1996 , pág. 22–27.
↑ Robertson, Webb, 1998 , pág. 66.
↑ Robertson, Webb, 1998 , pág. 71.
↑ Brams y Taylor 1996 , pág. 43–44.

Literatura

Austin AK Compartiendo un pastel // The Mathematical Gazette. - 1982. - T. 66 , núm. 437 . -doi : 10.2307/ 3616548 . — .
Jack Robertson, William Webb. Algoritmos de corte de torta: Sea justo si puede. - Natick, Massachusetts: AK Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. división justa. - 1996. - ISBN 978-0-521-55644-6 .
- Traducido por Stephen J. Brahms, Alan D. Taylor. Compartimos de manera justa o garantizamos una victoria para todos. - Moscú: SINTEG, 2002. - (Serie "Economía y Negocios"). - ISBN 5-89638-058-5 .

Enlaces

Fisher, Daniel. División por consenso de un pastel entre dos personas en proporciones arbitrarias . Matemáticas.SE. Recuperado: 23 junio 2015. (indefinido)