En la teoría de juegos , un equilibrio épsilon , o equilibrio cercano a Nash, es un perfil de estrategia que satisface aproximadamente la condición de equilibrio de Nash . En un equilibrio de Nash, ningún jugador tiene un incentivo para cambiar su comportamiento. En un equilibrio de Nash aproximado, este requisito se debilita para permitir la posibilidad de que un jugador tenga un pequeño incentivo para hacer algo diferente. Esto todavía puede considerarse un concepto de solución adecuado, asumiendo, por ejemplo , un sesgo de statu quo. Este concepto de solución puede preferirse al equilibrio de Nash debido a que es más fácil de calcular, o alternativamente debido a la posibilidad de que en juegos de más de 2 jugadores, las probabilidades involucradas en un equilibrio de Nash exacto no necesitan ser números racionales . [1]
Equilibrio épsilon | |
---|---|
Un concepto de solución en la teoría de juegos | |
Relación | |
Superconjunto de | Equilibrio de Nash |
Significado | |
Usado para | juegos estocásticos |
Definición
Hay más de una definición alternativa.
La definición estándar
Dado un juego y un parámetro real no negativo , se dice que un perfil de estrategia es un-equilibrio si no es posible que ningún jugador gane más de en la recompensa esperada al desviarse unilateralmente de su estrategia . [2] : 45 Todo equilibrio de Nash es equivalente a un-equilibrio donde .
Formalmente, deja frijol -juego de jugador con conjuntos de acción para cada jugador y función de utilidad . Dejar denotar la recompensa para el jugador cuando perfil de estrategia es jugado. Dejar ser el espacio de distribuciones de probabilidad sobre . Un vector de estrategias es un -Nash Equilibrium para Si
- para todos
Equilibrio aproximado bien apoyado
La siguiente definición [3] impone el requisito más estricto de que un jugador solo puede asignar probabilidad positiva a una estrategia pura. si la recompensa de ha esperado una recompensa como máximo menos que la mejor recompensa de respuesta. Dejar ser la probabilidad de que el perfil de la estrategia es jugado. Para el jugador dejar Ser perfiles de estrategia de jugadores distintos a ; por y una pura estrategia de dejar ser el perfil de la estrategia donde obras de teatro y otros jugadores juegan . Dejar ser la recompensa para cuando perfil de estrategia se utiliza. El requisito puede expresarse mediante la fórmula
Resultados
La existencia de un esquema de aproximación de tiempo polinómico (PTAS) para los equilibrios de ε-Nash es equivalente a la cuestión de si existe uno para los equilibrios de Nash aproximados con un buen soporte, [4] pero la existencia de un PTAS sigue siendo un problema abierto . Para valores constantes de ε, se conocen algoritmos de tiempo polinómico para equilibrios aproximados para valores más bajos de ε que los que se conocen para equilibrios aproximados bien sustentados. Para juegos con pagos en el rango [0,1] y ε = 0.3393, los equilibrios de ε-Nash se pueden calcular en tiempo polinomial [5] Para juegos con pagos en el rango [0,1] y ε = 2/3, ε -los equilibrios bien soportados se pueden calcular en tiempo polinomial [6]
Ejemplo
La noción de ε-equilibrios es importante en la teoría de juegos estocásticos de duración potencialmente infinita. Hay ejemplos simples de juegos estocásticos sin equilibrio de Nash pero con un equilibrio ε para cualquier ε estrictamente mayor que 0.
Quizás el ejemplo más simple sea la siguiente variante de Matching Pennies , sugerida por Everett. El jugador 1 esconde un centavo y el jugador 2 debe adivinar si sale cara o cruz. Si el jugador 2 adivina correctamente, gana el centavo del jugador 1 y el juego termina. Si el jugador 2 adivina incorrectamente que el centavo es mano a mano, el juego termina con un pago cero para ambos jugadores. Si adivina incorrectamente que es cruz, el juego se repite . Si el juego continúa para siempre, la recompensa para ambos jugadores es cero.
Dado un parámetro ε > 0, cualquier perfil de estrategia en el que el jugador 2 adivine cara con probabilidad ε y cruz con probabilidad 1 - ε (en cada etapa del juego e independientemente de las etapas anteriores) es un equilibrio ε para el juego. La recompensa esperada del Jugador 2 en tal perfil de estrategia es al menos 1 - ε . Sin embargo, es fácil ver que no existe una estrategia para el jugador 2 que pueda garantizar una recompensa esperada de exactamente 1. Por lo tanto, el juego no tiene equilibrio de Nash .
Otro ejemplo simple es el dilema del prisionero repetido finitamente para períodos T, donde la recompensa se promedia durante los períodos T. El único equilibrio de Nash de este juego es elegir Defecto en cada período. Ahora considere las dos estrategias ojo por ojo y desencadenante sombrío . Aunque ni el ojo por ojo ni el desencadenante sombrío son equilibrios de Nash para el juego, ambos son-equilibrios para algunos positivos . Los valores aceptables de dependen de los beneficios del juego constituyente y del número T de períodos.
En economía, el concepto de equilibrio épsilon de estrategia pura se utiliza cuando el enfoque de estrategia mixta se considera poco realista. En un equilibrio épsilon de estrategia pura, cada jugador elige una estrategia pura que está dentro del épsilon de su mejor estrategia pura. Por ejemplo, en el modelo de Bertrand-Edgeworth , donde no existe un equilibrio de estrategia pura, puede existir un equilibrio épsilon de estrategia pura.
Referencias
- Citas en línea
- ^ V. Bubelis (1979). "Sobre equilibrios en juegos finitos". Revista Internacional de Teoría de Juegos . 8 (2): 65–79. doi : 10.1007 / bf01768703 .
- ^ Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
- ^ PW Goldberg y CH Papadimitriou (2006). "Reducibilidad entre problemas de equilibrio". 38º Simposio de Teoría de la Computación . págs. 61–70. doi : 10.1145 / 1132516.1132526 .
- ^ C. Daskalakis, PW Goldberg y CH Papadimitriou (2009). "La complejidad de calcular un equilibrio de Nash". Revista SIAM de Computación . 39 (3): 195-259. CiteSeerX 10.1.1.68.6111 . doi : 10.1137 / 070699652 .
- ^ H. Tsaknakis y Paul G. Spirakis (2008). "Un enfoque de optimización para equilibrios de Nash aproximados" . Matemáticas de Internet . 5 (4): 365–382. doi : 10.1080 / 15427951.2008.10129172 .
- ^ Spyros C. Kontogiannis y Paul G. Spirakis (2010). "Equilibrios aproximados bien soportados en juegos Bimatrix". Algoritmica . 57 (4): 653–667. doi : 10.1007 / s00453-008-9227-6 .
- Fuentes
- H Dixon Approximate Bertrand Equilibrium in a Replicated Industry , Review of Economic Studies, 54 (1987), páginas 47–62.
- H. Everett. "Juegos recursivos". En HW Kuhn y AW Tucker, editores. Contribuciones a la teoría de juegos , vol. III, volumen 39 de Annals of Mathematical Studies . Prensa de la Universidad de Princeton, 1957.
- Leyton-Brown, Kevin; Shoham, Yoav (2008), Fundamentos de la teoría de juegos: una introducción concisa y multidisciplinaria , San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. Una introducción matemática de 88 páginas; consulte la Sección 3.7. Gratis en línea en muchas universidades.
- R. Radner . Comportamiento colusorio en equilibrios épsilon no cooperativos de oligopolios con vidas largas pero finitas , Journal of Economic Theory, 22 , 121-157, 1980.
- Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos , Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia integral desde una perspectiva computacional; consulte la Sección 3.4.7. Descarga gratuita en línea .
- SH Tijs. Equilibrios de Nash para juegos no cooperativos de n personas en forma normal , SIAM Review, 23 , 225-237, 1981.