Problema del restaurante Kolkata Paise

El Problema del Restaurante Paise de Calcuta (Problema KPR) es un juego matemático de asignación competitiva de recursos sin coordinación alguna. Su nombre proviene de los antaño comunes "Restaurantes Paise" de la ciudad india de Calcuta . Estos establecimientos, que funcionaron desde principios del siglo XX hasta la década de 1970, ofrecían comidas a precio fijo a precios extremadamente bajos (véase ^{[ 1 ]} para referencias a los pocos que aún existen; el paise es la denominación más pequeña de la rupia india). El problema KPR es un juego de anticoordinación que modela cómo un gran número de individuos (jugadores) compiten por recursos limitados sin comunicación ni coordinación directa.

El problema se vuelve trivial —y a la vez óptimamente eficiente— si interviene un coordinador o dictador que no participe en el juego . Con tan solo instruir a todos los jugadores para que formen una cola y visiten el restaurante que les corresponda en la fila el primer día, y luego roten al siguiente restaurante cada día subsiguiente (siguiendo condiciones límite periódicas ), se logra de inmediato la plena utilización de los recursos. Esto garantiza comida para todos los clientes, los máximos ingresos para todos los restaurantes y no requiere tiempo de aprendizaje ni de convergencia.

Sin embargo, la verdadera complejidad del problema surge cuando los individuos actúan de forma independiente, tomando decisiones basadas en experiencias personales de éxito o fracaso, o en información disponible sobre la afluencia de público en los restaurantes. En este entorno descentralizado, los jugadores buscan maximizar sus propias ganancias, lo que, a su vez, impulsa la utilización óptima y los ingresos a nivel del sistema, pero solo a través de un comportamiento emergente y autoorganizado.

El modelo KPR generaliza el problema del El Farol Bar (véase ^{[ 2 ]} para la formulación inicial), extendiéndolo de una elección binaria (ir o quedarse en casa) a múltiples opciones. Para trabajos fundamentales sobre KPR, véase ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]} y para algunas revisiones iniciales, véase ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]} . Cuando se reduce a dos jugadores, el juego se alinea con modelos clásicos de anticoordinación como el Juego del Pollo o el Juego del Halcón-Paloma. ^{[ 11 ]} Tamir ^{[ 10 ]} argumentó, siguiendo a Anderson "Más es diferente", ^{[ 12 ]} que esta extensión a un gran número de elecciones para todos los jugadores hace que el juego KPR sea mucho más complejo y apropiado para problemas de optimización descentralizados que los juegos de opciones/elecciones finitas. Para un estudio sobre la emergencia de la coordinación distribuida en el problema KPR con información finita, véase. ^{[ 13 ]} Algorítmicamente, KPR comparte rasgos con el algoritmo de Gale-Shapley en contextos de emparejamiento descentralizados. ^{[ 14 ]} Conexiones más amplias con el "Juego de Calcuta" o "Algoritmo de Calcuta" aparecen en estudios como Refs. ^{[ 15 ] [ 16 ]}

• Hay N restaurantes y λN jugadores (clientes potenciales); normalmente λ=1. N puede ser arbitrariamente grande. ^{[ 3 ]}
• Cada día, los clientes eligen un restaurante de forma independiente, basándose en su experiencia previa, ya sea positiva o negativa. Los jugadores desconocen las elecciones de los demás, pero tienen acceso al historial de selecciones anteriores.
• En cada restaurante, solo uno de los jugadores (clientes potenciales) que llega es elegido al azar y atendido (recompensa = 1). El resto de los que llegan a ese restaurante se van sin comida ese día (recompensa = 0; no queda tiempo ni dinero para otra búsqueda).
• El resultado ideal es una coordinación perfecta (como la que se logra en presencia de un dictador), donde cada jugador elige un restaurante diferente en un tiempo de convergencia nulo o muy corto. Sin embargo, esto se dificulta (en ausencia de intercambios de comunicación paralelos o de un dictador) en el juego KPR. Esto genera ineficiencias (algunos restaurantes solo pueden atender a una persona, otros están vacíos) o una utilización parcial. El objetivo de KPR es desarrollar algoritmos colectivos de "aprendizaje paralelo" para maximizar la fracción de utilización en el menor tiempo posible (preferiblemente menor que el orden de lnN).

En el problema KPR, las estrategias se evalúan en función de su recompensa agregada o la fracción de utilización. Para${\displaystyle \lambda =1}$Esto viene dado por la fracción promedio de restaurantes frecuentados o por la fracción promedio de agentes que obtienen comida en un día cualquiera.

En el caso de elección aleatoria del problema KPR, cada uno de los${\displaystyle \lambda N}$Los agentes seleccionan aleatoriamente uno de los${\displaystyle N}$restaurantes. La probabilidad${\displaystyle P(n)}$eso mismo${\displaystyle n}$Los agentes eligen el mismo restaurante:

${\displaystyle P(n)={\binom {\lambda N}{n}}p^{n}(1-p)^{\lambda Nn};\quad p={\frac {1}{N}}}$,

dando una distribución de Poisson en el límite${\displaystyle N\to \infty }$:

${\displaystyle P(n)={\frac {\lambda ^{n}}{n!}}\exp(-\lambda ).}$

La fracción de restaurantes no elegidos por ningún agente es entonces${\displaystyle P(n=0)=\exp(-\lambda )}$, lo que da como resultado una fracción de utilización igual a ^{[ 3 ]}${\displaystyle 1-\exp(-\lambda )}$Esto se vuelve igual a ${\displaystyle 1-\exp(-1)\approx 0.63}$para${\displaystyle \lambda =1}$Esto significa que aproximadamente el 63% de los restaurantes se utilizan o que aproximadamente el 63% de los agentes obtienen comida en cualquier día en este caso. El tiempo de convergencia es cero.

Para el caso de elección aleatoria discutido anteriormente, los agentes no tienen memoria ni emplean ninguna estrategia de aprendizaje. Una estrategia estocástica de aprendizaje mínimo, con fracción de utilización ~0,79, ^{[ 4 ]} otorga a cada cliente una probabilidad de elegir el mismo restaurante que el de ayer que varía inversamente con el tamaño de la multitud allí (número de jugadores que eligieron ese restaurante) ayer, mientras que elige entre los demás restaurantes con probabilidad uniforme. Este es un mejor resultado que el caso de elección aleatoria simple (o comerciante de ruido ) mencionado anteriormente , aunque el tiempo de convergencia parece crecer muy débilmente, tal vez logarítmicamente o incluso más débilmente, con${\displaystyle N}$^{[ 17 ] [ 18 ]} (véase también ^{[ 19 ]} ).

Kastampolidou, Papalitsas y Andronikos también han estudiado el aumento de la fracción de utilización para los clientes, cada uno con un presupuesto fijo bajo para la búsqueda local utilizando un algoritmo tipo Problema del viajante (TSP). ^{[ 20 ]} Empleando una estructura agrupada localmente (cuyo tamaño está determinado por la cantidad del pequeño presupuesto de viaje permitido para cada uno de los agentes aquí) de la distribución de restaurantes (que por supuesto es globalmente uniforme en toda la ciudad), cada agente puede visitar varios restaurantes para buscar de forma óptima uno vacío y obtener comida allí. Este enfoque es efectivamente equivalente a${\displaystyle N}$vendedores resolviendo cada uno un TSP local para completar la visita${\displaystyle N}$ciudades. Por supuesto, algunos agentes seguirán sin encontrar un restaurante vacío en su vecindario, debido al escaso presupuesto, y la plena utilización no será posible con ningún presupuesto limitado. Este enfoque ayuda a derivar una fórmula probabilística que conduce a una mayor tasa de utilización, lo que confirma su clara ventaja.

Existen estrategias sin un dictador externo (como las estrategias de casta y de toma de turnos) para lograr la plena utilización de los recursos si todos los jugadores tienen acceso a ordenaciones objetivas de jugadores y recursos. ^{[ 21 ]} En algunos casos, una norma social (por ejemplo, la ordenación alfabética) podría proporcionar dicha ordenación; en otros, la historia del juego la proporcionaría con el tiempo (por ejemplo, ordenar los recursos por popularidad y ordenar a los jugadores por ganancias, estimación de habilidad o clasificación de deuda).

Las extensiones del problema KPR para problemas de alquiler de coches a demanda (donde los restaurantes también tienen la opción de trasladarse a sus ubicaciones elegidas) se han explorado en ^{[ 22 ] y [ 23 ]} por Martin et al., y véase ^{[ 24 ]} para la solución de campo medio de un problema KPR generalizado en la misma competencia de recursos en entornos espaciales del mercado de vehículos de alquiler. Para un análisis detallado y una revisión sobre reubicaciones estratégicas de conductores para una mayor eficiencia de las plataformas de transporte bajo demanda en un contexto similar al KPR, véase ^{[ 25 ] .}

Para la aplicación del KPR a problemas de asignación optimizada de tareas en Internet de las Cosas, véase ^{[ 26 ]} de Park y Saad. También se ha estudiado la estabilidad del KPR, inducida por la introducción de clubes de comidas. ^{[ 27 ]} Para un estudio sobre el impacto de las opiniones de expertos (o incluso de creencias) en estrategias de búsqueda de recursos que evolucionan y compiten entre sí, véase [ ^{28 ] .}

Véase también ^{[ 29 ]} para la aplicación del modelo KPR al análisis antropológico y sociológico de los modelos de politeísmo, y para una aplicación algorítmica a la terapia del cáncer, véase ^{[ 30 ] .}

Se han estudiado extensiones a juegos cuánticos para KPR de tres jugadores, donde, si la dimensionalidad lo permite, cada jugador puede lograr una recompensa media mucho mayor. ^{[ 31 ] [ 32 ]} Para algunos estudios recientes en el contexto del juego KPR de tres jugadores sobre las ventajas de recompensas más altas en juegos cuánticos cuando el estado inicial está máximamente entrelazado, véase. ^{[ 33 ] [ 34 ] [ 35 ]} Véase ^{[ 10 ]} para una introducción general a la econofísica , la sociofísica , el KPR clásico, los juegos cuánticos y el KPR cuántico, y véase ^{[ 36 ]} para una revisión posterior sobre juegos KPR clásicos y cuánticos.

Se puede consultar ^{[ 37 ]} para un primer intento de explotar estrategias tipo KPR para el desarrollo de modelos de Inteligencia Artificial ( IA) . Para un estudio de enfoques tipo KPR relacionados con el problema de partición de grafos, véase ^{[ 38 ]} . Recientemente, el juego KPR se ha extendido (a juegos tipo Silla Musical) y se ha utilizado ^{[ 21 ]} para crear un nuevo punto de referencia para evaluar algoritmos de IA .

Torneos

El problema KPR se puede estudiar mediante torneos para establecer su estrategia de gran maestro, de forma similar a como se estudió el dilema del prisionero para descubrir/establecer estrategias de ojo por ojo , ojo por ojo generoso y determinante cero (etc.). ^{[ 39 ] [ 40 ] [ 41 ] [ 42 ]} El software de código abierto MAD Chairs crea un servidor otree como estándar para experimentos con sujetos humanos, ^{[ 43 ]} pero también permite que los torneos incluyan IA y estrategias codificadas para el problema KPR (y para el juego MAD Chairs, que difiere de KPR en que los restaurantes abarrotados, como los botes salvavidas, ^{[ 44 ]} no producen victorias). ^{[ 45 ]}

Ninguna estrategia tuvo un buen desempeño contra todas las demás en los torneos del Dilema del Prisionero de Axelrod, por lo que Axelrod las clasificó según las ganancias totales, ^{[ 39 ]} pero la estrategia del gran maestro para las clasificaciones del torneo KPR mostradas arriba es más clara: la estrategia de toma de turnos logra resultados altos y también ventaja sobre cada otra estrategia individual (o sobre la casta que tiene ventaja sobre otras estrategias) cuando las estrategias comparadas tienen poblaciones iguales, donde "ventaja" se refiere al resultado más bajo promedio menos el resultado más bajo promedio de la estrategia comparada. En otras palabras, ninguna coalición que compita contra la toma de turnos sería sostenible porque incluiría un miembro que racionalmente debería esperar mejorar sus resultados al desertar a la toma de turnos. Suponiendo que cada sociedad alienígena llegaría a la misma conclusión al realizar sus propios torneos, la toma de turnos es una base universal para la coordinación. Ordena los restaurantes por popularidad y a los clientes por deudas de favores que se deben entre sí, y cualquier jugador puede calcular estos independientemente a partir del historial de juego (la estrategia del gran maestro emplea la coordinación para romper empates, pero las situaciones realistas tienen historias ricas que hacen que los empates sean raros). ^{[ 21 ]}

El modelo KPR puede describir varios problemas de asignación de recursos de la vida real, tales como:

• Servicios de transporte bajo demanda: Los pasajeros de las empresas de transporte compartido y los taxistas compiten por los taxis solicitados , lo que a veces satura algunas zonas mientras que otras permanecen desocupadas, a menos que los gestores del servicio bajo demanda realicen una asignación dinámica adecuada (basada en la distribución prevista de la multitud o en los registros históricos de afluencia). ^{[ 22 ] [ 23 ] [ 25 ]}
• Acceso a recursos en línea: Los usuarios compiten por recursos informáticos limitados (por ejemplo, reserva de franjas horarias, asignación de ancho de banda , etc.). En este caso, la gestión informática necesita una asignación de tareas adecuada y dinámica, anticipándose/extrapolando a partir del tamaño de las tareas entrantes y de las colas , en el contexto del Internet de las Cosas . ^{[ 26 ]}
• Clubes gastronómicos en KPR: Donde los clubes pueden actuar como intermediarios (anticipándose a las elecciones) en nombre de los jugadores, quienes no están dispuestos a correr el riesgo de elegir un restaurante abarrotado y, por consiguiente, no conseguir comida. ^{[ 27 ] [ 11 ]}
• Evaluación comparativa de IA : Algoritmos que optimizan la utilización descentralizada de recursos generados empleando estrategias inspiradas en KPR. ^{[ 14 ] [ 15 ] [ 16 ] [ 21 ]}

Comenzamos con un ejemplo sencillo de un juego cuántico que demuestra el uso del entrelazamiento cuántico en la definición de la estrategia del juego. La configuración fue introducida por Cluse, Horn, Shimony y Holt ^{[ 46 ]} en el contexto de la teoría de variables ocultas, y posteriormente se convirtió en un ejemplo prototipo en la teoría de juegos cuánticos. ^{[ 47 ]} El "juego" también se utilizó como prueba de cuántica en el contexto de las computadoras cuánticas. ^{[ 48 ]}

Consideremos un juego en el que a Alice y Bob se les hace una pregunta de sí o no. Hay 4 pares de preguntas posibles: (C,C), (C,D), (D,C) o (D,D), que se eligen aleatoriamente. En la pregunta (C,C), obtienen una recompensa de 1 por respuestas no correlacionadas (1,0) o (0,1), y en los demás casos, obtienen una recompensa de 1 por respuestas correlacionadas (1,1) o (0,0). El juego se repite. Alice y Bob no pueden comunicarse durante el juego, pero pueden acordar una estrategia de antemano. Podrían acordar responder siempre (1,1), lo que resultaría en un 75% de éxito. Alternativamente, podrían lanzar una moneda al aire, y es fácil demostrar que esta estrategia resultaría en un 50% de éxito. Supongamos ahora que comparten un estado de dos cúbits máximamente entrelazado:

${\displaystyle \rho ={\frac {1}{\sqrt {2}}}\left(|00\rangle +|11\rangle \right)}$.

Defina el operador unitario local:

${\displaystyle U(\theta )=\left({\begin{matrix}\cos \theta &\sin \theta \\-\sin \theta &\cos \theta \end{matrix}}\right)}$

Alice y Bob pueden aplicar tales operadores unitarios en${\displaystyle \rho }$y luego medir su estado entrelazado en el${\displaystyle |0\rangle ,|1\rangle }$base. Alice usa${\displaystyle U_{C}=U(-\theta)}$,${\displaystyle U_{D}=U(\theta)}$Bob usa${\displaystyle V_{C}=U(2\theta),V_{D}=U(0)}$Es fácil demostrar que para${\displaystyle \theta =\pi /8}$Alice y Bob ganarán en el 85% de los casos. Los operadores unitarios sobre el estado entrelazado producen un par de "monedas" no correlacionadas para las preguntas (C,C) y un par de "monedas" correlacionadas para las demás preguntas.

Por lo tanto, el uso de estados entrelazados, operadores unitarios y mediciones cuánticas puede mejorar el éxito de este tipo de juegos.

Podemos usar el ejemplo anterior para definir una estrategia cuántica de un juego. Los jugadores comparten un estado entrelazado y pueden usar operadores unitarios locales. Tras las operaciones locales, una medición cuántica del estado dará como resultado una distribución de probabilidad de las recompensas definidas por el juego. El entrelazamiento es la parte "estratégica" de la estrategia cuántica, y los operadores unitarios locales son la parte "táctica" de la misma. ^{[ 49 ]}

Las estrategias cuánticas podrían cambiar el panorama de los equilibrios de Nash, podrían eliminar las estrategias clásicas de equilibrio de Nash y construir nuevas estrategias cuánticas de equilibrio de Nash. Además, es posible obtener equilibrios de Nash cuánticos con posibles recompensas diferentes a las de los equilibrios clásicos.

Por ejemplo, en el dilema del prisionero cuántico de Eisert, ^{[ 50 ]} el antiguo equilibrio de Nash ya no es válido; existe una nueva estrategia de equilibrio de Nash, en forma de dos matrices unitarias locales idénticas. Además, en el nuevo equilibrio de Nash, ambos jugadores obtienen una mejor recompensa que en el caso clásico, la cual es igual a la recompensa clásica por cooperación mutua, y por lo tanto, los jugadores escapan del dilema.

En la configuración anterior del Dilema del Prisionero cuántico de Eisert, existe la posibilidad de "agitación", donde un jugador puede deshacer las acciones de los demás jugadores mediante una estrategia que "conmuta" a través de J, el operador de entrelazamiento. Esto da la impresión de que el jugador opera en el espacio antes de que se entrelazara, destruyendo el orden temporal del juego (entrelazar → estrategia → desenredar → medir). Sin embargo, si restringimos las operaciones unitarias locales (como el uso de un subconjunto de matrices SU(2)), podemos evitar la agitación. ^{[ 51 ]}

En general, las operaciones locales del jugador A siempre pueden afectar el estado conjunto y, por lo tanto, la matriz de densidad reducida para B puede cambiar. Claramente, si permitimos operaciones no locales, entonces es posible la mezcla.

Una estrategia cuántica mixta (definida como en un caso clásico similar) es una estrategia en la que cada jugador tiene una distribución de probabilidad sobre operaciones unitarias locales que se aplican a una matriz de densidad compartida entre los jugadores. El estado cuántico mixto no debe ser separable, de lo contrario, el juego se asemeja a uno clásico. En general, una estrategia cuántica mixta produce equilibrios de Nash.

Flitney y Abbott ^{[ 52 ]} introdujeron una versión cuántica del juego de Monty-Hall. Se demostró que la introducción de una estrategia cuántica elimina el equilibrio de Nash clásico, y una estrategia cuántica mixta sobre estados máximamente entrelazados lo restablece.

En un juego repetido, la introducción de estrategias cuánticas podría afectar la estabilidad del equilibrio de Nash clásico, en el sentido de la Estrategia de Estabilidad Evolutiva. ^{[ 53 ]} Un equilibrio de Nash estable podría volverse inestable por la invasión de «mutantes cuánticos», y viceversa, un equilibrio de Nash evolutivamente inestable podría volverse estable bajo «mutaciones» cuánticas. ^{[ 54 ]}

En un juego CHSH repetido, Reichardt, Unger y Vazirani demostraron que la estrategia cuántica anterior es robusta ; si Alice y Bob juegan el juego CHSH muchas veces y ganan aproximadamente el 85 por ciento de las veces, podemos concluir que están utilizando una forma cercana de la estrategia cuántica anterior. Además, la estrategia cuántica anterior es generadora : si Alice y Bob utilizan estrategias que podrían depender del éxito de juegos anteriores, y ganan aproximadamente el 85 por ciento de las veces, podemos concluir que hay suficientes juegos independientes jugados con la estrategia cuántica anterior.

Harlalka, Belmonte y Griffin ^{[ 27 ]} y Harlalka y Griffin ^{[ 11 ]} introdujeron el concepto de clubes gastronómicos en el problema KPR. Un club gastronómico consta de agentes que acuerdan gestionar su elección de restaurante de forma centralizada, pero que no tienen control ni interacción con individuos fuera del club. Por lo tanto, dos miembros del club no pueden chocar entre sí, pero sí pueden chocar con personas que no son miembros del club. Cuando un club está disponible y${\displaystyle g}$Los agentes son parte de ello mientras${\displaystyle n}$Los agentes no son miembros del club (o son gratuitos), tenemos${\displaystyle N=n+g}$agentes totales (con${\displaystyle \lambda =1}$) y la probabilidad de que un miembro del club coma es,

${\displaystyle p_{g}(n,g)=\sum _{k=0}^{n}{\binom {n}{k}}\left({\frac {n+g-1}{n+g}}\right)^{nk}\left({\frac {1}{n+g}}\right)^{k}{\frac {1}{k+1}}}$,

mientras que la probabilidad de que un no miembro del club coma es,

${\displaystyle p_{n}(n,g)=\sum _{k=0}^{n-1}{\binom {n-1}{k}}\left({\frac {n}{n+g}}{\frac {1}{k+1}}+{\frac {g}{n+g}}{\frac {1}{k+2}}\right)\left({\frac {n+g-1}{n+g}}\right)^{nk-1}\left({\frac {1}{n+g}}\right)^{k}}$.

Alquiler${\displaystyle g=\alpha n}$y suponiendo${\displaystyle n\to \infty }$, es decir, asumir que una población de agentes infinitamente grande produce probabilidades asintóticas,

${\displaystyle p_{g}(\alpha )=\left(1-e^{-{\frac {1}{\alpha +1}}}\right)(\alpha +1)}$ y ${\displaystyle p_{n}(\alpha )=-\alpha ^{2}+e^{-{\frac {1}{\alpha +1}}}\left(\alpha ^{2}+\alpha -1\right)+1}$.

Cuando${\displaystyle \alpha =0}$y no hay miembros del club de comidas, la probabilidad de que cualquier agente coma vuelve a ser la esperada.${\displaystyle 1-e^{-1}}$En términos generales para${\displaystyle \alpha >0}$, tenemos${\displaystyle p_{g}(\alpha )>p_{n}(\alpha )}$Si los agentes son conscientes de esto y tienen la opción de elegir, esto crea un incentivo para formar una especie de coalición en el sentido de la teoría de juegos cooperativos .

Harlaka, Belmonte y Griffin ^{[ 27 ]} reformulan el problema de la formación de coaliciones como un juego evolutivo al permitir,

${\displaystyle \beta ={\frac {g}{N}}}$,

sea ​​la proporción de agentes que actualmente juegan la estrategia del club de cenas, y suponiendo que esta proporción debe seguir la ecuación del replicador ,

${\displaystyle {\dot {\beta }}=\beta \left[p_{g}(\beta )-{\bar {p}}(\beta )\right]}$,

dónde${\displaystyle p_{g}(\beta )}$es la probabilidad de que un agente en el club de comidas coma, escrita en términos de${\displaystyle \beta }$dado como,

${\displaystyle p_{g}(\beta )={\frac {1-e^{\beta -1}}{1-\beta }}}$,

y

${\displaystyle {\bar {p}}(\beta )=e^{\beta -1}(\beta -1)+1}$.

La curva de solución para la dinámica del replicador se muestra a la derecha. Al igual que una ecuación logística , la dinámica tiene un punto fijo inestable en${\displaystyle \beta =0}$y un punto fijo estable en${\displaystyle \beta =1}$Bajo esta dinámica, la población evolucionará naturalmente hacia un club gastronómico gestionado centralmente. Harlalka y Griffin muestran un resultado similar para la dinámica de imitación. ^{[ 11 ]}