Un corte de pastel sin envidia es una especie de corte de pastel justo . Es una división de un recurso heterogéneo ("pastel") que satisface el criterio libre de envidia , es decir, que cada socio siente que su parte asignada es al menos tan buena como cualquier otra parte, según su propia valoración subjetiva.
¿Cuál es la complejidad del tiempo de ejecución de cortar pasteles sin envidia?
Cuando solo hay dos socios, el problema es fácil y se ha resuelto en los tiempos bíblicos mediante el protocolo de dividir y elegir . Cuando hay tres o más socios, el problema se vuelve mucho más desafiante.
Se han estudiado dos variantes principales del problema:
- Piezas conectadas , por ejemplo, si el pastel es un intervalo unidimensional, cada socio debe recibir un único subintervalo. Si hay socios, solo se necesitan cortes.
- Piezas generales , por ejemplo, si el pastel es un intervalo unidimensional, entonces cada socio puede recibir una unión de subintervalos inconexos.
Historia corta
La investigación moderna del problema de la tarta justa comenzó en la década de 1940. El primer criterio de equidad estudiado fue la división proporcional , y pronto se encontró un procedimiento para n socios .
George Gamow y Marvin Stern introdujeron en la década de 1950 el criterio más estricto de la ausencia de envidia en el problema del corte de la torta . [1]
Un procedimiento para tres socios y piezas generales se encontró en 1960. Un procedimiento para tres socios y piezas conectadas sólo se encontró en 1980.
La división sin envidias para cuatro o más socios ha sido un problema abierto hasta la década de 1990, cuando se publicaron tres procedimientos para piezas generales y un procedimiento para piezas conectadas . Todos estos procedimientos son ilimitados ; pueden requerir una serie de pasos que no están limitados de antemano. El procedimiento para piezas conectadas puede incluso requerir un número infinito de pasos.
En la década de 2000 se publicaron dos límites inferiores sobre la complejidad en tiempo de ejecución de la ausencia de envidia.
- Para piezas generales, el límite inferior es Ω ( n 2 ) .
- Para las piezas conectadas, el límite inferior es infinito ; es probable que no haya un protocolo finito para tres o más socios.
En la década de 2010, se han publicado varios procedimientos de aproximación y procedimientos para casos especiales . La cuestión de si existen procedimientos de tiempo acotado para el caso de piezas generales ha permanecido abierta durante mucho tiempo. El problema finalmente se resolvió en 2016. Haris Aziz y Simon Mackenzie presentaron un protocolo discreto sin envidia que requiere como máximoconsultas. Todavía hay una brecha muy grande entre el límite inferior y el procedimiento. En agosto de 2016, aún se desconoce la complejidad exacta en tiempo de ejecución de la ausencia de envidia.
Para el caso de piezas conectadas, se observó que el resultado de la dureza supone que se debe dividir toda la torta. Si este requisito se reemplaza por el requisito más débil de que cada socio reciba un valor proporcional (al menos 1 / n del valor total de la torta según su propia valoración), entonces se conoce un procedimiento acotado para tres socios , pero ha permanecido abierto. Problema de si existen procedimientos de tiempo limitado para cuatro o más socios.
Piezas conectadas
Prueba de existencia
Una división libre de envidia para n agentes con piezas conectadas siempre existe bajo las siguientes suposiciones moderadas: [2]
- Ningún agente prefiere una pieza vacía sobre una no vacía.
- Las preferencias de los agentes son continuas.
Tenga en cuenta que se no se requiere que las preferencias de los agentes están representados por una función aditiva .
El concepto principal en la demostración es el simplex de particiones . Suponga que el pastel es el intervalo [0,1]. Cada partición con piezas conectadas se puede representar de forma única mediante n - 1 números en [0,1] que representan las ubicaciones de corte. La unión de todas las particiones es simple.
Para cada partición, cada agente tiene una o más piezas que prefieren débilmente. Por ejemplo, para la partición representada por "0.3,0.5", un agente puede preferir la pieza n. ° 1 (la pieza [0,0.3]) mientras que otro agente puede preferir la pieza n. ° 2 (la pieza [0.3,0.5]) mientras que un tercer agente podría preferir tanto la pieza n. ° 1 como la pieza n. ° 2 (lo que significa que son indiferentes entre ellas pero les gusta más que la pieza n. ° 3).
Para cada agente, la partición simplex está cubierta por n partes, posiblemente superpuestas en sus límites, de modo que para todas las particiones de la parte i , el agente prefiere la parte i . En el interior de la parte i , el agente prefiere solo la parte i , mientras que en el límite de la parte i , el agente también prefiere algunas otras partes. Entonces, para cada i , hay una cierta región en la partición simplex en la que al menos un agente prefiere solo la parte i . Llame a esta región U i . Usando un cierto lema topológico (que es similar al lema de Knaster-Kuratowski-Mazurkiewicz ), es posible probar que la intersección de todas las U i no es vacía. Por lo tanto, existe una partición en la que cada pieza es la preferencia única de un agente. Dado que la cantidad de piezas es igual a la cantidad de agentes, podemos asignar cada pieza al agente que la prefiera y obtener una asignación sin envidia.
Procedimientos
Para tres agentes, se puede encontrar una división sin envidia utilizando varios procedimientos diferentes:
- El procedimiento de cuchillos móviles de Stromquist utiliza cuatro cuchillos que se mueven simultáneamente: uno movido por un árbitro y otro para cada agente.
- El procedimiento de cuchillos móviles de Barbanel-Brams utiliza dos cuchillos que se mueven simultáneamente.
- El procedimiento de cuchilla giratoria de Robertson-Webb se puede utilizar cuando la torta es bidimensional y utiliza sólo una cuchilla móvil.
Estos son procedimientos continuos: se basan en personas que mueven los cuchillos de forma continua y simultánea. No se pueden ejecutar en un número finito de pasos discretos.
Para n agentes, se puede encontrar una división libre de envidia mediante el protocolo de corte de pastel de Simmons . El protocolo usa un simplex de particiones similar al usado en la prueba de existencia de Stromquist. Genera una secuencia de particiones que converge en una partición sin envidia. La convergencia puede tomar infinitos pasos.
No es una coincidencia que todos estos algoritmos puedan requerir infinitas consultas. Como mostramos en la siguiente subsección, puede ser imposible encontrar un corte de pastel sin envidias con piezas conectadas con un número finito de consultas.
Resultado de dureza
Una división sin envidia con piezas conectadas para 3 o más agentes no se puede encontrar mediante un protocolo finito en el modelo de consulta de Robertson-Webb . [3] La razón por la que este resultado no contradice los algoritmos mencionados anteriormente es que no son finitos en el sentido matemático. [4]
La prueba de imposibilidad utiliza un sistema de medida rígido (RMS), un sistema de n medidas de valor, para el cual una división sin envidia debe cortar el pastel en lugares muy específicos. Entonces, encontrar una división libre de envidia se reduce a encontrar estas ubicaciones específicas. Suponiendo que el pastel es el intervalo real [0,1], encontrar una división libre de envidia mediante consultas a los agentes es equivalente a encontrar un número real en el intervalo [0,1] utilizando preguntas de sí / no. Esto puede requerir un número infinito de preguntas.
Se puede construir un RMS para tres agentes de la siguiente manera. Sean x , y , s y t parámetros que satisfagan:
Construya un conjunto de tres medidas con estas dos propiedades:
- La densidad de cada medida es siempre estrictamente entre √ 2 /2 y √ 2 (por lo que para una determinada pieza, las valoraciones de los agentes difieren por un factor de menos de 2).
- Los valores de las piezas determinadas por x y y son como en la tabla:
Agente [0, x ] [ x , y ] [ y , 1] A t t s B s t t C t s t
Entonces, todas las divisiones libre de envidias entre Alice, Bob y Carl debe tener cortes en X e Y (hay exactamente dos de estas divisiones), ya que todas las demás opciones conducen a la envidia:
- Si se hacen cortes a la izquierda de xy a la derecha de y , entonces Alice y Bob insisten en obtener la pieza del medio.
- Si x * ≤ x e y * ≥ Y , y una de las desigualdades es estricta, entonces los valores de todo el mundo, ya sea la pieza, derecha o izquierda la pieza más de la mitad, así que quien recibe la mitad será envidioso.
- Si x * ≥ x e y * ≤ Y , y una de las desigualdades es estricta, a continuación, Alice y Bob prefieren la pieza central sobre cualquier otra pieza, por lo que el que no sacarlo de los dos será envidioso de la otra .
- Si se hacen cortes a la derecha de x ya la derecha de Y (por ejemplo, en x * > x e y * > y ), entonces Alice y Carl prefieren la pieza más a la izquierda de la pieza más a la derecha, por lo que Bob debe aceptar la pieza más a la derecha. Esto significa que Bob debe valorar la pieza [ x , x * ] al menos el doble que [ y , y * ]. Pero debido a la restricción en las densidades de valor, esto significa que tanto Alice como Carl valoran [ y , y * ] menos del doble que [ x , x * ], por lo que insisten en la pieza más a la izquierda.
- El cuarto caso (cortes a la izquierda de xy a la izquierda de y ) es análogo.
Para cada RMS, cada agente iy cada constante ε> 0, hay un RMS ligeramente diferente con las siguientes propiedades:
- La nueva medida de valor del agente i es completamente idéntica a su antigua medida de valor;
- Las nuevas medidas de valor de los otros dos agentes son idénticas a su antigua medida de valor en todas partes excepto en una vecindad ε de x e y .
Esto implica que, si todas las preguntas contestadas hasta ahora estaban fuera de la ε -neighbourhood de x y y , a continuación, el agente i no tiene manera de saber si estamos en los viejos RMS o en las nuevas RMS.
Equipado con este conocimiento, un adversario puede engañar a todos los protocolos de división sin envidia para que continúen para siempre:
- Empiece con cualquier valor eficaz, por ejemplo, con los parámetros x = 1/3, y = 2/3, s = 0,3 y t = 0,35.
- Mientras el protocolo hace cortes en puntos distintos de x e y , dejar que continúe.
- Cada vez que el protocolo de pregunta agente i para hacer un corte en X o Y , cambiar a otro RMS con x '≠ x e y' ≠ y , asegurándose de que los valores son los mismos para todos los cortes realizados previamente.
Por lo tanto el protocolo no puede hacer cortes en la correcta x e y se requiere para una división libre de envidias.
Aproximaciones
Dado que el corte de pasteles sin envidias con piezas conectadas no se puede hacer en un tiempo finito, los cortadores de pasteles han tratado de encontrar soluciones alternativas.
Una solución alternativa es buscar divisiones que solo estén aproximadamente libres de envidia . Hay dos formas de definir la aproximación: en unidades de longitud o en unidades de valor .
La aproximación basada en longitud utiliza las siguientes definiciones:
- Una partición de un pastel está representada por las n longitudes de intervalos que crea. Entonces (0.2, 0.5, 0.3) es una partición del intervalo unitario en tres subintervalos con longitudes 0.2, 0.5 y 0.3 (se genera cortando el intervalo unitario en 0.2 y en 0.7).
- Una partición múltiple es un conjunto de varias particiones diferentes.
- Una partición múltiple X se llama libre de envidia si existe una permutación de los socios tal que, para cada i , existe un elemento de X tal que el i -ésimo socio prefiere el i -ésimo segmento.
- Una partición múltiple δ es una partición múltiple en la que, para cada par de particiones, la diferencia entre cada una de sus coordenadas es como máximo δ . Por ejemplo: {(0.2+ δ , 0.5,0.3), (0.2,0.5+ δ , 0.3), (0.2,0.5,0.3+ δ )}.
El parámetro δ representa la tolerancia de los socios en unidades de longitud. Por ejemplo, si la tierra está dividida y los socios están de acuerdo en que una diferencia de 0.01 metros en la ubicación de la frontera no es relevante para ellos, entonces tiene sentido buscar una partición múltiple de 0.01 que no tenga envidia. Deng et al [5] presentan una modificación del protocolo de corte de pastel de Simmons que encuentra una partición δ -múltiple sin envidia usandoconsultas. Además, demuestran un límite inferior deconsultas. Incluso cuando las funciones de utilidad son dadas explícitamente por algoritmos de tiempo polinomial, el problema de cortar el pastel sin envidia es PPAD -completo.
La aproximación basada en valores utiliza las siguientes definiciones:
- Una partición X se llama ε-libre de envidia si existe una permutación de los socios tal que, para cada i , el valor de la i -ésima pieza más ε es al menos tanto como el valor de cualquier otra pieza:.
- Una medida de valor se llama Lipschitz-continua si existe una constante K tal que, para cualquier par de intervalos, la diferencia de valores entre ellos es como máximo K veces la longitud de su diferencia simétrica.
Si todas las medidas de valor son continuas de Lipschitz, entonces las dos definiciones de aproximación están relacionadas. Dejar. Entonces, cada partición en una envidia de libre δ -partición -multi es ε -envy libre. [5] Por lo tanto, los resultados de Deng et al. Demuestran que, si todos los socios tienen valoraciones continuas de Lipschitz, se puede encontrar una partición libre de envidia ε con consultas con valoraciones generales.
Con valoraciones aditivas, para cualquier ε> 0, un corte de pastel conectado sin envidia requiere al menos consultas de Ω (log ε −1 ). Para 3 agentes, existe un protocolo O (log ε −1 ). Para 4 o más agentes, el protocolo más conocido requiere O ( n ε −1 ), que muestra una brecha exponencial en la complejidad de la consulta. [6] Además, aunque el último protocolo tiene un polinomio de complejidad de consulta en n , su complejidad computacional es exponencial en n , incluso para ε constante. Si se requiere el cálculo de tiempo polinomial, la aproximación más conocida es-envidia-libre. [7]
El cálculo fuera de línea es una segunda solución alternativa que encuentra una división totalmente libre de envidia, pero solo para una clase restringida de valoraciones. Si todas las medidas de valor son los polinomios de grado a lo sumo d , hay un algoritmo que es polinomio en n y d . [8] Dado d , el algoritmo pregunta a los agentes d +1 consultas de evaluación, que dan d +1 puntos en el gráfico de la medida del valor. Se sabe que d +1 puntos son suficientes para interpolar un polinomio de grado d . Por lo tanto, el algoritmo puede interpolar todas las medidas de valor de todos los agentes y encontrar una división sin envidia fuera de línea. La cantidad de consultas requeridas es.
Otra restricción de las valoraciones es que son constantes por partes : para cada agente, hay como máximo m intervalos deseados y la densidad de valor del agente en cada intervalo es constante. Bajo este supuesto, se puede encontrar una asignación sin envidia conectada resolviendoprogramas lineales. Por tanto, cuando n es constante, el problema es polinomio en m . [9]
La eliminación gratuita es una tercera solución alternativa que mantiene el requisito de que la división sea totalmente libre de envidia y funcione para todas las medidas de valor, pero elimina el requisito de que todo el pastel debe dividirse. Es decir, permite dividir un subconjunto del bizcocho y descartar el resto. Sin más requisitos el problema es trivial, ya que siempre es libre de envidia no dar nada a todos los agentes. Por tanto, el objetivo real es dar a cada agente un valor estrictamente positivo. Cada asignación de pastel se puede caracterizar por su nivel de proporcionalidad , que es el valor del agente menos afortunado. Una división sin envidia de todo el pastel es también una división proporcional , y su nivel de proporcionalidad es al menos, que es lo mejor posible. Pero cuando se permite la libre disposición, una división sin envidia puede tener un nivel de proporcionalidad más bajo, y el objetivo es encontrar una división sin envidia con la proporcionalidad más alta posible. Los límites conocidos actualmente son:
- Para 3 agentes, la proporcionalidad es , es decir, una división proporcional y sin envidia es alcanzable en tiempo limitado. [10]
- Para 4 agentes, la proporcionalidad es . [10]
- Para n agentes, la proporcionalidad es. [11]
No se sabe si existe un procedimiento de división proporcional y sin envidia en tiempo limitado para cuatro o más socios con piezas conectadas.
Variantes
La mayoría de los procedimientos para cortar pasteles con piezas conectadas asumen que la torta es un intervalo unidimensional y que las piezas son subintervalos unidimensionales. A menudo, es deseable que las piezas tengan una determinada forma geométrica, como un cuadrado. Con tales restricciones, puede ser imposible dividir todo el pastel (por ejemplo, un cuadrado no se puede dividir en dos cuadrados), por lo que debemos permitir la libre disposición. Como se explicó anteriormente , cuando se permite la libre disposición, los procedimientos se miden por su nivel de proporcionalidad , el valor que garantizan a todos los agentes. Actualmente se conocen los siguientes resultados: [12]
- Para dos socios que comparten un pastel cuadrado y quieren trozos cuadrados, la proporcionalidad es , y esto es lo mejor que se puede garantizar incluso sin envidia.
- Para tres socios que comparten un pastel cuadrado y quieren trozos cuadrados, la proporcionalidad es ; lo mejor que se puede garantizar sin envidia es.
Piezas desconectadas
Procedimientos
Para tres socios, el procedimiento discreto Selfridge-Conway hace una división sin envidia con un máximo de 5 cortes. Otros procedimientos que utilizan cuchillos móviles requieren menos cortes:
- El procedimiento de cuchillas móviles de Levmore-Cook requiere como máximo 4 cortes;
- El procedimiento de cuchillas giratorias de Brams-Taylor-Zwicker para cortar pasteles requiere como máximo 3 cortes (esto da como resultado tres piezas conectadas cuando la torta es un círculo, pero cuando la torta es un intervalo, habrá cuatro piezas);
- Usando el procedimiento de cuchilla móvil de Austin para dos socios, es posible obtener una división sin envidia para 3 socios utilizando como máximo 3 cortes. Esta idea se atribuye a William Webb. [13] : 124-125
Para cuatro socios, el procedimiento de Brams-Taylor-Zwicker crea una división sin envidia con un máximo de 11 cortes. [14] Para cinco socios, un procedimiento de Saberi y Wang crea una división sin envidia con un número limitado de cortes. [15] Ambos procedimientos utilizan el procedimiento de Austin para dos socios y fracciones generales como paso inicial. Por lo tanto, estos procedimientos deben considerarse infinitos; no se pueden completar con un número finito de pasos.
Para cuatro o más socios, hay tres algoritmos que son finitos pero ilimitados: no hay un límite fijo en el número de cortes requeridos. [16] Hay tres algoritmos de este tipo:
- El protocolo Brams-Taylor , publicado por primera vez en un artículo de 1995 y más tarde en un libro de 1996.
- El protocolo Robertson-Webb , publicado por primera vez en un artículo de 1997 y más tarde en un libro de 1998.
- El protocolo Pikhurko, [17] publicado en 2000.
Aunque los protocolos son diferentes, la idea principal detrás de ellos es similar: Divida el pastel en un número finito pero ilimitado de "migajas", cada una de las cuales es tan pequeña que su valor para todos los socios es insignificante. Luego combine las migas de una manera sofisticada para obtener la división deseada. William Gasarch ha comparado los tres algoritmos ilimitados utilizando números ordinales . [18]
La cuestión de si se puede cortar un pastel sin envidias en un tiempo limitado para cuatro o más socios ha estado abierta durante muchos años. Finalmente fue resuelto en 2016 por Hariz Aziz y Simon Mackenzie. Inicialmente, desarrollaron un algoritmo de tiempo limitado para cuatro socios. [19] Luego ampliaron su algoritmo para manejar cualquier número de socios. [11] Su algoritmo requiere como máximoconsultas. Si bien este número está acotado, está muy lejos del límite inferior de. Entonces, la pregunta de cuántas consultas se requieren para cortar pasteles sin envidia aún está abierta.
Aproximaciones y soluciones parciales
Una variante reentrante del último protocolo reductor encuentra una aproximación aditiva a una división libre de envidia en el tiempo limitado. Específicamente, para cada constante, devuelve una división en la que el valor de cada socio es al menos el valor más grande menos , a tiempo .
Si todas las medidas de valor son lineales por partes , existe un algoritmo que es polinomial en el tamaño de la representación de las funciones de valor. [20] El número de consultas es, dónde es el número de discontinuidades en las derivadas de las funciones de densidad de valor.
Resultado de dureza
Cada procedimiento sin envidia para n personas requiere al menos Ω ( n 2 ) consultas en el modelo de consulta de Robertson-Webb . [21] La prueba se basa en un análisis cuidadoso de la cantidad de información que el algoritmo tiene sobre cada socio.
A. Suponga que el pastel es el intervalo unidimensional [0,1], y que el valor del pastel completo para cada uno de los socios está normalizado 1. En cada paso, el algoritmo le pide a un socio determinado que evalúe un determinado intervalo contenido en [0,1], o para marcar un intervalo con un valor especificado. En ambos casos, el algoritmo recopila información solo sobre los intervalos cuyos puntos finales se mencionaron en la consulta o en la respuesta. Llamemos puntos de referencia a estos puntos finales . Inicialmente, los únicos puntos de referencia de i son 0 y 1, ya que lo único que el algoritmo sabe sobre el socio i es que v i ([0,1]) = 1. Si el algoritmo le pide al socio i que evalúe el intervalo [0.2,1], luego de la respuesta los puntos de referencia de i son {0,0.2,1}. El algoritmo puede calcular v i ([0,0.2]), pero no el valor de ningún intervalo cuyo punto final sea diferente de 0.2. El número de puntos de referencia aumenta como máximo en 2 en cada consulta. En particular, el valor del intervalo [0,0.2] podría concentrarse completamente cerca de 0, o completamente cerca de 0.2, o en cualquier punto intermedio.
B. Un intervalo entre dos hitos consecutivos del socio i se denomina intervalo de hitos del socio i . Cuando el algoritmo decide asignar un trozo de pastel al socio i , debe asignar un trozo cuyo valor total para i sea al menos igual de grande como cualquier intervalo de referencia de i . La prueba es por contradicción: suponga que hay un cierto intervalo de referencia J cuyo valor para i es mayor que el valor realmente asignado a i . Algún otro asociado, por ejemplo j , recibirá necesariamente una parte de la señal de intervalo J . Según el párrafo A, es posible que todo el valor del intervalo J se concentre dentro de la participación asignada al socio j . Por lo tanto, i Envies j y la división no es libre de envidias.
C. Suponga que todos los socios responden a todas las consultas como si su medida de valor fuera uniforme (es decir, el valor de un intervalo es igual a su longitud). Según el párrafo B, el algoritmo puede asignar una pieza al socio i , solo si es más largo que todos los intervalos de referencia de i . Al menos n / 2 socios deben recibir un intervalo con una duración de como máximo 2 / n ; por tanto, todos sus intervalos de puntos de referencia deben tener una longitud máxima de 2 / n ; por lo tanto, deben tener al menos n / 2 intervalos de referencia; por lo tanto, deben tener al menos n / 2 puntos de referencia.
D. Cada consulta respondida por el socio i implica como máximo dos nuevos puntos finales, por lo que aumenta el número de puntos de referencia de i en un máximo de 2. Por lo tanto, en el caso descrito en el párrafo C, el algoritmo debe preguntar a cada uno de n / 2 socios, al menos n / 4 consultas. El número total de consultas es así al menos n 2 /8 = Ω ( n 2 ).
Pruebas de existencia y variantes.
Además de las pruebas de existencia generales implícitas en los algoritmos descritos anteriormente, existen pruebas de la existencia de particiones libres de envidia con propiedades adicionales:
- Existe una división exacta , que en particular no tiene envidia; véanse los teoremas de Dubins-Spanier .
- Existe una división libre de envidia que también es Pareto eficiente ; Vea el teorema de Weller .
Ambas pruebas funcionan solo para medidas de valor aditivo y no atómico, y se basan en la capacidad de proporcionar a cada socio una gran cantidad de piezas desconectadas.
División sin envidia con diferentes derechos
Una generalización común del criterio libre de envidia es que cada uno de los socios tiene un derecho diferente. Es decir, para cada socio i hay un peso w i que describe la fracción del pastel que tienen derecho a recibir (la suma de todos w i es 1). Entonces, una división ponderada libre de envidia se define de la siguiente manera. Para cada agente i con la medida de valor V i , y para todos los demás agentes j :
Es decir, cada socio piensa que su asignación en relación con su derecho es al menos tan grande como cualquier otra asignación en relación con el derecho del otro socio.
Cuando todos los pesos son iguales (e iguales a 1 / n ), esta definición se reduce a la definición estándar de ausencia de envidia.
Cuando las piezas pueden desconectarse, siempre existe una división ponderada sin envidia y se puede encontrar mediante el protocolo Robertson-Webb , para cualquier conjunto de pesos. Zeng presentó un algoritmo alternativo para la división sin envidia ponderada aproximada, que requiere un número menor de cortes. [22]
Pero cuando las piezas deben estar conectadas, es posible que no exista una división ponderada sin envidia. Para ver esto, tenga en cuenta que cada división ponderada libre de envidia también es ponderada proporcional con el mismo vector de peso; esto significa que, para cada agente i con medida de valor V i :
Se sabe que es posible que no exista la asignación proporcional ponderada con piezas conectadas: consulte el ejemplo de corte proporcional de pasteles con diferentes derechos .
Tenga en cuenta que existe una definición alternativa de división sin envidia ponderada, en la que los pesos se asignan a las piezas en lugar de a los agentes. Con esta definición, se sabe que existe una división ponderada libre de envidia en los siguientes casos (cada caso generaliza el caso anterior):
- Las funciones de valor aditivo, la torta unidimensional (intervalo) y las piezas deben ser intervalos conectados. [23]
- Las funciones de valor aditivo, la torta simplex multidimensional y las piezas deben ser símplex. [24] La prueba utiliza el teorema de Sperner , el KKM lema , lema que cubre de Gale y Ky Fan lema 's en los puntos de coincidencia .
- Funciones de valor no aditivo, torta simplex multidimensional y las piezas deben ser politopos . [25]
Dividiendo un pastel 'malo'
En algunos casos, el 'pastel' a dividir tiene un valor negativo. Por ejemplo, podría ser un trozo de césped que deba cortarse o un terreno baldío que deba limpiarse. Entonces, el pastel es un "mal heterogéneo" en lugar de un "bien heterogéneo".
Algunos procedimientos para cortar pasteles sin envidia se pueden adaptar para que funcionen con un pastel malo, pero la adaptación a menudo no es trivial. Consulte la división de tareas sin envidia para obtener más detalles.
Tablas de resumen
Nombre | Tipo | Pastel | Piezas | #consultas | #cortes | envidia | Comentarios | ||
---|---|---|---|---|---|---|---|---|---|
Dividir y elegir | Proc discreto | Alguna | Conectado | 2 | 2 | 1 (óptimo) | Ninguno | 1/2 | |
Stromquist | Proc de cuchilla móvil | Intervalo | Conectado | 3 | ∞ | 2 (óptimo) | Ninguno | 1/3 | |
Selfridge – Conway | Proc discreto | Alguna | Desconectado | 3 | 9 | 5 | Ninguno | 1/3 | |
Brams – Taylor – Zwicker | Proc de cuchilla móvil | Alguna | Desconectado | 4 | ∞ | 11 | Ninguno | 1/4 | |
Saberi – Wang [15] | Proc discreto | Alguna | Desconectado | 4 | Encerrado | Encerrado | Ninguno | 1/4 | Eliminación gratuita |
Aziz – Mackenzie [19] | Proc discreto | Alguna | Desconectado | 4 | 203 | 584 | Ninguno | 1/4 | |
Saberi – Wang [15] | Proc de cuchilla móvil | Alguna | Desconectado | 5 | ∞ | Encerrado | Ninguno | 1/5 | |
Stromquist | Existencia | Intervalo | Conectado | norte | - | n -1 | Ninguno | 1 / n | |
Simmons | Proc discreto | Intervalo | Conectado | norte | ∞ | n -1 | Ninguno | 1 / n | |
Deng-Qi-Saberi | Proc discreto | Intervalo | Conectado | norte | n -1 | Aditivo | Solo cuando las valoraciones son Lipschitz-continuas | ||
Branzei [8] | Proc discreto | Intervalo | Conectado | norte | ? | Ninguno | 1 / n | Solo cuando las densidades de valor sean polinomiales con grado como máximo d . | |
El desperdicio hace que se apresure | Proc discreto | Intervalo | Conectado | 3 | 9 | 4 | Ninguno | 1/3 | Eliminación gratuita |
El desperdicio hace que se apresure | Proc discreto | Alguna | Conectado | 4 | dieciséis | 6 | Ninguno | 1/7 | Eliminación gratuita |
El desperdicio hace que se apresure | Proc discreto | Alguna | Conectado | norte | Ninguno | Eliminación gratuita | |||
Aziz-Mackenzie ConnectedPieces [11] | Proc discreto | Alguna | Conectado | norte | Ninguno | Eliminación gratuita | |||
Brams-Taylor | Proc discreto | Alguna | Desconectado | norte | Ilimitado | Ilimitado | Ninguno | 1 / n | |
Robertson-Webb | Proc discreto | Alguna | Desconectado | norte | Ilimitado | Ilimitado | Ninguno | 1 / n | Sin ponderación de envidia. |
Pikhurko [17] | Proc discreto | Alguna | Desconectado | norte | Ilimitado | Ilimitado | Ninguno | 1 / n | |
Aziz – Mackenzie [11] | Proc discreto | Alguna | Desconectado | norte | Ninguno | 1 / n | |||
Último disminuidor reentrante | Proc discreto | Intervalo | Desconectado | norte | ? | Aditivo | 1 / n | ||
Kurokawa-Lai-Procaccia [20] | Proc discreto | Intervalo | Desconectado | norte | ? | Ninguno | 1 / n | Solo cuando las densidades de valor son lineales por partes con como máximo k discontinuidades. | |
Weller | Existencia | Alguna | Desconectado | norte | - | ∞ | Ninguno | 1 / n | Pareto eficiente . |
2-D | Proc discreto | Cuadrado | Conectado y Cuadrado | 2 | 2 | 2 | Ninguno | 1/4 | Eliminación gratuita |
2-D | Proc de cuchilla móvil | Cuadrado | Conectado y Cuadrado | 3 | ∞ | 6 | Ninguno | 1/10 | Eliminación gratuita |
Resumen por número de agentes y tipo de piezas:
# agentes | Piezas conectadas | Piezas generales |
---|---|---|
2 | Dividir y elegir | |
3 | Procedimiento de cuchillos móviles Stromquist (tiempo infinito); El desperdicio se apresura (tiempo limitado, cortes limitados, eliminación gratuita, proporcional) | Procedimiento discreto de Selfridge-Conway (tiempo acotado, como máximo 5 cortes). |
4 | El desperdicio se apresura (tiempo acotado, cortes acotados, eliminación gratuita, proporcionalidad 1/7). | Procedimiento de cuchillas móviles de Brams-Taylor-Zwicker (tiempo infinito, como máximo 11 cortes). Procedimiento discreto de Saberi-Wang [15] (tiempo acotado, cortes acotados, libre disposición, proporcional). Procedimiento discreto de Aziz-Mackenzie [19] (tiempo acotado, cortes acotados, proporcional). |
5 | Procedimiento de cuchillos móviles de Saberi – Wang [15] (tiempo infinito, cortes acotados). | |
norte | Protocolo de Simmons (tiempo infinito) Deng-Qi-Saberi (aproximadamente tiempo exponencial sin envidia). El desperdicio hace prisa (completamente libre de envidia, tiempo exponencial, libre disposición, proporcionalidad exponencial) Aziz-Mackenzie ConnectedPieces [11] (completamente libre de envidia, tiempo exponencial, libre disposición, proporcionalidad lineal) | Brams y Taylor (1995) ; Robertson y Webb (1998) . - Ambos algoritmos requieren un número de cortes finito pero ilimitado. Procedimiento discreto de Aziz-Mackenzie [11] (tiempo acotado, cortes acotados, proporcional). |
Dureza | Todos los algoritmos para n ≥ 3 deben ser infinitos (Stromquist, 2008). | Todos los algoritmos deben utilizar al menos Ω ( n 2 ) pasos (Procaccia, 2009). |
Variantes | Existe una división ponderada libre de envidia para pesos arbitrarios (Idzik, 1995), incluso cuando el pastel y las piezas son símplex (Idzik e Ichiishi, 1996), e incluso con preferencias no aditivas (Dall'Aglio y Maccheroni, 2009). | Robertson-Webb puede encontrar divisiones ponderadas sin envidia para pesos arbitrarios. Existe una división perfecta (Dubins & Spanier, 1961). Existe un corte de torta eficiente y sin envidia ( teorema de Weller ). |
Ver también
- División de tareas sin envidia
- Asignación de artículos sin envidia
- Corte justo de pasteles
- Grupo libre de envidia
- Corte de torta proporcional
enlaces externos
- Calculadora de división justa : un subprograma para calcular la división sin envidia de pasteles, quehaceres, habitaciones y alquileres.
Referencias
- ^ Gamow, George; Stern, Marvin (1958). Rompecabezas matemático . ISBN 978-0670583355.
- ^ Stromquist, Walter (1980). "Cómo cortar un pastel de forma justa". The American Mathematical Monthly . 87 (8): 640–644. doi : 10.2307 / 2320951 . JSTOR 2320951 .
- ^ Stromquist, Walter (2008). "Las divisiones de pastel sin envidia no se pueden encontrar mediante protocolos finitos" (PDF) . Revista electrónica de combinatoria . 15 . doi : 10.37236 / 735 .
- ^ El procedimiento de cuchillos móviles de Stromquist requiere que los tres agentes ajusten sus cuchillos cada vez que se mueva la espada del árbitro. Dado que la espada se mueve continuamente, el número de pasos necesarios es un infinito incontable. El protocolo de corte de pastel de Simmons converge en una división sin envidia, pero la convergencia puede requerir un número infinito de pasos.
- ^ a b Deng, X .; Qi, Q .; Saberi, A. (2012). "Soluciones algorítmicas para cortar pasteles sin envidia". Investigación operativa . 60 (6): 1461-1476. doi : 10.1287 / opre.1120.1116 .
- ^ Brânzei, Simina; Nisan, Noam (13 de julio de 2018). "La complejidad de la consulta del corte de pasteles". arXiv : 1705.02946 [ cs.GT ].
- ^ Goldberg, Paul W .; Hollender, Alexandros; Suksompong, Warut (2020). "Corte de torta contigua: resultados de dureza y algoritmos de aproximación". Revista de Investigación en Inteligencia Artificial . 69 : 109-141. doi : 10.1613 / jair.1.12222 .
- ^ a b Brânzei, S. (2015). "Una nota sobre el corte de pasteles sin envidia con valoraciones polinomiales". Cartas de procesamiento de información . 115 (2): 93–95. doi : 10.1016 / j.ipl.2014.07.005 .
- ^ Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tayiko, Ahmad S. (10 de febrero de 2017). "Mecanismos libres de envidia con un número mínimo de cortes" . Trigésima Primera Conferencia AAAI sobre Inteligencia Artificial .
- ^ a b Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "Los residuos se apresuran". Transacciones ACM sobre algoritmos . 13 : 1–32. arXiv : 1511.02599 . doi : 10.1145 / 2988232 . S2CID 11358086 .
- ^ a b c d e f Aziz, Haris; MacKenzie, Simon (2016). "Un protocolo de corte de pastel discreto y limitado sin envidia para cualquier número de agentes". FOCS 2016 . arXiv : 1604.03655 . Código bibliográfico : 2016arXiv160403655A .
- ^ Erel Segal-Halevi y Avinatan Hassidim y Yonatan Aumann (enero de 2015). Corte de pastel sin envidia en dos dimensiones . La 29ª Conferencia AAAI sobre Inteligencia Artificial (AAAI-15). Austin, Texas. págs. 1021–1028. doi : 10.13140 / RG.2.1.5047.7923 .
- ^ Brams, Steven J .; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . Prensa de la Universidad de Cambridge. ISBN 0-521-55644-9.
- ^ 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" (PDF) . Actas de la American Mathematical Society . 125 (2): 547–555. doi : 10.1090 / S0002-9939-97-03614-9 . Consultado el 2 de septiembre de 2014 .
- ^ a b c d e Amin Saberi y Ying Wang (2009). Cortar un pastel para cinco personas . Aspectos algorítmicos en la información y la gestión. doi : 10.1007 / 978-3-642-02158-9_25 .
- ^ SJ Brams, MA Jones y C. Klamler, "Mejores formas de cortar un pastel", Avisos de la AMS, 2005. [En línea]. Disponible: http://www.ams.org/notices/200611/fea-brams.pdf
- ^ a b Pikhurko, O. (2000). "Sobre la división de pasteles sin envidia". The American Mathematical Monthly . 107 (8): 736–738. doi : 10.2307 / 2695471 . JSTOR 2695471 .
- ^ Gasarch, William (2015). "¿Qué protocolo ilimitado para cortar pasteles sin envidia es mejor?". arXiv : 1507.08497 [ matemáticas.LO ].
- ^ a b c Aziz, Haris; MacKenzie, Simon (2016). "Un protocolo de corte de tarta discreto y acotado sin envidia para cuatro agentes". Actas del 48 ° Simposio Anual ACM SIGACT sobre Teoría de la Computación - STOC 2016 . pag. 454. arXiv : 1508.05143 . doi : 10.1145 / 2897518.2897522 . ISBN 9781450341325.
- ^ a b Kurokawa, David; Lai, John K .; Procaccia, Ariel D (2013). "Cómo cortar un pastel antes de que termine la fiesta" . AAAI . Consultado el 2 de septiembre de 2014 .
- ^ Procaccia, Ariel (2009). "Codiciarás el pastel de tu prójimo" . IJCAI'09 Actas de la 21ª Conferencia Internacional Conjunta sobre Inteligencia Artificial : 239–244.
- ^ Zeng, Dao-Zhi (2000). "Procedimientos aproximados sin envidia". Práctica de juegos: contribuciones de la teoría de juegos aplicada . Biblioteca de teoría y decisión. 23 . Saltador. págs. 259-271. doi : 10.1007 / 978-1-4615-4627-6_17 . ISBN 9781461546276.
- ^ Idzik, Adam (1995). Divisiones óptimas del intervalo unitario . Conferencia internacional en honor de Robert J. Aumann en su 65 cumpleaños. Jerusalén.
- ^ Ichiishi, T .; Idzik, A. (1999). "Asignación equitativa de bienes divisibles". Revista de Economía Matemática . 32 (4): 389–400. doi : 10.1016 / s0304-4068 (98) 00053-6 .
- ^ Dall'Aglio, M .; MacCheroni, F. (2009). "Tierras en disputa" (PDF) . Juegos y comportamiento económico . 66 : 57–77. doi : 10.1016 / j.geb.2008.04.006 .
- ^ Proporcionalidad = el valor (como fracción de toda la torta) que se garantiza a cada agente con valoraciones aditivas. Cuando no hay envidia y se divide todo el pastel, la proporcionalidad es siempre 1 / n , que es la mejor posible.