2953：Nash Equilibrium

A two-player normal form game between two individuals A and B is completely specified by

• {a₁, …, a_m}, a set of actions for player A,
• {b₁, …, b_n}, a set of actions for player B,
• PA, an m × n payoff matrix for player A, and
• PB, an m × n payoff matrix for player B.

In such a game, both players simultaneously select actions to be played (say a_i and b_j for players A and B, respectively). Then payoffs for each player are determined according to the payoff matrices (PA[i, j] and PB[i, j] for players A and B, respectively). The goal of each player is to maximize his or her payoff.

For player A, the set of best responses to a particular action b_j by player B consists of any action a_i which maximizes A’s payoff, that is, whose payoff is max_i' PA[i', j]. Similarly, for player B, the set of best responses to a particular action a_i by player A is any action b_j whose payoff is max_j' PB[i, j']. A pair of strategies (a_i, b_j) is said to be a pure strategy Nash equilibrium if a_i is a best response to b_j and b_j is a best response to a_i.

In this problem, you are given the payoff matrices for two players A and B, and your task is to find and list all pure strategy Nash equilibria.

Consider the following two-player game in which A and B each have two possible actions, and the payoff matrices are:

Here, if player A chooses a₁, then choosing b₁ allows player B to maximize his payoff (PB[1, 1] = 1 > 0 = PB[1, 2]). Similarly, if player B choose b₁, then choosing a₁ allows player A to maximize his payoff (PA[1, 1] = 1 > 0 = PA[2, 1]). Thus, a₁ is the best response for b₁ and vice versa, so (a₁, b₁) is a pure strategy Nash equilibrium of this game. However, note that (a₂, b₂) is not a Nash equilibrium; if player A chooses action a₂, b₁ is the best response since PB[2, 1] = 5 > 3 = PB[2, 2].

The input test file will contain multiple test cases. Each test case begins with a single line containing two integers, m and n, where 1 ≤ m, n ≤ 20. The next m lines specify the m rows of payoff matrix PA. The m lines after that specify the m rows of payoff matrix PB. All payoff matrix values will be integers between −100 and 100, inclusive. The end-of-file is marked by a test case with m = n = 0 and should not be processed.

For each input case, suppose that N is the number of Nash equilibria for the described normal form game. Then, the output of the program consists of (1) a line containing the single integer N, and (2) N lines containing two integers i and j, where (a_i, b_j) is the corresponding Nash equilibrium. Note that the program must list all Nash equilibria in lexicographical order, i.e., (a_i1, b_j1) is listed before (a_i2 , b_j2) if i₁ < i₂ or if i₁ = i₂ and j₁ < j₂.