En teoría de juegos , un juego bayesiano es un modelo de toma de decisiones estratégicas que supone que los jugadores tienen información incompleta. Los jugadores pueden tener información privada relevante para el juego, lo que significa que los pagos no son de conocimiento público. [1] Los juegos bayesianos modelan el resultado de las interacciones de los jugadores utilizando aspectos de la probabilidad bayesiana . Son notables porque permitieron, por primera vez en la teoría de juegos, la especificación de las soluciones a los juegos con información incompleta .
El economista húngaro John C. Harsanyi introdujo el concepto de juegos bayesianos en tres artículos de 1967 y 1968: [2] [3] [4] Recibió el Premio Nobel de Economía por estas y otras contribuciones a la teoría de juegos en 1994. En términos generales, Harsanyi definió los juegos bayesianos de la siguiente manera: a los jugadores se les asigna por naturaleza al comienzo del juego un conjunto de características. Al asignar distribuciones de probabilidad a estas características y calcular el resultado del juego utilizando la probabilidad bayesiana, el resultado es un juego cuya solución es, por razones técnicas, mucho más fácil de calcular que un juego similar en un contexto no bayesiano. Para esas razones técnicas, consulte la sección Especificación de juegos en este artículo.
Un juego bayesiano se define por (N,A,T,p,u) , donde consta de los siguientes elementos: [5]
En un juego estratégico, una estrategia pura es la elección de acción de un jugador en cada punto en el que debe tomar una decisión. [6]
Hay tres etapas en los juegos bayesianos, cada una de las cuales describe el conocimiento de los jugadores sobre los tipos dentro del juego.
Hay dos aspectos importantes y novedosos de los juegos bayesianos que fueron especificados por Harsanyi. [8] El primero es que los juegos bayesianos deben considerarse y estructurarse de manera idéntica a los juegos de información completa. Excepto que, al adjuntar probabilidad al juego, el juego final funciona como si fuera un juego de información incompleta. Por lo tanto, los jugadores pueden modelarse esencialmente como si tuvieran información incompleta y el espacio de probabilidad del juego aún sigue la ley de probabilidad total . Los juegos bayesianos también son útiles porque no requieren cálculos secuenciales infinitos. Los cálculos secuenciales infinitos surgirían donde los jugadores (esencialmente) intentan "meterse en la cabeza de los demás". Por ejemplo, uno puede hacer preguntas y decidir "Si espero alguna acción del jugador B, entonces el jugador B anticipará que espero esa acción, por lo que entonces debería anticipar esa anticipación" ad infinitum . Los juegos bayesianos permiten el cálculo de estos resultados en un movimiento al asignar simultáneamente diferentes pesos de probabilidad a diferentes resultados. El efecto de esto es que los juegos bayesianos permiten modelar una cantidad de juegos que en un entorno no bayesiano serían irracionales de calcular.
Un equilibrio bayesiano-Nash de un juego bayesiano es un equilibrio de Nash de su juego de forma normal ex ante asociado.
En un juego no bayesiano, un perfil de estrategia es un equilibrio de Nash si cada estrategia en ese perfil es la mejor respuesta a todas las demás estrategias en el perfil; es decir, no hay ninguna estrategia que un jugador pueda jugar que produzca un pago mayor, dadas todas las estrategias jugadas por los otros jugadores.
Se puede definir un concepto análogo para un juego bayesiano, con la diferencia de que la estrategia de cada jugador maximiza su beneficio esperado dadas sus creencias sobre el estado de la naturaleza. Las creencias de un jugador sobre el estado de la naturaleza se forman condicionando las probabilidades previas al tipo de jugador según la regla de Bayes.
Un equilibrio de Nash bayesiano (BNE) se define como un perfil de estrategia que maximiza el resultado esperado para cada jugador dadas sus creencias y dadas las estrategias utilizadas por los otros jugadores. Es decir, un perfil de estrategia es un equilibrio de Nash bayesiano si y solo si para cada jugador, manteniendo fijas las estrategias de todos los demás jugadores, la estrategia maximiza el resultado esperado del jugador de acuerdo con las creencias de ese jugador. [5]
Para los juegos bayesianos finitos, es decir, tanto la acción como el espacio de tipos son finitos, hay dos representaciones equivalentes. La primera se llama juego en forma de agente (ver Teorema 9.51 del libro de Teoría de juegos [9] ) que expande el número de jugadores de a , es decir, cada tipo de cada jugador se convierte en un jugador. La segunda se llama forma normal inducida (ver Sección 6.3.3 de Sistemas multiagente [10] ) que todavía tiene jugadores pero expande el número de acciones de cada jugador i de a , es decir, la política pura es una combinación de acciones que el jugador debe tomar para diferentes tipos. El Equilibrio de Nash (EN) se puede calcular en estas dos representaciones equivalentes, y el BNE se puede recuperar a partir del EN.
Los juegos de forma extensiva con información perfecta o imperfecta, tienen los siguientes elementos: [12]
El nodo de la Naturaleza suele estar representado por un círculo vacío. Su estrategia siempre está especificada y siempre es completamente mixta. Normalmente, la Naturaleza se encuentra en la raíz del árbol, pero también puede moverse en otros puntos.
Un conjunto de información del jugador i es un subconjunto de los nodos de decisión del jugador i entre los cuales no puede distinguir. Es decir, si el jugador i está en uno de sus nodos de decisión en un conjunto de información, no sabe en qué nodo del conjunto de información se encuentra.
Para que dos nodos de decisión estén en el mismo conjunto de información , deben [13]
Los conjuntos de información se indican mediante líneas de puntos, que es la notación más común hoy en día.
En los juegos bayesianos, las creencias de los jugadores sobre el juego se denotan mediante una distribución de probabilidad de varios tipos.
Si los jugadores no tienen información privada, la distribución de probabilidad sobre los tipos se conoce como prior común . [1]
Una evaluación de un juego en forma extensiva es un par <b, μ>
Una evaluación <b, μ> satisface la regla de Bayes si [14] μ(x|h i ) = Pr[x se alcanza dado b−i ] / Σ Pr[x' se alcanza dado b −i ] siempre que h i se alcance con probabilidad estrictamente positiva de acuerdo con b −i .
Un equilibrio bayesiano perfecto en un juego de forma extensiva es una combinación de estrategias y una especificación de creencias tales que se satisfacen las dos condiciones siguientes: [15]
El equilibrio de Nash bayesiano puede dar lugar a equilibrios inverosímiles en juegos dinámicos, en los que los jugadores se mueven de forma secuencial en lugar de simultánea. Como en los juegos con información completa, estos pueden surgir a través de estrategias no creíbles que se alejan de la trayectoria del equilibrio. En los juegos con información incompleta existe también la posibilidad adicional de creencias no creíbles.
Para abordar estas cuestiones, el equilibrio bayesiano perfecto, según el equilibrio perfecto en subjuegos, exige que, a partir de cualquier conjunto de información, el juego posterior sea óptimo y que las creencias se actualicen de manera consistente con la regla de Bayes en cada camino de juego que ocurra con probabilidad positiva.
Los juegos bayesianos estocásticos [16] combinan las definiciones de juegos bayesianos y juegos estocásticos para representar estados del entorno (por ejemplo, estados del mundo físico) con transiciones estocásticas entre estados, así como incertidumbre sobre los tipos de diferentes jugadores en cada estado. El modelo resultante se resuelve mediante una combinación recursiva del equilibrio de Nash bayesiano y la ecuación de optimalidad de Bellman . Los juegos bayesianos estocásticos se han utilizado para abordar diversos problemas, incluidos la planificación de la defensa y la seguridad, [17] la ciberseguridad de las centrales eléctricas, [18] la conducción autónoma, [19] la informática de borde móvil, [20] la autoestabilización en sistemas dinámicos, [21] y el tratamiento de la mala conducta en la IoT de crowdsourcing. [22]
La definición de los juegos bayesianos y del equilibrio bayesiano se ha ampliado para abordar la agencia colectiva . Un enfoque consiste en seguir tratando a los jugadores individuales como si razonaran de forma aislada, pero permitirles, con cierta probabilidad, razonar desde la perspectiva de un colectivo. [23] Otro enfoque consiste en suponer que los jugadores dentro de cualquier agente colectivo saben que el agente existe, pero que los demás jugadores no lo saben, aunque lo sospechan con cierta probabilidad. [24] Por ejemplo, Alice y Bob pueden a veces optimizar como individuos y a veces coludirse como equipo, dependiendo del estado de la naturaleza, pero otros jugadores pueden no saber cuál de estos casos es el caso.
Un sheriff se enfrenta a un sospechoso armado. Ambos deben decidir simultáneamente si disparar al otro o no.
El sospechoso puede ser de tipo "criminal" o de tipo "civil". El sheriff tiene un solo tipo. El sospechoso conoce su tipo y el tipo del sheriff, pero el sheriff no conoce el tipo del sospechoso. Por lo tanto, hay información incompleta (porque el sospechoso tiene información privada), lo que lo convierte en un juego bayesiano. Existe una probabilidad p de que el sospechoso sea un criminal y una probabilidad 1-p de que el sospechoso sea un civil; ambos jugadores conocen esta probabilidad (suposición previa común, que se puede convertir en un juego de información completa con información imperfecta ).
El sheriff preferiría defenderse y disparar si el sospechoso dispara, o no disparar si el sospechoso no lo hace (incluso si el sospechoso es un criminal). El sospechoso preferiría disparar si es un criminal, incluso si el sheriff no dispara, pero preferiría no disparar si es un civil, incluso si el sheriff dispara. Por lo tanto, la matriz de pagos de este juego en forma normal para ambos jugadores depende del tipo de sospechoso. Este juego se define por (N,A,T,p,u) , donde:
Si ambos jugadores son racionales y ambos saben que ambos jugadores son racionales y todo lo que sabe cualquier jugador es conocido por todos los jugadores (es decir, el jugador 1 sabe que el jugador 2 sabe que el jugador 1 es racional y el jugador 2 sabe esto, etc. hasta el infinito – conocimiento común ), el juego será como sigue según el equilibrio bayesiano perfecto: [25] [26]
Cuando el tipo es "criminal", la estrategia dominante para el sospechoso es disparar, y cuando el tipo es "civil", la estrategia dominante para el sospechoso es no disparar; por lo tanto, se puede eliminar la estrategia alternativa estrictamente dominada. Dado esto, si el sheriff dispara, tendrá un pago de 0 con probabilidad p y un pago de -1 con probabilidad 1-p , es decir, un pago esperado de p-1 ; si el sheriff no dispara, tendrá un pago de -2 con probabilidad p y un pago de 0 con probabilidad 1-p , es decir, un pago esperado de -2p . Por lo tanto, el sheriff siempre disparará si p-1 > -2p , es decir, cuando p > 1/3 .
El mercado de limones está relacionado con un concepto conocido como selección adversa .
Configuración
Hay un coche usado. El jugador 1 es un comprador potencial que está interesado en el coche. El jugador 2 es el propietario del coche y conoce el valor v del mismo (qué tan bueno es, etc.). El jugador 1 no lo sabe y cree que el valor v del coche para el propietario (jugador 2) se distribuye uniformemente entre 0 y 100 (es decir, cada uno de los dos subintervalos de valor de [0, 100] de igual longitud son igualmente probables).
El jugador 1 puede hacer una oferta p entre 0 y 100 (inclusive). El jugador 2 puede aceptar o rechazar la oferta. Los pagos son los siguientes:
Punto secundario: estrategia de corte
La estrategia del jugador 2: Aceptar todas las ofertas por encima de un cierto límite P* y rechazar y ofertar por debajo de P* se conoce como estrategia de límite, donde P* se denomina límite.
Una nueva empresa (jugador1) que quiere entrar en un mercado monopolizado por una gran empresa se encontrará con dos tipos de monopolistas (jugador2), el tipo 1 está impedido y el tipo 2 está permitido. El jugador1 nunca tendrá información completa sobre el jugador2, pero puede inferir la probabilidad de que aparezcan el tipo 1 y el tipo 2 a partir de si la empresa anterior que entró en el mercado estaba bloqueada; es un juego bayesiano. La razón de estos juicios es que existen costos de bloqueo para el jugador2, que puede necesitar hacer recortes de precios significativos para evitar que el jugador1 entre en el mercado, por lo que bloqueará al jugador1 cuando la ganancia que roba al entrar en el mercado sea mayor que los costos de bloqueo.
