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 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 pueda tener 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]

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 para ningún jugador ganar más que el pago esperado al desviarse 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 . Sea , que denota la ganancia para el 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 }$a pesar de ${\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 solo puede asignar probabilidad positiva a una estrategia pura si el pago de tiene un pago esperado como máximo menor que el pago de la mejor respuesta. Sea la probabilidad de que se juegue el perfil de estrategia. Para el jugador, sean los perfiles de estrategia de jugadores distintos de ; para y una estrategia pura de sea el perfil de estrategia donde juega y otros jugadores juegan . Sea el pago para cuando se usa 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 polinomial (PTAS) para los equilibrios de Nash ε es equivalente a la pregunta de si existe uno para los equilibrios de Nash aproximados ε-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. Existen ejemplos sencillos de juegos estocásticos sin equilibrio de Nash pero con un equilibrio ε para cualquier ε estrictamente mayor que 0.

Tal vez el ejemplo más simple de este tipo sea la siguiente variante de Matching Pennies , sugerida por Everett. El jugador 1 esconde un centavo y el jugador 2 debe adivinar si es 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 cara, el juego termina con un premio de cero para ambos jugadores. Si adivina incorrectamente que es cruz, el juego se repite . Si el juego continúa indefinidamente, el premio 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 un perfil de estrategia de este tipo es al menos 1 −  ε . Sin embargo, es fácil ver que no hay 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, en el que el resultado se promedia a lo largo de los T períodos. El único equilibrio de Nash de este juego es elegir Defect en cada período. Consideremos ahora las dos estrategias tit-for-tat y grim trigger . Aunque ni tit-for-tat ni grim trigger son equilibrios de Nash para el juego, ambos son -equilibrios para algún positivo . Los valores aceptables de dependen de los resultados del juego constituyente y del número T de períodos. ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

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 é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 sobre 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". Internet Mathematics . 5 (4): 365–382. doi : 10.1080/15427951.2008.10129172 .
6. Spyros C. Kontogiannis y Paul G. Spirakis (2010). "Equilibrios aproximados bien sustentados en juegos de bimatrix". 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 HW Kuhn y AW Tucker, editores. Contribuciones a la teoría de juegos , vol. III, volumen 39 de Annals of Mathematical Studies . 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-1Introducción matemática de 88 páginas; consulte la Sección 3.7. Disponible en línea de forma gratuita. 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 completa desde una perspectiva computacional; consulte la Sección 3.4.7. Descargable en línea de forma gratuita.
• SH Tijs. Equilibrios de Nash para juegos no cooperativos de n personas en forma normal , SIAM Review, 23 , 225–237, 1981.