Juego cóncavo

En teoría de juegos , un juego cóncavo es una generalización del juego en forma normal definido por Rosen. ^{[ 1 ]} Extendió el teorema sobre la existencia de un equilibrio de Nash , que John Nash demostró originalmente para juegos en forma normal, a juegos cóncavos.

Describiremos la generalización paso a paso.

1. En un juego en forma normal, cada jugador i puede elegir una de m _i acciones puras. El conjunto de estrategias disponibles para cada jugador es el conjunto de loterías sobre las acciones puras, que es un simplex en R ^mi .

• En un juego cóncavo, el conjunto de estrategias disponibles para cada jugador puede ser cualquier conjunto convexo en R ^mi .

2. En un juego en forma normal, el conjunto de estrategias disponibles para cada jugador es independiente de las estrategias elegidas por los demás jugadores. Esto significa que el conjunto de todos los perfiles de estrategia posibles (denotado S ) es un producto cartesiano de los conjuntos de estrategias disponibles para los jugadores (en otras palabras, las restricciones sobre las elecciones de cada jugador son ortogonales ).

• En un juego cóncavo, el conjunto de perfiles de estrategia puede ser cualquier conjunto convexo en R ^m (donde m := m ₁ +...+ m _n ). Esto significa que las restricciones en la elección de cada jugador están acopladas : las estrategias disponibles de cada jugador pueden depender de lo que elijan los demás jugadores (dichas "restricciones acopladas" también fueron estudiadas anteriormente por Debreu ^{[ 2 ]} ).

3. En un juego en forma normal, la función de utilidad de cada jugador i (denotada u _i - una función de valor real en S ) es una función lineal en cada uno de sus componentes, para cualquier valor fijo de los otros componentes (para cada agente j , dada cualquier elección de estrategias por parte de los otros agentes, la recompensa del agente i es una función lineal en las probabilidades por las cuales el agente j elige sus acciones puras).

• En un juego cóncavo, cada u _i puede ser cualquier función continua que sea cóncava en la estrategia del agente i .
• Para enunciar esta propiedad de forma más explícita, fijemos algunas estrategias para todos los jugadores excepto i ; denotémoslas por x ₁ ,...,x _i-1 ,x _i+1 ,...,x _n , o usando la notación abreviada x _-i . Fijemos algunas dos estrategias posibles para el jugador i ; denotémoslas por x _i , y _i , de modo que tanto ( x _i , x _-i ) como ( y _i ,x _-i ) estén en S. Elija algún valor t en [0,1]. Nótese que, dado que S es convexo, toda combinación convexa de x _i , y _i también está en S ; en particular, (1- t )* x _i + t * y _i está en S . El requisito de concavidad es que u _i [(1- t )* x _i + t * y _i ] ≥ (1- t )* u _i ( x _i ) + t * u _i ( y _i ).

Si se cumplen las condiciones anteriores (es decir, el espacio S de posibles perfiles de estrategia es convexo, y cada función de pago u _i es continua en las estrategias de todos los jugadores y cóncava en la estrategia del jugador i ), entonces existe un equilibrio de Nash. ^{[ 1 ] : Thm.1} La demostración utiliza el teorema del punto fijo de Kakutani .

Rosen también demostró que, bajo ciertas condiciones técnicas que incluyen una concavidad estricta, el equilibrio es único. Dichas condiciones se explican a continuación.

Supongamos que el espacio S de perfiles de estrategia permitidos está definido por algunas k funciones (que representan restricciones), es decir,${\displaystyle S=\{x\in \mathbb {R} ^{m}|h_{1}(x)\geq 0,\ldots ,h_{k}(x)\geq 0\}}$En un juego en forma normal, las funciones de restricción son funciones lineales que definen los simpices de los jugadores; en un juego cóncavo, h _j puede ser cualquier función cóncava de x. Para la prueba de unicidad, también se requiere que cada h _j tenga derivadas primeras continuas en cualquier x de S.

Supongamos también que, para cada jugador i , la función de utilidad u _i tiene derivadas primeras continuas en las componentes de x _i (es decir, la utilidad de cada jugador es continuamente diferenciable en la propia estrategia del jugador).

Para cualquier vector positivo fijo r > 0 en R ⁿ , defina la suma ponderada por r de las ganancias de los jugadores:

${\displaystyle f(x,r):=r\cdot u(x)=\sum _{i=1}^{n}r_{i}\cdot u_{i}(x)}$.

Defina el pseudogradiente de f:

${\displaystyle g(x,r):=[r_{1}\cdot \bigtriangledown _{1}u_{1}(x),\ldots ,r_{n}\cdot \bigtriangledown _{n}u_{n}(x)]}$

dónde${\displaystyle \bigtriangledown _{i}u_{i}(x)}$es el gradiente de u _i con respecto a las componentes x _{i . Entonces}${\displaystyle \bigtriangledown _{i}u_{i}(x)}$es un vector en R ^mi y g(x,r) es un vector en R ^m .

Decimos que f es diagonalmente estrictamente cóncava en r si para todo x,y en S :${\displaystyle (yx)\cdot g(x,r)+(xy)\cdot g(y,r)>0}$

• Para conjuntos de restricciones ortogonales , si existe algún r>0 para el cual f es estrictamente cóncava diagonalmente en r , entonces el juego cóncavo tiene un equilibrio único . ^{[ 1 ] : Teorema 2}
• Para conjuntos de restricciones acopladas , si existe un subconjunto convexo Q de R ^m tal que, para cada r en Q , f es diagonalmente estrictamente cóncava en r , entonces para cada r en Q , el juego tiene un único equilibrio r -normalizado (un equilibrio donde los multiplicadores de Lagrange tienen la misma proporción que r ). ^{[ 1 ] : Teorema 3}

Una condición suficiente para que f sea estrictamente cóncava diagonalmente en r es que la matriz simétrica G ( x , r )+ G ^T ( x , r ) sea definida negativa. ^{[ 1 ] : Thm.5} Véase el artículo para un ejemplo de juegos bimatriciales .

Consideremos un modelo dinámico de un juego cóncavo en el que cada jugador cambia su estrategia de tal manera que el perfil de estrategias permanece en S y, sujeto a ello, su utilidad aumenta. Cada jugador i cambia su estrategia a una tasa r _i en la dirección del gradiente que define el máximo aumento de utilidad sujeto a las restricciones. Esto da como resultado un conjunto de n ecuaciones diferenciales . Para cualquier juego cóncavo y cualquier punto de partida en S, este conjunto de ecuaciones diferenciales tiene una solución continua x(t) que permanece en S para todo t>0. ^{[ 1 ] : Teorema 7}

Si, además, la matriz x G ( x , r )+ G ^T ( x , r ) es definida negativa para todo x en S , entonces la solución x ( t ) converge a un punto de equilibrio cuando t tiende a infinito. ^{[ 1 ] : Teorema 8}

Si, además, la matriz x G ( x , r )+ G ^T ( x , r ) es definida negativa para todo x en S , entonces la solución x ( t ) converge al único punto de equilibrio r -normalizado. ^{[ 1 ] : Teorema 9}

Takashi Ui ^{[ 3 ]} demuestra que la misma condición que garantiza la unicidad de un equilibrio de Nash también garantiza la unicidad de un equilibrio correlacionado . Además, una condición aún más débil garantiza la unicidad de un equilibrio correlacionado, una generalización de una condición demostrada por Abraham Neyman . ^{[ 4 ]}

Basándonos en los resultados anteriores, es posible calcular puntos de equilibrio para juegos cóncavos utilizando métodos de gradiente para optimización convexa . ^{[ 1 ]}

Flåm y Ruszczyński ^{[ 10 ]} definen un juego convexo-cóncavo. Este es un juego en el que el espacio S de perfiles de estrategia es convexo, como en la definición de Rosen. Pero en lugar de requerir suavidad y otras condiciones sobre g ( x , r ), permiten datos no suaves y solo requieren que la siguiente función sea convexa en x y cóncava en y : ${\displaystyle L(r,x,y):=\sum _{i=1}^{n}r_{i}\cdot u_{i}(x)-u_{i}(y_{i},x_{-i})}$.

Para este tipo de juegos convexo-cóncavos, presentan dos algoritmos para encontrar equilibrios, ambos utilizando regularizaciones parciales y proyecciones de subgradiente relajadas. Demuestran que estos algoritmos convergen.

• Cálculo del equilibrio de Nash
• Obra de teatro ficticia
• dinámica de mejor respuesta
• Método del punto de silla : un método para encontrar puntos máximos y mínimos.