Equilibrios de Nash P74619

El equilibrio de Nash es uno de los conceptos más famosos de teoría de juegos. Suponed que hay dos jugadores, A y B, que A puede realizar n jugadas, que B puede realizar m jugadas, y que todas las n × m combinaciones son posibles. Si A juega i y B juega j, A gana A_ij y B gana B_ij. Tanto A como B juegan egoístamente, intentando ganar el máximo posible. Los equilibrios de Nash son aquellas posiciones en las que nadie, cambiando sólo él de jugada, puede mejorar su propia recompensa.

A continuación se muestran dos juegos 2 × 2. Por ejemplo, el juego de la izquierda tiene A = (

) y B = (

):

Considerad cada posición del juego de la izquierda:

• En (1, 1) ambos jugadores quieren cambiar a 2. Por ejemplo, si A cambia (y B no lo hace), A pasa de ganar −1 a ganar 0. Para B la situación es simétrica.
• En (1, 2) B no quiere cambiar, pero A quiere jugar 2 para ganar −2 en vez de −3.
• La posición (2, 1) es simétrica a la (1, 2).
• En (2, 2) ni A ni B quieren cambiar, porque ganarían −3 en vez de −2. Por lo tanto, (2, 2) es un equilibrio de Nash.

Un equilibrio de Nash no tiene porqué ser la mejor combinación de jugadas. En el ejemplo, con (1, 1) ambos jugadores ganarían más que con (2, 2). Pero si ambos juegan egoístamente y sin poder negociar, jugarán (2, 2). (Esta tabla se corresponde al dilema del prisionero, donde 1 es callarse y 2 es acusar al otro, y las recompensas son los años de cárcel, en negativo.)

Como se puede ver en la tabla de la derecha, puede haber más de un equilibrio. Esa tabla podría representar dos amigos que tienen que escoger qué película ver, y sólo les importa ver la misma película. En ese caso, tanto (1, 1) como (2, 2) son equilibrios.

Entrada

La entrada tiene diversos casos, cada uno con n ≥ 1 y m ≥ 1, seguidas de n líneas con los m números de la matriz A_ij, seguidas de n líneas con los m números de la matriz B_ij. Todos los números son enteros no mayores que 10⁶ en valor absoluto.

Salida

Para cada caso, escribid el número de equilibrios de Nash. Además, si hay exactamente una solución, escribid otra línea con la jugada de A y la de B.

Puntuación

• test-1:   Casos con n = 1 y m = 1, como el Ejemplo 1.  10 Puntos 

• test-2:   Casos con n ≤ 2 y m ≤ 2.  20 Puntos 

• test-3:   Casos con n ≤ 100 y m ≤ 100, como el Ejemplo 2.  30 Puntos 

• test-4:   Casos con n ≤ 1000 y m ≤ 1000.  40 Puntos