Modelo de consulta de Robertson-Webb

Modelo de cálculo utilizado por los algoritmos

En informática , el modelo de consulta Robertson-Webb (RW) es un modelo de cálculo utilizado por algoritmos para el problema del corte justo de la tarta . En este problema, hay un recurso llamado "tarta" y varios agentes con diferentes medidas de valor en la tarta. El objetivo es dividir la tarta entre los agentes de modo que cada agente considere su trozo como "justo" según su medida de valor personal. Dado que las valoraciones de los agentes pueden ser muy complejas, no pueden -en general- proporcionarse como entradas a un algoritmo de división justa. El modelo RW especifica dos tipos de consultas que un algoritmo de división justa puede realizar a los agentes: Eval y Cut . De manera informal, una consulta Eval solicita a un agente que especifique su valor para un trozo dado de la tarta, y una consulta Cut (también llamada consulta Mark ) solicita a un agente que especifique un trozo de tarta con un valor dado.

A pesar de la simplicidad del modelo, muchos algoritmos clásicos de corte de torta se pueden describir solo con estas dos consultas. Por otro lado, hay problemas de corte de torta que es demostrable que no se pueden resolver en el modelo RW utilizando un número finito de consultas.

Las consultas Eval y Cut se describieron por primera vez en el libro de Jack M. Robertson y William A. Webb. ^[1] El nombre "modelo Robertson-Webb" fue acuñado y formalizado por Woeginger y Sgall. ^[2]

Definiciones

El modelo RW estándar supone que la torta es un intervalo, normalmente el intervalo [0,1]. Hay n agentes y cada agente i tiene una medida de valor v _i en la torta. El algoritmo no conoce v _i , pero puede acceder a ella mediante dos tipos de consultas:

• Una consulta de evaluación : dados dos números reales x e y , Eval _i ( x , y ) pide al agente i que informe el valor del intervalo [ x , y ], es decir, v _i ([ x , y ]).
• Una consulta de marca (también llamada consulta de corte ): dados dos números reales x y r, Mark _i ( x , r ) le pide al agente i que informe algún valor y tal que v _i ([ x , y ]) = r .

Ejemplo

El clásico algoritmo Divide y elige , para dividir un pastel entre dos niños, se puede realizar utilizando cuatro consultas.

• Pregúntele a Alice una consulta Eval(0,1); sea V ₁ la respuesta (este es el valor de Alice de todo el pastel).
• Pregúntele a Alice una consulta Mark(0, V ₁ / 2); sea x ₁ la respuesta (esta es la marca de Alice que da como resultado dos piezas iguales a sus ojos).
• Pregúntele a George una consulta Eval(0, x ₁ ) y una Eval( x ₁ , 1).
• Si el valor anterior es mayor, dale (0, x ₁ ) a George y ( x ₁ ,1) a Alice; de ​​lo contrario, dale (0, x ₁ ) a Alice y ( x ₁ ,1) a George.

Resultados

Además de dividir y elegir, se pueden realizar muchos algoritmos de división de tortas utilizando consultas RW cuyo número es polinomial en n (el número de agentes). Por ejemplo: el último disminuidor se puede realizar mediante consultas RW O( n ² ) y el protocolo Even–Paz se puede realizar mediante consultas RW O( n log n ). En paralelo, hay muchos resultados de dureza que prueban que ciertos problemas de división justa requieren muchas consultas RW para completarse. Algunos de estos resultados de dureza se muestran a continuación.

El corte de pastel proporcional requiere Ω( n log n ) consultas RW cuando

• Las piezas deben estar conectadas, ^[2] o
• el protocolo es determinista, ^[3] o
• La precisión del corte del pastel es finita. ^[3]
• El único protocolo que utiliza consultas O( n ) RW es un protocolo aleatorio, que puede devolver piezas desconectadas, y la asignación puede ser solo fraccionalmente proporcional.

El reparto proporcional de los resultados con diferentes derechos requiere al menos Ω( n log( D )) consultas RW, donde D es el denominador común de los derechos (en particular, no se puede encontrar utilizando un número limitado de consultas si los derechos son irracionales). Hay un algoritmo que utiliza O( n log( D )) consultas RW para derechos racionales y un algoritmo finito para derechos irracionales. ^[4]

Para cortar un pastel sin envidia es necesario

• Ω( n ² ) RW consulta cuándo se pueden desconectar las piezas, ^[5]
• Un número infinito de consultas cuando las piezas deben estar conectadas y hay al menos 3 agentes. ^[6] En otras palabras, no existe un algoritmo que siempre encuentre una asignación libre de envidia entre 3 o más agentes utilizando un número finito de consultas RW.
• Para cualquier ε > 0, un corte de pastel conectado sin envidia ε requiere al menos Ω(log ε ⁻¹ ) consultas. ^[7] Para 3 agentes, existe un protocolo O(log ε ⁻¹ ). Para 4 agentes, existe un protocolo O(poly(log ε ^{−1 )). [8]} Para 5 o más agentes, el protocolo más conocido requiere O( n ε ⁻¹ ), lo que muestra una brecha exponencial en la complejidad de la consulta.

No es posible realizar un reparto equitativo de los resultados ^{utilizando un número finito de consultas RW, incluso para 2 agentes. [9]} Además, para cualquier ε > 0:

• Un corte de torta ε-equitativo conectado requiere al menos Ω(log ε ⁻¹ ) consultas. ^[7] Para 2 agentes, existe un protocolo O(log ε ^{−1 ). [10]} Para 3 o más agentes, el protocolo más conocido requiere O( n (log n + log ε ⁻¹ )) consultas. ^[11]
• Incluso sin conectividad, el corte de pastel ε-equitativo requiere al menos Ω(log ε ⁻¹ / log log ε ⁻¹ ) consultas RW. ^[9]

No es posible realizar un corte exacto de la torta (también conocido como corte perfecto de la torta ) utilizando un número finito de consultas RW, ni siquiera para 2 agentes. Además, para cualquier ε > 0:

• Un corte de torta ε-perfecto con el mínimo número posible de cortes requiere al menos Ω(log ε ⁻¹ ) consultas. Para 2 agentes, existe un protocolo O(log ε ^{−1 ). [7]} Para 3 o más agentes, el protocolo más conocido requiere O( n ³ ε ⁻¹ ) consultas. ^[12]

El corte de torta con la máxima participación , cuando las piezas deben estar separadas por una distancia positiva, no se puede realizar utilizando un número finito de consultas RW. Además, incluso para un solo agente, no existe un algoritmo que calcule la participación máxima del agente utilizando un número finito de consultas RW. Sin embargo: ^[13]

• Para cualquier ε > 0, es posible calcular un valor entre el MMS y el MMS-ε utilizando consultas RW O( n log ε ^{−1 ).}
• Cuando la torta es circular (es decir, en un corte de torta justo ), es posible calcular un valor entre el MMS y el MMS-ε utilizando consultas de RW O( n ε ⁻¹ ). No está claro si las consultas de RW O( n log ε ⁻¹ ) son suficientes.

El reparto proporcional promedio (es decir, una asignación entre n familias , de modo que para cada familia, el valor promedio sea al menos 1/ n del total) no se puede calcular utilizando un número finito de consultas RW, incluso cuando hay 2 familias con 2 miembros en cada familia. La prueba es mediante reducción a partir del reparto equitativo de la torta. ^[14]

Variantes

Marca izquierda y marca derecha

Cuando la medida de valor de un agente no es estrictamente positiva (es decir, hay partes que el agente valora en 0), una consulta de marca puede, en principio, devolver una cantidad infinita de valores. Por ejemplo, si un agente valora [0,0.9] en 1 y [0.9,1] en 0, entonces la consulta Mark(0,1) puede devolver cualquier valor entre 0.9 y 1. Algunos algoritmos requieren un valor más específico:

• La consulta de marca izquierda, LeftMark( x , r ), devuelve la y más a la izquierda (la más pequeña) tal que v _i ([ x , y ]) = r ;
• La consulta de marca derecha, RightMark( x , r ), devuelve la y más a la derecha (la más grande) tal que v _i ([ x , y ]) = r ;

Si sólo se proporciona una de estas dos variantes (además de la consulta Eval), la otra variante no se puede calcular en tiempo finito. ^[11]

Tortas bidimensionales

El modelo de consulta RW se ha generalizado a pasteles bidimensionales ^[15] y pasteles multidimensionales. ^[16]

Modelos alternativos

Existen muchos algoritmos de corte de torta que no utilizan el modelo RW. Por lo general, utilizan uno de los siguientes modelos.

Modelo de revelación directa

Algoritmos para clases restringidas de valoraciones, como por ejemplo lineal por partes, constante por partes o uniforme por partes, que pueden proporcionarse explícitamente como entrada al algoritmo. Algunos de estos algoritmos se desarrollaron para realizar un corte de pastel veraz .

Modelo de cuchilla móvil

En este modelo, hay cuchillos que se mueven continuamente a lo largo de la torta (ver procedimientos de cuchillos móviles ). Este modelo está relacionado con el modelo RW de la siguiente manera: cualquier procedimiento de cuchillo móvil con una cantidad fija de agentes y una cantidad fija de cuchillos se puede simular utilizando consultas RW de O(log ε ^{−1 ). [7]}

Modelo de consultas simultáneas

En este modelo, los agentes envían simultáneamente discretizaciones de sus preferencias. Una discretización es una secuencia de puntos de corte y los valores de las partes entre estos puntos de corte (por ejemplo: un protocolo para dos agentes podría requerir que cada agente informe una secuencia de tres puntos de corte (0, x ,1) donde los valores de (0, x ) y ( x ,1) son 1/2). Estos informes se utilizan para calcular una asignación justa. La complejidad de un algoritmo en este modelo se define como el número máximo de intervalos en una discretización requerida (por lo que la complejidad del protocolo anterior es 2).

Una ventaja de este modelo sobre el modelo RW es que permite obtener preferencias en paralelo. Esto permite calcular un corte de torta proporcional en el tiempo O( n ) al pedir simultáneamente a cada agente una discretización con n intervalos (de igual valor). En contraste, en el modelo RW hay un límite inferior O( n log n ). Por otro lado, en el modelo simultáneo, es imposible calcular un corte de torta sin envidia usando una discretización finita para 3 o más agentes; pero para cada e > 0, existe un protocolo simultáneo con complejidad O( n / e ² ), que logra una división sin envidia aproximada a e . ^[17]

Véase también

• Oráculo de demanda (y oráculo de valor ): un modelo de consulta similar en un entorno con objetos indivisibles.

Referencias

1. 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.
2. Gerhard J. Woeginger y Jiri Sgall (2007). "Sobre la complejidad del corte de torta". Optimización discreta . 4 (2): 213–220. doi : 10.1016/j.disopt.2006.07.003 .
3. Edmonds, Jeff (2006). "Cortar la torta no es realmente tarea fácil". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06 . págs. 271–278. CiteSeerX 10.1.1.412.7166 . doi :10.1145/1109557.1109588. ISBN  978-0898716054., Edmonds, Jeff (2011). "Cortar la torta no es realmente tarea fácil". ACM Transactions on Algorithms . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi :10.1145/2000807.2000819. S2CID  2440968. 
4. Cseh, Ágnes; Fleiner, Tamás (1 de junio de 2020). "La complejidad de cortar la torta con porciones desiguales". ACM Transactions on Algorithms . 16 (3): 29:1–29:21. arXiv : 1709.03152 . doi :10.1145/3380742. ISSN  1549-6325. S2CID  218517351.
5. Procaccia, Ariel (2009). "Codiciarás el pastel de tu vecino". Actas de la 21.ª Conferencia conjunta internacional sobre inteligencia artificial IJCAI'09 : 239–244.
6. Stromquist, Walter (2008). "Las divisiones de tortas sin envidia no se pueden encontrar mediante protocolos finitos" (PDF) . Revista electrónica de combinatoria . 15 . doi : 10.37236/735 .
7. Brânzei, Simina; Nisan, Noam (13 de julio de 2018). "La complejidad de la consulta del corte de pastel". arXiv : 1705.02946 [cs.GT].
8. Hollender, Alexandros; Rubinstein, Aviad (2023). Corte de pastel sin envidia para cuatro agentes. págs. 113–122. arXiv : 2311.02075 . doi :10.1109/FOCS57990.2023.00015. ISBN 979-8-3503-1894-4. Recuperado el 4 de enero de 2024 .
9. Procaccia, Ariel D.; Wang, Junxing (20 de junio de 2017). "Un límite inferior para un reparto equitativo de los gastos". Actas de la Conferencia ACM de 2017 sobre economía y computación . EC '17. Cambridge, Massachusetts, EE. UU.: Association for Computing Machinery. págs. 479–495. doi :10.1145/3033274.3085107. ISBN 978-1-4503-4527-9.S2CID 9834718  .
10. Cechlárová, Katarína; Pillárová, Eva (2012). "Un algoritmo de corte de pasteles para dos personas casi equitativo". Optimización . 61 (11): 1321. doi : 10.1080/02331934.2011.563306. S2CID  120300612.
11. Cechlárová, Katarína; Pillárová, Eva (1 de noviembre de 2012). "Sobre la computabilidad de las divisiones equitativas". Optimización discreta . 9 (4): 249–257. doi : 10.1016/j.disopt.2012.08.001 . ISSN  1572-5286.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
12. Brânzei, Simina; Miltersen, Peter Bro (25 de julio de 2015). "Un teorema de dictadura para cortar la torta". Actas de la 24.ª Conferencia Internacional sobre Inteligencia Artificial . IJCAI'15. Buenos Aires, Argentina: AAAI Press: 482–488. ISBN 978-1-57735-738-4.
13. Elkind, Edith; Segal-Halevi, Erel; Suksompong, Warut (2022). "Cuidado con el espacio: corte de pastel con separación". Inteligencia artificial . 313 : 103783. arXiv : 2012.06682 . doi :10.1016/j.artint.2022.103783. S2CID  229153490.
14. 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.
15. Segal-Halevi, Erel; Nitzan, Shmuel; Jasidim, Avinatan; Aumann, Yonatan (2017). "Justo y limpio: corte de tartas en dos dimensiones". Revista de Economía Matemática . 70 : 1–28. arXiv : 1409.4511 . doi :10.1016/j.jmateco.2017.01.007. S2CID  1278209.
16. Cseh, Ágnes; Fleiner, Tamás (2018), "La complejidad de cortar la torta con porciones desiguales", Teoría de juegos algorítmica , Springer International Publishing, págs. 19-30, arXiv : 1709.03152 , doi :10.1007/978-3-319-99660-8_3, ISBN 9783319996592, Número de identificación del sujeto  19245769
17. Balkanski, Eric; Brânzei, Simina; Kurokawa, David; Procaccia, Ariel (21 de junio de 2014). "Corte simultáneo de la torta". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). doi : 10.1609/aaai.v28i1.8802 . ISSN  2374-3468. S2CID  1867115.