La feria de pastel de corte problema es una variación de la torta de corte justo problema, en el que el recurso a ser dividida es circular.
Como ejemplo, considere un pastel de cumpleaños con forma de disco . El pastel debe dividirse entre varios niños de manera que ningún niño envidia a otro niño (como en un problema estándar de corte de pastel), con la restricción adicional de que los cortes deben ser radiales, de modo que cada niño reciba un sector circular .
Una posible aplicación del modelo circular podría ser dividir la costa de una isla en lotes conectados.
Otra posible aplicación es la división del tiempo periódico, como dividir un ciclo diario en períodos "de guardia".
Modelo
Por lo general, un pastel se modela como el intervalo unidimensional [0,2π] (o [0,1]), en el que se identifican los dos puntos finales.
Este modelo se introdujo en 1985 y posteriormente en 1993. [1] [2]
Todos los procedimientos para un corte de pastel justo también se pueden aplicar al corte de un pastel simplemente ignorando el hecho de que se identifican los dos puntos finales. Por ejemplo, si el procedimiento de corte de pastel arroja una división en la que Alice recibe [0,1 / 3] y George recibe [1 / 3,1], entonces le daríamos a Alice un sector circular de 120 grados y a George el restante. Sector con 240 grados.
El corte de pastel se vuelve más interesante cuando consideramos cuestiones de eficiencia , ya que en el corte de pastel son posibles más divisiones.
Dos socios
División sin envidia
Una división se llama libre de envidia (EF) si cada socio piensa que su pieza es al menos tan valiosa como la otra pieza.
Una división EF de un pastel siempre se puede encontrar usando dividir y elegir : un socio corta el pastel en dos sectores que considera iguales y el otro socio elige el sector que considera mejor. Pero para un pastel, pueden ser posibles mejores divisiones.
División sin envidia y Pareto-eficiente
Una división se llama Pareto eficiente (PE) si ninguna otra división es mejor para un socio y no peor para el otro. A menudo, la eficiencia de Pareto se evalúa solo en relación con un subconjunto de todas las divisiones posibles. Es decir, solo divisiones a dos sectores contiguos (divisiones con el mínimo de cortes).
Una división se llama PEEF si es tanto PE como EF.
Cuando las valoraciones de los socios son medidas (aditivas), el siguiente procedimiento de cuchilla móvil garantiza una división que es EF y PE en relación con las divisiones de dos sectores contiguos. [3]
Un socio (el Rotador) sostiene dos cuchillos radiales sobre el pastel de tal manera que, en su opinión, los dos sectores del pastel determinados por estos cuchillos tienen el mismo valor. Luego, gira estos cuchillos continuamente, por todo el camino alrededor del pastel, manteniendo este valor igual de los sectores hasta que los cuchillos vuelvan a sus posiciones originales.
El otro socio (el Elector) observa este proceso durante un ciclo completo. Luego, en el siguiente ciclo, identifica la posición que, a su juicio, da el valor máximo a uno de los dos sectores así determinados. El Selector recibe este sector y el Rotador recibe el otro sector.
Esta partición es obviamente EF, ya que el Rotador es indiferente entre los dos sectores, el Selector recibe el mejor sector. Es PE porque no hay una partición que le dé al Selector un valor mayor y deje un valor de 1/2 al Rotador.
Restricciones de aditividad
El procedimiento anterior funciona solo si la función de valor del Rotador es aditiva, de modo que las partes iguales siempre tengan el mismo valor de 1/2. Si su valor no es aditivo, entonces la división aún estaría libre de envidia, pero no necesariamente eficiente en el sentido de Pareto.
Además, cuando las valoraciones de ambos socios no son aditivas (por lo que ninguno de ellos puede jugar como Rotador), no siempre existe una división PEEF. [4]
División de consenso y división proporcional ponderada
Una división se llama división exacta (también conocida como división de consenso ) si el valor de la pieza es exactamente según todos los socios, donde el son pesos preespecificados.
Suponga que la suma de todos los pesos es 1 y que el valor del gráfico circular para todos los agentes también se normaliza a 1. Según el teorema de Stromquist-woodall , para cada peso, hay un subconjunto , que es una unión de como máximo sectores, que todos los socios valoran exactamente . Para agentes esto implica que siempre existe una división consensuada de un pastel con sectores conectados: dé al agente 1 un sector que vale exactamente para ambos agentes, y dale al agente 2 el sector restante, que vale para ambos agentes (ver [5] para una prueba alternativa).
Esto se puede generalizar a cualquier número de agentes: cada pieza excepto la última requiere como máximo cortes, por lo que el número total de cortes necesarios es .
Una división se llama proporcional si cada uno de los dos socios recibe un valor de al menos 1/2. Se llama proporcional ponderado (WPR) si el socio recibe un valor de al menos , dónde son pesos preespecificados que representan los diferentes derechos de los socios al pastel. El procedimiento anterior muestra que en un pastel, siempre existe una división WPR con piezas conectadas. Esto contrasta con una torta no circular (un intervalo), en la que es posible que no exista un WPR con piezas conectadas.
División ponderada sin envidia
Si las valoraciones de los socios son absolutamente continuas entre sí, entonces existe una división WPR que también es libre de envidia ponderada (WEF) y Pareto eficiente (PE), y la relación entre los valores de los socios es exactamente w 1 / w 2 . [5]
Prueba . Para cada ángulo t , deje ser el ángulo en el que la relación
La función es una función continua de t que alcanza un máximo para algunos. Cortar el pastel con cortes radiales en y , dando la pieza al socio n. ° 1 y el complemento al socio n. ° 2. La partición es WEF porque el valor de cada socio es exactamente la parte que le corresponde. Es PE porque se maximiza la participación del socio n. ° 1, por lo que no es posible dar más al socio n. ° 2 sin dañar al socio n. ° 1.
División equitativa
Una división equitativa es una división en la que el valor subjetivo de ambos socios es el mismo (es decir, cada socio es igualmente feliz).
Siempre existe una partición de un pastel para dos socios, que es a la vez libre de envidia y equitativa. Sin embargo, actualmente no se conoce ningún procedimiento para encontrar dicha partición. [3]
Cuando las medidas de valor de los socios son absolutamente continuas entre sí (es decir, cada pieza que tiene un valor positivo para un socio también tiene un valor positivo para el otro socio), entonces existe una partición libre de envidia, equitativa y Pareto eficiente. Nuevamente, no se conoce ningún procedimiento. [3]
División veraz
Una regla de división se llama veraz si informar las funciones de valor verdadero es una estrategia débilmente dominante en esa regla. Es decir, no es posible obtener ningún valor representando incorrectamente las valoraciones.
Una regla de división se llama dictatorial si asigna todo el pastel a un único socio preespecificado.
Una regla de división de educación física es verdadera si y solo si es dictatorial. [4]
Tres o más socios
Procedimiento 1 de ( n +1) para n socios
Iyer y Huhns [6] fueron los primeros en presentar un protocolo especializado para dividir un pastel. En su protocolo, cada agente marca ( n +1) piezas disjuntas en el pastel. El algoritmo le da a cada agente una de sus piezas.
División sin envidia para 3 socios
El procedimiento de cuchillos móviles de Stromquist se puede utilizar para cortar un pastel en una dimensión, por lo que, obviamente, también se puede usar para cortar un pastel.
Pero hay un algoritmo más simple, que aprovecha la circularidad del pastel. [7] [3]
El socio A gira tres cuchillas radiales continuamente alrededor del pastel, manteniendo lo que cree que son 1 / 3-1 / 3-1 / 3 sectores.
El socio B mide el valor de estos 3 sectores. Por lo general, todos tendrán valores diferentes, pero en un momento, dos sectores tendrán el mismo valor. ¿Por qué? Porque después de una rotación de 120 grados, el sector que antes era el más valioso ahora es menos valioso, y otro sector es ahora el más valioso. Por tanto, según el teorema del valor intermedio , debe haber una posición en la rotación cuando el socio B considera que dos sectores están empatados por el mayor. En este punto, el socio B llama "detener".
Los socios luego eligen sectores en el orden: C - B - A. El socio C, por supuesto, no siente envidia porque es el primero en elegir; el socio B tiene al menos un sector más grande para elegir; y el socio A piensa que todas las piezas tienen el mismo valor de todos modos.
División sin envidia y Pareto-eficiente
Para 3 socios, existe un pastel y las medidas correspondientes para las que no hay asignación PEEF. [8]
Esto también es válido para más de 3 socios. Esto es cierto incluso si todas las funciones de valor son aditivas y estrictamente positivas (es decir, cada socio valora cada bit del pastel). [3]
Ambos ejemplos utilizan medidas que son casi uniformes, pero con ajustes muy finos. Dado que las medidas son casi uniformes, es fácil encontrar asignaciones del pastel que están casi libres de envidia y casi sin dominar. No se sabe si es posible encontrar ejemplos en los que las discrepancias sean mucho mayores.
División proporcional con diferentes derechos
Cuando hay 3 o más socios con diferentes derechos, se necesita una división proporcional ponderada (WPR). No siempre existe una división WPR con piezas conectadas. [5]
Esto es análogo a un resultado de imposibilidad para pastel de intervalo unidimensional y 2 socios (ver corte de pastel proporcional con diferentes derechos ).
enlaces externos
Referencias
- ^ Stromquist, W .; Woodall, DR (1985). "Conjuntos en los que coinciden varias medidas" . Revista de Análisis y Aplicaciones Matemáticas . 108 : 241–248. doi : 10.1016 / 0022-247x (85) 90021-6 .
- ^ Gale, D. (2009). "Entretenimientos matemáticos". El inteligente matemático . 15 : 48–52. doi : 10.1007 / BF03025257 .
- ^ a b c d e Barbanel, JB; Brams, SJ; Stromquist, W. (2009). "Cortar una tarta no es pan comido". American Mathematical Monthly . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . doi : 10.4169 / 193009709X470407 .
- ^ a b Thomson, W. (2006). "Niños llorando en fiestas de cumpleaños. ¿Por qué?". Teoría económica . 31 (3): 501–521. doi : 10.1007 / s00199-006-0109-3 .
- ^ a b c Brams, SJ; Jones, MA; Klamler, C. (2007). "Corte de tarta proporcional". Revista Internacional de Teoría de Juegos . 36 (3–4): 353. doi : 10.1007 / s00182-007-0108-z .
- ^ Iyer, Karthik; Huhns, Michael (2005). Meersman, Robert; Tari, Zahir (eds.). "Negociación multiagente para la asignación de recursos justa e imparcial" . En movimiento hacia sistemas de Internet significativos 2005: CoopIS, DOA y ODBASE . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 3760 : 453–465. doi : 10.1007 / 11575771_29 . ISBN 978-3-540-32116-3.
- ^ Brams, Steven J .; Taylor, Alan D .; Zwicker, William S. (1997). "Una solución de cuchillo móvil para la división de pasteles sin envidia de cuatro personas". Actas de la American Mathematical Society . 125 (2): 547–554. CiteSeerX 10.1.1.104.3390 . doi : 10.1090 / s0002-9939-97-03614-9 .
- ^ Stromquist, Walter (junio de 2007). Un pastel que no se puede cortar de forma justa . Consultado el 15 de diciembre de 2014 . Parámetro desconocido
|book-title=
ignorado ( ayuda )