Equilibrio épsilon

En teoría de juegos , un equilibrio épsilon , o equilibrio cercano a Nash, es un perfil de estrategia que satisface aproximadamente la condición del equilibrio de Nash . En un equilibrio de Nash, ningún jugador tiene incentivos 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 status 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 tengan por qué ser números racionales . ^[1]

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 obtenga más que el beneficio esperado desviándose unilateralmente de su estrategia . ^{[2] : 45} Todo equilibrio de Nash es equivalente a un equilibrio - donde . ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon =0}$

Formalmente, sea un juego de jugadores con conjuntos de acciones para cada jugador y función de utilidad . Denotemos el pago al jugador cuando se juega el perfil de estrategia . Sea el espacio de distribuciones de probabilidad sobre . Un vector de estrategias es un equilibrio de -Nash para si ${\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})}$ ${\displaystyle N}$ ${\displaystyle A_{i}}$ ${\displaystyle i}$ ${\displaystyle u}$ ${\displaystyle u_{i}(s)}$ ${\displaystyle i}$ ${\displaystyle s}$ ${\displaystyle \Delta _{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}}$ ${\displaystyle \varepsilon }$ ${\displaystyle G}$

${\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon }$para todos ${\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N.}$

Equilibrio aproximado bien sustentado

La siguiente definición ^[3] impone el requisito más estricto de que un jugador sólo puede asignar probabilidad positiva a una estrategia pura si el pago esperado es como máximo menor que el pago de la mejor respuesta. Sea la probabilidad de que se juegue el perfil de estrategia. Para los jugadores, sean perfiles estratégicos de jugadores distintos de ; para y una estrategia pura de sea el perfil de estrategia donde juegan y juegan otros jugadores . Sea la recompensa cuando se utiliza el perfil de estrategia . El requisito se puede expresar mediante la fórmula. ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle \varepsilon }$ ${\displaystyle x_{s}}$ ${\displaystyle s}$ ${\displaystyle p}$ ${\displaystyle S_{-p}}$ ${\displaystyle p}$ ${\displaystyle s\in S_{-p}}$ ${\displaystyle j}$ ${\displaystyle p}$ ${\displaystyle js}$ ${\displaystyle p}$ ${\displaystyle j}$ ${\displaystyle s}$ ${\displaystyle u_{p}(s)}$ ${\displaystyle p}$ ${\displaystyle s}$

${\displaystyle \sum _{s\in S_{-p}}u_{p}(js)x_{s}>\varepsilon +\sum _{s\in S_{-p}}u_{p}(j's)x_{s}\Longrightarrow x_{j'}^{p}=0.}$

Resultados

La existencia de un esquema de aproximación en tiempo polinómico (PTAS) para los equilibrios de ε-Nash es equivalente a la pregunta de si existe uno para los equilibrios de Nash aproximados de ε bien sustentados, ^[4] pero la existencia de un PTAS sigue siendo un problema abierto. . Para valores constantes de ε, se conocen algoritmos de tiempo polinomial para equilibrios aproximados para valores de ε más bajos que los conocidos 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 sustentados 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 está cara arriba o cruz. Si el jugador 2 adivina correctamente, le gana el centavo al jugador 1 y el juego termina. Si el jugador 2 adivina incorrectamente que la moneda está mano a mano, el juego termina con un pago de cero para ambos jugadores. Si adivina incorrectamente que está cara arriba, el juego se repite . Si el juego continúa para siempre, el pago para ambos jugadores es cero.

Dado un parámetro ε > 0, cualquier perfil de estrategia en el que el jugador 2 adivine cara arriba con probabilidad ε y cruz arriba con probabilidad 1 −  ε (en cada etapa del juego, e independientemente de las etapas anteriores) es un ε -equilibrio para el juego. El pago esperado del Jugador 2 en tal perfil de estrategia es al menos 1 −  ε . Sin embargo, es fácil ver que no existe ninguna estrategia para el jugador 2 que pueda garantizar un pago esperado de exactamente 1. Por lo tanto, el juego no tiene equilibrio de Nash .

Otro ejemplo sencillo es el dilema del prisionero que se repite finitamente durante T períodos, donde la recompensa se promedia durante los T períodos. El único equilibrio de Nash de este juego es elegir Defecto en cada período. Consideremos ahora las dos estrategias: ojo por ojo y disparador sombrío . Aunque ni el ojo por ojo ni el disparador sombrío son equilibrios de Nash para el juego, ambos son equilibrios para algunos aspectos positivos . Los valores aceptables de dependen de los pagos del juego constituyente y del número T de períodos. ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

En economía, el concepto de estrategia pura de equilibrio épsilon 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

1. V. Bubelis (1979). "Sobre equilibrios en juegos finitos". Revista Internacional de Teoría de Juegos . 8 (2): 65–79. doi :10.1007/bf01768703. S2CID  122843303.
2. Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
3. 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.
4. 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. 
5. 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 .
6. Spyros C. Kontogiannis y Paul G. Spirakis (2010). "Equilibrios aproximados bien soportados en juegos Bimatrix". Algorítmica . 57 (4): 653–667. doi :10.1007/s00453-008-9227-6. S2CID  15968419.

Fuentes

• Equilibrio aproximado de Bertrand de H Dixon en una industria replicada, 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 Anales de Estudios Matemáticos . 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 Archivado el 15 de agosto de 2000 en Wayback Machine 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. Descargable gratis en línea.
• SH Tijs. Equilibrios de Nash para juegos no cooperativos de n personas en forma normal , SIAM Review, 23 , 225–237, 1981.