Procedimientos de cuchilla móvil de Austin

Procedimientos para la división equitativa de una torta

Los procedimientos de división proporcional de Austin son procedimientos para la división equitativa de una torta . A cada uno de los n socios se le asigna una porción de la torta que este socio valora exactamente como una porción de la torta. Esto contrasta con los procedimientos de división proporcional , que le dan a cada socio al menos una porción de la torta, pero pueden dar más a algunos de los socios. ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

Cuando , la división generada por el procedimiento de Austin es una división exacta y también está libre de envidia . Además, es posible dividir la torta en cualquier número k de pedazos que ambos socios valoren exactamente como 1/ k . Por lo tanto, es posible dividir la torta entre los socios en cualquier fracción (por ejemplo, dar 1/3 a Alice y 2/3 a George). ${\displaystyle n=2}$

Cuando , la división no es ni exacta ni libre de envidias, ya que cada socio sólo valora su propia pieza como , pero puede valorar otras piezas de forma diferente. ${\displaystyle n>2}$ ${\displaystyle 1/n}$

La principal herramienta matemática utilizada por el procedimiento de Austin es el teorema del valor intermedio (IVT). ^{[1] [2] [3] : 66}

Dos socios y medias tortas

Los procedimientos básicos implican que los socios quieran dividir un pastel de manera que cada uno reciba exactamente la mitad. ${\displaystyle n=2}$

Procedimiento de dos cuchillos

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

• Alicia coloca un cuchillo a la izquierda del pastel y un segundo paralelo a este a la derecha, donde considera que divide el pastel en dos.
• Alice mueve ambos cuchillos hacia la derecha de manera que la parte entre los dos cuchillos siempre contenga la mitad del valor del pastel a sus ojos (mientras que la distancia física entre los cuchillos puede cambiar).
• George dice "¡basta!" cuando piensa que la mitad del pastel está entre los cuchillos. ¿Cómo podemos estar seguros de que George puede decir "basta" en algún momento? Porque si Alice llega al final, debe tener su cuchillo izquierdo en la posición en la que comenzó el cuchillo derecho. La teoría de la transmisión verbal establece que George debe estar satisfecho de que el pastel se haya dividido por la mitad en algún momento.
• Se lanza una moneda para elegir entre dos opciones: o bien George recibe la pieza que está entre los cuchillos y Alice recibe las dos piezas de los flancos, o viceversa. Si los socios son sinceros, entonces están de acuerdo en que la pieza que está entre los cuchillos tiene un valor de exactamente 1/2, y por lo tanto la división es exacta.

Procedimiento con un solo cuchillo

Se puede utilizar un solo cuchillo para conseguir el mismo efecto.

• Alice gira el cuchillo sobre el pastel 180° dejando una mitad a cada lado.
• George dice "¡basta!" cuando está de acuerdo.

Por supuesto, Alice debe terminar el turno con el cuchillo en la misma línea en la que comenzó. Nuevamente, según el IVT, debe haber un punto en el que George sienta que las dos mitades son iguales.

Dos socios y fracciones generales

Como señaló Austin, los dos socios pueden encontrar una única porción de pastel que ambos valoren exactamente como , para cualquier entero . ^[2] Llame al procedimiento anterior : ${\displaystyle 1/k}$ ${\displaystyle k\geq 2}$ ${\displaystyle \mathrm {Cut} _{2}(1/k)}$

• Alicia hace marcas paralelas en el pastel de tal manera que los trozos así determinados tienen un valor de exactamente . ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle 1/k}$
• Si hay una pieza que George también valora como , entonces hemos terminado. ${\displaystyle 1/k}$
• De lo contrario, debe haber una pieza que George valore como menor que , y una pieza adyacente que George valore como mayor que . ${\displaystyle 1/k}$ ${\displaystyle 1/k}$
• Dejemos que Alice coloque dos cuchillos en las dos marcas de una de estas piezas y los mueva en paralelo, manteniendo el valor entre ellos exactamente en , hasta que se encuentren con las marcas de la otra pieza. Por la teoría de la igualdad entre los dos cuchillos, debe haber un punto en el que George esté de acuerdo en que el valor entre los cuchillos sea exactamente . ${\displaystyle 1/k}$ ${\displaystyle 1/k}$

Aplicando recursivamente , los dos socios pueden dividir todo el pastel en pedazos, cada uno de los cuales vale exactamente para ambos: ^[2] ${\displaystyle \mathrm {Cut} _{2}}$ ${\displaystyle k}$ ${\displaystyle 1/k}$

• Se utiliza para cortar un trozo que valga exactamente para ambos socios. ${\displaystyle \mathrm {Cut} _{2}(1/k)}$ ${\displaystyle 1/k}$
• Ahora el pastel restante vale exactamente para ambos socios; úselo para cortar otro pedazo que valga exactamente para ambos socios. ${\displaystyle (k-1)/k}$ ${\displaystyle \mathrm {Cut} _{2}(1/(k-1))}$ ${\displaystyle 1/k}$
• Continúa así hasta que queden trozos. ${\displaystyle k}$

Dos socios pueden lograr una división exacta con cualquier proporción racional de derechos mediante un procedimiento ligeramente más complicado. ^{[3] : 71}

Muchos socios

Combinando con el protocolo Fink , es posible dividir un pastel entre los socios, de tal manera que cada socio reciba un pedazo que valga exactamente para él: ^{[1] [4]} ${\displaystyle \mathrm {Cut} _{2}}$ ${\displaystyle n}$ ${\displaystyle 1/n}$

• Los socios #1 y #2 suelen dar a cada uno de ellos un trozo que vale exactamente la mitad para ellos. ${\displaystyle \mathrm {Cut} _{2}(1/2)}$
• El socio n.° 3 utiliza el pastel con el socio n.° 1 para obtener exactamente 1/3 de su parte y luego con el socio n.° 2 para obtener exactamente 1/3 de la suya. El primer trozo vale exactamente 1/6 para el socio n.° 1 y, por lo tanto, el socio n.° 1 se queda con exactamente 1/3; lo mismo sucede con el socio n.° 2. En cuanto al socio n.° 3, si bien cada trozo puede ser mayor o menor que 1/6, la suma de los dos trozos debe ser exactamente 1/3 de toda la tarta. ${\displaystyle \mathrm {Cut} _{2}(1/3)}$ ${\displaystyle \mathrm {Cut} _{2}(1/3)}$

Tenga en cuenta que, en el caso de , la división generada no es exacta, ya que una pieza vale solo para su propietario y no necesariamente para los demás socios. A partir de 2015, no se conoce ningún procedimiento de división exacto para los socios; solo se conocen procedimientos de división casi exactos . ${\displaystyle n>2}$ ${\displaystyle 1/n}$ ${\displaystyle n>2}$

Véase también

• El procedimiento de Austin es utilizado por el procedimiento de Brams-Taylor-Zwicker .
• Otros procedimientos y resultados sobre división equitativa y división exacta .

Referencias

1. Austin, AK (1982). "Compartiendo un pastel". The Mathematical Gazette . 66 (437): 212–215. doi :10.2307/3616548. JSTOR  3616548. S2CID  158398839.
2. Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [ Del corte de la torta a la resolución de disputas ]. pp. 22–27. ISBN 978-0-521-55644-6.
3. Robertson, Jack; Webb, William (1998). Algoritmos para cortar la torta: sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. Número de serie  97041258. OL  2730675W.
4. Brams, Steven J.; Taylor, Alan D. Fair Division [ Desde el corte de la torta hasta la resolución de disputas ]. págs. 43–44. ISBN 978-0-521-55644-6.

Enlaces externos

• Fischer, Daniel. «División por consenso de una tarta entre dos personas en proporciones arbitrarias». Math.SE. Consultado el 23 de junio de 2015 .