Corte de pastel sin envidia

Proceso para dividir equitativamente los recursos

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.

Problema sin resolver en informática :

¿Cuál es la complejidad en tiempo de ejecución del corte de pastel sin envidia?

(más problemas sin resolver en informática)

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:

• Piezas conectadas , por ejemplo, si la torta es un intervalo unidimensional, cada parte debe recibir un único subintervalo. Si hay partes, solo se necesitan cortes. ${\displaystyle n}$ ${\displaystyle n-1}$
• Piezas generales , por ejemplo, si el pastel es un intervalo unidimensional, entonces cada socio puede recibir una unión de subintervalos disjuntos.

Breve historia

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.

• Para piezas generales, el límite inferior es Ω(n2).
• Para las piezas conectadas, el límite inferior es infinito: no existe un protocolo finito para tres o más socios.

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. ${\displaystyle n^{n^{n^{n^{n^{n}}}}}}$ ${\displaystyle n\uparrow \uparrow 6}$

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.

Piezas conectadas

Prueba de existencia

Siempre existe una división libre de envidia para n agentes con piezas conectadas bajo las siguientes suposiciones suaves: ^[3]

• Ningún agente prefiere una pieza vacía a una pieza no vacía.
• Las preferencias de los agentes son continuas.

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.

Procedimientos

Para tres agentes, se puede encontrar una división libre de 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 cuchillas móviles de Barbanel-Brams utiliza dos cuchillas que se mueven simultáneamente.
• El procedimiento de cuchilla giratoria de Robertson-Webb se puede utilizar cuando la torta es bidimensional y utiliza solo una cuchilla móvil.

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.

Resultado de dureza

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:

• ${\displaystyle 0<x<y<1,}$
• ${\displaystyle 0<s<1/3<t<1/2,}$
• ${\displaystyle s+2t=1.}$

Construya un conjunto de tres medidas con estas dos propiedades:

1. La densidad de cada medida está siempre estrictamente entre √ 2 /2 y √ 2 (por lo que, para una pieza dada, las valoraciones de los agentes difieren en un factor de menos de 2).
2. Los valores de las piezas determinadas por x e y son los que se muestran en la tabla:

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:

• Si x* ≥ x e y* ≤ y , y una de las desigualdades es estricta, entonces todos valoran la pieza derecha o la izquierda más que la del medio, por lo que quien obtenga la del medio sentirá envidia.
• Si x* ≤ x e y* ≥ y , y una de las desigualdades es estricta, entonces tanto Alice como Bob prefieren la pieza del medio sobre cualquier otra, por lo que quien no la obtenga de las dos sentirá envidia del otro.
• Si se hacen cortes a la derecha de x y a la derecha de y (por ejemplo, en x* > x e y * > y ), entonces tanto Alice como Carl prefieren la pieza más a la izquierda a la 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 valores, 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 (corta a la izquierda de x y a la izquierda de y ) es análogo.

Para cada RMS, cada agente i y cada constante ε>0, existe 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 un vecindario ε de x e y .

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:

1. Comience con cualquier RMS, por ejemplo con los parámetros x  = 1/3, y  = 2/3, s  = 0,3 y t  = 0,35.
2. Mientras el protocolo haga cortes en puntos distintos de x e y , que continúe.
3. Siempre que el protocolo le pide al agente i que haga un corte en x o y , cambie a un RMS diferente con x'≠x e y'≠y , asegurándose de que los valores sean los mismos para todos los cortes realizados previamente.

Por lo tanto, el protocolo nunca puede realizar cortes en los x e y correctos requeridos para una división libre de envidia.

Aproximaciones

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:

• La partición de una tarta se representa mediante las n longitudes de los intervalos que crea. Por lo tanto, (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 multipartición X se dice 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 δ-multipartición es una multipartición 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 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. ${\displaystyle O[(1/\delta )^{n-2}]}$ ${\displaystyle \Omega [(1/\delta )^{n-2}/2^{(n-1)(n-2)}]}$

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: . ${\displaystyle \forall i,j:V_{i}(X_{i})+\varepsilon \geq V_{i}(X_{j})}$
• Una medida de valor se denomina continua de Lipschitz 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 . ${\displaystyle \exists K:\forall j:|V_{i}(X_{i})-V_{i}(X_{j})|\leq K\cdot \mathrm {length} (X_{i}\setminus X_{j}\cup X_{j}\setminus X_{i})}$

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. ${\displaystyle \epsilon =2K\delta }$ ${\displaystyle \Theta [(1/\epsilon )^{n-2}]}$

Con valoraciones aditivas, para cualquier ε > 0, un corte de torta conectado sin envidia ε requiere al menos Ω(log ε ⁻¹ ) 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] ${\displaystyle 1/3}$

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 . ${\displaystyle O(n^{2}d)}$

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] ${\displaystyle {\frac {n\cdot (2mn+n-1)!}{(2mn)!}}\in O(m^{n})}$

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: ${\displaystyle 1/n}$

• Para 3 agentes la proporcionalidad es , es decir, se puede lograr una división proporcional y libre de envidia en un tiempo acotado. ^[11] ${\displaystyle 1/3}$
• Para 4 agentes la proporcionalidad es . ^[11] ${\displaystyle 1/7}$
• Para n agentes, la proporcionalidad es . ^[2] ${\displaystyle 1/(3n)}$

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.

Variantes

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]

• Para dos socios que comparten una tarta cuadrada y quieren trozos cuadrados la proporcionalidad es , y esto es lo mejor que se puede garantizar incluso sin envidia. ${\displaystyle 1/4}$
• Para tres socios que comparten una torta cuadrada y quieren pedazos cuadrados la proporcionalidad es ; lo mejor que se puede garantizar sin envidia es . ${\displaystyle 1/10}$ ${\displaystyle 1/6}$

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]

Piezas desconectadas

Procedimientos

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:

• El procedimiento de cuchillas móviles de Levmore-Cook requiere como máximo 4 cortes;
• El procedimiento de cuchillas rotatorias de Brams-Taylor-Zwicker para cortar tartas requiere como máximo 3 cortes (esto da como resultado tres piezas conectadas cuando la tarta es un círculo, pero cuando la tarta es un intervalo habrá cuatro piezas);
• Utilizando el procedimiento de cuchilla móvil de Austin para dos socios, es posible obtener una división sin envidias para tres socios utilizando como máximo tres cortes. Esta idea se atribuye a William Webb. ^{[14] : 124–125}

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:

• El protocolo Brams-Taylor , publicado por primera vez en un artículo de 1995 y luego en un libro de 1996.
• El protocolo Robertson-Webb , publicado por primera vez en un artículo de 1997 y luego en un libro de 1998.
• El protocolo Pikhurko, ^[18] publicado en 2000.

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. ${\displaystyle n^{n^{n^{n^{n^{n}}}}}}$ ${\displaystyle \Omega (n^{2})}$

Aproximaciones y soluciones parciales

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 . ${\displaystyle \epsilon >0}$ ${\displaystyle \epsilon }$ ${\displaystyle n^{2}/\epsilon }$

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. ${\displaystyle O(n^{6}k\ln {k})}$ ${\displaystyle k}$

Resultado de dureza

Todo procedimiento libre de envidia para n personas requiere al menos Ω( n ² ) 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 ² /8 = Ω( n ² ).

Pruebas de existencia y variantes

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:

• Existe una división exacta , que en particular está libre de envidia; véanse los teoremas de Dubins-Spanier .
• Existe una división libre de envidia que también es Pareto eficiente ; véase el teorema de Weller .

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 fuerte ausencia de envidia exige que cada agente prefiera estrictamente su conjunto a los otros conjuntos. ^[23]
• La súper ausencia de envidia requiere que cada agente prefiera estrictamente su paquete a 1/ n del valor total, y prefiera estrictamente 1/ n a cada uno de los otros paquetes. ^{[23] [24]} Claramente, la súper ausencia de envidia implica una fuerte ausencia de envidia, lo que implica ausencia de envidia.

División sin envidias 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 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 :

${\displaystyle V_{i}(X_{i})/w_{i}\geq V_{i}(X_{j})/w_{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 :

${\displaystyle V_{i}(X_{i})/w_{i}\geq V_{i}(C)}$

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):

• Funciones de valor aditivo, pastel unidimensional (intervalo), y las piezas deben ser intervalos conectados. ^[26]
• Funciones de valor aditivo, pastel símplex multidimensional y las piezas deben ser símplex. ^[27] La ​​prueba utiliza el teorema de Sperner , el lema KKM , el lema de cobertura de Gale y el lema de Ky Fan sobre puntos de coincidencia .

Dividiendo un pastel 'malo'

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.

Tablas de resumen

Resumen por número de agentes y tipo de piezas:

Véase también

• División de tareas sin envidia
• Asignación de elementos sin envidia
• Corte de pastel justo
• Sin envidia de grupo
• Corte de pastel proporcional

Enlaces externos

• Calculadora de división justa: una aplicación para calcular sin envidia la división de pasteles, tareas domésticas, habitaciones y alquileres.

Referencias

1. Gamow, George; Stern, Marvin (1958). Matemáticas de rompecabezas. Viking Press. ISBN 978-0670583355.
2. Aziz, Haris; Mackenzie, Simon (2016). "Un protocolo discreto y acotado de corte de pastel sin envidia para cualquier número de agentes". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . New Brunswick, NJ, EE. UU.: IEEE. págs. 416–427. arXiv : 1604.03655 . Bibcode :2016arXiv160403655A. doi :10.1109/FOCS.2016.52.
3. Stromquist, Walter (1980). "Cómo cortar un pastel de manera justa". The American Mathematical Monthly . 87 (8): 640–644. doi :10.2307/2320951. JSTOR  2320951.
4. Stromquist, Walter (2008). "Las divisiones de tortas sin envidia no se pueden encontrar mediante protocolos finitos" (PDF) . Revista electrónica de combinatoria . 15 . doi :10.37236/735.
5. 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. Como la espada se mueve continuamente, el número de pasos necesarios es un infinito incontable. El protocolo de corte de torta de Simmons converge hacia una división sin envidia, pero la convergencia podría requerir un número infinito de pasos.
6. Deng, X.; Qi, Q.; Saberi, A. (2012). "Soluciones algorítmicas para cortar pasteles sin envidia". Investigación de operaciones . 60 (6): 1461–1476. doi :10.1287/opre.1120.1116. S2CID  4430655.
7. Branzei, Simina; Nisan, Noam (6 de diciembre de 2022). "La complejidad de la consulta del corte de pastel". Avances en sistemas de procesamiento de información neuronal . 35 : 37905–37919., arXiv :1705.02946.
8. Goldberg, Paul W.; Hollender, Alexandros; Suksompong, Warut (2020). "Corte de torta contiguo: resultados de dureza y algoritmos de aproximación". Revista de investigación en inteligencia artificial . 69 : 109–141. arXiv : 1911.05416 . doi :10.1613/jair.1.12222. S2CID  221865778.
9. Brânzei, S. (2015). "Una nota sobre el corte de pastel sin envidia con valoraciones polinómicas". Cartas de procesamiento de la información . 115 (2): 93–95. doi :10.1016/j.ipl.2014.07.005.
10. Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tayiko, Ahmad S. (10 de febrero de 2017). "Mecanismos sin envidia y con un número mínimo de cortes". Trigésima Primera Conferencia AAAI sobre Inteligencia Artificial . 31 . doi : 10.1609/aaai.v31i1.10584 . S2CID  789550.
11. Segal-Halevi, Erel; Jasidim, Avinatan; Aumann, Yonatan (2016). "Los residuos se apresuran". Transacciones ACM sobre algoritmos . 13 : 1–32. arXiv : 1511.02599 . doi :10.1145/2988232. S2CID  11358086.
12. 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.
13. 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.
14. Brams, Steven J.; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . Cambridge University Press. ISBN 0-521-55644-9.
15. 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 entre cuatro personas" (PDF) . Actas de la American Mathematical Society . 125 (2): 547–555. doi :10.1090/S0002-9939-97-03614-9. S2CID  17233874 . Consultado el 2 de septiembre de 2014 .
16. Amin Saberi y Ying Wang (2009). Cortar un pastel para cinco personas . Aspectos algorítmicos en información y gestión. doi :10.1007/978-3-642-02158-9_25.
17. SJ Brams, MA Jones y C. Klamler, "Mejores formas de cortar un pastel", Notices of the AMS, 2005. [En línea]. Disponible en: http://www.ams.org/notices/200611/fea-brams.pdf
18. 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.
19. Gasarch, William (2015). "¿Cuál es el mejor protocolo ilimitado para cortar una tarta sin envidia?". arXiv : 1507.08497 [math.LO].
20. Aziz, Haris; MacKenzie, Simon (2016). "Un protocolo discreto y acotado de corte de torta sin envidia para cuatro agentes". Actas del 48.º Simposio anual ACM SIGACT sobre teoría de la computación – STOC 2016. pág. 454. arXiv : 1508.05143 . doi :10.1145/2897518.2897522. ISBN 9781450341325.
21. Kurokawa, David; Lai, John K.; Procaccia, Ariel D (2013). "Cómo cortar un pastel antes de que termine la fiesta". AAAI . 27 : 555–561. doi : 10.1609/aaai.v27i1.8629 . S2CID  12638556 . Consultado el 2 de septiembre de 2014 .
22. Procaccia, Ariel (2009). "Codiciarás el pastel de tu vecino". Actas de la 21.ª Conferencia conjunta internacional sobre inteligencia artificial IJCAI'09 : 239–244.
23. Barbanel, Julius B. (1 de enero de 1996). "División de tortas súper libre de envidia e independencia de medidas". Revista de análisis matemático y aplicaciones . 197 (1): 54–60. doi : 10.1006/S0022-247X(96)90006-2 . ISSN  0022-247X.
24. Webb, William A. (1999-11-01). "Un algoritmo para la división de pasteles sin envidia". Revista de análisis matemático y aplicaciones . 239 (1): 175–179. doi : 10.1006/jmaa.1999.6581 . ISSN  0022-247X.
25. Zeng, Dao-Zhi (2000). "Procedimientos aproximados libres de envidia". Práctica de juegos: contribuciones de la teoría de juegos aplicada . Biblioteca de teoría y decisión. Vol. 23. Springer. págs. 259–271. doi :10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.
26. Idzik, Adam (1995). Divisiones óptimas del intervalo unitario . Conferencia internacional en honor de Robert J. Aumann en su 65º cumpleaños. Jerusalén.
27. 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.
28. Proporcionalidad = el valor (como fracción de la torta entera) que se garantiza a cada agente con valoraciones aditivas. Cuando no hay envidia y se divide la torta entera, la proporcionalidad es siempre 1/ n , que es la mejor posible.