En teoría de juegos , el equilibrio de Nash , llamado así por el matemático John Forbes Nash Jr. , es la forma más común de definir la solución de un juego no cooperativo que involucra a dos o más jugadores. En un equilibrio de Nash, se supone que cada jugador conoce las estrategias de equilibrio de los otros jugadores y ningún jugador tiene nada que ganar si cambia únicamente su propia estrategia. [1] El principio del equilibrio de Nash se remonta a la época de Cournot , quien lo aplicó a empresas competidoras que eligen productos. [2]
equilibrio de Nash | |
---|---|
Un concepto de solución en la teoría de juegos | |
Relación | |
Subconjunto de | Racionalizabilidad , Epsilon-equilibrio , Equilibrio correlacionado |
Superconjunto de | Evolutivamente estrategia estable , equilibrio perfecto en subjuegos , Bayesiano Perfecto equilibrio , temblor mano perfecta de equilibrio , estable equilibrio de Nash , fuerte equilibrio de Nash , equilibrio de Cournot |
Significado | |
Propuesto por | John Forbes Nash Jr. |
Usado para | Todos los juegos no cooperativos |
Si cada jugador ha elegido una estrategia (un plan de acción que elige sus propias acciones en función de lo que ha sucedido hasta ahora en el juego) y ningún jugador puede aumentar su propio beneficio esperado cambiando su estrategia mientras los otros jugadores mantienen la suya sin cambios, entonces el actual El conjunto de opciones de estrategia constituye un equilibrio de Nash.
Si dos jugadores, Alice y Bob, eligen las estrategias A y B, (A, B) es un equilibrio de Nash si Alice no tiene otra estrategia disponible que funcione mejor que A para maximizar su beneficio en respuesta a que Bob elija B, y Bob no tiene otra estrategia. disponible que rinde mejor que B para maximizar su beneficio en respuesta a que Alice eligió A. En un juego en el que Carol y Dan también son jugadores, (A, B, C, D) es un equilibrio de Nash si A es la mejor respuesta de Alice a ( B, C, D), B es la mejor respuesta de Bob a (A, C, D), etc.
Nash demostró que existe un equilibrio de Nash para cada juego finito: ver más adelante el artículo sobre estrategia .
Aplicaciones
Los teóricos de juegos utilizan el equilibrio de Nash para analizar el resultado de la interacción estratégica de varios tomadores de decisiones . En una interacción estratégica, el resultado de cada decisor depende de las decisiones de los demás y de las suyas propias. La idea simple que subyace a la idea de Nash es que no se pueden predecir las elecciones de múltiples tomadores de decisiones si se analizan esas decisiones de forma aislada. En cambio, uno debe preguntar qué haría cada jugador teniendo en cuenta lo que espera que hagan los demás. El equilibrio de Nash requiere que sus elecciones sean consistentes: ningún jugador desea deshacer su decisión dado lo que los demás están decidiendo.
El concepto se ha utilizado para analizar situaciones hostiles como guerras y carreras de armamentos [3] (ver el dilema del prisionero ), y también cómo el conflicto puede ser mitigado por la interacción repetida (ver ojo por ojo ). También se ha utilizado para estudiar hasta qué punto las personas con diferentes preferencias pueden cooperar (ver batalla de sexos ), y si tomarán riesgos para lograr un resultado cooperativo (ver caza del ciervo ). Se ha utilizado para estudiar la adopción de estándares técnicos , [ cita requerida ] y también la ocurrencia de corridas bancarias y crisis monetarias (ver juego de coordinación ). Otras aplicaciones incluyen el flujo de tráfico (ver el principio de Wardrop ), cómo organizar subastas (ver la teoría de las subastas ), el resultado de los esfuerzos realizados por múltiples partes en el proceso educativo, [4] legislación reguladora como las regulaciones ambientales (ver la tragedia de los comunes ) , [5] gestión de recursos naturales, [6] análisis de estrategias de marketing, [7] incluso tiros penales en fútbol (ver centavos equivalentes ), [8] sistemas de energía, sistemas de transporte, problemas de evacuación [9] y comunicaciones inalámbricas. [10]
Historia
Equilibrio de Nash es el nombre de matemático estadounidense John Forbes Nash Jr . La misma idea fue utilizada en una aplicación particular en 1838 por Antoine Augustin Cournot en su teoría del oligopolio . [11] En la teoría de Cournot, cada una de varias empresas elige cuánta producción producir para maximizar su beneficio. El mejor resultado de una empresa depende de los resultados de las demás. Un equilibrio de Cournot ocurre cuando la producción de cada empresa maximiza sus beneficios dada la producción de las otras empresas, que es un equilibrio de Nash de estrategia pura . Cournot también introdujo el concepto de dinámica de mejor respuesta en su análisis de la estabilidad del equilibrio. Sin embargo, Cournot no usó la idea en ninguna otra aplicación, ni la definió en general.
En cambio, el concepto moderno de equilibrio de Nash se define en términos de estrategias mixtas , donde los jugadores eligen una distribución de probabilidad sobre posibles estrategias puras (que podrían poner el 100% de la probabilidad en una estrategia pura; estas estrategias puras son un subconjunto de estrategias mixtas). El concepto de equilibrio de estrategia mixta fue introducido por John von Neumann y Oskar Morgenstern en su libro de 1944 The Theory of Games and Economic Behavior , pero su análisis se restringió al caso especial de los juegos de suma cero . Demostraron que existirá un equilibrio de Nash de estrategia mixta para cualquier juego de suma cero con un conjunto finito de acciones. [12] La contribución de Nash en su artículo de 1951 "Non-Cooperative Games" fue definir un equilibrio de Nash de estrategia mixta para cualquier juego con un conjunto finito de acciones y demostrar que debe existir al menos un equilibrio de Nash (de estrategia mixta). en tal juego. La clave de la capacidad de Nash para demostrar la existencia de manera mucho más general que von Neumann radica en su definición de equilibrio. Según Nash, "un punto de equilibrio es una n-tupla tal que la estrategia mixta de cada jugador maximiza su beneficio si las estrategias de los demás se mantienen fijas. Por lo tanto, la estrategia de cada jugador es óptima frente a las de los demás". Poner el problema en este marco permitió a Nash emplear el teorema del punto fijo de Kakutani en su artículo de 1950 para demostrar la existencia de equilibrios. Su artículo de 1951 utilizó el teorema del punto fijo de Brouwer, más simple, con el mismo propósito. [13]
Los teóricos de los juegos han descubierto que, en algunas circunstancias, el equilibrio de Nash hace predicciones inválidas o no realiza una predicción única. Han propuesto muchos conceptos de solución ("refinamientos" de los equilibrios de Nash) diseñados para descartar equilibrios de Nash inverosímiles. Un tema particularmente importante es que algunos equilibrios de Nash pueden basarse en amenazas que no son " creíbles ". En 1965 Reinhard Selten propuso el equilibrio perfecto en subjuegos como un refinamiento que elimina los equilibrios que dependen de amenazas no creíbles . Otras extensiones del concepto de equilibrio de Nash han abordado qué sucede si se repite un juego , o qué sucede si se juega un juego en ausencia de información completa . Sin embargo, los refinamientos y extensiones posteriores del equilibrio de Nash comparten la idea principal sobre la que se basa el concepto de Nash: el equilibrio es un conjunto de estrategias tales que la estrategia de cada jugador es óptima dadas las opciones de los demás.
Definiciones
Equilibrio de Nash
Un perfil de estrategia es un conjunto de estrategias, una para cada jugador. De manera informal, un perfil de estrategia es un equilibrio de Nash si ningún jugador puede hacerlo mejor cambiando unilateralmente su estrategia. Para ver lo que esto significa, imagine que a cada jugador se le cuentan las estrategias de los demás. Supongamos entonces que cada jugador se pregunta: "Conociendo las estrategias de los otros jugadores y tratando las estrategias de los otros jugadores como algo escrito en piedra, ¿puedo beneficiarme cambiando mi estrategia?"
Si cualquier jugador pudiera responder "Sí", entonces ese conjunto de estrategias no es un equilibrio de Nash. Pero si todos los jugadores prefieren no cambiar (o son indiferentes entre cambiar o no), entonces el perfil de la estrategia es un equilibrio de Nash. Por tanto, cada estrategia en un equilibrio de Nash es la mejor respuesta a las estrategias de los otros jugadores en ese equilibrio. [14]
Formalmente, deja ser el conjunto de todas las estrategias posibles para el jugador , dónde . Dejar ser un perfil de estrategia, un conjunto que consta de una estrategia para cada jugador, donde denota el estrategias de todos los jugadores excepto . Dejarser la recompensa del jugador i en función de las estrategias. El perfil de la estrategiaes un equilibrio de Nash si [15]
Un juego puede tener más de un equilibrio de Nash. Incluso si el equilibrio es único, puede ser débil : un jugador puede ser indiferente entre varias estrategias dadas las opciones de los otros jugadores. Es único y se denomina equilibrio de Nash estricto si la desigualdad es estricta, por lo que una estrategia es la mejor respuesta única:
Tenga en cuenta que el conjunto de estrategias puede ser diferente para diferentes jugadores, y sus elementos pueden ser una variedad de objetos matemáticos. De manera más simple, un jugador puede elegir entre dos estrategias, p. Ej. O bien, el conjunto de estrategias podría ser un conjunto finito de estrategias condicionales que responden a otros jugadores, p. Ej. O podría ser un conjunto infinito, un continuo o ilimitado, p. Ej. tal que es un número real no negativo. Las pruebas de existencia de Nash asumen un conjunto de estrategias finito, pero el concepto de equilibrio de Nash no lo requiere.
El equilibrio de Nash a veces puede parecer no racional en una perspectiva de tercera persona. Esto se debe a que un equilibrio de Nash no es necesariamente óptimo de Pareto .
El equilibrio de Nash también puede tener consecuencias no racionales en los juegos secuenciales porque los jugadores pueden "amenazarse" entre sí con amenazas que en realidad no llevarían a cabo. Para tales juegos, el equilibrio de Nash perfecto en subjuegos puede ser más significativo como herramienta de análisis.
Equilibrio estricto / débil
Suponga que en el equilibrio de Nash, cada jugador se pregunta: "Conociendo las estrategias de los otros jugadores y tratando las estrategias de los otros jugadores como algo escrito en piedra, ¿sufriría una pérdida si cambiara mi estrategia?"
Si la respuesta de todos los jugadores es "Sí", entonces el equilibrio se clasifica como un equilibrio de Nash estricto . [dieciséis]
Si en cambio, para algún jugador, hay una igualdad exacta entre la estrategia en equilibrio de Nash y alguna otra estrategia que da exactamente el mismo pago (es decir, este jugador es indiferente entre cambiar y no), entonces el equilibrio se clasifica como un equilibrio de Nash débil .
Un juego puede tener un equilibrio de Nash de estrategia pura o de estrategia mixta . (En este último se elige estocásticamente una estrategia pura con una probabilidad fija ).
Teorema de existencia de Nash
Nash demostró que si se permiten estrategias mixtas (donde un jugador elige probabilidades de usar varias estrategias puras), entonces cada juego con un número finito de jugadores en el que cada jugador puede elegir entre un número finito de estrategias puras tiene al menos un equilibrio de Nash, que podría ser una estrategia pura para cada jugador o podría ser una distribución de probabilidad sobre las estrategias para cada jugador.
No es necesario que existan equilibrios de Nash si el conjunto de opciones es infinito y no compacto. Un ejemplo es un juego en el que dos jugadores nombran simultáneamente un número y el jugador que nombra el número mayor gana. Otro ejemplo es donde cada uno de los dos jugadores elige un número real estrictamente menor que 5 y el ganador es el que tenga el mayor número; no existe ningún número mayor estrictamente menor que 5 (si el número pudiera ser igual a 5, el equilibrio de Nash haría que ambos jugadores eligieran 5 y empataran el juego). Sin embargo, existe un equilibrio de Nash si el conjunto de opciones es compacto y la recompensa de cada jugador es continua en las estrategias de todos los jugadores. [17]
Ejemplos de
Juego de coordinacion
Jugador 2 Jugador 1 | El jugador 2 adopta la estrategia A | El jugador 2 adopta la estrategia B |
---|---|---|
El jugador 1 adopta la estrategia A | 4 4 | 3 1 |
El jugador 1 adopta la estrategia B | 1 3 | 2 2 |
El juego de coordinación es un juego clásico ( simétrico ) de dos jugadores y dos estrategias , con un ejemplo de matriz de pagos que se muestra a la derecha. Por tanto, los jugadores deben coordinarse, adoptando la estrategia A, para recibir la mayor recompensa; es decir, 4. Sin embargo, si ambos jugadores eligieron la estrategia B, todavía hay un equilibrio de Nash. Aunque a cada jugador se le otorga un pago inferior al óptimo, ninguno de los jugadores tiene incentivos para cambiar de estrategia debido a una reducción en el pago inmediato (de 2 a 1).
Un ejemplo famoso de este tipo de juego fue la caza del ciervo ; En el juego, dos jugadores pueden optar por cazar un ciervo o un conejo, proporcionando el primero más carne (4 unidades de utilidad) que el segundo (1 unidad de utilidad). La advertencia es que el ciervo debe ser cazado cooperativamente, por lo que si un jugador intenta cazar al ciervo, mientras que el otro caza al conejo, fallará en la caza (0 unidades de utilidad), mientras que si ambos lo cazan, se dividirán. la recompensa (2, 2). Por lo tanto, el juego exhibe dos equilibrios en (ciervo, ciervo) y (conejo, conejo) y, por tanto, la estrategia óptima de los jugadores depende de sus expectativas sobre lo que pueda hacer el otro jugador. Si un cazador confía en que el otro cazará el ciervo, debe cazar el ciervo; sin embargo, si sospechan que el otro cazará al conejo, deben cazar al conejo. Este juego se utilizó como una analogía para la cooperación social, ya que gran parte del beneficio que las personas obtienen en la sociedad depende de que las personas cooperen y confíen implícitamente entre sí para actuar de manera correspondiente a la cooperación.
Otro ejemplo de un juego de coordinación es el escenario en el que dos tecnologías están disponibles para dos empresas con productos comparables, y tienen que elegir una estrategia para convertirse en el estándar del mercado. Si ambas empresas están de acuerdo con la tecnología elegida, se esperan altas ventas para ambas empresas. Si las empresas no están de acuerdo con la tecnología estándar, pocas ventas resultan. Ambas estrategias son equilibrios de Nash del juego.
Conducir en una carretera contra un automóvil que viene en sentido contrario y tener que elegir entre virar a la izquierda o virar a la derecha de la carretera, también es un juego de coordinación. Por ejemplo, con las recompensas 10 que significan ningún accidente y 0 que significa un accidente, el juego de coordinación se puede definir con la siguiente matriz de recompensas:
Conductor 2 Conductor 1 | Maneja por la izquierda | Conduce por la derecha |
---|---|---|
Maneja por la izquierda | 10 10 | 0 0 |
Conduce por la derecha | 0 0 | 10 10 |
En este caso, hay dos equilibrios de Nash de estrategia pura, cuando ambos eligen conducir a la izquierda o a la derecha. Si admitimos estrategias mixtas (donde se elige una estrategia pura al azar, sujeta a alguna probabilidad fija), entonces hay tres equilibrios de Nash para el mismo caso: dos que hemos visto en la forma de estrategia pura, donde las probabilidades son (0 %, 100%) para el jugador uno, (0%, 100%) para el jugador dos; y (100%, 0%) para el jugador uno, (100%, 0%) para el jugador dos respectivamente. Agregamos otro donde las probabilidades para cada jugador son (50%, 50%).
Tráfico de red
Una aplicación de los equilibrios de Nash consiste en determinar el flujo de tráfico esperado en una red. Considere el gráfico de la derecha. Si asumimos que hay x "coches" viajando de A a D, ¿cuál es la distribución esperada del tráfico en la red?
Esta situación se puede modelar como un "juego" en el que cada viajero tiene una opción de 3 estrategias, donde cada estrategia es una ruta de A a D (una de ABD , ABCD o ACD ). La "recompensa" de cada estrategia es el tiempo de viaje de cada ruta. En el gráfico de la derecha, un automóvil que viaja por ABD experimenta un tiempo de viaje de (1+ x / 100) +2 , donde x es el número de automóviles que viajan por el borde AB . Por lo tanto, los beneficios de cualquier estrategia determinada dependen de las elecciones de los otros jugadores, como es habitual. Sin embargo, el objetivo, en este caso, es minimizar el tiempo de viaje, no maximizarlo. El equilibrio se producirá cuando el tiempo en todos los caminos sea exactamente el mismo. Cuando eso sucede, ningún conductor tiene ningún incentivo para cambiar de ruta, ya que solo puede aumentar su tiempo de viaje. Para el gráfico de la derecha, si, por ejemplo, 100 automóviles viajan de A a D, el equilibrio se producirá cuando 25 conductores viajen por ABD , 50 por ABCD y 25 por ACD . Cada conductor ahora tiene un tiempo de viaje total de 3.75 (para ver esto, tenga en cuenta que un total de 75 autos toman el borde AB , y de la misma manera, 75 autos toman el borde CD ).
Tenga en cuenta que esta distribución no es, en realidad, socialmente óptima. Si los 100 autos estuvieran de acuerdo en que 50 viajan por ABD y los otros 50 por ACD , entonces el tiempo de viaje para cualquier auto individual sería en realidad 3.5, que es menos de 3.75. Este también es el equilibrio de Nash si se elimina la ruta entre B y C, lo que significa que agregar otra ruta posible puede disminuir la eficiencia del sistema, un fenómeno conocido como paradoja de Braess .
Juego de competición
Jugador 2 Jugador 1 | Elija '0' | Elija '1' | Elija '2' | Elija '3' |
---|---|---|---|---|
Elija '0' | 0 , 0 | 2 , −2 | 2 , −2 | 2 , −2 |
Elija '1' | −2 , 2 | 1 , 1 | 3 , −1 | 3 , −1 |
Elija '2' | −2 , 2 | −1 , 3 | 2 , 2 | 4 , 0 |
Elija '3' | −2 , 2 | −1 , 3 | 0 , 4 | 3 , 3 |
Esto se puede ilustrar con un juego de dos jugadores en el que ambos jugadores eligen simultáneamente un número entero de 0 a 3 y ambos ganan el menor de los dos números en puntos. Además, si un jugador elige un número mayor que el otro, tendrá que ceder dos puntos al otro.
Este juego tiene un equilibrio de Nash de estrategia pura único: ambos jugadores eligen 0 (resaltado en rojo claro). Cualquier otra estrategia puede mejorarse si un jugador cambia su número a uno menos que el del otro jugador. En la mesa adyacente, si el juego comienza en el cuadrado verde, al jugador 1 le interesa moverse al cuadrado morado y al jugador 2 le interesa moverse al cuadrado azul. Aunque no se ajusta a la definición de un juego de competición, si el juego se modifica de modo que los dos jugadores ganen la cantidad indicada si ambos eligen el mismo número y, de lo contrario, no ganan nada, entonces hay 4 equilibrios de Nash: (0,0 ), (1,1), (2,2) y (3,3).
Equilibrios de Nash en una matriz de pagos
Existe una forma numérica fácil de identificar los equilibrios de Nash en una matriz de pagos. Es especialmente útil en juegos de dos personas donde los jugadores tienen más de dos estrategias. En este caso, el análisis formal puede resultar demasiado largo. Esta regla no se aplica al caso en el que las estrategias mixtas (estocásticas) sean de interés. La regla es la siguiente: si el primer número de pago, en el par de pago de la celda, es el máximo de la columna de la celda y si el segundo número es el máximo de la fila de la celda, entonces la celda representa un Nash equilibrio.
Jugador 2 Jugador 1 | Opcion A | Opción B | Opción C |
---|---|---|---|
Opcion A | 0, 0 | 25, 40 | 5, 10 |
Opción B | 40, 25 | 0, 0 | 5, 15 |
Opción C | 10, 5 | 15, 5 | 10, 10 |
Podemos aplicar esta regla a una matriz de 3 × 3:
Usando la regla, podemos ver muy rápidamente (mucho más rápido que con el análisis formal) que las celdas de equilibrio de Nash son (B, A), (A, B) y (C, C). De hecho, para la celda (B, A) 40 es el máximo de la primera columna y 25 es el máximo de la segunda fila. Para (A, B) 25 es el máximo de la segunda columna y 40 es el máximo de la primera fila. Lo mismo para la celda (C, C). Para otras celdas, uno o ambos miembros duplet no son el máximo de las filas y columnas correspondientes.
Dicho esto, la mecánica real de encontrar celdas de equilibrio es obvia: encuentre el máximo de una columna y verifique si el segundo miembro del par es el máximo de la fila. Si se cumplen estas condiciones, la celda representa un equilibrio de Nash. Verifique todas las columnas de esta manera para encontrar todas las celdas NE. Una matriz N × N puede tener entre 0 y N × N equilibrios de Nash de estrategia pura .
Estabilidad
El concepto de estabilidad , útil en el análisis de muchos tipos de equilibrios, también se puede aplicar a los equilibrios de Nash.
Un equilibrio de Nash para un juego de estrategia mixta es estable si un pequeño cambio (específicamente, un cambio infinitesimal) en las probabilidades de un jugador conduce a una situación en la que se cumplen dos condiciones:
- el jugador que no cambió no tiene mejor estrategia en la nueva circunstancia
- el jugador que cambió ahora está jugando con una estrategia estrictamente peor.
Si ambos casos se cumplen, entonces un jugador con el pequeño cambio en su estrategia mixta regresará inmediatamente al equilibrio de Nash. Se dice que el equilibrio es estable. Si la condición uno no se cumple, el equilibrio es inestable. Si solo se cumple la condición uno, es probable que haya un número infinito de estrategias óptimas para el jugador que cambió.
En el ejemplo anterior del "juego de conducción" hay equilibrios estables e inestables. Los equilibrios que involucran estrategias mixtas con 100% de probabilidades son estables. Si alguno de los jugadores cambia ligeramente sus probabilidades, ambos estarán en desventaja y su oponente no tendrá ninguna razón para cambiar su estrategia a su vez. El equilibrio (50%, 50%) es inestable. Si alguno de los jugadores cambia sus probabilidades (lo que no beneficiaría ni dañaría las expectativas del jugador que hizo el cambio, si la estrategia mixta del otro jugador sigue siendo (50%, 50%)), entonces el otro jugador tiene inmediatamente una mejor estrategia en ya sea (0%, 100%) o (100%, 0%).
La estabilidad es crucial en las aplicaciones prácticas de los equilibrios de Nash, ya que la estrategia mixta de cada jugador no se conoce perfectamente, pero debe inferirse de la distribución estadística de sus acciones en el juego. En este caso, es muy poco probable que surjan equilibrios inestables en la práctica, ya que cualquier cambio mínimo en las proporciones de cada estrategia vista conducirá a un cambio de estrategia y la ruptura del equilibrio.
El equilibrio de Nash define la estabilidad solo en términos de desviaciones unilaterales. En los juegos cooperativos, este concepto no es suficientemente convincente. El equilibrio de Nash fuerte permite desviaciones por parte de todas las coaliciones imaginables. [18] Formalmente, un equilibrio de Nash fuerte es un equilibrio de Nash en el que ninguna coalición, tomando las acciones de sus complementos como dadas, puede desviarse cooperativamente de una manera que beneficie a todos sus miembros. [19] Sin embargo, el concepto fuerte de Nash a veces se percibe como demasiado "fuerte" en el sentido de que el entorno permite una comunicación privada ilimitada. De hecho, el equilibrio de Nash fuerte tiene que ser Pareto eficiente . Como resultado de estos requisitos, un Nash fuerte es demasiado raro para ser útil en muchas ramas de la teoría de juegos. Sin embargo, en juegos como elecciones con muchos más jugadores que posibles resultados, puede ser más común que un equilibrio estable.
Un equilibrio de Nash refinado conocido como equilibrio de Nash a prueba de coaliciones (CPNE) [18] ocurre cuando los jugadores no pueden hacerlo mejor incluso si se les permite comunicarse y hacer un acuerdo "autoaplicable" para desviarse. Cada estrategia correlacionada apoyada por un dominio estricto iterado y en la frontera de Pareto es un CPNE. [20] Además, es posible que un juego tenga un equilibrio de Nash que sea resistente contra coaliciones menores que un tamaño específico, k. CPNE está relacionado con la teoría del núcleo .
Finalmente, en los años ochenta, basándose con gran profundidad en estas ideas , se introdujeron los equilibrios estables de Mertens como concepto de solución . Mertens equilibrios estables satisfacen tanto la inducción hacia adelante y la inducción hacia atrás . En un contexto de teoría de juegos, los equilibrios estables ahora se refieren generalmente a los equilibrios estables de Mertens.
Ocurrencia
Si un juego tiene un equilibrio de Nash único y se juega entre jugadores bajo ciertas condiciones, entonces se adoptará el conjunto de estrategias NE. Las condiciones suficientes para garantizar que se juega el equilibrio de Nash son:
- Todos los jugadores harán todo lo posible para maximizar la recompensa esperada como se describe en el juego.
- Los jugadores son impecables en la ejecución.
- Los jugadores tienen suficiente inteligencia para deducir la solución.
- Los jugadores conocen la estrategia de equilibrio planificada de todos los demás jugadores.
- Los jugadores creen que una desviación en su propia estrategia no provocará desviaciones por parte de otros jugadores.
- Es de conocimiento común que todos los jugadores cumplen estas condiciones, incluida esta. Por lo tanto, cada jugador no solo debe saber que los otros jugadores cumplen las condiciones, sino que también deben saber que todos saben que las cumplen y que saben que saben que las cumplen, y así sucesivamente.
Donde no se cumplen las condiciones
Ejemplos de problemas de teoría de juegos en los que no se cumplen estas condiciones:
- La primera condición no se cumple si el juego no describe correctamente las cantidades que un jugador desea maximizar. En este caso, no hay ninguna razón particular para que ese jugador adopte una estrategia de equilibrio. Por ejemplo, el dilema del prisionero no es un dilema si alguno de los jugadores está feliz de ser encarcelado indefinidamente.
- Defectos intencionales o accidentales en la ejecución. Por ejemplo, una computadora capaz de un juego lógico impecable frente a una segunda computadora impecable resultará en equilibrio. La introducción de la imperfección conducirá a su alteración, ya sea por la pérdida del jugador que comete el error, o por la negación del criterio de conocimiento común que conduce a una posible victoria para el jugador. (Un ejemplo sería un jugador que repentinamente ponga el auto en reversa en el juego de la gallina , asegurando un escenario sin pérdidas y sin victoria).
- En muchos casos, la tercera condición no se cumple porque, aunque el equilibrio debe existir, se desconoce debido a la complejidad del juego, por ejemplo en el ajedrez chino . [21] O, si se conoce, es posible que no todos los jugadores lo sepan, como cuando se juega al tic-tac-toe con un niño pequeño que desea desesperadamente ganar (cumpliendo los otros criterios).
- El criterio de conocimiento común puede no cumplirse incluso si todos los jugadores cumplen, de hecho, todos los demás criterios. Los jugadores que desconfían erróneamente de la racionalidad de los demás pueden adoptar estrategias contrarias al juego irracional esperado en nombre de sus oponentes. Ésta es una consideración importante en el " pollo " o una carrera armamentista , por ejemplo.
Donde se cumplen las condiciones
En su Ph.D. En su disertación, John Nash propuso dos interpretaciones de su concepto de equilibrio, con el objetivo de mostrar cómo los puntos de equilibrio pueden conectarse con fenómenos observables.
(...) Una interpretación es racionalista: si asumimos que los jugadores son racionales, conocen la estructura completa del juego, el juego se juega solo una vez y solo hay un equilibrio de Nash, entonces los jugadores jugarán de acuerdo con ese equilibrio .
Esta idea fue formalizada por Aumann, R. y A. Brandenburger, 1995, Condiciones epistémicas para el equilibrio de Nash , Econometrica, 63, 1161-1180, quienes interpretaron la estrategia mixta de cada jugador como una conjetura sobre el comportamiento de otros jugadores y demostraron que si el juego y la racionalidad de los jugadores se conocen mutuamente y estas conjeturas se conocen comúnmente, entonces las conjeturas deben ser un equilibrio de Nash (se necesita una suposición previa común para este resultado en general, pero no en el caso de dos jugadores. En este caso, las conjeturas sólo necesitan conocerse mutuamente).
Una segunda interpretación, a la que Nash se refirió con la interpretación de acción masiva, es menos exigente para los jugadores:
[i] Es innecesario suponer que los participantes tienen pleno conocimiento de la estructura total del juego, o la capacidad e inclinación para pasar por cualquier proceso de razonamiento complejo. Lo que se asume es que existe una población de participantes para cada posición en el juego, que será jugada a lo largo del tiempo por participantes seleccionados al azar de las diferentes poblaciones. Si existe una frecuencia promedio estable con la cual cada estrategia pura es empleada por el miembro promedio de la población apropiada, entonces esta frecuencia promedio estable constituye un equilibrio de Nash de estrategia mixta.
Para obtener un resultado formal en este sentido, consulte Kuhn, H. y et al., 1996, "The Work of John Nash in Game Theory", Journal of Economic Theory , 69, 153-185.
Debido a las condiciones limitadas en las que se puede observar la NE, rara vez se trata como una guía para el comportamiento diario, o se observa en la práctica en las negociaciones humanas. Sin embargo, como concepto teórico en economía y biología evolutiva , la EN tiene poder explicativo. La recompensa en economía es la utilidad (o, a veces, el dinero), y en biología evolutiva es la transmisión genética; ambos son el resultado fundamental de la supervivencia. Los investigadores que aplican la teoría de los juegos en estos campos afirman que las estrategias que no maximicen estos por cualquier motivo serán competidas por el mercado o el entorno, a los que se les atribuye la capacidad de probar todas las estrategias. Esta conclusión se extrae de la teoría de la " estabilidad " anterior. En estas situaciones, la suposición de que la estrategia observada es en realidad una EN a menudo ha sido confirmada por la investigación. [22]
NE y amenazas no creíbles
El equilibrio de Nash es un superconjunto del equilibrio de Nash perfecto en subjuegos. El equilibrio perfecto en subjuegos además del equilibrio de Nash requiere que la estrategia también sea un equilibrio de Nash en todos los subjuegos de ese juego. Esto elimina todas las amenazas no creíbles , es decir, las estrategias que contienen movimientos no racionales para hacer que el contrajugador cambie su estrategia.
La imagen de la derecha muestra un juego secuencial simple que ilustra el problema con los equilibrios de Nash imperfectos en subjuegos. En este juego, el jugador uno elige izquierda (L) o derecha (R), a lo que le sigue el llamado al jugador dos para que sea amable (K) o desagradable (U) con el jugador uno.Sin embargo, el jugador dos solo se beneficia de ser desagradable si el jugador uno va a la izquierda. Si el jugador uno va bien, el jugador racional dos sería de facto amable con él / ella en ese subjuego. Sin embargo, la amenaza no creíble de ser cruel en 2 (2) sigue siendo parte del equilibrio azul de Nash (L, (U, U)). Por lo tanto, si ambas partes pueden esperar un comportamiento racional, el equilibrio de Nash perfecto en subjuegos puede ser un concepto de solución más significativo cuando surgen tales inconsistencias dinámicas .
Prueba de existencia
Prueba usando el teorema del punto fijo de Kakutani
La demostración original de Nash (en su tesis) usó el teorema del punto fijo de Brouwer (por ejemplo, ver una variante a continuación). Damos una demostración más simple a través del teorema de punto fijo de Kakutani , siguiendo el artículo de Nash de 1950 (le da crédito a David Gale con la observación de que tal simplificación es posible).
Para demostrar la existencia de un equilibrio de Nash, sea ser la mejor respuesta del jugador i a las estrategias de todos los demás jugadores.
Aquí, , dónde , es un perfil de estrategia mixta en el conjunto de todas las estrategias mixtas y es la función de pago para el jugador i. Definir una función de valor establecido tal que . La existencia de un equilibrio de Nash es equivalente a tener un punto fijo.
El teorema del punto fijo de Kakutani garantiza la existencia de un punto fijo si se cumplen las cuatro condiciones siguientes.
- es compacto, convexo y no vacío.
- no está vacío.
- es hemicontinuo superior
- es convexo.
La condición 1 se satisface por el hecho de que es un simplex y por lo tanto compacto. La convexidad se deriva de la capacidad de los jugadores para mezclar estrategias. no está vacío siempre que los jugadores tengan estrategias.
Las condiciones 2. y 3. se satisfacen mediante el teorema del máximo de Berge . Porque es continuo y compacto, es no vacío y hemicontinuo superior .
La condición 4. se satisface como resultado de estrategias mixtas. Suponer, luego . es decir, si dos estrategias maximizan los beneficios, entonces una combinación entre las dos estrategias producirá el mismo resultado.
Por tanto, existe un punto fijo en y un equilibrio de Nash. [23]
Cuando Nash le comentó este punto a John von Neumann en 1949, von Neumann lo descartó con las palabras: "Eso es trivial, ya sabes. Eso es solo un teorema de punto fijo ". (Véase Nasar, 1998, p. 94.)
Prueba alternativa usando el teorema del punto fijo de Brouwer
Tenemos un juego dónde es el número de jugadores y es el conjunto de acciones para los jugadores. Todos los conjuntos de acciónson finitos. Dejardenotar el conjunto de estrategias mixtas para los jugadores. La finitud de las asegura la compacidad de .
Ahora podemos definir las funciones de ganancia. Por una estrategia mixta, dejamos la ganancia para el jugador en acción ser
La función de ganancia representa el beneficio que obtiene un jugador al cambiar unilateralmente su estrategia. Ahora definimos dónde
por . Vemos eso
A continuación definimos:
Es fácil ver que cada es una estrategia mixta válida en . También es fácil comprobar que cada es una función continua de , y por lo tanto es una función continua. Como producto cruzado de un número finito de conjuntos convexos compactos,también es compacto y convexo. Aplicando el teorema del punto fijo de Brouwer a y concluimos que tiene un punto fijo en , llámalo . Afirmamos que es un equilibrio de Nash en . Para ello, basta con demostrar que
Esto simplemente establece que cada jugador no obtiene ningún beneficio al cambiar unilateralmente su estrategia, que es exactamente la condición necesaria para un equilibrio de Nash.
Ahora suponga que las ganancias no son todas cero. Por lo tanto, y tal que . Tenga en cuenta entonces que
Entonces deja
También denotaremos como el vector de ganancia indexado por acciones en . Desde es el punto fijo que tenemos:
Desde tenemos eso es una escala positiva del vector . Ahora afirmamos que
Para ver esto, primero notamos que si entonces esto es cierto por definición de la función de ganancia. Ahora asuma que. Por nuestras declaraciones anteriores tenemos que
y entonces el término de la izquierda es cero, lo que nos da que la expresión completa es según sea necesario.
Entonces finalmente tenemos eso
donde sigue la última desigualdad desde es un vector distinto de cero. Pero esta es una clara contradicción, por lo que todas las ganancias deben ser cero. Por lo tanto, es un equilibrio de Nash para según sea necesario.
Calcular los equilibrios de Nash
Si un jugador A tiene una estrategia dominante entonces existe un equilibrio de Nash en el que A juega . En el caso de dos jugadores A y B, existe un equilibrio de Nash en el que A juega y B tiene una mejor respuesta a . Si es una estrategia estrictamente dominante, A juega en todos los equilibrios de Nash. Si tanto A como B tienen estrategias estrictamente dominantes, existe un equilibrio de Nash único en el que cada uno juega su estrategia estrictamente dominante.
En juegos con equilibrios de Nash de estrategia mixta, la probabilidad de que un jugador elija cualquier estrategia particular (tan pura) se puede calcular asignando una variable a cada estrategia que represente una probabilidad fija de elegir esa estrategia. Para que un jugador esté dispuesto a aleatorizar, su recompensa esperada para cada estrategia (pura) debe ser la misma. Además, la suma de las probabilidades para cada estrategia de un jugador en particular debe ser 1. Esto crea un sistema de ecuaciones a partir del cual se pueden derivar las probabilidades de elegir cada estrategia. [14]
Ejemplos de
Jugador B Jugador A | El jugador B juega H | El jugador B juega T |
---|---|---|
El jugador A juega H | −1, +1 | +1, −1 |
El jugador A juega T | +1, −1 | −1, +1 |
En el juego de emparejar monedas de un centavo, el jugador A pierde un punto frente a B si A y B juegan la misma estrategia y gana un punto de B si juegan estrategias diferentes. Para calcular el equilibrio de Nash de estrategia mixta, asigne a A la probabilidad p de jugar H y (1− p ) de jugar T, y asigne a B la probabilidad q de jugar H y (1− q ) de jugar T.
- E [pago por A jugando H] = (−1) q + (+1) (1− q ) = 1−2 q
- E [pago por A jugando T] = (+1) q + (−1) (1− q ) = 2 q −1
- E [recompensa por A jugando H] = E [recompensa por A jugando T] ⇒ 1−2 q = 2 q −1 ⇒ q = 1/2
- E [pago por B jugando H] = (+1) p + (−1) (1− p ) = 2 p −1
- E [pago por B jugando T] = (−1) p + (+1) (1− p ) = 1−2 p
- E [recompensa por B jugando H] = E [recompensa por B jugando T] ⇒ 2 p −1 = 1−2 p ⇒ p = 1/2
Por lo tanto, un equilibrio de Nash de estrategia mixta, en este juego, es que cada jugador elija al azar H o T con p = 1/2 yq = 1/2.
La rareza de los puntos de equilibrio
En 1971, a Robert Wilson se le ocurrió el Teorema de la rareza [24] diciendo que casi todos los juegos finitos tienen un número finito de soluciones que es impar. En 1993, Harsanyi también publicó un artículo para respaldar el teorema. [25] Por ejemplo, el dilema del prisionero (1), la batalla de los sexos (3) y la caza del ciervo (3). Todos estos juegos tienen un número impar de equilibrios de Nash.
Los juegos rara vez tienen un número infinito o un número par. El dominio débil suele ser el culpable. Por ejemplo, el juego de dinero gratis, donde dos jugadores tienen que aceptar votar sí para obtener la recompensa y los votos son simultáneos y ciegos, tiene dos equilibrios de Nash, que son (sí, sí) y (no, no), mientras que (no, no) es un equilibrio de Nash débil. Tres equilibrios de Nash totales hacen de este un juego típico.
Jugador B Jugador A | sí | No |
---|---|---|
sí | 1, 1 | 0, 0 |
No | 0, 0 | 0, 0 |
Ver también
- Procedimiento ganador ajustado
- Teoría de la complementariedad
- Investigación de resolución de conflictos
- Cooperación : proceso de grupos de organismos que trabajan o actúan juntos para obtener un beneficio común, mutuo o algún beneficio subyacente.
- Selección de equilibrio
- Estrategia evolutivamente estable : estrategia que, si la adopta una población en un entorno determinado, no puede ser invadida por ninguna estrategia alternativa que inicialmente sea rara.
- Glosario de teoría de juegos : lista de definiciones de términos y conceptos utilizados en la teoría de juegos
- Ley de Hotelling
- Equilibrio de Nash manipulado
- Enfrentamiento mexicano : confrontación entre dos o más partes en la que ningún participante puede avanzar o retirarse sin estar expuesto al peligro.
- Teorema de Minimax : proporciona condiciones que garantizan que la desigualdad máxima-mínima también es una igualdad
- Destrucción mutua asegurada - Doctrina de estrategia militar
- Programación matemática extendida para problemas de equilibrio
- Contrato óptimo y contrato a la par
- Equilibrio autoconfirmante
- Concepto de solución
- Competencia Stackelberg - Modelo económico
- Principio de Wardrop
Notas
- ^ Osborne, Martin J .; Rubinstein, Ariel (12 de julio de 1994). Un curso de teoría de juegos . Cambridge, MA: MIT. pag. 14. ISBN 9780262150415.
- ^ Kreps DM (1987) "Equilibrio de Nash". En: Palgrave Macmillan (eds) The New Palgrave Dictionary of Economics . Palgrave Macmillan, Londres.
- ^ Schelling, Thomas, La estrategia del conflicto , copyright 1960, 1980, Harvard University Press, ISBN 0-674-84031-3 .
- ^ De Fraja, G .; Oliveira, T .; Zanchi, L. (2010). "Debe esforzarse más: evaluar el papel del esfuerzo en el logro educativo". Revisión de Economía y Estadística . 92 (3): 577. doi : 10.1162 / REST_a_00013 .
- ^ Ward, H. (1996). "Teoría de juegos y la política del calentamiento global: el estado del juego y más allá". Estudios Políticos . 44 (5): 850–871. doi : 10.1111 / j.1467-9248.1996.tb00338.x .,
- ^ Thorpe, Robert B .; Jennings, Simon; Dolder, Paul J. (2017). "Riesgos y beneficios de obtener un rendimiento bastante bueno en pesquerías mixtas de múltiples especies" . Revista ICES de Ciencias Marinas . 74 (8): 2097–2106. doi : 10.1093 / icesjms / fsx062 .,
- ^ "Lecciones de marketing del Dr. Nash - Andrew Frank" . 2015-05-25 . Consultado el 30 de agosto de 2015 .
- ^ Chiappori, P. -A .; Levitt, S .; Groseclose, T. (2002). "Prueba de equilibrios de estrategia mixta cuando los jugadores son heterogéneos: el caso de los tiros penales en el fútbol" (PDF) . American Economic Review . 92 (4): 1138. CiteSeerX 10.1.1.178.1646 . doi : 10.1257 / 00028280260344678 .
- ^ Djehiche, B .; Tcheukam, A .; Tembine, H. (2017). "Un juego de evacuación de campo medio en edificio multinivel". Transacciones IEEE sobre control automático . 62 (10): 5154–5169. doi : 10.1109 / TAC.2017.2679487 . ISSN 0018-9286 .
- ^ Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (27 de septiembre de 2017). "Juegos de tipo campo medio en ingeniería". AIMS Electrónica e Ingeniería Eléctrica . 1 : 18–73. arXiv : 1605.03281 . doi : 10.3934 / ElectrEng.2017.1.18 .
- ^ Cournot A. (1838) Investiga sobre los principios matemáticos de la teoría de la riqueza
- ^ J. Von Neumann, O. Morgenstern, Teoría de los juegos y comportamiento económico , copyright 1944, 1953, Princeton University Press
- ^ Carmona, Guilherme; Podczeck, Konrad (2009). "Sobre la existencia de equilibrios de Nash de estrategia pura en juegos grandes" (PDF) . Revista de teoría económica . 144 (3): 1300-1319. doi : 10.1016 / j.jet.2008.11.009 . SSRN 882466 .
- ^ a b von Ahn, Luis. "Preliminares de la teoría de juegos" (PDF) . Archivado desde el original (PDF) el 18 de octubre de 2011 . Consultado el 7 de noviembre de 2008 .
- ^ La definición es estándar; véase, por ejemplo, Fudenberg y Tirole, pág. 11.
- ^ "Equilibrios de Nash" . hoylab.cornell.edu . Consultado el 8 de diciembre de 2019 .
- ^ MIT OpenCourseWare. 6.254: Teoría de juegos con aplicaciones de ingeniería, primavera de 2010. Clase 6: Juegos continuos y discontinuos .
- ^ a b BD Bernheim; B. Peleg; MD Whinston (1987), "Coalition-Proof Equilibria I. Concepts", Journal of Economic Theory , 42 (1): 1-12, doi : 10.1016 / 0022-0531 (87) 90099-8 .
- ^ Aumann, R. (1959). "Puntos aceptables en juegos cooperativos generales de n-personas". Contribuciones a la teoría de los juegos . IV . Princeton, Nueva Jersey: Princeton University Press. ISBN 978-1-4008-8216-8.
- ^ D. Moreno; J. Wooders (1996), "Equilibrio a prueba de coaliciones" (PDF) , Games and Economic Behavior , 17 (1): 80-112, doi : 10.1006 / game.1996.0095 , hdl : 10016/4408 .
- ^ TL Turocy, B. Von Stengel, Game Theory , copyright 2001, Texas A&M University, London School of Economics, páginas 141-144. Nash demostró que existe un NE perfecto para este tipo de juego de forma extensiva finita [ cita requerida ] - se puede representar como una estrategia que cumple con sus condiciones originales para un juego con un NE. Es posible que tales juegos no tengan un NE único, pero al menos una de las muchas estrategias de equilibrio la jugarían jugadores hipotéticos que tuvieran un conocimiento perfecto de los 10 150 árboles de juego [ cita requerida ] .
- ^ JC Cox, M. Walker, Learning to Play Cournot Duoploy Strategies Archivado el 11 de diciembre de 2013 en Wayback Machine , copyright 1997, Texas A&M University, Universidad de Arizona, páginas 141-144
- ^ Fudenburg, Drew; Tirole, Jean (1991). Teoría de juegos . MIT Press. ISBN 978-0-262-06141-4.
- ^ Wilson, Robert (1 de julio de 1971). "Equilibrios de cálculo de juegos de N-Person" . Revista SIAM de Matemática Aplicada . 21 (1): 80–87. doi : 10.1137 / 0121011 . ISSN 0036-1399 .
- ^ Harsanyi, JC (1 de diciembre de 1973). "La rareza del número de puntos de equilibrio: una nueva prueba" . Revista Internacional de Teoría de Juegos . 2 (1): 235–250. doi : 10.1007 / BF01737572 . ISSN 1432-1270 .
Referencias
Libros de texto de teoría de juegos
- Dixit, Avinash, Susan Skeath y David Reiley. Juegos de estrategia. WW Norton & Company. (Tercera edición en 2009)
- Dutta, Prajit K. (1999), Estrategias y juegos: teoría y práctica , MIT Press , ISBN 978-0-262-04169-0. Adecuado para estudiantes de pregrado y negocios.
- Fudenberg, Drew y Jean Tirole (1991) Game Theory MIT Press.
- 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 el Capítulo 2. Gratis en línea en muchas universidades.
- Morgenstern, Oskar y John von Neumann (1947) La teoría de los juegos y el comportamiento económico Princeton University Press
- Myerson, Roger B. (1997), Teoría de juegos: análisis del conflicto , Harvard University Press , ISBN 978-0-674-34116-6
- Papayoanou, Paul (2010), Game Theory for Business: A Primer in Strategic Gaming , Probabilistic Publishing , ISBN 978-0964793873
- Rubinstein, Ariel ; Osborne, Martin J. (1994), Un curso de teoría de juegos , MIT Press , ISBN 978-0-262-65040-3. Una introducción moderna a nivel de posgrado.
- 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 el Capítulo 3. Descarga gratuita en línea .
- Gibbons, Robert (1992), teoría de juegos para economistas aplicados , Princeton University Press (13 de julio de 1992), ISBN 978-0-691-00395-5. Introducción lúcida y detallada a la teoría de juegos en un contexto explícitamente económico.
- Osborne, Martin (2004), Introducción a la teoría de juegos , Oxford University Press , ISBN 978-0-19-512895-6. Introducción al equilibrio de Nash.
- Binmore, Ken (2007), Playing for Real: A Text on Game Theory , Oxford University Press , ISBN 978-0195300574.
Papeles Nash originales
- Nash, John (1950) "Puntos de equilibrio en juegos de n personas" Actas de la Academia Nacional de Ciencias 36 (1): 48-49.
- Nash, John (1951) "Juegos no cooperativos" The Annals of Mathematics 54 (2): 286-295.
otras referencias
- Mehlmann, A. (2000) ¡ El juego está en marcha! Teoría de juegos en mitos y paradojas , American Mathematical Society .
- Nasar, Sylvia (1998), Una mente hermosa , Simon & Schuster .
enlaces externos
- "Teorema de Nash (en teoría de juegos)" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Prueba completa de la existencia de equilibrios de Nash
- Forma simplificada y resultados relacionados