prisoner.gms : Prisoners dilemma as EMP and MCP

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

Reference

  • Cottle, R W, Pang, J S, and Stone, R E, The Linear Complementarity Problem. Academic Press, San Diego, CA, 1992.

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

$offtext

sets
  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 variables
  x(i) 'player 1 strategy'
  y(j) 'player 2 strategy'
  ;

variables
  z1  'player one jail time'
  z2  'player two jail time'
  ;

equations
  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';

parameters
  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

variables
  u1  'dual multiplier for s1Def'
  u2  'dual multiplier for s2Def'
  ;
equations
  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;