Nash Equilibrium
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
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 maxi0PA[i0, 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 maxj0PB[i, j0]. 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.
For an example, 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 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].
입력
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 (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
노트
