Nash Equilibrium ---- ----------- In Game Theory a simple finite two-person game consists of two players a finite set of `strategies' for each player a payoff matrix for each player Let the two players be R (`rows') and C (`columns'). Let the strategies for R be labeled 1, 2, ..., NR, and the strategies for C be labeled 1, 2, ..., NC. The payoff matrix for R is R(r,c) where r is a strategy for R and c a strategy for C; while the payoff matrix for C is similarly C(r,c). These matrices have integer elements and larger payoffs are better. A round of the game consists of each player privately choosing a strategy, and then the two players simultaneously announce their strategies. Let r be R's strategy and c be C's. Then the round pays R the amount R(r,c) and pays C the amount C(r,c). You might think this simple minded, but it is an abstraction that covers games such as TicTacToe. For TicTacToe a strategy will be some algorithm for playing the game, and a round will consist of each player choosing a strategy privately and the game being played according to these strategies. The payoffs might be +1 for winning, -1 for losing, and 0 for tie. The payoff matrices are commonly specified by a single matrix whose elements are `R(r,c)/C(r,c)'. Thus we have the classic game: Prisoner's Dilemma 1=Remain-Silent 2=Confess 1=Remain-Silent -6/-6 -120/0 2=Confess 0/-120 -60/-60 Two prisoner's are charge with a crime they committed. If both remain silent, they each serve 6 months. If both confess, they each serve 60 months (5 years). If one confesses and the other remains silent, the confes- sor goes free and the other prisoner serves 120 months (10 years). This game is symmetric: R(r,c) = C(c,r). But not all games are. Given a game, a `dominated strategy' for R is an r such that there exists an r' for which R(r',c) >= R(r,c) for every c and R(r',c') > R(r,c') for some c'. The idea here is that r' is always a better strategy than r, so r is `dominated' if and only if there is some other strategy that is always better. A dominated strategy for C is defined analogously. One way to decide how to game should be played is to iteratively eliminate dominated strategies. In the case of Prisoner's Dilemma, Remaining Silent is a domi- nated strategy for both prisoners, and eliminating it gives a game in which both prisoners Confess. Given a game, a `Nash Equilibrium' is a pair (r,c) such that for every r', R(r,c) >= R(r',c) and for every c', C(r,c) >= C(r,c'). The Prisoner's Dilemma has one Nash Equilibrium: the pair where both players Confess. Given a game you are asked to find all the dominated strategies and all the Nash Equilibria. Input ----- The input consists of test cases. Each test case begins with a line containing the name of the test case. This is followed by a single line containing NR and NC in that order, and this is followed by NR lines each containing NC number pairs, where each pair is written as `#/#' where # stands for an integer. The c'th pair of the r'th line is R(r,c)/C(r,c). 1 <= NR,NC <= 20. Some of the input lines may be very long. The input is terminated by an end of file. Output ------ For each test case, four lines, the first being a copy of the first test case input line that contains the test case name. The remaining three lines, in order, are: Dominated R Strategies: r1 r2 ... Dominated C Strategies: c1 c2 ... Nash Equilibria: (r1',c1') (r2',c2') ... where r1, r2, ..., c1, c2, ... are strategy numbers (integers from 1 through NR and 1 through NC respec- tively) and (r1',c1'), (r2',c2'), ... are strategy pairs. You must list ALL the dominated R and C strategies and all the Nash Equilibria and not have duplicates, but the order does not matter. Its possible that there will be nothing after a `:' on a line. Some of the output lines will be very long. Sample Input ------ ----- -- PRISONER'S DILEMMA -- 2 2 -6/-6 -120/0 0/-120 -60/-60 -- BATTLE OF SEXES -- 2 2 0/0 2/1 1/2 0/0 -- MATCHING PENNIES -- 2 2 1/-1 -1/1 -1/1 1/-1 -- COURNOT COMPETITION, 3 GOODS, PRICE 5, COST 1 4 4 0/0 0/3 0/4 0/3 3/0 2/2 1/2 0/0 4/0 2/1 0/0 -2/-3 3/0 0/0 -3/-2 -3/-3 Sample Output ------ ------ -- PRISONER'S DILEMMA -- Dominated R Strategies: 1 Dominated C Strategies: 1 Nash Equilibria: (2,2) -- BATTLE OF SEXES -- Dominated R Strategies: Dominated C Strategies: Nash Equilibria: (1,2) (2,1) -- MATCHING PENNIES -- Dominated R Strategies: Dominated C Strategies: Nash Equilibria: -- COURNOT COMPETITION, 3 GOODS, PRICE 5, COST 1 Dominated R Strategies: 1 4 Dominated C Strategies: 1 4 Nash Equilibria: (2,2) (2,3) (3,2) File: nasheq.txt Author: Bob Walton Date: Sun Oct 11 23:19:29 EDT 2009 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2009/10/12 04:14:48 $ $RCSfile: nasheq.txt,v $ $Revision: 1.7 $