División del consenso

División por consenso , también llamada división exacta , ^[1]^{: 127} es una partición de un recurso continuo (" pastel ") en algunos k trozos, de modo que cada una de n personas con diferentes gustos esté de acuerdo con el valor de cada uno de los trozos. Por ejemplo, considere un pastel que es mitad chocolate y mitad vainilla. Alice valora solo el chocolate y George valora solo la vainilla. El pastel se divide en tres trozos: un trozo contiene 20% del chocolate y 20% de la vainilla, el segundo contiene 50% del chocolate y 50% de la vainilla, y el tercero contiene el resto del pastel. Esta es una división exacta (con k = 3 y n = 2), ya que tanto Alice como George valoran los tres trozos 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 : la torta 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 – la torta debe dividirse en k porciones, y todos los agentes están de acuerdo en que las porciones tienen valores iguales. ^[2] Otro término es división por consenso . ^[3]
División perfecta : el número de porciones es igual al número de agentes: la torta debe dividirse en n porciones y todos los agentes están de acuerdo en que todas las porciones tienen valores iguales.
${\estilo de visualización \varepsilon}$ -División casi exacta : para cualquier constante , los agentes pueden estar en desacuerdo sobre los valores de las piezas, pero la diferencia entre los valores debe ser como máximo de . De manera similar, las variantes aproximadas de los problemas mencionados anteriormente se denominan -reducción a la mitad por consenso , -división por consenso 1/ k o -división por consenso y -división perfecta. $\varepsilon >0$ ${\estilo de visualización \varepsilon}$ ${\estilo de visualización \varepsilon}$ ${\estilo de visualización \varepsilon}$ ${\estilo de visualización \varepsilon}$ ${\estilo de visualización \varepsilon}$
Problema del Nilo : hay infinitos agentes.
División de collar : el recurso para dividir está formado por un número finito de objetos indivisibles ("cuentas").

Cuando tanto n como k son finitos, siempre existen divisiones de 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 de valor del agente i se denota por . Se supone que es una medida no atómica en C . Una división exacta en las proporciones es una partición del pastel en k pedazos: , tal que para cada agente i y cada pedazo j : $w_{1},w_{2},\ldots,w_{k}$ $Estilo de visualización V_{i}}$ $w_{1},w_{2},\ldots,w_{k}$ $C=X_{1}\sqcup \cdots \sqcup X_{k}$

{\ Displaystyle V_ {i} (X_ {j}) = w_ {j}}

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

Consenso 1/ división k – el caso especial en el que . $w_{1}=\cdots =w_{n}=1/k$
Reducción a la mitad por consenso : el caso especial en el que y . ${\estilo de visualización k=2}$ $w_{1}=w_{2}=1/2$
División perfecta : el caso especial en el que y . $k=n$ $w_{1}=\cdots =w_{n}=1/n$

División casi exacta

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

|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: $estilo de visualización w_ {j}}$ ${\estilo de visualización \varepsilon}$

${\estilo de visualización \varepsilon}$ -división de consenso 1/ k – el caso especial en el que . $w_{1}=\cdots =w_{n}=1/k$
${\estilo de visualización \varepsilon}$ -reducción a la mitad por consenso : el caso especial en el que y . ${\estilo de visualización k=2}$ $w_{1}=w_{2}=1/2$
${\estilo de visualización \varepsilon}$ -división perfecta – el caso especial en el que y . $k=n$ $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 constantes por partes . Esto significa que la torta puede dividirse en R regiones, de modo que todos los agentes estén de acuerdo en que la densidad de valores en cada región es uniforme. Por ejemplo, considere una torta circular en la que cada uno de sus 4 cuartos tiene una cobertura diferente. Los agentes pueden valorar cada una de las coberturas de manera diferente, pero no distinguen entre diferentes porciones que tienen la misma cobertura: el valor de cada porción para cada agente solo depende de la cantidad que obtenga de cada región. Una división exacta puede lograrse de la siguiente manera:

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

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] $k\cdot R$

Existe una división exacta en el contexto 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 (la existencia de una división 1/ k consensuada fue señalada previamente por Jerzy Neyman ^[5] ). 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 para tortas homogéneas por partes descrito anteriormente. En general, la torta no es homogénea por partes. Sin embargo, debido a que las medidas de valor son continuas, es posible dividir la torta 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 a una división de consenso. Sin embargo, el número de cortes requeridos en el límite es infinito. Fremlin demostró más tarde que es posible construir dicha división como una unión finita de intervalos. $R\to \infty$

Número limitado de cortes

Supongamos que el pastel es un intervalo formado por n distritos (subintervalos) y que cada uno de los n socios valora sólo un único distrito. En ese caso, una división consensuada del pastel en k subconjuntos requiere cortes, ya que cada uno de los distritos debe cortarse en k trozos que sean iguales a los ojos del socio que valora este distrito. Esto plantea la cuestión de si siempre existe una división consensuada con este número exacto de cortes. Esta cuestión se ha estudiado ampliamente, centrándose principalmente en un pastel unidimensional (un intervalo). $n\cdot (k-1)$

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

Cada partición de un intervalo mediante cortes se puede representar como un vector de longitud , en el que los elementos son las longitudes de los subintervalos. ${\estilo de visualización n}$ ${\estilo de visualización 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 . $Estilo de visualización Sn$
Definir una función de la siguiente manera: para cada partición $x$ , es 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. $V:S^{n}\to \mathbb {R} ^{n}$ ${\estilo de visualización V(x)}$
La función $V$ es continua. Además, para todo $x$ , . $V(x)+V(-x)=0$
Por lo tanto, según el teorema de Borsuk-Ulam , existe una $x$ tal que . En esa partición, todos los socios valoran la pieza n.° 1 (y la pieza n.° 2) exactamente en 1/2. $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 función de conjunto continua definida en el álgebra sigma de Borel. Por lo tanto, no se requiere que las valoraciones de los socios sobre subconjuntos de la torta sean aditivamente separables. ^[2]

Consideremos ahora el caso de consenso de la división 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. Hay diferentes medidas en el intervalo, todas absolutamente continuas con respecto a la longitud. La medida de todo el collar, según la medida , es . Entonces es posible dividir el intervalo en partes (no necesariamente contiguas), de modo que la medida de cada parte, según la medida , sea exactamente . Como máximo se necesitan cortes, y esto es óptimo. ${\estilo de visualización n}$ ${\estilo de visualización i}$ $k\cdot a_{i}$ ${\estilo de visualización k}$ ${\estilo de visualización i}$ $Estilo de visualización ai$ ${\estilo de visualización (k-1)n}$

Consideremos ahora el caso k = 2 y pesos arbitrarios . Stromquist y Woodall ^[9] demostraron que existe una división exacta de una tarta (una torta circular) en la que cada porción contiene como máximo n -1 intervalos; por lo tanto, se necesitan como máximo 2 n -2 cortes. Véase el 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 O( nk ) cortes.

Pastel multidimensional, muchos socios, muchos subconjuntos, pesos iguales

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

Dicho de otro modo: si la torta es el espacio , y las medidas de valor de los socios son finitas y se anulan en cualquier hiperplano dimensional, entonces existe un semiespacio cuyo valor es exactamente 1/2 para cada socio. Por lo tanto, existe una división consensuada utilizando un solo corte. $\mathbb {R} ^{n}$ ${\estilo de visualización n-1}$

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

Sin embargo, existen generalizaciones que permiten realizar dicha división. No utilizan un hiperplano, sino una superficie polinómica más compleja. ^[10]

También existen 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 y k = 2 piezas, los pesos son iguales a 1/2. ^[1]^{: 103–104} Esto significa que lo mejor que podemos lograr usando un algoritmo discreto es una división casi exacta.

Demostración : Cuando el protocolo está en el paso k , tiene una colección de k piezas como máximo. Para proporcionar una división exacta, el protocolo debe encontrar un subconjunto exacto , es decir, un subconjunto de las piezas que ambos socios valoren 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 lo tanto, el protocolo podría tener que continuar sin fin.

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

Supongamos ahora que estamos en el paso k y que hay k piezas. Sin perder la generalidad, podemos suponer que cada pieza tiene un valor distinto de cero para ambos socios. Esto se debe a que, si Alice (por ejemplo) corta una pieza que 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 otras piezas.

El número total de subconjuntos diferentes es ahora 2 ^k , y por la suposición de inducción ninguno de ellos es exacto. En el paso k , el protocolo puede pedir 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 suposición no son exactos, por lo que la única posibilidad del protocolo de encontrar un subconjunto exacto es mirar los nuevos subconjuntos. Cada nuevo subconjunto está formado por un antiguo subconjunto en el que la pieza X ha sido sustituida por X1 o X2. Como 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 un determinado subconjunto que contiene la pieza X tenía un valor de 3/4, George puede cortar X de forma que X1 tenga un valor de 1/4 en su opinión, de modo que el nuevo subconjunto tenga un valor de exactamente 1/2). Pero George no conoce la valoración de Alice y no puede tenerla en cuenta al cortar. Por lo tanto, existe una infinidad incontable de valores diferentes que las piezas X1 y X2 pueden tener para Alice. Como el número de nuevos subconjuntos es finito, existe un número infinito de casos en los que ningún nuevo subconjunto tiene un valor de 1/2 para Alice, por lo tanto, ningún nuevo subconjunto es exacto.

Procedimientos con cuchilla móvil

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

El caso más simple es cuando los pesos son 1/2, es decir, quieren cortar un trozo que ambos acuerdan que es la mitad del valor del pastel. 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 (por el teorema del valor intermedio ) que en algún momento, el valor del trozo entre los cuchillos para el otro compañero también será exactamente 1/2. El otro agente grita "¡basta!" en ese momento y el trozo se corta.

El mismo protocolo puede utilizarse para cortar una pieza cuyo valor ambos agentes acuerden exactamente . Al combinar varias de estas piezas, es posible lograr una división consensuada con cualquier proporción que sea un número racional. Pero esto puede requerir una gran cantidad de cortes. ${\estilo de visualización 1/n}$

Una mejor manera de lograr una división de consenso es identificar los dos puntos finales del pastel y tratarlo como un círculo. Es decir, cuando el cuchillo derecho llega al lado derecho, va inmediatamente al lado izquierdo, y el trozo entre los cuchillos es ahora en realidad la unión del trozo a la derecha del cuchillo derecho y el trozo 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 punto, el valor del trozo entre los cuchillos para el otro socio también será exactamente p . ^[12] El otro agente dice "¡alto!" en ese punto y el trozo se corta. Esto requiere solo dos cortes. $p\in [0,1]$

Aplicando repetidamente el procedimiento anterior, es posible lograr una división de consenso entre n = 2 socios y cualquier k > 1 subconjunto. El número de cortes es . ${\estilo de visualización 2(k-1)}$

Hasta 2015, no se conoce ninguna generalización de este procedimiento de cuchillo móvil a n >2 agentes. ^[13]

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

Procedimiento de migajas y empaque

Para cualquier , 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} $\varepsilon >0$ ${\estilo de visualización \varepsilon}$

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

El procedimiento de división casi exacta tiene dos pasos: desmenuzado y compactado .

Paso de desmigado : el objetivo es cortar el pastel en pedacitos ("migajas") de modo que cada socio asigne un valor suficientemente pequeño a cada miga. Esto se hace de la siguiente manera. Sea k una cierta constante. Pídale al socio #1 que corte el pastel en k pedazos que valore como 1/ k . Pídale al socio #2 que recorte los pedazos según sea necesario (usando como máximo k -1 cortes) de modo que cada pedazo tenga un valor de como máximo 1/ k . Estos nuevos pedazos, por supuesto, todavía tienen un valor de como máximo 1/ k para el socio #1. Continúe con los socios #3, #4, …, # n . Finalmente, todos los n socios valoran cada miga resultante como 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 sea cercana a w _j . Aquí hay una explicación intuitiva del paso de empaquetado para dos socios (Alice y George) cuando los pesos son 1/2. ^[1]^{: 68–71}

Coge un recipiente vacío.
Introduce en el bol una de las migas.
Si el valor del recipiente llega a ser mayor que la mitad para cualquiera de los socios, entregue el recipiente a ese socio y las otras migajas al otro socio.
En caso contrario (el valor del recipiente es menor que la mitad para ambos socios), si el valor del recipiente es mayor para Alice que para George, entonces encuentre una migaja cuyo valor para George sea mayor que su valor para Alice (tal migaja debe existir porque la suma de los valores de todas las migajas es 1 tanto para Alice como para George). Agregue esta migaja al recipiente y regrese 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 puede representarse como un vector de valores, uno por socio. La longitud de cada vector está acotada, es decir, para cada uno de esos vectores v : . Nuestro objetivo es crear, para cada socio j , un vector cuyos elementos estén todos cerca de w _j . Para ello, tenemos que dividir los vectores en subconjuntos, de modo que la suma de los vectores en cada subconjunto j sea suficientemente cercana a un vector cuyos elementos sean todos w _j . Esto es posible gracias a un teorema de V. Bergström, ^[14]^[1]^{: 126–128} $||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 casi exacta y no provoca envidia .

Brams y Taylor ofrecen una explicación diferente del procedimiento de migajas y empaquetado. ^[15]

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

La mayoría de los resultados para un número limitado 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 del consenso aproximada en ε 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 se cumple 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, la reducción a la mitad del consenso es computacionalmente difícil en varios aspectos.

En primer lugar, se supone que se permite que ε sea exponencial inverso en n (es decir, 1/ ε es una función exponencial de n ). Entonces, encontrar una reducción a la mitad consensual aproximada de ε es difícil según PPA . La dificultad se cumple incluso con las siguientes condiciones adicionales: ^[16]

Los agentes tienen valoraciones constantes por partes . La entrada del problema contiene, para cada agente, los puntos finales y los 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 polinomial en n (los valores en sí mismos pueden ser exponenciales en n ).
Se permite que el factor de aproximación ε sea polinomial 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 polinomial). ^[19]

A continuación, supongamos que ε es una constante (no depende de n ). Entonces, encontrar una reducción por consenso aproximada a ε es difícil de PPAD , lo que es teóricamente más débil que difícil de PPA. La prueba se realiza mediante reducción a partir del problema del circuito generalizado aproximado a ε . La dificultad se cumple incluso en las siguientes condiciones:

Las valoraciones son constantes por tramos;
Se permite utilizar un número constante de cortes adicionales (es decir, buscamos una reducción a la mitad de consenso para n agentes utilizando n + d cortes, para una constante d ). ^[20]
Cuando ε es una constante, no está claro si la reducción a la mitad del consenso aproximado de ε es PPA-hard (que es más fuerte que PPAD-hard) . ^[16]
Además, decidir si existe una reducción de consenso aproximada de ε con n -1 cortes es NP-difícil incluso cuando ε es una constante. La prueba es por reducción a partir de 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 lograr las siguientes aproximaciones:

Encontrar una partición tal que cada agente valore cada parte al menos 1/ 2n , utilizando cortes. ${\estilo de visualización n}$
Encontrar una partición tal que cada agente valore cada parte en 1/2 ± ε , utilizando cortes en un algoritmo en línea , o utilizando cortes en un algoritmo fuera de línea . $O((n\log {n})/(\varepsilon ^{2}))$ $n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil$
- Téngase 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 polinomial inverso en n , la reducción a la mitad por consenso aproximada de ε es computacionalmente equivalente al problema de división del collar : cada uno puede reducirse al otro en tiempo polinomial (esto implica que la división del collar es difícil en PPAD). ^[16]
Si nos interesa encontrar una solución exacta , entonces la reducción a la mitad por 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, la reducción a la mitad del consenso aproximado de ε 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 es completa 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 una torta sino un conjunto de recursos divisibles, el problema se vuelve más fácil: ^[23]

Para los agentes con utilidades aditivas , existe un algoritmo de tiempo polinomial para calcular una reducción a la mitad de consenso con un máximo de n cortes, y para calcular una división k de consenso con un máximo de ( 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 una instancia dada. Además, es NP-difícil calcular una reducción a la mitad por consenso con un máximo de OPT+ n -1 cortes, donde OPT es el número óptimo de cortes para la instancia.
Es casi seguro que se necesitan n recortes para lograr el consenso de reducir a la mitad cuando las utilidades de los agentes se extraen de distribuciones probabilísticas.
Para los agentes con utilidades monótonas no aditivas, la reducción a la mitad del consenso aún es difícil de PPAD, pero existen algoritmos de tiempo polinomial para una cantidad fija de agentes.

Muchos subconjuntos (consenso 1/división k)

Desde una perspectiva computacional, no se sabe mucho sobre el cálculo de una división exacta con cortes para . Nótese que el problema no es necesariamente más difícil que para , ya que se nos permite usar una mayor cantidad de cortes. Lo que se sabe actualmente es: ${\estilo de visualización (k-1)n}$ $k\geq 3$ $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 polinomial de consultas de Robertson-Webb : ^[3]

Encontrar una partición tal que cada agente valore cada parte al menos 1/ kn , utilizando cortes, en un algoritmo en línea . ${\estilo de visualización (k-1)n}$
- No se sabe si se puede mejorar el 1/ kn . En particular, no se sabe 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 ), utilizando cortes. ${\estilo de visualización (k-1)n}$
Encontrar una partición tal que cada agente valore cada parte en 1/ k ± ε , utilizando cortes en un algoritmo en línea , o utilizando cortes. ^[3]^{: Sec.6} $O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})$ $n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil$
- No está claro si se puede mejorar el número de cortes. Para los algoritmos en línea, el límite inferior del número de cortes para k = 2 es , por lo que existe una brecha logarítmica. $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 envidias 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 tal manera que todos los socios reciban más de lo que les corresponde en términos de . $1/n$ $1/n$

Una división exacta con pesos diferentes no es necesariamente justa. Volviendo al ejemplo inicial, si la porción del 20% se le da a Alice y las otras dos porciones (del 50% y el 30%) se le dan a George, esto es obviamente injusto para Alice. Pero tales divisiones se pueden usar como subrutinas para dividir la torta de manera justa .

Proporcionalidad unánime

En el problema de la división de la torta entre familias , ^[25] hay n agentes agrupados en k familias; el objetivo es dividir una torta en k porciones y asignar una porción a cada 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 porción de su familia al menos en 1/ k (para otros criterios y problemas relacionados, véase división justa entre grupos ). El problema es equivalente a la división exacta en el siguiente sentido:

Para cada n y k , una solución a la división unánime-proporcional entre n ( k -1)+1 agentes agrupados en k familias implica una solución a la división exacta entre n agentes con k partes (y pesos iguales). En particular, implica que la división unánime-proporcional requiere al menos n -1 cortes, y que encontrar una división unánime-proporcional aproximada es difícil desde el punto de vista de la PPA.
Para cada n y k , una solución a la división exacta entre n agentes y k piezas implica una solución a la división unánime-proporcional entre n+1 agentes agrupados en k familias. En particular, implica que la división unánime-proporcional exacta se puede hacer con ( n -1)( k -1) cortes, y que encontrar una división unánime-proporcional 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 de división por consenso se basa en las medidas de valor que informan los socios. Si estos saben cómo funciona el algoritmo, pueden tener un incentivo para mentir sobre sus medidas de valor para recibir más de lo que les corresponde. Para evitarlo, se debe utilizar un mecanismo veraz . ^[4]^[26]

El mecanismo de división veraz más simple es el siguiente: se selecciona un único socio al azar (con probabilidades determinadas por los pesos) y se le da todo el pastel. Este mecanismo es trivialmente veraz porque no hace preguntas. Además, es un consenso en expectativa: el valor esperado de cada socio es exactamente su peso, y esto es cierto de acuerdo con todas las medidas de valor. Sin embargo, la división resultante, por supuesto, no es una división por consenso.

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

Pídale a cada socio que informe su medida de valor.
Utilice el algoritmo/oráculo existente para generar una partición en la que todas las n piezas sean exactamente 1/ n de acuerdo con las funciones de valor informadas por los socios.
Realice una permutación aleatoria en la partición de consenso y dé a cada socio una de las piezas.

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

Ver también: corte de pastel veraz .

Tabla resumen

Véase también

Problema del Nilo

Referencias

^ abcdefg Robertson, Jack; Webb, William (1998). Algoritmos para cortar la torta: sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. Número de serie 97041258. OL 2730675W.
^ abcde 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.
^ abcd Alon, Noga ; Graur, Andrei (30 de junio de 2020). "División eficiente de medidas y collares". arXiv : 2006.16613 [cs.DS].
^ ab Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013). "Verdad, justicia y corte de pastel". Juegos y comportamiento económico . 77 (1): 284–297. doi :10.1016/j.geb.2012.10.009. S2CID 2096977.
^ Neyman, Jerzy (enero de 1946). "Un teorema de existencia". Cuentas Rendus de la Academia de Ciencias . 222 : 843–845.
^ Woodall, DR (1980). "Dividir un pastel de manera justa". Revista de análisis matemático y aplicaciones . 78 : 233–247. doi : 10.1016/0022-247x(80)90225-5 .
^ Goldberg, Charles H.; West, Douglas B. (1985). "Bisección de coloraciones de círculos". Revista SIAM sobre métodos algebraicos y discretos . 6 : 93–106. doi :10.1137/0606010.
^ Alon, Noga; West, Douglas B. (1986). "El teorema de Borsuk-Ulam y la bisección de collares" (PDF) . Actas de la American Mathematical Society . 98 (4): 623. doi : 10.1090/s0002-9939-1986-0861764-9 .
^ Stromquist, Walter; Woodall, DR (1985). "Conjuntos en los que concuerdan varias medidas". Revista de análisis matemático y aplicaciones . 108 : 241–248. doi :10.1016/0022-247x(85)90021-6.
^ B. Grünbaum (1960). "Particiones de distribuciones de masa y cuerpos convexos por hiperplanos". Pacific J. Math . 10 (4): 1257–1261. doi : 10.2140/pjm.1960.10.1257 . MR 0124818.
^ de Longueville, Mark; Živaljević, Rade T. (2008). "Dividiendo collares multidimensionales". Avances en Matemáticas . 218 (3): 926–939. arXiv : math/0610800 . doi : 10.1016/j.aim.2008.02.003 .
^ Fischer, Daniel. "División por consenso de un pastel entre dos personas en proporciones arbitrarias". Math.SE. Consultado el 23 de junio de 2015 .
^ Hay una generalización que otorga a cada uno de los n socios una pieza que vale exactamente para él. Pero no se trata de una división por consenso, porque los socios pueden no estar de acuerdo sobre el valor de las otras piezas además de la pieza que les corresponde. Véase el procedimiento de cuchillo móvil de Austin#Muchos socios . $1/n$
^ V. Bergström (1930). "Zwei Sätze über ebene Vectorpolygone". Hamburgische Abhandlungen . 8 : 205–219.
^ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [ Del corte de la torta a la resolución de disputas ]. Cambridge University Press. págs. 131–133. ISBN 978-0-521-55644-6.
^ abcde Filos-Ratsikas, Aris; Goldberg, Paul W. (20 de junio de 2018). "La reducción a la mitad del consenso es PPA-completa". Actas del 50.º Simposio anual ACM SIGACT sobre teoría de la computación . STOC 2018. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 51–64. arXiv : 1711.04503 . doi :10.1145/3188745.3188880. ISBN 978-1-4503-5559-9.S2CID8111195 .
^ ab Filos-Ratsikas, Aris; Goldberg, Paul W. (23 de junio de 2019). "La complejidad de partir collares y dividir sándwiches de jamón". Actas del 51.º Simposio anual ACM SIGACT sobre teoría de la computación. STOC 2019. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 638–649. doi :10.1145/3313276.3316334. ISBN 978-1-4503-6705-9.S2CID 44085263 .
^ abcdef Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (13 de julio de 2020). "Reducción a la mitad del consenso: ¿se vuelve cada vez más fácil?". Actas de la 21.ª Conferencia de la ACM sobre economía y computación . EC '20. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 381–399. arXiv : 2002.11437 . doi :10.1145/3391403.3399527. hdl :1721.1/146185. ISBN . 978-1-4503-7975-5.S2CID211505917 .
^ abcd Deligkas, Argyrios; Filos-Ratsikas, Aris; Hollender, Alexandros (18 de julio de 2021). "Dos son compañía, tres son multitud: reducción a la mitad del consenso para un número constante de agentes". Actas de la 22.ª Conferencia de la ACM sobre economía y computación . EC '21. Nueva York, NY, EE. UU.: Association for Computing Machinery. 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. Número de identificación del sujeto 220871193.
^ abcdefg 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].
^ abc Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. (1 de mayo de 2021). "Cálculo de soluciones exactas de la reducción a la mitad por consenso y el teorema de Borsuk-Ulam". Revista de Ciencias Informáticas y de Sistemas . 117 : 75–98. arXiv : 1903.03101 . doi :10.1016/j.jcss.2020.10.006. ISSN 0022-0000. S2CID 228908526.
^ ab Batziou, Eleni; Hansen, Kristoffer Arnsfelt; Høgh, Kasper (7 de marzo de 2021). "Reducción a la mitad del consenso aproximado fuerte y el teorema de Borsuk-Ulam". arXiv : 2103.04452 [cs.GT].
^ Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Reducción a la mitad por 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.
^ ab Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (1 de enero de 2021), "Una caracterización topológica de los argumentos módulo-p y las implicaciones 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, S2CID214667000
^ ab Segal-Halevi, Erel; Nitzan, Shmuel (1 de diciembre de 2019). "Corte justo de la torta 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.
^ Mossel, Elchanan; Tamuz, Omer (2010). "División justa y veraz". Teoría de juegos algorítmicos . Apuntes de clase en 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. Número de identificación del sujeto 11732339.
^ Requisitos previos sobre las funciones de valor de los socios. Menos requisitos previos significa que el resultado es más general. Con=Continuo es el más general; Con+Agregar=Aditivo es menos general; Con+Agregar+Pwl=Trazado-lineal es el menos general.