Equilibrios de Nash P74619


Statement
 

pdf   zip

thehtml

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 Aij y B ‍gana Bij. 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 = (

−1−3 
0−2 

) y B = (

−10 
−3−2 

):



||
(A, B)12
1(−1,−1)(−3,0)
2(0,−3)(−2,−2)
||         ||
(A, B)12
1⁠ ⁠(1, 1) ⁠ ⁠⁠ ⁠(0, 0) ⁠ ⁠
2⁠ ⁠(0, 0) ⁠ ⁠⁠ ⁠(1, 1) ⁠ ⁠
||



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 Aij, seguidas de n líneas con los m ‍números de la matriz Bij. Todos los números son enteros no mayores que 106 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 ‍
Public test cases
  • Input

    1 1
    2
    3
    
    1 1
    4
    5
    

    Output

    1
    1 1
    1
    1 1
    
  • Input

    2 2
    -1 -3
    0 -2
    -1 0
    -3 -2
    
    2 2
    0 1
    1 0
    0 1
    1 0
    
    2 2
    0 1
    1 0
    1 0
    0 1
    
    1 3
    1 2 3
    1 1 1
    

    Output

    1
    2 2
    2
    0
    3
    
  • Information
    Author
    Ferran Alet
    Language
    Spanish
    Official solutions
    C++
    User solutions