Un reparto de la torta sin envidia es una especie de reparto justo de la torta . Se trata de una división de un recurso heterogéneo ("torta") que satisface el criterio de no envidiar , 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.
Cuando sólo hay dos socios, el problema es fácil y se resolvió en la antigüedad con el protocolo de divide y elige . Cuando hay tres o más socios, el problema se vuelve mucho más complicado.
Se han estudiado dos variantes principales del problema:
La investigación moderna sobre el problema del reparto justo de la torta 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 .
El criterio más fuerte de ausencia de envidia fue introducido en el problema del corte de la torta por George Gamow y Marvin Stern en la década de 1950. [1]
En 1960 se descubrió un procedimiento con tres compañeros y piezas generales . En 1980 se descubrió un procedimiento con tres compañeros y piezas conexas .
La división sin envidias para cuatro o más socios había sido un problema abierto hasta la década de 1990, cuando se publicaron tres procedimientos para piezas generales y un procedimiento para piezas conexas. Todos estos procedimientos son ilimitados : pueden requerir un número de pasos que no está acotado de antemano. El procedimiento para piezas conexas puede incluso requerir un número infinito de pasos.
En la década del 2000 se publicaron dos límites inferiores para la complejidad en tiempo de ejecución de la ausencia de envidia.
En la década de 2010, se publicaron 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 había permanecido abierta durante mucho tiempo. El problema finalmente se resolvió en 2016. Haris Aziz y Simon Mackenzie presentaron un protocolo discreto libre de envidia que requiere como máximo o consultas. [2] Todavía existe una brecha muy grande entre el límite inferior y el procedimiento. A febrero de 2024, la complejidad exacta en tiempo de ejecución de la ausencia de envidia aún se desconoce.
En el caso de piezas conectadas, se observó que el resultado de 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 sigue siendo un problema abierto si existen procedimientos acotados en el tiempo para cuatro o más socios.
Siempre existe una división libre de envidia para n agentes con piezas conectadas bajo las siguientes suposiciones suaves: [3]
Téngase en cuenta que no es necesario que las preferencias de los agentes estén representadas por una función aditiva .
El concepto principal de la prueba es el símplex de particiones . Supongamos que la tarta es el intervalo [0,1]. Cada partición con partes conectadas puede representarse de forma única mediante n −1 números en [0,1] que representan las posiciones de corte. La unión de todas las particiones es un símplex.
Para cada partición, cada agente tiene una o más piezas que prefiere 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, 0,5]) mientras que un tercer agente puede preferir tanto la pieza n.° 1 como la pieza n.° 2 (lo que significa que son indiferentes entre ellas pero les gusta cualquiera de ellas más que la pieza n.° 3).
Para cada agente, el símplex de partición está cubierto por n partes, posiblemente superpuestas en sus límites, de modo que para todas las particiones en la parte i , el agente prefiere la pieza i . En el interior de la parte i , el agente prefiere solo la pieza i , mientras que en el límite de la parte i , el agente también prefiere algunas otras piezas. Entonces, para cada i , hay una cierta región en el símplex de partición en la que al menos un agente prefiere solo la pieza i . Llamemos 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 todos los U i no está vacía. Por lo tanto, hay una partición en la que cada pieza es la preferencia única de un agente. Dado que el número de piezas es igual al número de agentes, podemos asignar cada pieza al agente que la prefiere y obtener una asignación libre de envidia.
Para tres agentes, se puede encontrar una división libre de envidia utilizando varios procedimientos diferentes:
Se trata de procedimientos continuos, es decir, que requieren que las personas muevan cuchillos de forma continua y simultánea. No pueden ejecutarse en un número finito de pasos discretos.
Para n agentes, se puede encontrar una división sin envidia mediante el protocolo de corte de torta de Simmons . El protocolo utiliza un símplex de particiones similar al utilizado en la prueba de existencia de Stromquist. Genera una secuencia de particiones que converge a una partición sin envidia. La convergencia puede requerir una cantidad infinita de pasos.
No es casualidad que todos estos algoritmos puedan requerir una cantidad infinita de consultas. Como mostramos en la siguiente subsección, puede resultar imposible encontrar un corte de pastel sin envidia con piezas conectadas con un número finito de consultas.
No se puede encontrar una división sin envidia con piezas conectadas para 3 o más agentes mediante un protocolo finito en el modelo de consulta Robertson-Webb . [4] La razón por la que este resultado no contradice los algoritmos mencionados anteriormente es que no son finitos en el sentido matemático. [5]
La prueba de imposibilidad utiliza un sistema de medida rígido (RMS), un sistema de medidas de valor n , para el cual una división sin envidia debe cortar la torta en lugares muy específicos. Luego, encontrar una división sin envidia se reduce a encontrar estos lugares específicos. Suponiendo que la torta es el intervalo real [0,1], encontrar una división sin envidia usando consultas a los agentes es equivalente a encontrar un número real en el intervalo [0,1] usando preguntas de sí/no. Esto podría requerir una cantidad infinita de preguntas.
Se puede construir un RMS para tres agentes de la siguiente manera. Sean x , y , s y t parámetros que satisfacen:
Construya un conjunto de tres medidas con estas dos propiedades:
Entonces, cada división libre de envidia entre Alice Bob y Carl debe tener cortes en x e y (hay exactamente dos divisiones de este tipo), ya que todas las demás opciones conducen a la envidia:
Para cada RMS, cada agente i y cada constante ε>0, existe un RMS ligeramente diferente con las siguientes propiedades:
Esto implica que, si todas las consultas respondidas hasta ahora estuvieran fuera del vecindario ε de x e y , entonces el agente i no tendría forma de saber si estamos en el antiguo RMS o en el nuevo RMS.
Equipado con este conocimiento, un adversario puede engañar a cualquier protocolo de división libre de envidia para que continúe indefinidamente:
Por lo tanto, el protocolo nunca puede realizar cortes en los x e y correctos requeridos para una división libre de envidia.
Dado que cortar una tarta sin envidia y con piezas conectadas no se puede hacer en un tiempo finito, los cortadores de tartas han intentado encontrar soluciones alternativas.
Una solución alternativa es buscar divisiones que solo sean aproximadas y sin envidia . Hay dos formas de definir la aproximación: en unidades de longitud o en unidades de valor .
La aproximación basada en la longitud utiliza las siguientes definiciones:
El parámetro δ representa la tolerancia de los socios en unidades de longitud. Por ejemplo, si se divide la tierra 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 esté libre de envidia. Deng et al [6] presentan una modificación del protocolo de corte de torta de Simmons que encuentra una partición múltiple δ libre de envidia utilizando consultas. Además, prueban un límite inferior de consultas. Incluso cuando las funciones de utilidad se dan explícitamente mediante algoritmos de tiempo polinomial, el problema de corte de torta sin envidia es PPAD -completo.
La aproximación basada en valores utiliza las siguientes definiciones:
Si todas las medidas de valor son Lipschitz continuas, entonces las dos definiciones de aproximación están relacionadas. Sea . Entonces, cada partición en una δ -multipartición libre de envidia es ε -libre de envidia. [6] Por lo tanto, los resultados de Deng et al. prueban que, si todos los socios tienen valoraciones Lipschitz continuas, se puede encontrar una partición ε -libre de envidia con consultas con valoraciones generales.
Con valoraciones aditivas, para cualquier ε > 0, un corte de torta conectado sin envidia ε requiere al menos Ω(log ε −1 ) consultas. Para 3 agentes, existe un protocolo O(log ε −1 ). Para 4 o más agentes, el protocolo más conocido requiere O( n ε −1 ) , lo que muestra una brecha exponencial en la complejidad de la consulta. [7] Además, aunque el último protocolo tiene una complejidad de consulta polinómica en n , su complejidad computacional es exponencial en n , incluso para ε constante. Si se requiere un cálculo en tiempo polinómico, la aproximación más conocida es la ausencia de envidia. [8]
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 polinomios de grado d como máximo , existe un algoritmo que es polinomial en n y d . [9] Dado d , el algoritmo realiza a los agentes d +1 consultas de evaluación, que dan d +1 puntos en el gráfico de la medida de 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 fuera de línea libre de envidia. El número 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 valores del agente en cada intervalo es constante. Bajo este supuesto, se puede encontrar una asignación conectada y libre de envidias resolviendo programas lineales. Por lo tanto, cuando n es constante, el problema es polinómico en m . [10]
La disposición libre es una tercera solución alternativa que mantiene el requisito de que la división sea totalmente libre de envidia y funciona para todas las medidas de valor, pero elimina el requisito de que se debe dividir todo el pastel. Es decir, permite dividir un subconjunto del pastel 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 lo 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 libre de envidia de todo el pastel también es una división proporcional , y su nivel de proporcionalidad es al menos, que es el mejor posible. Pero cuando se permite la disposición libre, una división libre de envidia puede tener un nivel de proporcionalidad menor, y el objetivo es encontrar una división libre de envidia con la proporcionalidad más alta posible. Los límites conocidos actualmente son:
No se sabe si existe un procedimiento de división proporcional y libre de envidia en el tiempo acotado para cuatro o más socios con piezas conexas.
La mayoría de los procedimientos para cortar una torta con porciones conectadas suponen que la torta es un intervalo unidimensional y las porciones son subintervalos unidimensionales. A menudo, es deseable que las porciones tengan una forma geométrica determinada, como un cuadrado. Con tales restricciones, puede resultar imposible dividir la torta entera (por ejemplo, un cuadrado no puede dividirse 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]
Existe una división libre de envidia incluso con funciones de valor no aditivas, una torta simplex multidimensional y las piezas deben ser politopos . [13]
Para tres socios, el procedimiento discreto Selfridge-Conway realiza una división sin envidias con un máximo de 5 cortes. Otros procedimientos que utilizan cuchillas móviles requieren menos cortes:
Para cuatro socios, el procedimiento de Brams–Taylor–Zwicker realiza una división sin envidia con un máximo de 11 cortes. [15] Para cinco socios, un procedimiento de Saberi y Wang realiza una división sin envidia con un número limitado de cortes. [16] 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 utilizando 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 la cantidad de cortes necesarios. [17] Hay tres de estos algoritmos:
Aunque los protocolos son diferentes, la idea principal que los sustenta es similar: dividir 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 participantes es insignificante. Luego, combinar las migajas de una manera sofisticada para obtener la división deseada. William Gasarch ha comparado los tres algoritmos ilimitados utilizando números ordinales . [19]
La cuestión de si se puede cortar la tarta sin envidia en un tiempo limitado para cuatro o más socios ha estado abierta durante muchos años. Finalmente, Haris Aziz y Simon Mackenzie la resolvieron en 2016. Inicialmente, desarrollaron un algoritmo de tiempo limitado para cuatro socios. [20] Luego, ampliaron su algoritmo para que manejara cualquier número de socios. [2] Su algoritmo requiere como máximo consultas. Si bien este número es limitado, está muy lejos del límite inferior de . Por lo tanto, la cuestión de cuántas consultas se requieren para cortar la tarta sin envidia aún está abierta.
Una variante reentrante del último protocolo reductor encuentra una aproximación aditiva a una división sin envidia en tiempo acotado. 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 , en 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. [21] El número de consultas es , donde es el número de discontinuidades en las derivadas de las funciones de densidad de valor.
Todo procedimiento libre de envidia para n personas requiere al menos Ω( n 2 ) consultas en el modelo de consulta de Robertson-Webb . [22] La prueba se basa en un análisis cuidadoso de la cantidad de información que tiene el algoritmo sobre cada socio.
A. Supongamos que el pastel es el intervalo unidimensional [0,1] y que el valor del pastel entero para cada uno de los socios está normalizado 1. En cada paso, el algoritmo pide a un socio determinado que evalúe un intervalo determinado contenido en [0,1] o que marque un intervalo con un valor especificado. En ambos casos, el algoritmo recopila información solo sobre intervalos cuyos puntos finales se mencionaron en la consulta o en la respuesta. Llamemos a estos puntos finales puntos de referencia . 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 pide al socio i que evalúe el intervalo [0,2,1], entonces después 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 lugar intermedio.
B. Un intervalo entre dos puntos de referencia consecutivos del socio i se llama intervalo de punto de referencia 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 tan grande como cualquier intervalo de punto de referencia de i . La prueba es por contradicción: supongamos que hay un cierto intervalo de punto de referencia J cuyo valor para i es mayor que el valor realmente asignado a i . Algún otro socio, digamos j , necesariamente recibirá alguna parte del intervalo de punto de referencia J . Por el párrafo A, es posible que todo el valor del intervalo J esté concentrado dentro de la parte asignada al socio j . Por lo tanto, i envidia a j y la división no está libre de envidia.
C. Supongamos 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). Por el párrafo B, el algoritmo puede asignar un fragmento 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 longitud de como máximo 2/ n ; por lo tanto, todos sus intervalos de referencia deben tener una longitud de como máximo 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 como máximo 2. Por lo tanto, en el caso descrito en el párrafo C, el algoritmo debe realizar a cada uno de los n /2 socios, al menos n /4 consultas. El número total de consultas es, por lo tanto, como mínimo n 2 /8 = Ω( n 2 ).
Además de las pruebas de existencia general implicadas en los algoritmos descritos anteriormente, existen pruebas de la existencia de particiones libres de envidia con propiedades adicionales:
Ambas pruebas funcionan únicamente para medidas de valor aditivo y no atómico, y se basan en la capacidad de dar a cada socio una gran cantidad de piezas desconectadas.
Algunas otras variantes son:
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 de la torta que tiene derecho a recibir (la suma de todos los w i es 1). Entonces, una división ponderada libre de envidia se define de la siguiente manera. Para cada agente i con medida de valor V i , y para cada otro agente 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 ponderada aproximada sin envidia, que requiere un número menor de cortes. [25]
Pero cuando las piezas deben estar conectadas, puede que no exista una división ponderada sin envidia. Para ver esto, observe que cada división ponderada sin 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 la asignación proporcional ponderada con porciones conectadas puede no existir: véase el reparto proporcional con diferentes derechos como ejemplo.
Tenga en cuenta que existe una definición alternativa de división ponderada sin envidia, 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 sin envidia en los siguientes casos (cada caso generaliza el caso anterior):
En algunos casos, la "torta" que se reparte tiene un valor negativo. Por ejemplo, puede tratarse de un trozo de césped que hay que cortar o de un terreno baldío que hay que limpiar. En ese caso, la torta es un "mal heterogéneo" en lugar de un "bien heterogéneo".
Algunos procedimientos para cortar una tarta sin envidia se pueden adaptar para que funcionen con una tarta en mal estado, pero la adaptación no suele ser trivial. Consulta la división de tareas sin envidia para obtener más detalles.
Resumen por número de agentes y tipo de piezas: