#P2953. Nash Equilibrium

Nash Equilibrium

Description

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

  • {a1, …, am}, a set of actions for player A,
  • {b1, …, bn}, 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 ai and bj 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 bj by player B consists of any action ai which maximizes A’s payoff, that is, whose payoff is maxi' PA[i', j]. Similarly, for player B, the set of best responses to a particular action ai by player A is any action bj whose payoff is maxj' PB[i, j']. A pair of strategies (ai, bj) is said to be a pure strategy Nash equilibrium if ai is a best response to bj and bj is a best response to ai.

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:

PAb1b2
a115
a203
PBb1b2
a110
a253

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

Input

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.

Output

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 (ai, bj) is the corresponding Nash equilibrium. Note that the program must list all Nash equilibria in lexicographical order, i.e., (ai1, bj1) is listed before (ai2 , bj2) if i1 < i2 or if i1 = i2 and j1 < j2.

3 4
1 5 -3 2
4 2 -1 -3
3 -2 5 9
0 -4 -1 -5
-9 2 8 3
-3 4 -2 3
2 2
1 10
0 5
1 0
10 5
2 2
1 1
1 1
1 1
1 1
0 0
0
1
1 1
4
1 1
1 2
2 1
2 2

Source

Stanford Local 2004