El corte de tarta veraz es el estudio de algoritmos para el corte de tarta justo que también son mecanismos veraces , es decir, incentivan a los participantes a revelar sus verdaderas valoraciones a las distintas partes del pastel.
El procedimiento clásico de dividir y elegir para cortar pasteles no es veraz: si el cortador conoce las preferencias del seleccionador, puede obtener mucho más de la mitad actuando estratégicamente. Por ejemplo, supongamos que el cortador valora una pieza por su tamaño mientras que el selector valora una pieza por la cantidad de chocolate que contiene. Entonces el cortador puede cortar el pastel en dos trozos con casi la misma cantidad de chocolate, de modo que el trozo más pequeño tenga un poco más de chocolate. Luego, el selector tomará el trozo más pequeño y el cortador ganará el trozo más grande, que puede valer mucho más de la mitad (dependiendo de cómo se distribuya el chocolate).
Mecanismos aleatorizados
Hay un mecanismo veraz aleatorio trivial para cortar el pastel de manera justa : seleccione un solo agente uniformemente al azar y entréguele todo el pastel. Este mecanismo es trivialmente veraz porque no hace preguntas. Además, la expectativa es justa: el valor esperado de cada socio es exactamente 1 / n . Sin embargo, la asignación resultante no es justa. El desafío es desarrollar mecanismos veraces que sean justos ex post y no solo ex ante. Se han desarrollado varios de estos mecanismos.
Mecanismo de división exacta
Una división exacta (también conocida como división de consenso ) es una partición del pastel en n trozos de modo que cada agente valora cada trozo 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áximocortes este es un corolario del teorema de Stromquist-Woodall y del teorema de la división del collar .
En general, no se puede encontrar una división exacta mediante un algoritmo finito. Sin embargo, se puede encontrar en algunos casos especiales, por ejemplo, cuando todos los agentes tienen valoraciones lineales por partes. Supongamos que tenemos un algoritmo (u oráculo) no veraz para encontrar una división exacta. Se puede utilizar para construir un mecanismo aleatorio que sea veraz en las expectativas. [1] [2] El mecanismo aleatorio es un mecanismo de revelación directa : comienza pidiendo a todos los agentes que revelen todas sus medidas de valor:
- Pida a los agentes que informen sobre sus medidas de valor.
- Utilice el algoritmo / oráculo existente para generar una división exacta.
- Realice una permutación aleatoria en la partición de consenso y entregue a cada socio una de las piezas.
Aquí, el valor esperado de cada agente es siempre 1 / n independientemente de la función de valor informado. Por lo tanto, el mecanismo es veraz: ningún agente 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 tanto, los socios tienen un incentivo para revelar sus verdaderas funciones de valor.
Mecanismo superproporcional
Una división superproporcional es una división de torta en la que cada agente recibe estrictamente más de 1 / n según sus propias medidas de valor. Se sabe que existe tal división si y solo si hay al menos dos agentes que tienen valoraciones diferentes para al menos una parte del pastel. Cualquier mecanismo determinista que siempre devuelva una división proporcional y siempre devuelva una división superproporcional cuando existe, no puede ser veraz.
Mossel y Tamuz presentan un mecanismo aleatorio superproporcional cuya expectativa es veraz: [1]
- Elija una división de una determinada distribución D sobre divisiones.
- Pídale a cada agente que evalúe su trabajo.
- Si todas las n evaluaciones son más de 1 / n , 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 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 real: informar un valor más bajo no tiene ningún efecto o puede hacer que el valor del agente caiga de superproporcional a simplemente proporcional (en el paso 4); informar un valor más alto no tiene ningún efecto o puede hacer que el valor del agente caiga de proporcional a menos de 1 / n (en el paso 3).
División exacta aproximada mediante consultas
Suponga que, en lugar de revelar directamente sus valoraciones, los agentes revelan sus valores indirectamente respondiendo a las consultas mark y eval (como en el modelo de Robertson-Webb).
Branzei y Miltersen [3] muestran que el mecanismo de división exacta se puede "discretizar" y ejecutar en el modelo de consulta. Esto produce, para cualquier, un protocolo basado en consultas aleatorias , que pregunta como máximo consultas, es veraz en expectativa y asigna a cada agente una pieza de valor entre y , por las valoraciones de todos los agentes.
Por otro lado, demuestran que, en cualquier protocolo determinista y veraz basado en consultas, si todos los agentes valoran positivamente todas las partes del pastel, hay al menos un agente que obtiene la pieza vacía. Esto implica que, si solo hay dos agentes, entonces al menos un agente es un "dictador" y se lleva todo el pastel. Obviamente, cualquier mecanismo de este tipo no puede estar exento de envidia.
Mecanismo aleatorio para valoraciones constantes por partes
Suponga que todos los agentes tienen valoraciones constantes por partes . Esto significa que, para cada agente, la torta 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, robusta proporcional y satisface una propiedad llamada unanimidad : si la longitud 1 / n del pastel más preferida de cada agente es disjunta de otros agentes, cada agente obtiene su longitud 1 / n de torta más preferida . Ésta es una forma débil de eficiencia que no se satisface con los mecanismos basados en la división exacta. Cuando solo hay dos agentes, también es de tiempo polinomial y robusto sin envidia. [4]
Mecanismos deterministas: valoraciones constantes a trozos
Para los mecanismos deterministas , los resultados son en su mayoría negativos, incluso cuando todos los agentes tienen valoraciones constantes por partes.
Kurokawa, Lai y Procaccia demuestran que no existe un mecanismo determinista, veraz y libre de envidia que requiera un número limitado de consultas de Robertson-Webb. [5]
Aziz y Ye prueban que no existe un mecanismo verdadero determinista que satisfaga una 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 quiera; es más débil que el óptimo de Pareto).
Menon y Larson introducen la noción de veracidad ε , lo que significa que ningún agente gana más de una fracción ε de la información errónea, 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]
- ε -verdadero, aproximadamente proporcional y sin desperdicio (para constantes de aproximación como máximo 1 / n );
- Veraz, aproximadamente proporcional y conectado (para aproximación constante como máximo 1 / n ).
Presentan una pequeña modificación al protocolo Even-Paz y prueban que es ε -verdadero con ε = 1-3 / (2 n ) cuando n es par, y ε = 1-3 / (2 n ) + 1 / n 2 cuando n es impar.
Bei, Chen, Huzhang, Tao y Wu prueban que no existe un mecanismo determinista, veraz y libre de envidia, incluso en el modelo de revelación directa, que satisfaga cualquiera de las siguientes propiedades adicionales: [7]
- Piezas conectadas;
- No derrocha;
- Posición inconsciente: la asignación de una parte del pastel se basa solo en las valoraciones de los agentes de esa parte, y no en su posición relativa en el pastel.
Tenga en cuenta que estos resultados de imposibilidad se mantienen con o sin eliminación gratuita.
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, la verdad converge a un equilibrio de Nash cuando k se acerca al infinito;
- Sin el 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.
Valoraciones uniformes por partes
Suponga que todos los agentes tienen valoraciones uniformes por partes . Esto significa que, para cada agente, hay un subconjunto de la torta que es deseable para el agente, y el valor del agente para cada pieza es solo la cantidad de torta deseable que contiene. Por ejemplo, suponga que algunas partes del pastel están cubiertas por una capa uniforme de chocolate, mientras que otras no. Un agente que valora cada pieza solo 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 tiempo polinómico. [2] Funciona para cualquier número de agentes. A continuación se muestra una ilustración del mecanismo CLPP para dos agentes (donde el pastel es un intervalo).
- Pídale a cada agente que informe sus intervalos deseados.
- Se descarta cada subintervalo que ningún agente desea.
- Cada subintervalo, deseado por exactamente un agente, se asigna a ese agente.
- Los subintervalos, que son deseados por ambos agentes, se asignan de manera que ambos agentes obtengan una longitud total igual .
Ahora, si un agente dice que quiere un intervalo que en realidad no quiere, entonces puede obtener un pastel más inútil en el paso 3 y un pastel menos útil en el paso 4. Si dice que no quiere un intervalo que realmente quiere , entonces obtiene una torta menos útil en el paso 3 y más útil en el paso 4, sin embargo, la cantidad dada en el paso 4 se comparte con el otro agente, por lo que, en general, el agente mentiroso está perdido. El mecanismo se puede generalizar a cualquier número de agentes.
El mecanismo CLPP se basa en el supuesto de libre disposición , es decir, la capacidad de descartar piezas que ningún agente desea.
Nota : Aziz y Ye [4] presentaron dos mecanismos que extienden el mecanismo CLPP a valoraciones constantes por partes: algoritmo de consumo de torta restringido y algoritmo de equilibrio de mercado. Sin embargo, estas dos extensiones ya no son veraces cuando las valoraciones no son uniformes por partes.
Maya y Nisan muestran que el mecanismo CLPP es único en el siguiente sentido. [8] Considere 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 algunos a <1, y Bob solo desea el subintervalo [1 - b , 1] para algunos b <1. Considere solo los mecanismos que no generan desperdicio : mecanismos que asignan cada pieza deseada por al menos un jugador a un jugador que la quiere. Cada uno de estos mecanismos debe dar a Alice un subconjunto [0, c ] para algunos c <1 y Bob un subconjunto [1- d , 1] para algunos d <1. En este modelo:
- Un mecanismo determinístico que no genera desperdicio es verdadero 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]
- Tal mecanismo está libre de envidia si f t = 1/2 ; en este caso es equivalente al mecanismo CLPP
También muestran que, incluso para 2 agentes, cualquier mecanismo veraz alcanza como máximo 0,93 del bienestar social óptimo.
Li, Zhang y Zhang muestran que el mecanismo CLPP funciona bien incluso cuando hay externalidades (es decir, algunos agentes obtienen algún beneficio del valor que se les da a otros), siempre que las externalidades sean lo suficientemente pequeñas. Por otro lado, si las externalidades (positivas o negativas) son grandes, no existe ningún mecanismo veraz que no genere desperdicio y que sea independiente de la posición. [9]
Alijani, Farhadi, Ghodsi, Seddighin y Tajik presentan varios mecanismos para casos especiales de valoraciones uniformes por partes: [10]
- El proceso de expansión maneja valoraciones uniformes por partes en las que cada agente tiene un único intervalo deseado y, además, los intervalos deseados de los agentes satisfacen una propiedad de pedido . Es polinomial-temporal, veraz, sin 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 pedido. Es de tiempo polinomial, veraz, sin envidia y no necesariamente conectado, pero hace como máximo 2 n -2 cortes.
Bei, Huzhang y Suksompong presentan un mecanismo para dos agentes con valoraciones uniformes por partes, que tiene las mismas propiedades de CLPP (veraz, determinista, proporcional, sin envidia, óptimo de Pareto y se ejecuta en tiempo polinomial), pero garantiza que la totalidad pastel se asigna: [11]
- Encuentre la x más pequeña en [0,1] tal que la longitud deseada de Alice en [0, x ] sea igual a la longitud deseada de Bob en [ x , 1].
- Dale a Alice los intervalos en [0, x ] valorados por Alice y los intervalos en [ x , 1] no valorados por Bob; dale el resto a Bob.
El mecanismo BHS funciona tanto para el corte de pasteles como para la división de tareas (donde las valoraciones de los agentes son negativas). Tenga en cuenta que BHS no satisface algunas propiedades naturales deseables:
- 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 corte de pastel simétrico justo ) : si Alice quiere [0,1] y Bob quiere [0,0.5], Alice obtiene una longitud deseada de 0.75 y Bob obtiene 0.25, pero si se cambian 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 la posición ajena : si Alice quiere [0,0.5] y Bob quiere [0,1] entonces ambos agentes obtienen el valor 0.5, pero si el intervalo deseado de 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 sin envidias que asigne todo el pastel y garantice cualquiera de estas tres propiedades, incluso para dos agentes con valoraciones uniformes por partes. [11]
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 [12] demuestra que ningún mecanismo veraz puede lograr un corte de torta óptimo utilitario , incluso cuando todos los agentes tienen valoraciones uniformes por partes. Además, ningún mecanismo veraz puede lograr una asignación con un bienestar utilitario al menos tan grande como cualquier otro mecanismo. Sin embargo, existe un mecanismo simple y veraz (denominado Orden Lex) que no genera desperdicio : entregue al agente 1 todas las piezas que le gusten; luego, entregue al agente 2 todas las piezas que le gusten y que aún no le hayan sido entregadas al agente 1; etc. Una variante de este mecanismo es el Juego de duración, en el que los agentes se renombran por la duración 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, se produce una asignación utilitaria óptima.
- Si los agentes son estratégicos, entonces todos sus equilibrios de Nash de buen comportamiento son Pareto-eficientes y libres de envidia, y producen los mismos beneficios que el mecanismo CLPP.
Resumen de mecanismos veraces y resultados de imposibilidad
Nombre | Tipo | Determinista? | #agentes ( n ) | Valoraciones [13] | ¿Tareas? [14] | Tiempo de ejecución | ¿Todas? [15] | ¿CORREOS? [dieciséis] | EF? [17] | ¿Luego? [18] | Conn? [19] | Pos.Ob.? [20] | ¿Sin desperdicio? [21] |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
División exacta [1] [2] | Directo | No | Muchos | General | sí | Ilimitado [22] | sí | No | sí | sí | No | ? | ? |
Superproporcional [1] | Directo | No | Muchos | General | sí | Ilimitado | sí | No | No | sí | No | ? | ? |
División exacta discreta [3] | Consultas | No | Muchos | General | sí | sí | No | -EF | sí | No | ? | ? | |
Dictadura en serie restringida [4] | Directo | No | Muchos | PWC | ? | ? | No | Unanimidad | Apuntalar. | ? | No | ? | ? |
CLPP [2] | Directo | sí | Muchos | PWU | No | Polinomio | No | sí | sí | sí | No | ? | sí |
BHS 1, 2 | Directo | sí | 2 | PWU | sí | Polinomio | sí | sí | sí | No | No | No | sí |
BHS 3, 4 | Directo | sí | Muchos | PWU1 | sí | Polinomio | sí | sí | Si (para pasteles) | ? | ? | ? | sí |
Expansión [10] | Directo | sí | Muchos | PWU1 + pedido | ? | Polinomio | ? | ? | sí | ? | sí | ? | ? |
Expansión + Desbloqueo | Directo | sí | Muchos | PWU1 | ? | Polinomio | ? | ? | sí | ? | 2 n -2 cortes | ? | ? |
COMBINACIONES IMPOSIBLES: | |||||||||||||
[BM] [3] | Consultas | sí | 2+ | Alguna | |||||||||
[ BHS] [11] | Directo | sí | 2+ | PWU | sí | sí | sí | ||||||
[ BHS] | Directo | sí | 2+ | PWU | sí | sí | sí | ||||||
[ BHS] | Directo | sí | 2+ | PWU | sí | sí | sí | ||||||
[BCHTW] [7] | Directo | sí | 2+ | PWC | sí | sí | |||||||
[BCHTW] | Directo | sí | 2+ | PWC | sí | sí | |||||||
[BCHTW] | Directo | sí | 2+ | PWC | sí | sí | |||||||
[BCHTW] | Secuencial | sí | 2+ | PWC | sí |
Ver también
- División ferial estratégica
- Asignación de recursos veraz
Referencias
- ^ a b c d Mossel, Elchanan; Tamuz, Omer (2010). "División justa veraz". Teoría algorítmica de juegos . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 6386 : 288-299. arXiv : 1003.5480 . Código bibliográfico : 2010LNCS.6386..288M . doi : 10.1007 / 978-3-642-16170-4_25 . ISBN 9783642161704.
- ^ a b c d Chen, Yiling; Lai, John K .; Parkes, David C .; Procaccia, Ariel D. (1 de enero de 2013). "Verdad, justicia y corte de pastel". Juegos y comportamiento económico . 77 (1): 284-297. doi : 10.1016 / j.geb.2012.10.009 . ISSN 0899-8256 .
- ^ a b c Brânzei, Simina; Miltersen, Peter Bro (22 de junio de 2015). "Un teorema de la dictadura para el corte de pasteles" . Vigésima Cuarta Conferencia Conjunta Internacional sobre Inteligencia Artificial .
- ^ a b c d Aziz, Haris; Ye, Chun (2014). Liu, Tie-Yan; Qi, Qi; Sí, Yinyu (eds.). "Algoritmos de corte de torta para valoraciones constantes por partes y uniformes por partes". Economía Web e Internet . Apuntes de conferencias en Ciencias de la Computación. Springer International Publishing. 8877 : 1–14. doi : 10.1007 / 978-3-319-13129-0_1 . ISBN 9783319131290.
- ^ 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éptimo Congreso AAAI sobre Inteligencia Artificial .
- ^ Menon, Vijay; Larson, Kate (17 de mayo de 2017). "Corte de pastel determinista, a prueba de estrategias y justo". arXiv : 1705.06306 [ cs.GT ].
- ^ a b c Bei, Xiaohui; Chen, Ning; Huzhang, Guangda; Tao, Biaoshuai; Wu, Jiajun (2017). "Cake Cutting: Envidia y Verdad" . Actas de la 26ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI'17. AAAI Press: 3625–3631. ISBN 9780999241103.
- ^ Maya, Avishay; Nisan, Noam (2012). Goldberg, Paul W. (ed.). "Corte de pastel para dos jugadores compatible con incentivos". Economía de Internet y redes . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 7695 : 170–183. arXiv : 1210.0155 . Código bibliográfico : 2012arXiv1210.0155M . doi : 10.1007 / 978-3-642-35311-6_13 . ISBN 9783642353116.
- ^ Li, Minming; Zhang, Jialin; Zhang, Qiang (22 de junio de 2015). "Mecanismos veraces para cortar pasteles con externalidades: ¡No haga que se preocupen demasiado por los demás!" . Vigésima Cuarta Conferencia Conjunta Internacional sobre Inteligencia Artificial .
- ^ a b Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tayiko, Ahmad S. (10 de febrero de 2017). "Mecanismos libres de envidia con un número mínimo de cortes" . Trigésima Primera Conferencia AAAI sobre Inteligencia Artificial .
- ^ a b c Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (2020). "Verdadera división justa 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 (1 de marzo de 2012). "Mecanismos de corte de tartas". 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 puede manejar también pasteles con utilidades negativas (tareas domésticas).
- ^ Si todo el pastel está dividido, sin desecharlo.
- ^ Si la asignación resultante es siempre óptima en el sentido de Pareto .
- ^ Si la asignación resultante siempre está libre de envidia .
- ^ Si el mecanismo es anónimo .
- ^ Si las piezas resultantes siempre están conectadas.
- ^ Si el mecanismo está ajeno a la posición .
- ^ Si el algoritmo garantiza la ausencia de despilfarro.
- ^ El tiempo de ejecución se domina calculando una división exacta . En general es ilimitado, pero en casos especiales puede ser polinomio.