El problema de un corte justo del pastel

El problema del corte justo del pastel es una variante del problema del reparto justo del pastel en el que el elemento a dividir es un círculo .

Como ejemplo, considere un pastel de cumpleaños en forma de círculo . El pastel debe dividirse entre varios niños de tal manera que ninguno de ellos esté celoso del otro (como en el problema estándar de división del pastel). Una condición adicional es que los cortes deben ser radiales para que cada niño reciba un sector circular . El término "pastel" es solo una metáfora de un procedimiento de corte de pastel que se puede usar para compartir diferentes tipos de recursos. Por ejemplo: propiedad de la tierra, espacio publicitario o tiempo de transmisión.

La tarea de cortar el pastel fue propuesta por Hugo Steinhaus después de la Segunda Guerra Mundial . Desde entonces, ha sido objeto de intenso estudio en matemáticas, informática, economía y ciencias políticas.

El modelo circular de división se puede aplicar para dividir la costa de una isla en secciones contiguas. Otra posible aplicación es la división del tiempo periódico: la división del ciclo diario en períodos de "servicio".

Modelo

El pastel generalmente se modela como un intervalo unidimensional [0.2π] (o [0.1]) en el que se identifican los dos puntos finales.

Este modelo fue propuesto en 1985 y posteriormente en 1993 [1] [2] .

Cualquier procedimiento para una división justa del pastel se puede aplicar al corte del pastel, ignorando el hecho de que se pueden identificar los dos puntos finales. Por ejemplo, si Alice obtiene [0,1/3] y George obtiene [1/3,1] como resultado del procedimiento de corte de torta, entonces le daremos a Alice un sector circular de 120 grados , mientras que George obtendrá los 240 grados restantes. sector.

El corte del pastel se vuelve más interesante cuando consideramos los problemas de eficiencia , ya que son posibles más cortes al dividir el pastel.

Dos socios

División sin envidia

Una división se llama división libre de envidia ( EF) si cada socio piensa que su pieza tiene al menos el mismo precio que todos los demás.

La división del pastel del OP se puede hacer mediante el procedimiento de dividir y elegir : un socio divide el pastel en dos sectores que considera iguales y el otro socio elige el sector que considera mejor. Pero para un pastel, puede haber una mejor división.

División sin envidia y eficiente en el sentido de Pareto

La división se llama Pareto eficiente (EP, inglés Pareto eficiente , PE) si ninguna otra división del pastel es la mejor para un socio y la peor para el otro. A menudo , la eficiencia de Pareto se determina solo para subconjuntos de todas las divisiones posibles. Es decir, solo para corte en dos sectores continuos (corte con un número mínimo de cortes).

La división se llama EPOS si es tanto EP como OZ.

Si las puntuaciones de los socios son medidas ( aditivas ), el siguiente procedimiento de "cuchillo móvil" garantiza una división que es OC y EP cuando se divide en sectores contiguos [3] .

Un compañero (Rotador) sostiene dos cuchillos radiales sobre el pastel de tal manera que desde su punto de vista, los dos sectores definidos por estos cuchillos tienen el mismo valor. Gira estos cuchillos continuamente todo el tiempo, manteniendo el mismo número de sectores, hasta que los cuchillos llegan a la posición inicial.

El otro compañero (el Selector) observa este proceso a lo largo del ciclo. Luego, en el ciclo siguiente, determina la posición en la que, desde su punto de vista, se obtiene el valor máximo para uno de los dos sectores. El selector obtiene este sector y el rotador obtiene el sector restante.

Esta división es obviamente el EP, ya que al Rotador no le importa qué cuadrantes elige el Selector. Este es EP ya que no hay división que le dé a Selector un valor mayor y deje un valor de 1/2 para Rotar.

Restricciones de aditividad

El procedimiento anterior solo funciona si la función de valor de Rotating es aditiva , por lo que las partes iguales siempre tienen el mismo valor 1/2. Si no es aditivo, entonces la división permanecería libre de envidia, pero no necesariamente eficiente en el sentido de Pareto .

Además, si las puntuaciones de ambos jugadores no son aditivas (de modo que ninguno de ellos puede actuar como rotador), la división de EPOS no siempre existe [4] .

División consistente y división proporcional ponderada

La división se llama exacta (o consistente ) si el valor de la pieza es exactamente igual según todos los socios, donde hay pesos predefinidos. $i$ $Wisconsin}$ $Wisconsin}$

Supongamos que la suma de todos los pesos es igual a 1, y el valor del pastel para todos los agentes también se normaliza a 1. Según el teorema de Stromquist-Woodall , para cualquier peso existe un subconjunto , que es la unión de los sectores máximos , cuyo valor todos los socios estiman exactamente en . Para el caso de los agentes, se sigue que siempre hay una división consistente del pastel con sectores conectados, donde al agente 1 se le da un sector que cuesta exactamente para ambos agentes, y al agente 2 se le da el sector restante que cuesta para ambos agentes ( véase el artículo de Brahms, Jos y Klumler [5] para una prueba alternativa). ${\ estilo de visualización w \ en [0,1]}$ ${\ estilo de visualización C_ {w}}$ $n-1$ $w$ $n=2$ $w_{1}$ ${\ estilo de visualización 1-w_{1}=w_{2))$

Esto se puede generalizar a cualquier cantidad de agentes: cada pieza, excepto la última, requiere como máximo cortes, por lo que la cantidad total de cortes necesarios es . ${\ estilo de visualización 2 (n-1)}$ ${\ estilo de visualización 2 (n-1) ^ {2))$

Se dice que una división es proporcional si cada uno de los dos socios recibe un valor de al menos 1/2. La división se llama división proporcional ponderada ( WPR ) si el socio recibe un valor de al menos , donde es un peso predefinido que representa las diferentes participaciones de los socios en el pastel. El procedimiento descrito anteriormente muestra que en el pastel siempre existe la división del VPD con piezas conectadas. Esto contrasta con un pastel no circular (intervalo), en el que puede no existir una división proporcional ponderada (WPR, ing. División proporcional ponderada , WPR) con partes conectadas. $i$ $Wisconsin}$ $Wisconsin}$

División ponderada sin ofensas

Si las calificaciones de los socios son absolutamente continuas entre sí, entonces hay una división VPD que también es OMS (ponderada en ausencia de envidia, ing. ponderada sin envidia , WEF) y eficiente en el sentido de Pareto (EP, ing . . Pareto eficiente , PE), y la relación entre los valores de los socios es exactamente w 1 / w 2 [5] .

prueba _ Para cualquier ángulo t , sea el ángulo en el que la relación . $y(t)$ ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))))={\tfrac {w_{1}}{w_{2} }}$

La función es continua en t y alcanza su máximo en algún . Cortamos el pastel con cortes radiales en los puntos y , le damos un pedazo al socio No. 1 y una adición al socio y principal No. 2. La división es QUIÉN, ya que el valor de cada socio es exactamente igual a su estimación. También es EP porque se maximiza la participación del socio n.º 1, por lo que no hay forma de dar más al socio n.º 2 sin perder al socio n.º 1. $v_{1}([t,y(t)])$ ${\ estilo de visualización t ^ {\ ast}}$ ${\ estilo de visualización t ^ {\ ast}}$ $y(t^{\ast})$ ${\ estilo de visualización [t ^ {\ ast}, y (t ^ {\ ast})]}$

División equitativa

Una división imparcial es una división en la que el valor subjetivo de ambos socios es el mismo (es decir, cada socio está igualmente satisfecho).

Siempre hay una división del pastel para dos socios que es imparcial y libre de envidia. Sin embargo, actualmente no se conoce ningún procedimiento para encontrar tal separación [3] .

Si los valores de las medidas de los socios son absolutamente continuos entre sí (es decir, cualquier pieza que tiene un valor positivo para un socio también tiene un valor positivo para el otro socio), entonces hay una libre de envidia. partición que también es imparcial y eficiente en el sentido de Pareto . Nuevamente, no se conoce ningún procedimiento para tal división [3] .

División adecuada

Se dice que una regla de división es correcta si mostrar funciones de valor verdadero es una estrategia débilmente dominante en esta regla. Es decir, no es posible obtener ningún valor tergiversando los valores.

Se dice que una regla de división es dictatorial si le da todo el pastel a un solo socio predeterminado.

La regla de división EP es correcta si y solo si es dictatorial [4] .

Tres o más socios

División sin envidia para 3 socios

El procedimiento de cuchillo móvil de Stromquist se puede usar para cortar en la dimensión 1, por lo que obviamente se puede usar para cortar un pastel.

Pero hay un algoritmo más simple que aprovecha la forma redonda del pastel [6] [3] .

El compañero A rota tres cuchillas radiales continuamente alrededor del pastel, asegurándose de que los sectores tengan (en su estimación) 1/3-1/3-1/3 de tamaño.

El socio B evalúa el valor de estos tres cuadrantes. Por lo general, todos tienen valores diferentes, pero en algún momento los dos sectores tendrán el mismo valor. Esto se debe a que después de una rotación de 120 grados , el cuadrante que antes era más importante ahora tendrá menos importancia y el otro cuadrante será ahora el más significativo. Por lo tanto, por el teorema del valor intermedio , debe haber una posición de rotación cuando el usuario B ve dos sectores idénticos. En este punto, el compañero B dice "detente".

Luego, los socios eligen sectores en el orden C - B - A. El socio C, por supuesto, no siente celos, ya que elige primero. El socio B tiene al menos un sector más grande para elegir y el socio A cree que todas las piezas tienen el mismo valor.

Versiones de división sin envidia y eficientes en el sentido de Pareto

Para 3 socios, hay un pastel y las medidas correspondientes para las cuales no habrá corte EPOS [7] .

Esto también es cierto para más de 3 socios. Esto es cierto incluso si todas las funciones de valor son aditivas y estrictamente positivas (es decir, cualquier socio valora cualquier parte del pastel) [3] .

Ambos ejemplos usan medidas que son casi idénticas, pero con un refinamiento muy sutil. Debido a que las medidas son casi uniformes, es fácil encontrar cortes de pastel casi libres de envidia y casi no dominados. No se sabe si es posible encontrar ejemplos en los que los desacuerdos sean mucho mayores.

División proporcional con diferentes acciones

Cuando hay 3 o más socios con diferentes participaciones, se requiere una división proporcional ponderada (WPA). La división VPD con piezas conectadas no siempre existe [5] .

Esto es análogo a la imposibilidad de un pastel de intervalo unidimensional y 2 socios (consulte la sección División proporcional ponderada del artículo El problema del corte justo del pastel ).

Notas

↑ Stromquist, Woodall, 1985 , pág. 241–248.
↑ Vendaval, 2009 , pág. 48–52.
↑ 1 2 3 4 5 Barbanel, Brams, Stromquist, 2009 , pág. 496.
↑ 12 Thomson , 2006 , pág. 501–521.
↑ 1 2 3 Brams, Jones, Klamler, 2007 , pág. 353.
↑ Brams, Taylor, Zwicker, 1997 , pág. 547–554.
↑ Stromquist, 2007 .

Literatura

Stromquist W., Woodall DR Conjuntos en los que concuerdan varias medidas // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Gale D. Entretenimientos matemáticos // The Mathematical Intelligencer. - 2009. - T. 15 . -doi : 10.1007/ BF03025257 .
Barbanel JB, Brams SJ, Stromquist W. Cortar un pastel no es pan comido // American Mathematical Monthly. - 2009. - T. 116 , núm. 6 _ -doi : 10.4169 / 193009709X470407 .
Thomson W. Niños llorando en fiestas de cumpleaños. ¿Por qué? // Teoría económica. - 2006. - T. 31 , núm. 3 . -doi : 10.1007/ s00199-006-0109-3 .
Brams SJ, Jones MA, Klamler C. Corte de tarta proporcional // International Journal of Game Theory. - 2007. - T. 36 , núm. 3–4 . -doi : 10.1007 / s00182-007-0108-z .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. Una solución de cuchillo móvil para la división de pasteles sin envidia de cuatro personas // Actas de la Sociedad Matemática Estadounidense. - 1997. - T. 125 , núm. 2 . -doi : 10.1090 / s0002-9939-97-03614-9 .
Walter Stromquist. Un pastel que no se puede cortar de manera justa // Actas del Seminario Dagstuhl 07261 . — 2007.