\$title Prisoners Dilemma as EMP and MCP (prisoner,SEQ=392) \$onText Two criminals are caught and held in separate cells, unable to communicate with each other. They are each offered the same deal, independently, and each knows that the other is offered this deal. They each have two options: 1) confess and be a witness against the other person, or 2) deny their guilt. If they both confess, they will each get 5 years in jail. If one confesses and the other denies guilt, then the one who confessed will get 1 year in jail and the other will get 6 years in jail. If they both deny guilt, they will each get 2 years in jail. This problem is a good example of a two-person nonzerosum bimatrix game, as described in Cottle, Pang, and Stone. The Prisoner's Dilemma has been posed and studied in various forms by many game theory researchers. It was originally framed by Merrill Flood and Melvin Dresher at RAND in 1950 and formalized with prison sentence rewards as the Prisoner's Dilemma by Al Tucker. Note that the KKT conditions for the two players' optimization problems contain free variables: the duals to the sum-to-one constraints. This is not a problem for the mixed complementarity format used by GAMS, but it requires some algebraic gymnastics to create a problem that fits into the LCP framework, as described in CPS. Cottle, R W, and Pang, J-S, and Stone, R E, The Linear Complementarity Problem, Academic Press, San Diego, CA, 1992 Keywords: mixed complementarity problem, extended mathematical programming, applied general equilibrium, prisoner's dilemma, game theory \$offText Set i 'player 1 strategies' / confess, deny /; Alias (i,j); Table A(i,j) 'jail time for player 1 is xAy' confess deny confess 5 1 deny 6 2; Parameter B(i,j) 'jail time for player 2 is xBy'; B(i,j) = A(j,i); Positive Variable x(i) 'player 1 strategy' y(j) 'player 2 strategy'; Variable z1 'player one jail time' z2 'player two jail time'; Equation z1Def, z2Def s1Def, s2Def; z1Def.. sum(i, x(i)*sum(j, A(i,j)*y(j))) =e= z1; s1Def.. sum(i, x(i)) =e= 1; z2Def.. sum(i, x(i)*sum(j, B(i,j)*y(j))) =e= z2; s2Def.. sum(j, y(j)) =e= 1; * starting values for MILES x.l(i)\$(ord(i) = 1) = 1; y.l(j)\$(ord(j) = 1) = 1; Model m 'bimatrix game' / all /; File empinfo / '%emp.info%' /; putClose empinfo 'equilibrium' / ' min z1 x z1Def s1Def' / ' min z2 y z2Def s2Def' /; solve m using emp; abort\$(m.solveStat <> 1) 'bad solvestat for EMP model'; abort\$(m.modelStat > 2) 'bad modelstat for EMP model'; Parameter xRes(*,i), yRes(*,j); xRes('emp',i) = x.l(i); yRes('emp',j) = y.l(j); * now explicitly formulate and jointly solve the KKT systems for * players 1 and 2 Variable u1 'dual multiplier for s1Def' u2 'dual multiplier for s2Def'; Equation dLdx(i) 'FOC for player 1: deriv wrt x' dLdy(j) 'FOC for player 2: deriv wrt y'; dLdx(i).. sum{j, A(i,j)*y(j)} - u1 =n= 0; dLdy(j).. sum{i, B(i,j)*x(i)} - u2 =n= 0; Model kkt 'KKT conditions for bimatrix game' / dLdx.x, dLdy.y, s1Def.u1, s2Def.u2 /; * starting values for MILES x.l(i) = 1\$(ord(i) = 1); y.l(j) = 1\$(ord(j) = 1); solve kkt using mcp; abort\$(kkt.solveStat <> 1) 'bad solvestat for MCP model'; abort\$(kkt.modelStat > 2) 'bad modelstat for MCP model'; xRes('kkt',i) = x.l(i); yRes('kkt',j) = y.l(j); xRes('dif',i) = abs(xRes('kkt',i) - xRes('emp',i)); yRes('dif',j) = abs(yRes('kkt',j) - yRes('emp',j)); Scalar t; t = sum{i, xRes('dif',i)} + sum{j, yRes('dif',j)}; abort\$(t > 1e-5) 'solutions do not agree', xRes, yRes;