내시 균형

두 참가자 $A$와 $B$가 벌이는 2인 정규형 게임(normal-form game)은 다음 네 가지로 완전히 정의된다.

• $\{a_1, \dots, a_m\}$: 참가자 $A$가 선택할 수 있는 행동들의 집합
• $\{b_1, \dots, b_n\}$: 참가자 $B$가 선택할 수 있는 행동들의 집합
• $P_A$: 참가자 $A$의 $m \times n$ 보수 행렬(payoff matrix)
• $P_B$: 참가자 $B$의 $m \times n$ 보수 행렬

두 참가자는 행동을 동시에 선택한다. 예를 들어 $A$가 $a_i$를, $B$가 $b_j$를 선택했다고 하자. 이때 각 참가자의 보수는 보수 행렬에서 결정되어 $A$는 $P_A[i,j]$를, $B$는 $P_B[i,j]$를 받는다. 각 참가자의 목표는 자신의 보수를 최대화하는 것이다.

$B$가 특정 행동 $b_j$를 골랐을 때, $A$의 최선 반응(best response) 은 $A$의 보수를 최대로 만드는 행동 $a_i$, 즉 $P_A[i,j] = \max_{i'} P_A[i',j]$를 만족하는 모든 $a_i$이다. 마찬가지로 $A$가 특정 행동 $a_i$를 골랐을 때, $B$의 최선 반응은 $P_B[i,j] = \max_{j'} P_B[i,j']$를 만족하는 모든 $b_j$이다.

행동의 쌍 $(a_i, b_j)$가 서로에게 최선 반응일 때, 즉 $a_i$가 $b_j$에 대한 최선 반응이고 동시에 $b_j$가 $a_i$에 대한 최선 반응일 때, 이 쌍을 순수 전략 내시 균형(pure-strategy Nash equilibrium) 이라 한다.

두 보수 행렬 $P_A$와 $P_B$가 주어질 때, 이 게임의 모든 순수 전략 내시 균형을 찾아 나열하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $m$과 $n$이 주어진다 ($1 \le m, n \le 20$). 이어지는 $m$개의 줄에는 보수 행렬 $P_A$의 각 행이, 그다음 $m$개의 줄에는 보수 행렬 $P_B$의 각 행이 주어지며, 각 행은 $n$개의 정수로 이루어진다. 모든 보수 값은 $-100$ 이상 $100$ 이하의 정수이다.

입력의 끝은 0 0인 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스에 대해, 게임의 순수 전략 내시 균형의 개수를 $N$이라 하자. 다음을 출력한다.

1. 정수 $N$이 적힌 한 줄
2. 이어서 $N$개의 줄. 각 줄에는 두 정수 $i$와 $j$(1부터 시작)를 출력하며, 이는 $(a_i, b_j)$가 내시 균형임을 뜻한다.

내시 균형은 사전식 순서로 나열해야 한다. 즉 $i_1 < i_2$이거나, $i_1 = i_2$이면서 $j_1 < j_2$일 때 $(a_{i_1}, b_{j_1})$을 $(a_{i_2}, b_{j_2})$보다 먼저 출력한다.

참가자 $A$와 $B$가 각각 두 개의 행동을 가지며, 보수 행렬이 아래와 같은 게임을 생각해 보자.

$A$가 $a_1$을 선택하면, $B$는 $b_1$을 선택할 때 보수를 최대화한다. $P_B[1,1] = 1 > 0 = P_B[1,2]$이기 때문이다. 마찬가지로 $B$가 $b_1$을 선택하면, $A$는 $a_1$을 선택할 때 보수를 최대화한다. $P_A[1,1] = 1 > 0 = P_A[2,1]$이기 때문이다. 따라서 $a_1$은 $b_1$에 대한 최선 반응이고 그 반대도 성립하므로, $(a_1, b_1)$은 이 게임의 순수 전략 내시 균형이다.

반면 $(a_2, b_2)$는 내시 균형이 아니다. $A$가 $a_2$를 선택하면 $B$의 최선 반응은 $b_1$인데, $P_B[2,1] = 5 > 3 = P_B[2,2]$이기 때문이다.