Description

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

Small Model of Types : EMP mcp

Category : GAMS Model library

Main file : prisoner.gms

$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;