Corte de pastel sincero

El reparto veraz de pasteles es el estudio de algoritmos para un reparto justo de pasteles que también sean mecanismos veraces , es decir, que incentiven a los participantes a revelar sus verdaderas valoraciones de las distintas partes del pastel.

El método clásico de dividir y elegir para cortar un pastel no es del todo cierto: si quien corta conoce las preferencias de quien elige, puede obtener mucho más de la mitad actuando estratégicamente. Por ejemplo, supongamos que quien corta valora un trozo por su tamaño, mientras que quien elige lo valora por la cantidad de chocolate que contiene. Entonces, quien corta puede dividir el pastel en dos trozos con casi la misma cantidad de chocolate, de manera que el trozo más pequeño tenga un poco más. En ese caso, quien elige se quedará con el trozo más pequeño y quien corta se quedará con el más grande, que puede valer mucho más de la mitad (dependiendo de cómo se distribuya el chocolate).

Mecanismos aleatorios

Existe un mecanismo aleatorio y veraz, aparentemente sencillo, para el reparto equitativo de un pastel : se selecciona un único agente al azar y se le entrega el pastel entero. Este mecanismo es trivialmente veraz porque no plantea preguntas. Además, es justo en términos de expectativa: el valor esperado de cada participante es exactamente 1/ n . Sin embargo, la distribución resultante no es justa. El reto consiste en desarrollar mecanismos veraces que sean justos a posteriori y no solo a priori. Ya se han desarrollado varios de estos mecanismos.

Mecanismo de división exacto

Una división exacta (también conocida como división por consenso ) es una partición del pastel en n partes tales que cada agente valora cada parte exactamente en 1/ n . La existencia de tal división es un corolario del teorema de convexidad de Dubins-Spanier . Además, existe tal división con como máximo $n(n-1)^{2}$ cortes; este es un corolario del teorema de Stromquist-Woodall y del teorema de división de collares .

En general, un algoritmo finito no puede encontrar una división exacta. Sin embargo, puede encontrarse en algunos casos especiales, por ejemplo, cuando todos los agentes tienen valoraciones lineales a trozos. Supongamos que tenemos un algoritmo (u oráculo) no veraz para encontrar una división exacta. Este puede utilizarse para construir un mecanismo aleatorio que sea veraz en expectativa. ^{[ 1 ]}^{[ 2 ]} El mecanismo aleatorio es un mecanismo de revelación directa : comienza pidiendo a todos los agentes que revelen sus medidas de valor completas:

Pida a los agentes que informen sobre sus indicadores de valor.
Utilice el algoritmo/oráculo existente para generar una división exacta.
Realiza una permutación aleatoria en la partición de consenso y entrega una de las piezas a cada socio.

Aquí, el valor esperado de cada agente es siempre 1/ n, independientemente de la función de valor declarada. Por lo tanto, el mecanismo es veraz: ningún agente obtiene beneficio alguno mintiendo. Además, a un socio sincero se le garantiza un valor exacto de 1/ n con probabilidad 1 (no solo en términos de expectativa). En consecuencia, los socios tienen un incentivo para revelar sus verdaderas funciones de valor.

Mecanismo superproporcional

Una división superproporcional es aquella en la que cada agente recibe estrictamente más de 1/ n según su propia valoración. Se sabe que existe tal división si y solo si hay al menos dos agentes que valoran de forma diferente al menos una porción del pastel. Cualquier mecanismo determinista que siempre devuelva una división proporcional, y que siempre devuelva una división superproporcional cuando existe, no puede ser veraz.

Mossel y Tamuz presentan un mecanismo aleatorio superproporcional que es veraz en expectativa: ^{[ 1 ]}

Elija una división de una determinada distribución D sobre divisiones.
Pida a cada agente que evalúe su pieza.
Si todas las n evaluaciones son mayores que 1/ n , entonces implemente la asignación y finalice.
De lo contrario, utilice el mecanismo de división exacta.

La distribución D en el paso 1 debe elegirse de tal manera que, independientemente de las valoraciones de los agentes, exista una probabilidad positiva de que se seleccione una división superproporcional si existe. Luego, en el paso 2, es óptimo que cada agente informe el valor verdadero: informar un valor menor no tiene efecto o podría hacer que el valor del agente pase de superproporcional a simplemente proporcional (en el paso 4); informar un valor mayor no tiene efecto o podría hacer que el valor del agente pase de proporcional a menor que 1/ n (en el paso 3).

División aproximada exacta mediante consultas

Supongamos que, en lugar de revelar directamente sus valoraciones, los agentes revelan sus valores indirectamente al responder a consultas de valoración ( como en el modelo de Robertson-Webb).

Branzei y Miltersen ^{[ 3 ]} muestran que el mecanismo de división exacta puede ser "discretizado" y ejecutado en el modelo de consulta. Esto produce, para cualquier $\epsilon >0$ , un protocolo aleatorio basado en consultas, que pregunta como máximo $O(n^{2}/\epsilon )$ consultas, es sincero en sus expectativas y asigna a cada agente una parte de valor entre $1/n-\epsilon$ y $1/n+\epsilon$ , según las valoraciones de todos los agentes.

Por otro lado, demuestran que, en cualquier protocolo determinista basado en consultas veraces, si todos los agentes valoran positivamente todas las partes del pastel, existe al menos un agente que recibe el trozo vacío. Esto implica que, si solo hay dos agentes, al menos uno de ellos es un "dictador" y se queda con todo el pastel. Obviamente, ningún mecanismo de este tipo puede estar exento de envidia.

Mecanismo aleatorio para valoraciones constantes por partes

Supongamos que todos los agentes tienen valoraciones constantes por partes . Esto significa que, para cada agente, el pastel se divide en un número finito de subconjuntos, y la densidad de valor del agente en cada subconjunto es constante. Para este caso, Aziz y Ye presentan un algoritmo aleatorio que es más eficiente económicamente: la Dictadura Serial Restringida es veraz en expectativa, robustamente proporcional y satisface una propiedad llamada unanimidad : si la longitud 1/ n del pastel más preferida por cada agente es disjunta de la de los demás agentes, entonces cada agente obtiene su longitud 1/ n del pastel más preferida. Esta es una forma débil de eficiencia que no satisfacen los mecanismos basados en la división exacta. Cuando solo hay dos agentes, también es de tiempo polinomial y robustamente libre de envidia. ^{[ 4 ]}

Mecanismos deterministas: valoraciones constantes por partes

En el caso de los mecanismos deterministas , los resultados son mayoritariamente negativos, incluso cuando todos los agentes tienen valoraciones constantes a trozos.

Kurokawa, Lai y Procaccia demuestran que no existe ningún mecanismo determinista, veraz y libre de envidia que requiera un número limitado de consultas de Robertson-Webb. ^{[ 5 ]}

Aziz y Ye demuestran que no existe ningún mecanismo veraz determinista que satisfaga alguna de las siguientes propiedades: ^{[ 4 ]}

Proporcional y óptimo de Pareto;
Robusto, proporcional y no derrochador ("no derrochador" significa que ninguna pieza se asigna a un agente que no la desea; es más débil que la optimalidad de Pareto).

Menon y Larson introducen la noción de ε-veracidad , que significa que ningún agente obtiene más que una fracción ε al informar erróneamente, donde ε es una constante positiva independiente de las valoraciones de los agentes. Demuestran que ningún mecanismo determinista satisface ninguna de las siguientes propiedades: ^{[ 6 ]}

ε -veraz, aproximadamente proporcional y no derrochador (para constantes de aproximación como máximo 1/ n );
Veraz, aproximadamente proporcional y conectado (para una aproximación constante como máximo 1/ n ).

Presentan una modificación menor al protocolo Even-Paz y demuestran que es ε -verdadero con ε = 1 - 3/(2 n ) cuando n es par, y ε = 1 - 3/(2 n ) + 1/ n ² cuando n es impar.

Bei, Chen, Huzhang, Tao y Wu demuestran que no existe ningún mecanismo determinista, veraz y libre de envidia, ni siquiera en el modelo de revelación directa, que satisfaga alguna de las siguientes propiedades adicionales: ^{[ 7 ]}

Piezas conectadas;
No derrochador;
Sin tener en cuenta la posición, la asignación de una parte del pastel se basa únicamente en la valoración que los agentes hacen de esa parte, y no en su posición relativa en el pastel.

Cabe señalar que estos resultados de imposibilidad se mantienen con o sin libre disposición.

En el lado positivo, en una economía replicada, donde cada agente se replica k veces, existen mecanismos libres de envidia en los que decir la verdad es un equilibrio de Nash : ^{[ 7 ]}

Con el requisito de conectividad, en cualquier mecanismo libre de envidia, decir la verdad converge a un equilibrio de Nash cuando k tiende a infinito;
Sin requisito de conectividad, en el mecanismo que asigna cada subintervalo homogéneo por igual entre todos los agentes, decir la verdad es un equilibrio de Nash ya cuando k ≥ 2.

Tao mejora el resultado de imposibilidad anterior de Bei, Chen, Huzhang, Tao y Wu y muestra que no hay un mecanismo determinista, veraz y proporcional, incluso en el modelo de revelación directa, e incluso cuando se cumplen todas las siguientes condiciones: ^{[ 8 ]}

Solo hay dos agentes;
Los agentes tienen hambre: la valoración de cada agente es positiva (es decir, no puede ser 0);
El mecanismo permite que una parte del pastel quede sin asignar.

Queda por determinar si este resultado de imposibilidad se extiende a tres o más agentes.

En el lado positivo, Tao presenta dos algoritmos que alcanzan una noción más débil llamada "veracidad proporcional con aversión al riesgo" (PRAT). Esto significa que, en cualquier desviación rentable para el agente i , existen valoraciones de los otros agentes por las cuales i recibe menos de su parte proporcional. Esta propiedad es más fuerte que la "veracidad con aversión al riesgo", que significa que, en cualquier desviación rentable para i, existen valoraciones de los otros agentes por las cuales i recibe menos de su valor en un informe veraz. Presenta un algoritmo que es PRAT y libre de envidia, y un algoritmo que es PRAT, proporcional y conectado. ^{[ 8 ]}^{[ 9 ]}

Valoraciones uniformes por partes

Supongamos que todos los agentes tienen valoraciones uniformes por partes . Esto significa que, para cada agente, existe un subconjunto del pastel que le resulta deseable , y el valor que el agente le otorga a cada porción es simplemente la cantidad de pastel deseable que contiene. Por ejemplo, supongamos que algunas partes del pastel están cubiertas por una capa uniforme de chocolate, mientras que otras no. Un agente que valora cada porción únicamente por la cantidad de chocolate que contiene tiene una valoración uniforme por partes. Este es un caso especial de valoraciones constantes por partes. Se han desarrollado varios algoritmos veraces para este caso especial.

Chen, Lai, Parkes y Procaccia presentan un mecanismo de revelación directa que es determinista , proporcional, libre de envidia , óptimo de Pareto y de tiempo polinomial. ^{[ 2 ]} Funciona para cualquier número de agentes. Aquí se muestra una ilustración del mecanismo CLPP para dos agentes (donde el pastel es un intervalo).

Pida a cada agente que indique los intervalos que desea.
Se descarta cualquier subintervalo que no sea deseado por ningún agente.
Cada subintervalo que sea deseado por un único agente se asigna a ese agente.
Los subintervalos que desean ambos agentes se asignan de manera que ambos agentes obtengan una longitud total igual .

Ahora bien, si un agente dice que quiere un intervalo que en realidad no quiere, puede que reciba más pastel inútil en el paso 3 y menos pastel útil en el paso 4. Si dice que no quiere un intervalo que sí quiere, recibirá menos pastel útil en el paso 3 y más pastel útil en el paso 4; sin embargo, la cantidad entregada en el paso 4 se comparte con el otro agente, por lo que, en definitiva, el agente mentiroso sale perdiendo. Este mecanismo puede generalizarse a cualquier número de agentes.

El mecanismo CLPP se basa en el supuesto de libre disposición , es decir, la capacidad de desechar las piezas que no son deseadas por ningún agente.

Nota : Aziz y Ye ^{[ 4 ]} presentaron dos mecanismos que extienden el mecanismo CLPP a valoraciones constantes por partes: el algoritmo de reparto restringido de pasteles y el algoritmo de equilibrio de mercado. Sin embargo, ninguna de estas extensiones es válida cuando las valoraciones no son uniformes por partes.

Maya y Nisan demuestran que el mecanismo CLPP es único en el siguiente sentido. ^{[ 10 ]} Consideremos el caso especial de dos agentes con valoraciones uniformes por partes, donde el pastel es [0,1], Alice solo quiere el subintervalo [0, a ] para algún a <1, y Bob solo desea el subintervalo [1 − b ,1] para algún b <1. Consideremos solo mecanismos no derrochadores , es decir, mecanismos que asignan cada pieza deseada por al menos un jugador a un jugador que la desea. Cada uno de estos mecanismos debe darle a Alice un subconjunto [0, c ] para algún c <1 y a Bob un subconjunto [1 − d ,1] para algún d <1. En este modelo:

Un mecanismo determinista no derrochador es veraz si y solo si, para algún parámetro t en [0,1], le da a Alice el intervalo [0, min( a , max(1 − b , t ))] y a Bob el intervalo [1 − min( b ,max(1 − a ,1 − t )),1]
Dicho mecanismo está libre de envidia si y solo si t = 1/2; en este caso es equivalente al mecanismo CLPP.

También demuestran que, incluso para 2 agentes, cualquier mecanismo veraz alcanza como máximo el 0,93 del bienestar social óptimo.

Li, Zhang y Zhang demuestran que el mecanismo CLPP funciona bien incluso cuando existen externalidades (es decir, algunos agentes obtienen algún beneficio del valor otorgado a otros), siempre que las externalidades sean suficientemente pequeñas. Por otro lado, si las externalidades (ya sean positivas o negativas) son grandes, no existe ningún mecanismo veraz, no derrochador e independiente de la posición. ^{[ 11 ]}

Alijani, Farhadi, Ghodsi, Seddighin y Tajik presentan varios mecanismos para casos especiales de valoraciones uniformes por partes: ^{[ 12 ]}

El proceso de expansión maneja valoraciones uniformes por partes, donde cada agente tiene un único intervalo deseado y, además, los intervalos deseados de los agentes satisfacen una propiedad de ordenación . Es de tiempo polinomial, veraz, libre de envidia y garantiza piezas conectadas.
El proceso de expansión con desbloqueo maneja valoraciones uniformes por partes, donde cada agente tiene un único intervalo deseado, pero sin el requisito de ordenación. Es de tiempo polinomial, veraz, libre de envidia y no necesariamente conexo, pero realiza como máximo 2n − 2 cortes.

Bei, Huzhang y Suksompong presentan un mecanismo para dos agentes con valoraciones uniformes por partes, que tiene las mismas propiedades que CLPP (veraz, determinista, proporcional, libre de envidia, óptimo de Pareto y se ejecuta en tiempo polinomial), pero garantiza que se asigne todo el pastel: ^{[ 13 ]}

Encuentra el menor x en [0,1] tal que la longitud deseada por Alice en [0, x ] sea igual a la longitud deseada por Bob en [ x ,1].
Dale a Alice los intervalos en [0, x ] que Alice valora y los intervalos en [ x , 1] que Bob no valora; dale el resto a Bob.

El mecanismo BHS funciona tanto para el reparto de pasteles como para la división de tareas (cuando las valoraciones de los agentes son negativas). Cabe señalar que BHS no satisface algunas propiedades deseables naturales:

No garantiza piezas conectadas , por ejemplo, cuando Alice quiere [0,1] y Bob quiere [0,0.5], entonces x =0.25, Alice obtiene [0,0.25] y [0.5,1], y Bob obtiene [0.25,0.5].
No es anónimo (ver reparto equitativo simétrico de pasteles ) : si Alice quiere [0,1] y Bob quiere [0,0.5], entonces Alice obtiene una longitud deseada de 0.75 y Bob obtiene 0.25, pero si se intercambian las valoraciones (Alice quiere [0,0.5] y Bob quiere [0,1]), entonces x = 0.5 y ambos agentes obtienen la longitud deseada 0.5.
No es ajeno a la posición : si Alice quiere [0,0.5] y Bob quiere [0,1], entonces ambos agentes obtienen el valor 0.5, pero si el intervalo deseado por Alice se mueve a [0.5,1], entonces x = 0.75 y Alice obtiene 0.25 y Bob obtiene 0.75.

Esto no es un problema con el mecanismo específico: es demostrablemente imposible tener un mecanismo veraz y libre de envidia que asigne todo el pastel y garantice cualquiera de estas tres propiedades, incluso para dos agentes con valoraciones uniformes por partes. ^{[ 13 ]}

El mecanismo BHS se extendió a cualquier número de agentes, pero solo para un caso especial de valoraciones uniformes por partes, en el que cada agente desea solo un único intervalo de la forma [0, x _i ].

Ianovsky ^{[ 14 ]} demuestra que ningún mecanismo veraz puede alcanzar un reparto de pastel utilitarista óptimo , incluso cuando todos los agentes tienen valoraciones uniformes por partes. Además, ningún mecanismo veraz puede alcanzar una asignación con un bienestar utilitarista al menos tan grande como cualquier otro mecanismo. Sin embargo, existe un mecanismo veraz simple (denominado Orden Lex) que no es derrochador : dar al agente 1 todas las piezas que le gustan; luego, dar al agente 2 todas las piezas que le gustan y que aún no se le han dado al agente 1; etc. Una variante de este mecanismo es el Juego de la Longitud, en el que los agentes se renombran según la longitud total de sus intervalos deseados, de modo que el agente con el intervalo más corto se llama 1, el agente con el siguiente intervalo más corto se llama 2, etc. Sin embargo, este no es un mecanismo veraz.

Si todos los agentes son veraces, entonces se produce una asignación óptima desde el punto de vista utilitarista.
Si los agentes son estratégicos, entonces todos sus equilibrios de Nash bien comportados son Pareto-eficientes y libres de envidia, y producen las mismas recompensas que el mecanismo CLPP.

Resumen de mecanismos veraces y resultados de imposibilidad

Véase también

Referencias

1 2 3 4 Mossel, Elchanan; Tamuz, Omer (2010). "División justa y veraz". En Kontogiannis, Spyros C.; Koutsoupias, Elias; Spirakis, Paul G. (eds.). Teoría de juegos algorítmica: Tercer Simposio Internacional, SAGT 2010, Atenas, Grecia, 18-20 de octubre de 2010. Actas . Lecture Notes in Computer Science. Vol. 6386. Springer. pp. 288-299 . arXiv : 1003.5480 . Bibcode : 2010LNCS.6386..288M . doi : 10.1007/978-3-642-16170-4_25 . ISBN 9783642161704. S2CID 11732339 .
1 2 3 4 Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013-01-01). "Verdad, justicia y cortar el pastel" (PDF) . Games and Economic Behavior . 77 (1): 284– 297. doi : 10.1016/j.geb.2012.10.009 . ISSN 0899-8256 . S2CID 2096977 .
1 2 3 Brânzei, Simina; Miltersen, Peter Bro (2015-06-22). "Un teorema de dictadura para cortar pasteles" . Vigésimo cuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial .
1 2 3 4 Aziz, Haris; Ye, Chun (2014). "Algoritmos de corte de pastel para valoraciones constantes y uniformes por partes". En Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Economía de la Web e Internet – 10.ª Conferencia Internacional, WINE 2014, Pekín, China, 14-17 de diciembre de 2014. Actas . Lecture Notes in Computer Science. Vol. 8877. Springer. pp. 1-14 . arXiv : 1307.2908 . doi : 10.1007/978-3-319-13129-0_1 . ISBN 978-3-319-13128-3.
↑ Kurokawa, David; Lai, John K.; Procaccia, Ariel D. (30 de junio de 2013). "Cómo cortar un pastel antes de que termine la fiesta" . Vigésimo séptima Conferencia AAAI sobre Inteligencia Artificial . 27 : 555–561 . doi : 10.1609/aaai.v27i1.8629 . S2CID 12638556 .
↑ Menon, Vijay; Larson, Kate (2017-05-17). "Deterministic, Strategyproof, and Fair Cake Cutting". arXiv : 1705.06306 [ cs.GT ].
1 2 3 Bei, Xiaohui; Chen, Ning; Huzhang, Guangda; Tao, Biaoshuai; Wu, Jiajun (2017). "Cortando el pastel: envidia y verdad" . Actas de la 26.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'17. AAAI Press: 3625–3631 . ISBN 9780999241103.
1 2 3 Tao, Biaoshuai (13 de julio de 2022). "Sobre la existencia de mecanismos veraces y justos para el reparto de pasteles" . Actas de la 23.ª Conferencia ACM sobre Economía y Computación . págs. 404–434 . arXiv : 2104.07387 . doi : 10.1145/3490486.3538321 . ISBN 9781450391504. S2CID 233241229 .
↑ Bu, Xiaolin; Song, Jiaxin; Tao, Biaoshuai (2023-06-01). "Sobre la existencia de mecanismos veraces y justos para cortar pasteles" . Inteligencia Artificial . 319 103904. arXiv : 2104.07387 . doi : 10.1016/j.artint.2023.103904 . ISSN 0004-3702 .
↑ Maya, Avishay; Nisan, Noam (2012). "Reparto de pastel para dos jugadores con incentivos compatibles". En Goldberg, Paul W. (ed.). Economía de Internet y redes: 8.º Taller Internacional, WINE 2012, Liverpool, Reino Unido, 10-12 de diciembre de 2012. Actas . Lecture Notes in Computer Science. Vol. 7695. Springer. pp. 170-183 . arXiv : 1210.0155 . doi : 10.1007/978-3-642-35311 & minus ; 6_13 (inactivo el 7 de septiembre de 2025) . ISBN 9783642353116. S2CID 1927798 . {{cite conference}}: CS1 maint: DOI inactivo desde septiembre de 2025 ( enlace )
↑ Li, Minming; Zhang, Jialin; Zhang, Qiang (22 de junio de 2015). "Mecanismos veraces para cortar pasteles con externalidades: ¡No los haga preocuparse demasiado por los demás!" . Vigésimo cuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial .
1 2 Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tayiko, Ahmad S. (10 de febrero de 2017). «Mecanismos sin envidia y con un número mínimo de cortes» . Trigésima Primera Conferencia AAAI sobre Inteligencia Artificial . 31 . doi : 10.1609/aaai.v31i1.10584 . S2CID 789550 .
1 2 3 Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (2020). "División justa y veraz sin libre disposición" . Elección social y bienestar . 55 (3): 523– 545. arXiv : 1804.06923 . doi : 10.1007/s00355-020-01256-0 . PMC 7497335. PMID 33005068 .
↑ Ianovski, Egor (2012-03-01). "Mecanismos de corte de pasteles". arXiv : 1203.0100 [ cs.GT ].
↑ PWC = constante por partes, PWU = uniforme por partes, PWU1 = uniforme por partes con un único intervalo deseado.
↑ Si el algoritmo también puede manejar pasteles con utilidades negativas (tareas).
↑ Si se divide todo el pastel, sin desperdiciar nada.
↑ Si la asignación resultante es siempre óptima de Pareto .
↑ Si la asignación resultante siempre está libre de envidia .
↑ Si el mecanismo es anónimo .
↑ Si las piezas resultantes están siempre conectadas.
↑ Si el mecanismo es independiente de la posición .
↑ Si el algoritmo garantiza que no haya desperdicio.
↑ El tiempo de ejecución está dominado por el cálculo de una división exacta . En general, es ilimitado, pero en casos especiales puede ser polinomial.

[:0-1] 1 2 3 4 Mossel, Elchanan; Tamuz, Omer (2010). "División justa y veraz". En Kontogiannis, Spyros C.; Koutsoupias, Elias; Spirakis, Paul G. (eds.). Teoría de juegos algorítmica: Tercer Simposio Internacional, SAGT 2010, Atenas, Grecia, 18-20 de octubre de 2010. Actas . Lecture Notes in Computer Science. Vol. 6386. Springer. pp. 288-299 . arXiv : 1003.5480 . Bibcode : 2010LNCS.6386..288M . doi : 10.1007/978-3-642-16170-4_25 . ISBN 9783642161704. S2CID 11732339 .

[:1-2] 1 2 3 4 Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013-01-01). "Verdad, justicia y cortar el pastel" (PDF) . Games and Economic Behavior . 77 (1): 284– 297. doi : 10.1016/j.geb.2012.10.009 . ISSN 0899-8256 . S2CID 2096977 .

[:5-3] 1 2 3 Brânzei, Simina; Miltersen, Peter Bro (2015-06-22). "Un teorema de dictadura para cortar pasteles" . Vigésimo cuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial .

[:6-4] 1 2 3 4 Aziz, Haris; Ye, Chun (2014). "Algoritmos de corte de pastel para valoraciones constantes y uniformes por partes". En Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Economía de la Web e Internet – 10.ª Conferencia Internacional, WINE 2014, Pekín, China, 14-17 de diciembre de 2014. Actas . Lecture Notes in Computer Science. Vol. 8877. Springer. pp. 1-14 . arXiv : 1307.2908 . doi : 10.1007/978-3-319-13129-0_1 . ISBN 978-3-319-13128-3.

[5] Kurokawa, David; Lai, John K.; Procaccia, Ariel D. (30 de junio de 2013). "Cómo cortar un pastel antes de que termine la fiesta" . Vigésimo séptima Conferencia AAAI sobre Inteligencia Artificial . 27 : 555–561 . doi : 10.1609/aaai.v27i1.8629 . S2CID 12638556 .

[6] Menon, Vijay; Larson, Kate (2017-05-17). "Deterministic, Strategyproof, and Fair Cake Cutting". arXiv : 1705.06306 [ cs.GT ].

[:42-7] 1 2 3 Bei, Xiaohui; Chen, Ning; Huzhang, Guangda; Tao, Biaoshuai; Wu, Jiajun (2017). "Cortando el pastel: envidia y verdad" . Actas de la 26.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'17. AAAI Press: 3625–3631 . ISBN 9780999241103.

[:44-8] 1 2 3 Tao, Biaoshuai (13 de julio de 2022). "Sobre la existencia de mecanismos veraces y justos para el reparto de pasteles" . Actas de la 23.ª Conferencia ACM sobre Economía y Computación . págs. 404–434 . arXiv : 2104.07387 . doi : 10.1145/3490486.3538321 . ISBN 9781450391504. S2CID 233241229 .

[9] Bu, Xiaolin; Song, Jiaxin; Tao, Biaoshuai (2023-06-01). "Sobre la existencia de mecanismos veraces y justos para cortar pasteles" . Inteligencia Artificial . 319 103904. arXiv : 2104.07387 . doi : 10.1016/j.artint.2023.103904 . ISSN 0004-3702 .

[:2-10] Maya, Avishay; Nisan, Noam (2012). "Reparto de pastel para dos jugadores con incentivos compatibles". En Goldberg, Paul W. (ed.). Economía de Internet y redes: 8.º Taller Internacional, WINE 2012, Liverpool, Reino Unido, 10-12 de diciembre de 2012. Actas . Lecture Notes in Computer Science. Vol. 7695. Springer. pp. 170-183 . arXiv : 1210.0155 . doi : 10.1007/978-3-642-35311 & minus ; 6_13 (inactivo el 7 de septiembre de 2025) . ISBN 9783642353116. S2CID 1927798 . {{cite conference}}: CS1 maint: DOI inactivo desde septiembre de 2025 ( enlace )

[11] Li, Minming; Zhang, Jialin; Zhang, Qiang (22 de junio de 2015). "Mecanismos veraces para cortar pasteles con externalidades: ¡No los haga preocuparse demasiado por los demás!" . Vigésimo cuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial .

[:7-12] 1 2 Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tayiko, Ahmad S. (10 de febrero de 2017). «Mecanismos sin envidia y con un número mínimo de cortes» . Trigésima Primera Conferencia AAAI sobre Inteligencia Artificial . 31 . doi : 10.1609/aaai.v31i1.10584 . S2CID 789550 .

[:3-13] 1 2 3 Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (2020). "División justa y veraz sin libre disposición" . Elección social y bienestar . 55 (3): 523– 545. arXiv : 1804.06923 . doi : 10.1007/s00355-020-01256-0 . PMC 7497335. PMID 33005068 .

[14] Ianovski, Egor (2012-03-01). "Mecanismos de corte de pasteles". arXiv : 1203.0100 [ cs.GT ].

[15] PWC = constante por partes, PWU = uniforme por partes, PWU1 = uniforme por partes con un único intervalo deseado.

[16] Si el algoritmo también puede manejar pasteles con utilidades negativas (tareas).

[17] Si se divide todo el pastel, sin desperdiciar nada.

[18] Si la asignación resultante es siempre óptima de Pareto .

[19] Si la asignación resultante siempre está libre de envidia .

[20] Si el mecanismo es anónimo .

[21] Si las piezas resultantes están siempre conectadas.

[22] Si el mecanismo es independiente de la posición .

[23] Si el algoritmo garantiza que no haya desperdicio.

[24] El tiempo de ejecución está dominado por el cálculo de una división exacta . En general, es ilimitado, pero en casos especiales puede ser polinomial.

[ 5 ]

[ 6 ]

[ 9 ]

[ 11 ]

[ 14 ]