Nash Equilibrium

A two-player normal-form game between players $A$ and $B$ is completely described by:

• $\{a_1, \dots, a_m\}$, the set of actions available to player $A$;
• $\{b_1, \dots, b_n\}$, the set of actions available to player $B$;
• $P_A$, an $m \times n$ payoff matrix for player $A$;
• $P_B$, an $m \times n$ payoff matrix for player $B$.

Both players choose their actions simultaneously — say player $A$ plays $a_i$ and player $B$ plays $b_j$. The payoffs are then read from the matrices: player $A$ receives $P_A[i,j]$ and player $B$ receives $P_B[i,j]$. Each player wants to maximize their own payoff.

Given a fixed action $b_j$ of player $B$, a best response of player $A$ is any action $a_i$ that maximizes $A$'s payoff, that is, any $a_i$ with $P_A[i,j] = \max_{i'} P_A[i',j]$. Symmetrically, given a fixed action $a_i$ of player $A$, a best response of player $B$ is any action $b_j$ with $P_B[i,j] = \max_{j'} P_B[i,j']$.

A pair of actions $(a_i, b_j)$ is a pure-strategy Nash equilibrium if $a_i$ is a best response to $b_j$ and, at the same time, $b_j$ is a best response to $a_i$.

Given the two payoff matrices $P_A$ and $P_B$, find and list all pure-strategy Nash equilibria of the game.

The input contains multiple test cases.

Each test case begins with a line containing two integers $m$ and $n$ ($1 \le m, n \le 20$). The next $m$ lines give the rows of payoff matrix $P_A$, and the following $m$ lines give the rows of payoff matrix $P_B$; each row lists $n$ integers. Every payoff value is an integer in the range $-100$ to $100$, inclusive.

The input ends with a line 0 0, which must not be processed.

For each test case, let $N$ be the number of pure-strategy Nash equilibria of the game. Output:

1. a line containing the single integer $N$;
2. then $N$ lines, each containing two integers $i$ and $j$ (1-indexed), meaning that $(a_i, b_j)$ is a Nash equilibrium.

List the equilibria in lexicographic order: $(a_{i_1}, b_{j_1})$ comes before $(a_{i_2}, b_{j_2})$ if $i_1 < i_2$, or if $i_1 = i_2$ and $j_1 < j_2$.

Consider a game in which players $A$ and $B$ each have two actions, with the payoff matrices shown below:

If player $A$ plays $a_1$, then player $B$ maximizes their payoff by playing $b_1$, since $P_B[1,1] = 1 > 0 = P_B[1,2]$. Likewise, if player $B$ plays $b_1$, then player $A$ maximizes their payoff by playing $a_1$, since $P_A[1,1] = 1 > 0 = P_A[2,1]$. So $a_1$ is a best response to $b_1$ and vice versa, which makes $(a_1, b_1)$ a pure-strategy Nash equilibrium.

By contrast, $(a_2, b_2)$ is not a Nash equilibrium: if player $A$ plays $a_2$, then $B$'s best response is $b_1$, because $P_B[2,1] = 5 > 3 = P_B[2,2]$.