División del consenso

La división por consenso , también llamada división exacta , ^{[1] : 127} es una partición de un recurso continuo (" pastel ") en algunos k pedazos, de manera que cada una de n personas con gustos diferentes están de acuerdo en el valor de cada uno de los pedazos. Por ejemplo, considere un pastel que es mitad chocolate y mitad vainilla. Alice valora sólo el chocolate y George valora sólo la vainilla. El bizcocho se divide en tres trozos: un trozo contiene el 20% del chocolate y el 20% de la vainilla, el segundo contiene el 50% del chocolate y el 50% de la vainilla y el tercero contiene el resto del bizcocho. Esta es una división exacta (con k  = 3 y n  = 2), ya que tanto Alice como George valoran las tres piezas como 20%, 50% y 30% respectivamente. Varias variantes comunes y casos especiales se conocen con diferentes términos:

• Reducción a la mitad por consenso : el pastel debe dividirse en dos partes ( k  = 2), y todos los agentes están de acuerdo en que las partes tienen valores iguales. ^[2]
• Consenso 1/ k -división , para cualquier constante k  > 1 – el pastel debe dividirse en k pedazos, y todos los agentes están de acuerdo en que los pedazos tienen valores iguales. ^[2] Otro término es división por consenso . ^[3]
• División perfecta : el número de piezas es igual al número de agentes: el pastel debe dividirse en n piezas y todos los agentes están de acuerdo en que todas las piezas tienen valores iguales.
• ${\displaystyle \varepsilon }$-División casi exacta , para cualquier constante , los agentes pueden no estar de acuerdo en los valores de las piezas, pero la diferencia entre los valores debe ser como máximo . De manera similar, las variantes aproximadas de los problemas mencionados anteriormente se denominan -consenso-reducción a la mitad , -consenso 1/ k -división o -división-consenso y -división-perfecta. ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$
• El problema del Nilo : hay infinitos agentes.
• División de collares : el recurso a dividir está formado por un número finito de objetos indivisibles ("cuentas").

Cuando tanto n como k son finitos, siempre existen divisiones por consenso. Sin embargo, no se pueden encontrar mediante protocolos discretos (con un número finito de consultas). En algunos casos, se pueden encontrar divisiones exactas mediante protocolos de cuchilla móvil. Se pueden encontrar divisiones casi exactas mediante protocolos discretos.

Definiciones

Sean k pesos cuya suma es 1. Supongamos que hay n agentes, todos los cuales valoran el pastel C como 1. La medida del valor del agente i se denota por . Se supone que es una medida no atómica en C. Una división exacta de las proporciones es una partición del pastel en k pedazos: , tal que para cada agente i y cada pedazo j : ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$ ${\displaystyle V_{i}}$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$ ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k}}$

${\displaystyle V_{i}(X_{j})=w_{j}}$

También se le llama división de consenso , ya que existe consenso entre todos los agentes de que el valor de la pieza j es exactamente . ^{[1] : 127} Algunos casos especiales son: ${\displaystyle w_{j}}$

• Consenso 1/ k división : el caso especial en el que . ${\displaystyle w_{1}=\cdots =w_{n}=1/k}$
• Reducción a la mitad del consenso : el caso especial en el que y . ${\displaystyle k=2}$ ${\displaystyle w_{1}=w_{2}=1/2}$
• División perfecta : el caso especial en el que y . ${\displaystyle k=n}$ ${\displaystyle w_{1}=\cdots =w_{n}=1/n}$

División casi exacta

Para cada , una división casi exacta de las razones es una división en la que: ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

Es decir, existe un consenso entre todos los socios de que el valor de la pieza j es casi exactamente , donde la diferencia es menor que . ^{[1] : 127} Algunos casos especiales son: ${\displaystyle w_{j}}$ ${\displaystyle \varepsilon }$

• ${\displaystyle \varepsilon }$-consenso 1/ k división – el caso especial en el que . ${\displaystyle w_{1}=\cdots =w_{n}=1/k}$
• ${\displaystyle \varepsilon }$-reducción a la mitad por consenso : el caso especial en el que y . ${\displaystyle k=2}$ ${\displaystyle w_{1}=w_{2}=1/2}$
• ${\displaystyle \varepsilon }$-división perfecta – el caso especial en el que y . ${\displaystyle k=n}$ ${\displaystyle w_{1}=\cdots =w_{n}=1/n}$

Existencia

Número ilimitado de cortes

Es fácil demostrar la existencia de una división exacta cuando los agentes tienen valoraciones por partes constantes . Esto significa que la torta se puede dividir en R regiones, de modo que todos los agentes estén de acuerdo en que la densidad de valor en cada región es uniforme. Por ejemplo, considere un pastel circular en el que cada uno de sus 4 cuartos tiene un aderezo diferente. Los agentes podrán valorar de forma diferente cada uno de los toppings, pero no distinguen entre diferentes piezas que tengan el mismo topping: el valor de cada pieza para cada agente sólo depende de la cantidad que obtengan de cada región. Una división exacta se puede lograr de la siguiente manera:

• Divida cada región en k subregiones, de modo que la subregión j contenga exactamente todas las regiones. ${\displaystyle w_{j}}$
• Sea la pieza j la unión de las subregiones j -ésimas en todas las regiones R.

El número de cortes necesarios es , donde R es el número de regiones. Este algoritmo se puede generalizar a valoraciones lineales por partes . ^[4] ${\displaystyle k\cdot R}$

Existe una división exacta en el entorno más general en el que los agentes tienen medidas no atómicas contablemente aditivas . Este es un corolario del teorema de convexidad de Dubins-Spanier ( Jerzy Neyman ^[5] señaló previamente la existencia de una división consensuada 1/ k ). Sin embargo, este teorema no dice nada sobre el número de cortes necesarios.

Woodall ^[6] demostró que es posible construir una división exacta de una torta de intervalos como una unión contable de intervalos. Intuición: considere el procedimiento de división de tortas homogéneas por partes descrito anteriormente. En general, el pastel no es homogéneo por partes. Sin embargo, debido a que las medidas de valor son continuas, es posible dividir el pastel en regiones cada vez más pequeñas, de modo que las regiones se vuelvan cada vez más homogéneas. Cuando , este proceso converge hacia una división por consenso. Sin embargo, el número de recortes necesarios en el límite es infinito. Fremlin demostró más tarde que es posible construir tal división como una unión finita de intervalos. ${\displaystyle R\to \infty }$

Número acotado de cortes

Supongamos que el pastel es un intervalo formado por n distritos (subintervalos) y cada uno de los n socios valora solo un distrito. Entonces, una división consensuada del pastel en k subconjuntos requiere cortes, ya que cada uno de los distritos debe dividirse en k partes que sean iguales a los ojos del socio que valora este distrito. Esto plantea la cuestión de si siempre existe una división de consenso con este número exacto de recortes. Esta cuestión se estudió exhaustivamente, centrándose principalmente en una torta unidimensional (un intervalo). ${\displaystyle n\cdot (k-1)}$

Consideremos primero el caso de la reducción a la mitad por consenso : y pesos iguales. El límite inferior del número de cortes es . De hecho, siempre existe un consenso sobre la reducción a la mitad con como máximo n recortes. ^[7] Este es un corolario directo del teorema de Hobby-Rice . También se puede demostrar utilizando el teorema de Borsuk-Ulam : ^[8] ${\displaystyle k=2}$ ${\displaystyle n\cdot (k-1)=n}$

• Cada partición de un intervalo que utiliza cortes se puede representar como un vector de longitud , en el que los elementos son las longitudes de los subintervalos. ${\displaystyle n}$ ${\displaystyle n+1}$
• Cada elemento del vector puede ser positivo (si pertenece a la pieza 1) o negativo (si pertenece a la pieza 2).
• El conjunto de todas las particiones es homeomorfo a la esfera . ${\displaystyle S^{n}}$
• Defina una función de la siguiente manera: para cada partición x , hay un vector cuyo i -ésimo elemento es el valor de la pieza #1 en esa partición según el socio i , menos 1/2. ${\displaystyle V:S^{n}\to \mathbb {R} ^{n}}$ ${\displaystyle V(x)}$
• La función V es continua. Además, para todo x , . ${\displaystyle V(x)+V(-x)=0}$
• Por tanto, según el teorema de Borsuk-Ulam , existe una x tal que . En esa partición, todos los socios valoran la pieza 1 (y la pieza 2) exactamente a 1/2. ${\displaystyle V(x)=0}$

Aunque las preferencias de los agentes se modelan con medidas, las pruebas no requieren que las funciones de valor sean positivas o aditivas sobre subconjuntos; pueden ser cualquier conjunto continuo de funciones definidas en el álgebra sigma de Borel. Por lo tanto, no es necesario que las valoraciones de los socios sobre subconjuntos del pastel sean separables de forma aditiva. ^[2]

Consideremos ahora el caso de división por consenso 1/ k : cualquier k >1 y pesos iguales. Noga Alon , en su artículo de 1987 sobre el problema de la división del collar , demostró el siguiente resultado. Existen diferentes medidas sobre el intervalo, todas absolutamente continuas respecto a la longitud. La medida de todo el collar, según medida , es de . Entonces es posible dividir el intervalo en partes (no necesariamente contiguas), de modo que la medida de cada parte, según medida , sea exactamente . Como máximo se necesitan cortes, y esto es óptimo. ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle k\cdot a_{i}}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle (k-1)n}$

Consideremos ahora el caso k =2 y pesos arbitrarios . Stromquist y Woodall ^[9] demostraron que existe una división exacta de un pastel (un pastel circular) en el que cada trozo contiene como máximo n -1 intervalos; por lo tanto, se necesitan como máximo 2 n -2 cortes. Véase teorema de Stromquist-Woodall . El número de cortes es esencialmente óptimo para pesos generales. Este teorema se puede aplicar de forma recursiva para obtener una división exacta para cualquier k > 1 y cualquier peso, utilizando cortes O( nk ).

Pastel multidimensional, muchos socios, muchos subconjuntos, pesos iguales

El teorema de Stone-Tukey establece que dados n "objetos" mensurables en un espacio de n dimensiones , es posible dividirlos todos por la mitad (con respecto a su medida , es decir, volumen) con un único hiperplano de dimensiones ( n − 1). .

Dicho de otra manera: si el pastel es el espacio y las medidas de valor de los socios son finitas y desaparecen en cualquier hiperplano dimensional, entonces hay un medio espacio cuyo valor es exactamente 1/2 para cada socio. De ahí que exista una división consensuada utilizando un solo corte. ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n-1}$

La versión original de este teorema solo funciona si el número de dimensiones del pastel es igual al número de socios. Por ejemplo, no es posible utilizar este teorema para dividir un sándwich tridimensional en 4 o más socios.

Sin embargo, existen generalizaciones que permiten tal división. No utilizan una cuchilla hiperplana sino una superficie polinomial más complicada. ^[10]

También hay adaptaciones discretas de estos resultados multidimensionales. ^[11]

Cálculo de divisiones exactas.

Imposibilidad de utilizar procedimientos discretos.

Es imposible calcular una división exacta con un número finito de consultas, incluso cuando solo hay n = 2 agentes yk = 2 piezas, los pesos equivalen a 1/2. ^{[1] : 103–104} Esto significa que lo mejor que podemos lograr usando un algoritmo discreto es una división casi exacta.

Prueba : cuando el protocolo está en el paso k , tiene una colección de como máximo k piezas. Para proporcionar una división exacta, el protocolo debe encontrar un subconjunto exacto : un subconjunto de piezas que ambos socios valoran exactamente como 1/2. Vamos a demostrar que, para cada k , hay situaciones en las que en el paso k no hay un subconjunto exacto y, por tanto, el protocolo podría tener que continuar infinitamente.

Inicialmente, sólo hay una pieza que ambos socios valoran como 1, por lo que obviamente no existe un subconjunto exacto. Después de un paso, como máximo un compañero (por ejemplo, Alicia) ha tenido la opción de cortar el pastel. Incluso si Alice corta el pastel en dos pedazos que en su opinión son iguales, en opinión de George pueden ser diferentes, por lo que nuevamente no existe un subconjunto exacto.

Supongamos ahora que estamos en el paso k y hay k piezas. Sin pérdida de generalidad, podemos suponer que cada pieza tiene un valor distinto de cero para ambos socios. Esto se debe a que, si Alicia (por ejemplo) corta una pieza que ella valora como 0, es posible que George también valore la misma pieza como 0, por lo que podemos descartar esta pieza y continuar con las demás piezas.

El número total de subconjuntos diferentes ahora es 2 ^k y, según el supuesto de inducción, ninguno de ellos es exacto. En el paso k , el protocolo puede pedirle a Alice o George que corten una determinada pieza en dos piezas. Supongamos que el cortador es George y que corta la pieza X en dos subpiezas: X1 y X2. Ahora, el número total de subconjuntos es 2 ^{k +1} : la mitad de ellos ya existían y, por supuesto, no son exactos, por lo que la única posibilidad del protocolo de encontrar un subconjunto exacto es observar los nuevos subconjuntos. Cada nuevo subconjunto está formado por un subconjunto antiguo en el que la pieza X ha sido reemplazada por X1 o X2. Dado que George es el cortador, puede cortar de una manera que haga que uno de estos subconjuntos sea un subconjunto exacto para él (por ejemplo, si cierto subconjunto que contiene la pieza X tuviera un valor de 3/4, George puede cortar X de modo que X1 tenga un valor de 1/4 en su opinión, de modo que el nuevo subconjunto tenga un valor exactamente de 1/2). Pero George no conoce la valoración de Alice y no puede tenerla en cuenta al realizar el corte. Por lo tanto, existe una infinidad incontable de valores diferentes que las piezas X1 y X2 pueden tener para Alice. Dado que el número de subconjuntos nuevos es finito, hay un número infinito de casos en los que ningún subconjunto nuevo tiene un valor de 1/2 para Alice, por lo que ningún subconjunto nuevo es exacto.

Procedimientos con cuchilla móvil

Dos agentes pueden lograr una división por consenso utilizando el procedimiento de cuchilla móvil de Austin .

El caso más sencillo es cuando los pesos son 1/2, es decir quieren cortar un trozo que ambos acuerdan que vale la mitad del valor del bizcocho. Esto se hace de la siguiente manera. Un agente mueve dos cuchillos sobre el pastel de izquierda a derecha, manteniendo siempre el valor entre los cuchillos exactamente 1/2. Es posible demostrar (mediante el teorema del valor intermedio ) que en algún momento, el valor de la pieza entre los cuchillos para el otro compañero también será exactamente 1/2. El otro agente grita "¡alto!" en ese punto y se corta la pieza.

Se puede utilizar el mismo protocolo para cortar una pieza si ambos agentes coinciden en que su valor es exacto . Combinando varias de estas piezas, es posible lograr una división por consenso con cualquier proporción que sea número racional. Pero esto puede requerir una gran cantidad de recortes. ${\displaystyle 1/n}$

Una mejor manera de lograr una división por consenso es identificar los dos extremos del pastel y tratarlo como un círculo. Es decir, cuando el cuchillo derecho llega al lado derecho, inmediatamente pasa al lado izquierdo, y la pieza-entre-cuchillos ahora es en realidad la unión de la pieza a la derecha del cuchillo derecho y la pieza a la izquierda. del cuchillo izquierdo. De esta manera, es posible encontrar una división de consenso para cada . Un agente mueve los cuchillos cíclicamente alrededor del pastel, manteniendo siempre el valor entre ellos exactamente en p . Es posible demostrar que en algún momento, el valor de la pieza entre los cuchillos para el otro compañero también será exactamente p . ^[12] El otro agente grita "¡alto!" en ese punto y se corta la pieza. Esto requiere sólo dos cortes. ${\displaystyle p\in [0,1]}$

Al aplicar repetidamente el procedimiento anterior, es posible lograr una división por consenso entre n = 2 socios y cualquier k > 1 subconjuntos. El número de cortes es . ${\displaystyle 2(k-1)}$

A partir de 2015, no se conoce ninguna generalización de este procedimiento de cuchilla móvil para n >2 agentes. ^[13]

Cálculo de divisiones casi exactas con un número ilimitado de cortes

Procedimiento de desmenuzar y empacar

Para cualquier dado , se puede dar a cada socio una pieza tal que todos los socios crean que los valores que tienen difieren en menos de , es decir, para cada i y cada j : ^{[1] : 127} ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

El procedimiento de división casi exacto consta de dos pasos: desmenuzado y empacado .

Paso de desmenuzado : el objetivo es cortar el bizcocho en pedacitos muy pequeños ("migajas") de modo que cada compañero asigne un valor suficientemente pequeño a cada migaja. Esto se hace de la siguiente manera. Sea k una determinada constante. Pídale al compañero #1 que corte el pastel en k pedazos que él valore como 1/ k . Pídale al compañero #2 que recorte las piezas según sea necesario (usando como máximo k -1 cortes) de modo que cada pieza tenga un valor de como máximo 1/ k . Estas nuevas piezas, por supuesto, todavía tienen un valor de como máximo 1/ k para el socio n.º 1. Continúe con los compañeros #3, #4,…, #n . Finalmente, los n socios valoran cada migaja resultante como máximo 1/ k .

Paso de empaquetado : el objetivo aquí es dividir las migajas en n subconjuntos, de modo que la suma de los valores en cada subconjunto j esté cerca de w _j . Aquí hay una explicación intuitiva del paso de empaquetar para dos socios (Alice y George) cuando los pesos son 1/2. ^{[1] : 68–71}

1. Consigue un cuenco vacío.
2. Introducir en el bol una de las migas.
3. Si el valor en el tazón llega a ser más de 1/2 para cualquiera de los socios, déle el tazón a ese compañero y déle las otras migajas al otro compañero.
4. De lo contrario (el valor en el cuenco es menor que 1/2 para ambos socios), si el valor en el cuenco es mayor para Alice que para George, entonces encuentre una migaja cuyo valor para George sea mayor que su valor para Alice (como la migaja debe existir porque la suma de los valores de todas las migajas es 1 tanto para Alice como para George). Añade esta miga al bol y vuelve al paso 2.

Es posible demostrar por inducción que la diferencia en el valor del cuenco entre Alice y George es siempre como máximo 1/ k . Por lo tanto, cuando uno de los socios recibe el cuenco, su valor para ambos socios está entre 1/2-1/ k y 1/2+1/ k .

Formalmente, cada pieza se puede representar como un vector de valores, uno por socio. La longitud de cada vector está acotada, es decir, para cada uno de dichos vectores v : . Nuestro objetivo es crear, para cada socio j , un vector cuyos elementos estén cerca de w _j . Para hacer esto, tenemos que dividir los vectores en subconjuntos, de modo que la suma de los vectores en cada subconjunto j sea lo suficientemente cercana a un vector cuyos elementos sean w _j . Esto es posible gracias a un teorema de V.Bergström, ^{[14] [1] : 126–128} ${\displaystyle ||v||\leq {\sqrt {n}}/k}$

El procedimiento Crumb-and-Pack es una subrutina del protocolo Robertson-Webb . Este último protocolo genera una división que es a la vez casi exacta y sin envidia .

Brams y Taylor proporcionan una explicación diferente del procedimiento de miga y empaque. ^[15]

Cálculo de divisiones casi exactas con un número limitado de cortes

La mayoría de los resultados para un número acotado de cortes se centran en el caso en el que los pesos son iguales.

Dos subconjuntos (reducción a la mitad por consenso)

Se puede calcular una reducción a la mitad de consenso aproximada de ε mediante un algoritmo basado en el lema de Tucker , que es la versión discreta del teorema de Borsuk-Ulam . ^[2] Una adaptación de este algoritmo muestra que el problema está en la clase de complejidad PPA . ^[16] Esto es válido incluso para valoraciones arbitrarias acotadas y no atómicas. Sin embargo, el tiempo de ejecución de este algoritmo puede ser exponencial en los parámetros del problema. De hecho, reducir a la mitad el consenso es computacionalmente difícil en varios aspectos.

Primero, se supone que se permite que ε sea inversamente exponencial en n (es decir, 1/ ε es una función exponencial de n ). Entonces, encontrar una reducción a la mitad de consenso aproximada de ε es difícil de alcanzar según la PPA . La dureza se mantiene incluso con las siguientes condiciones adicionales: ^[16]

• Los agentes tienen valoraciones por partes constantes . La entrada al problema contiene, para cada agente, los puntos finales y valores de su valoración constante por partes; y todos los números (incluida la precisión de aproximación ε ) se representan en binario .

• El número de piezas en las valoraciones constantes por partes es polinómico en n (los valores mismos pueden ser exponenciales en n ).
• Se permite que el factor de aproximación ε sea polinomio inverso en n . ^[17]
• Las valoraciones de los agentes son uniformes por partes con solo dos bloques (sin embargo, cuando los agentes tienen valoraciones uniformes por partes con un solo bloque, el problema se puede resolver en tiempo polinomial parametrizado para n cortes y en tiempo polinomial para 2 n - d cortes para cualquier constante d) . ^[18]
• El número de agentes es constante y al menos 3 (sin embargo, con 2 agentes se puede resolver en tiempo polinómico). ^[19]

A continuación, supongamos que ε es una constante (no depende de n ). Entonces, encontrar una reducción a la mitad de consenso aproximada de ε es PPAD-duro , que es teóricamente más débil que PPA-duro. La prueba es por reducción del problema del Circuito Generalizado aproximado de ε . La dureza se mantiene incluso en las siguientes condiciones:

• Las valoraciones son constantes por partes;
• Se permite usar un número constante de cortes adicionales (es decir, buscamos una reducción a la mitad por consenso para n agentes usando n + d cortes, para alguna constante d ). ^[20]
• Cuando ε es una constante, no está claro si ε -la reducción a la mitad por consenso aproximada es PPA-duro (que es más fuerte que PPAD-duro) . ^[dieciséis]
• Además, decidir si existe un consenso aproximado de ε para reducir a la mitad con n -1 cortes es NP-difícil incluso cuando ε es una constante. La prueba es por reducción del 3SAT . ^[20]

Cuando ε es una constante, se pueden calcular dos tipos de aproximaciones en tiempo polinomial. Los algoritmos funcionan para valoraciones aditivas generales (no necesariamente constantes por partes); Se accede a las valoraciones mediante consultas en el modelo de consulta de Robertson-Webb , incluida una consulta de marca para la suma de todas las n valoraciones. ^[3] Se pueden obtener las siguientes aproximaciones:

• Encontrar una partición tal que cada agente valore cada parte al menos 1/ 2n , utilizando cortes. ${\displaystyle n}$
• Encontrar una partición tal que cada agente valore cada parte en 1/2 ± ε , usando cortes en un algoritmo en línea o usando cortes en un algoritmo fuera de línea . ${\displaystyle O((n\log {n})/(\varepsilon ^{2}))}$ ${\displaystyle n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil }$
  • Tenga en cuenta que existe una brecha entre la dureza PPAD para n + d cortes para cualquier constante d y el algoritmo de tiempo polinomial para 2 n +O(log( ε)).

• Cuando ε es constante o polinómico inverso en n , ε -la división por consenso aproximada a la mitad es computacionalmente equivalente al problema de división del collar : cada uno puede reducirse al otro en tiempo polinómico (esto implica que la división del collar es difícil de PPAD). ^[dieciséis]
• Si estamos interesados ​​en encontrar una solución exacta , entonces reducir a la mitad el consenso es mucho más difícil: encontrar una solución con n cortes es FIXP-difícil, y decidir si existe una solución con n -1 cortes es ETR-completo. ^[21]
• Cuando las valoraciones de los agentes se representan mediante circuitos algebraicos, ε -reducir a la mitad el consenso aproximado es equivalente en tiempo polinomial a calcular una aproximación a una solución exacta del problema de búsqueda de Borsuk-Ulam. Esto significa que está completo para la clase de complejidad BU, una superclase de FIXP que implica soluciones a problemas cuya existencia está garantizada por el teorema de Borsuk-Ulam. ^[22]

Cuando el recurso a dividir no es un pastel sino un conjunto de recursos divisibles, el problema se vuelve más fácil: ^[23]

• Para agentes con utilidades aditivas , existe un algoritmo de tiempo polinomial para calcular una división por consenso con como máximo n cortes, y para calcular una k -división de consenso con como máximo ( k -1) n cortes.
• Es NP-difícil calcular una reducción a la mitad por consenso con el número óptimo de cortes para un caso determinado. Además, es NP-difícil calcular una reducción a la mitad por consenso con como máximo OPT+ n -1 cortes, donde OPT es el número óptimo de cortes para la instancia.
• Es casi seguro que los recortes de n son necesarios para lograr una reducción a la mitad por consenso cuando las utilidades de los agentes se obtienen de distribuciones probabilísticas.
• Para agentes con utilidades monótonas no aditivas, la reducción a la mitad por consenso sigue siendo difícil para PPAD, pero existen algoritmos de tiempo polinómico para un número fijo de agentes.

Muchos subconjuntos (consenso 1/k-división)

Desde una perspectiva computacional, no se sabe mucho sobre el cálculo de una división exacta con cortes para . Tenga en cuenta que el problema no es necesariamente más difícil que para , ya que podemos utilizar una mayor cantidad de cortes. Lo que se sabe actualmente es: ${\displaystyle (k-1)n}$ ${\displaystyle k\geq 3}$ ${\displaystyle k\geq 2}$

• El problema está en PPA- k para cualquier k . ^[24]
• El problema es PPA-difícil para k =3, cuando 1/ ε puede ser una función exponencial de n. ^[18]

Se pueden calcular dos tipos de aproximaciones utilizando el número polinómico de consultas de Robertson-Webb : ^[3]

• Encontrar una partición tal que cada agente valore cada parte al menos 1/ kn , mediante cortes, en un algoritmo en línea . ${\displaystyle (k-1)n}$
  • Está abierto si se puede mejorar el 1/ kn . En particular, está abierto si existe un algoritmo eficiente (en línea o fuera de línea) tal que cada agente valore cada parte al menos 1/ c ( k ), donde c(k) es alguna función de k (independiente de n ), usando cortes. . ${\displaystyle (k-1)n}$
• Encontrar una partición tal que cada agente valore cada parte en 1/ k ± ε , usando cortes en un algoritmo en línea , o usando cortes. ^{[3] : Sección 6} ${\displaystyle O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})}$ ${\displaystyle n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil }$
  • Está por ver si es posible mejorar el número de recortes. Para los algoritmos en línea, un límite inferior en el número de cortes para k = 2 es , por lo que existe una brecha logarítmica. ${\displaystyle O({\frac {n}{\varepsilon ^{2}}})}$

Comparación con otros criterios

Una división exacta con pesos iguales ( ) es, en particular, también proporcional , libre de envidia y equitativa . Sin embargo, no es necesariamente eficiente en el sentido de Pareto , ya que en muchos casos es posible aprovechar las valoraciones subjetivas y dividir los recursos de manera que todos los socios reciban más de lo que les corresponde . ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

Una división exacta con diferentes pesos no es necesariamente justa. Volviendo al ejemplo inicial, si la pieza del 20% se le da a Alice y las otras dos piezas (del 50% y del 30%) se le dan a George, esto es obviamente injusto para Alice. Pero tales divisiones pueden usarse como subrutinas para un corte justo del pastel .

Proporcionalidad unánime

En el problema de cortar el pastel entre familias , ^[25] hay n agentes agrupados en k familias; El objetivo es dividir un pastel en k pedazos y asignar un pedazo por familia. Un criterio de equidad natural en este contexto es la proporcionalidad unánime , lo que significa que todos los miembros de todas las familias valoran la parte de su familia al menos 1/ k (para otros criterios y problemas relacionados, consulte división justa entre grupos ). El problema equivale a la división exacta en el siguiente sentido:

• Para cada n y k , una solución para la división proporcional unánime entre n ( k -1)+1 agentes agrupados en k familias implica una solución para la división exacta entre n agentes con k piezas (y pesos iguales). En particular, implica que la división proporcional unánime requiere al menos n -1 cortes, y que encontrar una división proporcional unánime aproximada es difícil según la PPA.
• Para cada n y k , una solución para la división exacta entre n agentes y k piezas implica una solución para la división unánime proporcional entre n+1 agentes agrupados en k familias. En particular, implica que se puede hacer una división proporcional unánime exacta con ( n -1)( k -1) cortes, y que encontrar una división proporcional unánime aproximada está en PPA. El número de cortes es ajustado para k =2 familias pero no para k >2. ^[25]

Mecanismos veraces

Cualquier algoritmo para la división por consenso se basa en las medidas de valor informadas por los socios. Si los socios saben cómo funciona el algoritmo, pueden tener un incentivo para mentir sobre sus medidas de valor para recibir más de su peso. Para evitarlo, se debe utilizar un mecanismo veraz . ^{[4] [26]}

El mecanismo de división veraz más simple es: seleccionar un solo socio al azar (con probabilidades determinadas por los pesos) y darle el pastel completo. Este mecanismo es trivialmente veraz porque no plantea preguntas. Además, hay consenso en las expectativas: el valor esperado de cada socio es exactamente su peso, y esto es cierto según todas las medidas de valor. Sin embargo, la división resultante no es, por supuesto, una división de consenso.

Se puede construir un mecanismo mejor y veraz, que funcione para el caso en el que todos los pesos sean 1/ n , dado cualquier algoritmo (u oráculo) existente para encontrar una división de consenso:

1. Pida a cada socio que informe su medida de valor.
2. Utilice el algoritmo/oráculo existente para generar una partición en la que las n piezas sean exactamente 1/ n según las funciones de valor informadas por los socios.
3. Realice una permutación aleatoria en la partición de consenso y entregue a cada socio una de las piezas.

Aquí, el valor esperado de cada socio sigue siendo 1/ n independientemente de la función de valor reportada, por lo que el mecanismo sigue siendo veraz: ningún socio puede ganar nada mintiendo. Además, a un socio veraz se le garantiza un valor de exactamente 1/ n con probabilidad 1 (no sólo en la expectativa). Por tanto, los socios tienen un incentivo para revelar sus verdaderas funciones de valor.

Ver también: corte de pastel veraz .

Tabla de resumen

Ver también

• Problema del Nilo

Referencias

1. , Jack; Webb, William (1998). "Algoritmos para cortar pasteles: sea justo si puede" . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.
2. Simmons, Bosque W.; Su, Francis Edward (2003). "Reducción del consenso a la mitad mediante teoremas de Borsuk-Ulam y Tucker". Ciencias Sociales Matemáticas . 45 : 15–25. CiteSeerX 10.1.1.203.1189 . doi :10.1016/S0165-4896(02)00087-2. 
3. Alon, Noga ; Graur, Andrei (30 de junio de 2020). "División Eficiente de Medidas y Collares". arXiv : 2006.16613 [cs.DS].
4. Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013). "Verdad, justicia y cortar el pastel". Juegos y comportamiento económico . 77 (1): 284–297. doi :10.1016/j.geb.2012.10.009. S2CID  2096977.
5. Neyman, Jerzy (enero de 1946). "Un teorema de existencia". Cuentas Rendus de la Academia de Ciencias . 222 : 843–845.
6. Woodall, DR (1980). "Dividir un pastel de manera justa". Revista de Análisis y Aplicaciones Matemáticas . 78 : 233–247. doi : 10.1016/0022-247x(80)90225-5 .
7. Goldberg, Charles H.; Oeste, Douglas B. (1985). "Bisección de colores de círculos". Revista SIAM de Métodos Algebraicos y Discretos . 6 : 93-106. doi :10.1137/0606010.
8. Alon, Noga; Oeste, Douglas B. (1986). "El teorema de Borsuk-Ulam y la bisección de collares" (PDF) . Actas de la Sociedad Matemática Estadounidense . 98 (4): 623. doi : 10.1090/s0002-9939-1986-0861764-9 .
9. Stromquist, Walter; Woodall, DR (1985). "Conjuntos en los que coinciden varias medidas". Revista de Análisis y Aplicaciones Matemáticas . 108 : 241–248. doi :10.1016/0022-247x(85)90021-6.
10. B. Grünbaum (1960). "Particiones de distribuciones de masa y cuerpos convexos por hiperplanos". Pacífico J. Matemáticas . 10 (4): 1257–1261. doi : 10.2140/pjm.1960.10.1257 . SEÑOR  0124818.
11. de Longueville, Marcos; Živaljević, Rade T. (2008). "Dividir collares multidimensionales". Avances en Matemáticas . 218 (3): 926–939. arXiv : matemáticas/0610800 . doi : 10.1016/j.aim.2008.02.003 .
12. Fischer, Daniel. "División por consenso de un pastel entre dos personas en proporciones arbitrarias". Matemáticas.SE . Consultado el 23 de junio de 2015 .
13. Hay una generalización que le da a cada uno de n socios una pieza que vale exactamente para él. Pero esta no es una división por consenso, porque los socios pueden no ponerse de acuerdo sobre el valor de las otras piezas además de la pieza que les ha sido asignada. Consulte los procedimientos de cuchilla móvil de Austin # Muchos socios . ${\displaystyle 1/n}$
14. V. Bergström (1930). "Zwei Sätze über ebene Vectorpolygone". Hamburgische Abhandlungen . 8 : 205–219.
15. Brams, Steven J.; Taylor, Alan D. (1996). División justa [ Del corte del pastel a la resolución de disputas ]. Prensa de la Universidad de Cambridge. págs. 131-133. ISBN 978-0-521-55644-6.
16. Filos-Ratsikas, Aris; Goldberg, Paul W. (20 de junio de 2018). "La reducción a la mitad del consenso es un PPA completo". Actas del 50º Simposio Anual ACM SIGACT sobre Teoría de la Computación . STOC 2018. Nueva York, NY, EE. UU.: Asociación de Maquinaria de Computación. págs. 51–64. arXiv : 1711.04503 . doi :10.1145/3188745.3188880. ISBN 978-1-4503-5559-9. S2CID  8111195.
17. Filos-Ratsikas, Aris; Goldberg, Paul W. (23 de junio de 2019). "La complejidad de partir collares y dividir bocadillos de jamón". Actas del 51º Simposio anual ACM SIGACT sobre teoría de la informática. STOC 2019. Nueva York, NY, EE. UU.: Asociación de Maquinaria de Computación. págs. 638–649. doi :10.1145/3313276.3316334. ISBN 978-1-4503-6705-9. S2CID  44085263.
18. Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (13 de julio de 2020). "Reducir el consenso a la mitad: ¿alguna vez será más fácil?". Actas de la 21ª Conferencia ACM sobre Economía y Computación . CE '20. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 381–399. arXiv : 2002.11437 . doi :10.1145/3391403.3399527. hdl : 1721.1/146185. ISBN 978-1-4503-7975-5. S2CID  211505917.
19. Deligkas, Argyrios; Filos-Ratsikas, Aris; Hollender, Alexandros (18 de julio de 2021). "Compañía de dos, multitud de tres: consenso reducido a la mitad para un número constante de agentes". Actas de la 22ª Conferencia ACM sobre Economía y Computación . CE '21. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 347–368. arXiv : 2007.15125 . doi :10.1145/3465456.3467625. hdl :20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7. ISBN 978-1-4503-8554-1. S2CID  220871193.
20. Filos-Ratsikas, Aris; Frederiksen, Soren Kristoffer Stiil; Goldberg, Paul W.; Zhang, Jie (8 de agosto de 2018). "Resultados de dureza para reducir a la mitad el consenso". arXiv : 1609.05136 [cs.GT].
21. Deligkas, Argyrios; Fearnley, John; Melissourgos, Temístoklis; Spirakis, Paul G. (1 de mayo de 2021). "Calcular soluciones exactas de reducción a la mitad por consenso y el teorema de Borsuk-Ulam". Revista de Ciencias de la Computación y de Sistemas . 117 : 75–98. arXiv : 1903.03101 . doi :10.1016/j.jcss.2020.10.006. ISSN  0022-0000. S2CID  228908526.
22. Batziou, Eleni; Hansen, Kristoffer Arnsfelt; Høgh, Kasper (7 de marzo de 2021). "Fuerte reducción a la mitad por consenso aproximado y el teorema de Borsuk-Ulam". arXiv : 2103.04452 [cs.GT].
23. Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Reducción a la mitad del consenso para conjuntos de elementos". Matemáticas de la Investigación de Operaciones . 47 (4): 3357–3379. arXiv : 2007.06754 . doi :10.1287/moor.2021.1249. S2CID  246764981.
24. Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (1 de enero de 2021), "Una caracterización topológica de argumentos e implicaciones de módulo-p para la división de collares", Actas del Simposio ACM-SIAM de 2021 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas , págs. 2615–2634, doi : 10.1137/1.9781611976465.155 , ISBN 978-1-61197-646-5, S2CID  214667000
25. Segal-Halevi, Erel; Nitzan, Shmuel (1 de diciembre de 2019). "Corte de tartas justo entre familias". Elección social y bienestar . 53 (4): 709–740. arXiv : 1510.03903 . doi :10.1007/s00355-019-01210-9. ISSN  1432-217X. S2CID  1602396.
26. Mossel, Eljanán; Tamuz, Omer (2010). "División justa y veraz". Teoría algorítmica de juegos . Apuntes de conferencias sobre informática. vol. 6386, págs. 288–299. arXiv : 1003.5480 . doi :10.1007/978-3-642-16170-4_25. ISBN 978-3-642-16169-8. S2CID  11732339.
27. Requisitos previos sobre las funciones de valor de los socios. Menos requisitos previos significan que el resultado es más general. Con=Continuo es el más general; Con+Add=Aditivo es menos general; Con+Add+Pwl=Lineal por partes es el menos general.