División del consenso

Por cada${\displaystyle \varepsilon >0}$, Un${\displaystyle \varepsilon }$-División casi exacta en las proporciones${\displaystyle w_{1},w_{2},\ldots,w_{k}}$es una división en la que:

${\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${\displaystyle w_{j}}$donde la diferencia es menor que${\displaystyle \varepsilon }$. ^{[ 1 ] : 127} Algunos casos especiales son:

• ${\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 del consenso : el caso especial en el que${\displaystyle k=2}$y${\displaystyle w_{1}=w_{2}=1/2}$.
• ${\displaystyle \varepsilon }$-división perfecta – el caso especial en el que${\displaystyle k=n}$y${\displaystyle w_{1}=\cdots =w_{n}=1/n}$.

Es fácil demostrar la existencia de una división exacta cuando los agentes tienen valoraciones constantes por partes . Esto significa que el pastel se puede dividir en R regiones, de modo que todos los agentes coincidan en que la densidad de valor en cada región es uniforme. Por ejemplo, consideremos un pastel circular en el que cada uno de sus 4 cuartos tiene una cobertura diferente. Los agentes pueden valorar cada cobertura de manera distinta, pero no distinguen entre diferentes trozos que tienen la misma cobertura: el valor de cada trozo para cada agente solo depende de la cantidad que recibe de cada región. Una división exacta se puede lograr de la siguiente manera:

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

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

Existe una división exacta en el contexto más general en el que los agentes tienen medidas no atómicas numerablemente aditivas . Esto es un corolario del teorema de convexidad de Dubins-Spanier (la existencia de una división de consenso 1/ k 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 un pastel de intervalos como una unión numerable de intervalos. Intuición: considérese el procedimiento de división para pasteles homogéneos 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${\displaystyle R\to \infty }$Este proceso converge a una división por consenso. Sin embargo, en el límite, el número de cortes necesarios es infinito. Fremlin demostró posteriormente que es posible construir dicha división como una unión finita de intervalos.

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

Consideremos primero el caso de reducción a la mitad del consenso :${\displaystyle k=2}$y pesos iguales. El límite inferior del número de cortes es ${\displaystyle n\cdot (k-1)=n}$. De hecho, siempre existe una reducción a la mitad por consenso con como máximo 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 ]}

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

Aunque las preferencias de los agentes se modelan con medidas, las demostraciones 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 del pastel sean aditivamente separables. ^{[ 2 ]}

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

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 la que cada porción contiene como máximo n - 1 intervalos; por lo tanto, se necesitan como máximo 2n - 2 cortes. Véase el teorema de Stromquist-Woodall . El número de cortes es esencialmente óptimo para pesos generales. Este teorema puede aplicarse recursivamente para obtener una división exacta para cualquier k > 1 y cualquier peso, utilizando O( nk ) cortes.

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 otra manera: si el pastel es el espacio${\displaystyle \mathbb {R} ^{n}}$y las medidas de valor de los socios son finitas y se desvanecen en cualquier${\displaystyle n-1}$Si se trata de un hiperplano dimensional, existe un semiplano cuyo valor es exactamente 1/2 para cada socio. Por lo tanto, existe una división por consenso mediante un único corte.

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

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

También existen adaptaciones discretas de estos resultados multidimensionales. ^{[ 11 ]}

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 se encuentra en el paso k , dispone de una colección de como máximo k piezas. Para realizar una división exacta, el protocolo debe encontrar un subconjunto exacto , es decir, un subconjunto de las piezas que ambos participantes valoran exactamente como 1/2. Demostraremos que, para cada k , existen situaciones en las que, en el paso k, no existe un subconjunto exacto y, por lo tanto, el protocolo podría tener que continuar indefinidamente.

Inicialmente, solo hay una pieza que ambos socios valoran como 1, por lo que obviamente no existe un subconjunto exacto. Tras un paso, como máximo uno de los socios (por ejemplo, Alicia) ha tenido la opción de cortar el pastel. Incluso si Alicia corta el pastel en dos trozos que, en su opinión, son iguales, pueden ser diferentes para George, por lo que, de nuevo, no existe un subconjunto exacto.

Supongamos ahora que estamos en el paso k y hay k piezas. Sin pérdida de generalidad , podemos asumir 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 descartarla y continuar con las demás.

El número total de subconjuntos diferentes ahora es 2k ^, y por la suposición de inducción ninguno de ellos es exacto. En el paso k , el protocolo puede pedirle a Alice o a George que corten una pieza determinada en dos piezas. Supongamos sin pérdida de generalidad que quien corta es George y que corta la pieza X en dos subpiezas: X1 y X2. Ahora, el número total de subconjuntos es 2k ^{+ 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 examinar 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 quien corta, puede cortar de manera que uno de estos subconjuntos sea un subconjunto exacto para él (por ejemplo, si un subconjunto determinado que contiene la pieza X tenía un valor de 3/4, George puede cortar X de tal manera que X1 tenga un valor de 1/4 en su opinión, de modo que el nuevo subconjunto tenga un valor exacto de 1/2). Pero George desconoce 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, existe un número infinito de casos en los que ningún subconjunto nuevo tiene un valor de 1/2 para Alice; por consiguiente, ningún subconjunto nuevo es exacto.

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

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

El mismo protocolo se puede utilizar para cortar un trozo cuyo valor ambos agentes coinciden en que es exactamente igual.${\displaystyle 1/n}$Al combinar varias de estas piezas, es posible lograr una división consensuada con cualquier proporción que sean números racionales. Sin embargo, esto puede requerir una gran cantidad de cortes.

Una mejor manera de lograr una división consensuada es identificar los dos extremos del pastel y tratarlo como un círculo. Es decir, cuando el cuchillo derecho llega al lado derecho, inmediatamente va 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 consensuada para cada${\displaystyle p\in [0,1]}$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 del trozo 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 el trozo. Esto requiere solo dos cortes.

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

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

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

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

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

Paso de desmenuzar : el objetivo es cortar el pastel en trozos diminutos ("migas") de manera que cada participante asigne un valor suficientemente pequeño a cada miga. Esto se hace de la siguiente manera. Sea k una constante. Pida al participante n.° 1 que corte el pastel en k trozos que valore como 1/ k . Pida al participante n.° 2 que recorte los trozos según sea necesario (usando como máximo k - 1 cortes) de manera que cada trozo tenga un valor de como máximo 1/ k . Estos nuevos trozos, por supuesto, todavía tienen un valor de como máximo 1/ k para el participante n.° 1. Continúe con los participantes n.° 3, n.° 4, ..., n . Finalmente, todos los n participantes valoran cada miga resultante como como máximo 1/ k .

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

1. Coge un cuenco vacío.
2. Introduce una de las migas en el bol.
3. Si el valor en el tazón supera la mitad para cualquiera de los socios, dele el tazón a ese socio y déle las migas restantes al otro.
4. De lo contrario (si el valor en el recipiente es menor que 1/2 para ambos), si el valor en el recipiente es mayor para Alice que para George, entonces encuentra una miga cuyo valor para George sea mayor que su valor para Alice (tal miga debe existir porque la suma de los valores de todas las migas es 1 tanto para Alice como para George). Agrega esta miga al recipiente y regresa al paso 2.

Es posible demostrar por inducción que la diferencia en la valoración 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 cada socio. La longitud de cada vector está limitada, es decir, para cada vector v :${\displaystyle ||v||\leq {\sqrt {n}}/k}$Nuestro objetivo es crear, para cada socio j , un vector cuyos elementos estén todos cerca de w _j . Para ello, debemos dividir los vectores en subconjuntos, de modo que la suma de los vectores en cada subconjunto j esté suficientemente cerca de un vector cuyos elementos sean todos w _j . Esto es posible gracias a un teorema de V. Bergström, ^{[ 14 ] [ 1 ] : 126–128}

El procedimiento Crumb-and-Pack es una subrutina del protocolo Robertson-Webb . Este último protocolo genera una división que es casi exacta y un corte de pastel sin envidia .

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

Una reducción a la mitad del consenso ε -aproximada puede calcularse 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 pertenece a 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.

Primero, supongamos que ε puede ser 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 a ε es PPA-difícil . La dificultad se mantiene incluso con las siguientes condiciones adicionales: ^{[ 16 ]}

• Los agentes tienen valoraciones constantes por partes . La entrada al 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 mismos pueden ser exponenciales en n ).
• El factor de aproximación ε puede ser un 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 polinomial). ^{[ 19 ]}

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

• Las valoraciones son constantes por partes;
• Se permite utilizar un número constante de cortes adicionales (es decir, buscamos una reducción a la mitad por consenso para n agentes utilizando n + d cortes, para alguna constante d ). ^{[ 20 ]}
• Cuando ε es una constante, queda abierto si la reducción a la mitad del consenso aproximada a ε es PPA-difícil (que es más fuerte que PPAD-difícil) . ^{[ 16 ]}
• Además, decidir si existe una reducción a la mitad de consenso aproximada a ε con n -1 cortes es NP-difícil incluso cuando ε es una constante. La demostración se realiza mediante 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 , incluyendo una consulta de marca a 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${\displaystyle n}$cortes.
• Encontrar una partición tal que cada agente valore cada parte en 1/2 ± ε , utilizando${\displaystyle O((n\log {n})/(\varepsilon ^{2}))}$recortes en un algoritmo en línea o utilizando${\displaystyle n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil }$recortes en un algoritmo fuera de línea .
  • Nótese que hay una diferencia 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 del consenso aproximada por ε es computacionalmente equivalente al problema de la división del collar : cada uno puede reducirse al otro en tiempo polinomial (esto implica que la división del collar es PPAD difícil). ^{[ 16 ]}
• Si nos interesa encontrar una solución exacta , entonces la reducción por mitades del 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 ε -aproximada es equivalente en tiempo polinomial al cálculo de 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 involucra 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 la mitad de consenso con como máximo n cortes, y para calcular una división k de consenso con como máximo ( k -1) n cortes.
• Calcular una reducción a la mitad por consenso con el número óptimo de cortes para una instancia dada es un problema NP-difícil. Además, 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, también es un problema NP-difícil.
• Es casi seguro que se necesitan n cortes para la reducción a la mitad del consenso cuando las utilidades de los agentes se extraen de distribuciones probabilísticas.
• Para agentes con utilidades monótonas no aditivas, la reducción a la mitad del consenso sigue siendo PPAD-difícil, pero existen algoritmos de tiempo polinomial para un número fijo de agentes.

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

• 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 un 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${\displaystyle (k-1)n}$recortes, en un algoritmo en línea .
  • Queda por determinar si el 1/ kn puede mejorarse. En particular, queda por determinar si existe un algoritmo eficiente (en línea o fuera de línea) tal que cada agente valore cada parte al menos como 1/ c ( k ), donde c(k) es alguna función de k (independiente de n ), utilizando${\displaystyle (k-1)n}$cortes.
• Encontrar una partición tal que cada agente valore cada parte en 1/ k ± ε , utilizando${\displaystyle O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})}$recortes en un algoritmo en línea o utilizando${\displaystyle n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil }$cortes. ^{[ 3 ] : Sec.6}
  • Queda por determinar si se puede mejorar el número de cortes. Para algoritmos en línea, un límite inferior para el número de cortes para k = 2 es${\displaystyle O({\frac {n}{\varepsilon ^{2}}})}$, por lo que existe una brecha logarítmica.

En el problema de cortar un pastel entre familias , ^{[ 25 ]} hay n agentes agrupados en k familias; el objetivo es dividir un pastel en k trozos y asignar un trozo a cada familia. Un criterio natural de equidad 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 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 proporcional unánime entre n ( k -1)+1 agentes agrupados en k familias implica una solución a 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 PPA-difícil.
• 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 proporcional unánime entre n+1 agentes agrupados en k familias. En particular, implica que la división proporcional unánime exacta se puede realizar 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 ]}

Cualquier algoritmo para la división por consenso se basa en las medidas de valor reportadas por los socios. Si los socios conocen el funcionamiento del algoritmo, podrían tener un incentivo para mentir sobre sus medidas de valor con el fin de recibir más de lo que les corresponde. Para evitar esto, se debe utilizar un mecanismo veraz . ^{[ 4 ] [ 26 ]}

El mecanismo de división más sencillo y veraz consiste en seleccionar a un socio al azar (con probabilidades determinadas por los pesos) y darle el pastel entero. Este mecanismo es trivialmente veraz porque no plantea preguntas. Además, se basa en el consenso: el valor esperado de cada socio es exactamente igual a su peso, y esto se cumple según cualquier medida de valor. Sin embargo, la división resultante, por supuesto, no es una división por consenso.

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

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

En este caso, el valor esperado de cada participante sigue siendo 1/ n, independientemente de la función de valor declarada, por lo que el mecanismo sigue siendo veraz: ningún participante obtiene beneficio alguno al mentir. Además, a un participante sincero se le garantiza un valor exacto de 1/ n con una probabilidad de 1 (no solo en términos de expectativa). Por lo tanto, los participantes tienen un incentivo para revelar sus verdaderas funciones de valor.