Hispanopedia Wiki
Articulo de referencia

épsilon-equilibrio

En teoría de juegos , un equilibrio épsilon , o equilibrio cercano a Nash, es un perfil de estrategias que satisface aproximadamente la condición de equilibrio de Nash . En un e...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de juegos , un equilibrio épsilon , o equilibrio cercano a Nash, es un perfil de estrategias que satisface aproximadamente la condición de 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 aún 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 bien debido a la posibilidad de que en juegos de más de 2 jugadores, las probabilidades involucradas en un equilibrio de Nash exacto no necesariamente sean números racionales . [ 1 ]

Definición

Existe más de una definición alternativa.

La definición estándar

Dado un juego y un parámetro real no negativoε{\displaystyle \varepsilon }Se dice que un perfil estratégico es un ε{\displaystyle \varepsilon }-equilibrio si no es posible que ningún jugador gane más queε{\displaystyle \varepsilon }en la ganancia esperada al desviarse unilateralmente de su estrategia . [ 2 ] : 45 Todo equilibrio de Nash es equivalente a unε{\displaystyle \varepsilon }-equilibrio dondeε=0{\displaystyle \varepsilon =0}.

Formalmente, dejemosGRAMO=(norte,A=A1×⋯×Anorte,tú:A→Rnorte){\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})} frijolnorte{\displaystyle N}-juego de jugador con conjuntos de acciónAi{\displaystyle A_{i}}por cada jugadori{\displaystyle i}y función de utilidadtú{\displaystyle u}. Dejartúi(s){\displaystyle u_{i}(s)}denota la recompensa para el jugadori{\displaystyle i}cuando perfil de estrategias{\displaystyle s}se juega. DejaΔi{\displaystyle \Delta _{i}}sea ​​el espacio de distribuciones de probabilidad sobreAi{\displaystyle A_{i}}Un vector de estrategiasσ∈Δ=Δ1×⋯×Δnorte{\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}}es unε{\displaystyle \varepsilon }-Equilibrio de Nash paraGRAMO{\displaystyle G}si

túi(σ)≥túi(σi′,σ−i)−ε{\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon }a pesar deσi′∈Δi,i∈norte.{\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N.}

Tenga en cuenta que las utilidades de todos los jugadores están normalizadas a [0,1], [ 3 ], por lo que en realidad se trata de una aproximación multiplicativa : la ganancia no puede ser mayor queε{\displaystyle \varepsilon }veces la mayor utilidad.

Equilibrio aproximado bien respaldado

La siguiente definición [ 4 ] impone el requisito más estricto de que un jugador solo puede asignar probabilidad positiva a una estrategia pura.a{\displaystyle a}si la recompensa dea{\displaystyle a}tiene un retorno esperado como máximoε{\displaystyle \varepsilon }menos que la mejor respuesta recompensa. Dejaincógnitas{\displaystyle x_{s}}sea ​​la probabilidad de que el perfil de estrategias{\displaystyle s}Se juega. Para el jugadorpag{\displaystyle p}dejarS−pag{\displaystyle S_{-p}}ser perfiles estratégicos de jugadores distintos apag{\displaystyle p}; paras∈S−pag{\displaystyle s\in S_{-p}}y una estrategia puraj{\displaystyle j}depag{\displaystyle p}dejarjs{\displaystyle js}ser el perfil de estrategia dondepag{\displaystyle p}obrasj{\displaystyle j}y otros jugadores juegans{\displaystyle s}. Dejartúpag(s){\displaystyle u_{p}(s)}ser la recompensapag{\displaystyle p}cuando perfil de estrategias{\displaystyle s}se utiliza. El requisito se puede expresar mediante la fórmula

∑s∈S−pagtúpag(js)incógnitas>ε+∑s∈S−pagtúpag(j′s)incógnitas⟹incógnitaj′pag=0.{\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 polinomial (PTAS) para equilibrios de ε -Nash es equivalente a la pregunta de si existe uno para equilibrios de Nash aproximados ε -bien soportados, [ 5 ] pero la existencia de un PTAS sigue siendo un problema abierto. Para valores constantes de ε , se conocen algoritmos en tiempo polinomial para equilibrios aproximados para valores de ε menores que los conocidos para equilibrios aproximados bien soportados. Para juegos con pagos en el rango [0,1] y ε =0,3393, los equilibrios de ε -Nash se pueden calcular en tiempo polinomial. [ 6 ] Para juegos con pagos en el rango [0,1] y ε =2/3, los equilibrios ε -bien soportados se pueden calcular en tiempo polinomial. [ 7 ]

Ejemplo

La noción de ε-equilibrios es importante en la teoría de juegos estocásticos de duración potencialmente infinita. Existen ejemplos sencillos de juegos estocásticos sin equilibrio de Nash , pero con un ε-equilibrio para cualquier ε estrictamente mayor que 0.

Quizás el ejemplo más sencillo sea la siguiente variante de Matching Pennies , sugerida por Everett. El jugador 1 esconde una moneda y el jugador 2 debe adivinar si es cara o cruz. Si el jugador 2 acierta, gana la moneda al jugador 1 y el juego termina. Si el jugador 2 se equivoca y adivina que es cara, el juego termina sin que ninguno de los dos jugadores gane nada. Si se equivoca y adivina que es cruz, el juego se repite . Si el juego continúa indefinidamente, ninguno de los dos jugadores gana nada.

Dado un parámetro ε > 0, cualquier perfil de estrategia en el que el Jugador 2 acierte 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 dicho 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 una recompensa esperada de exactamente 1. Por lo tanto, el juego no tiene un equilibrio de Nash .    

Otro ejemplo sencillo es el dilema del prisionero repetido un número finito de veces durante T períodos, donde la recompensa se promedia sobre los T períodos. El único equilibrio de Nash de este juego es elegir Defecto en cada período. Ahora consideremos las dos estrategias ojo por ojo y gatillo sombrío . Aunque ni ojo por ojo ni gatillo sombrío son equilibrios de Nash para el juego, ambos sonϵ{\displaystyle \epsilon }-equilibrios para algún positivoϵ{\displaystyle \epsilon }. Los valores aceptables deϵ{\displaystyle \epsilon }dependen de las recompensas 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 se encuentra dentro de un margen é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.

Véase también

Referencias

Citas en línea
  1. ↑ V. Bubelis (1979). "Sobre los equilibrios en juegos finitos". International Journal of Game Theory . 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. ↑ Tsaknakis, Haralampos; Spirakis, Paul G. (2007). "Un enfoque de optimización para equilibrios de Nash aproximados" . En Deng, Xiaotie ; Graham, Fan Chung (eds.). Economía de Internet y redes . Lecture Notes in Computer Science. Vol. 4858. Berlín, Heidelberg: Springer. pp. 42–56 . doi : 10.1007/978-3-540-77105-0_8 . ISBN   978-3-540-77105-0.
  4. ↑ PW Goldberg y CH Papadimitriou (2006). "Reducibilidad entre problemas de equilibrio". 38º Simposio sobre Teoría de la Computación . págs. 61–70 . doi : 10.1145/1132516.1132526 . 
  5. ^ 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 . 
  6. ↑ H. Tsaknakis y Paul G. Spirakis (2008). "Un enfoque de optimización para equilibrios de Nash aproximados" . Internet Mathematics . 5 (4): 365– 382. doi : 10.1080/15427951.2008.10129172 .
  7. ↑ Spyros C. Kontogiannis y Paul G. Spirakis (2010). "Equilibrios aproximados bien respaldados en juegos bimatriciales". Algorithmica . 57 (4): 653– 667. doi : 10.1007/s00453-008-9227-6 . S2CID 15968419 . 
Fuentes
  • H Dixon Equilibrio aproximado de Bertrand en una industria replicada , Review of Economic Studies, 54 (1987), páginas 47–62.
  • H. Everett. «Juegos recursivos». En H. W. Kuhn y A. W. Tucker (eds.), Contribuciones a la teoría de juegos , vol. III, volumen 39 de Anales de Estudios Matemáticos . Princeton University Press, 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; véase la Sección 3.7. Disponible gratuitamente en línea. Archivado el 15 de agosto de 2000 en la Wayback Machine de 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, de teoría de juegos y lógicos , Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia completa desde una perspectiva computacional; véase la Sección 3.4.7. Descargable gratuitamente en línea .
  • SH Tijs. Equilibrios de Nash para juegos no cooperativos de n personas en forma normal , SIAM Review, 23 , 225–237, 1981.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Epsilon-equilibrium&oldid=1356441337 "