Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Nash Equilibrium
Description A two-player normal form game between two individuals A and B is completely specified by - {
*a*_{1}, …,*a*}, a set of actions for player A,_{m} - {
*b*_{1}, …,*b*}, a set of actions for player B,_{n} *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 b for players A and B, respectively). Then payoffs for each player are determined according to the payoff matrices (_{j}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 a which maximizes A’s payoff, that is, whose payoff is _{i}max _{i'}PA[i', j]. Similarly, for player B, the set of best responses to a particular action a by player A is any action _{i}b whose payoff is _{j}max _{j'}PB[i, j']. A pair of strategies (a, _{i}b) is said to be a _{j}pure strategy Nash equilibrium if a is a best response to _{i}b and _{j}b is a best response to _{j}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 Input The input test file will contain multiple test cases. Each test case begins with a single line containing two integers, Output For each input case, suppose that b) is the corresponding Nash equilibrium. Note that the program must list all Nash equilibria in lexicographical order, i.e., (_{j}a1, _{i}b1) is listed before (_{j}a2 , _{i}b2) if _{j}i_{1} < i_{2} or if i_{1} = i_{2} and j_{1} < j_{2}.Sample Input 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 Sample Output 0 1 1 1 4 1 1 1 2 2 1 2 2 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator