prisoner.gms : EMP와 MCP로서의 죄수의 딜레마

설명

두 명의 범죄자가 붙잡혀 별도의 감방에 갇혔습니다.
서로 소통합니다.  그들은 각각 동일한 거래를 제안받았습니다.
독립적으로, 서로는 상대방이 이 거래를 제안받았다는 것을 알고 있습니다.
각각에는 두 가지 옵션이 있습니다.
   1) 상대방을 자백하고 증인이 되거나
   2) 자신의 죄를 부인합니다.
둘 다 자백하면 각각 5년 징역형을 받게 된다.  만약에
한 사람은 자백하고 한 사람은 죄를 부인하면 자백한 사람이
1년 징역형을 받고 다른 한 명은 6년 징역형을 받게 됩니다. 만약에
둘 다 유죄를 부인하면 각각 2년의 징역형을 받게 됩니다.

이 문제는 2인 비제로섬 바이행렬(two-person nonzerosum bimatrix)의 좋은 예입니다.
Cottle, Pang, Stone에 설명된 게임입니다.  죄수의 딜레마
많은 게임이론에 의해 다양한 형태로 제기되고 연구되어 왔다.
연구원.  원래는 Merrill Flood와 Melvin이 액자에 넣었습니다.
Dresher는 1950년 RAND에서 다음과 같이 징역형 보상으로 공식화되었습니다.
죄수의 딜레마 - 알 터커

두 플레이어의 최적화를 위한 KKT 조건에 유의하세요.
문제에는 자유 변수가 포함되어 있습니다.
제약.  이는 혼합상보성에는 문제가 되지 않습니다.
슬롯 나라에서 사용하는 형식이지만 이를 위해서는 약간의 대수적 체조가 필요합니다.
에 설명된 대로 LCP 프레임워크에 맞는 문제를 만듭니다.
CPS.

Cottle, R W 및 Pang, J-S 및 Stone, R E, 선형 상보성
문제, Academic Press, 샌디에고, 캘리포니아, 1992

키워드: 혼합 상보성 문제, 확장된 수학 프로그래밍,
          응용일반균형, 죄수의 딜레마, 게임이론

소형 유형 모델 :EMP mcp

카테고리 : 슬롯 나라 모델 라이브러리

메인 파일 : prisoner.gms

$title EMP 및 MCP로서의 포로 딜레마 (포로,SEQ=392)

$onText
두 명의 범죄자가 체포되어 별도의 감방에 갇혔습니다.
서로 소통합니다.  그들은 각각 동일한 거래를 제안받았습니다.
독립적으로, 서로는 상대방이 이 거래를 제안받았다는 것을 알고 있습니다.
각각에는 두 가지 옵션이 있습니다.
   1) 상대방을 자백하고 증인이 되거나
   2) 자신의 죄를 부인합니다.
둘 다 자백하면 각각 5년 징역형을 받게 된다.  만약에
한 사람은 자백하고 한 사람은 죄를 부인하면 자백한 사람이
1년 징역형을 받고 다른 한 명은 6년 징역형을 받게 됩니다. 만약에
둘 다 유죄를 부인하면 각각 2년의 징역형을 받게 됩니다.

이 문제는 2인 비제로섬 바이행렬(two-person nonzerosum bimatrix)의 좋은 예입니다.
Cottle, Pang, Stone에 설명된 게임입니다.  죄수의 딜레마
많은 게임이론에 의해 다양한 형태로 제기되고 연구되어 왔다.
연구원.  원래는 Merrill Flood와 Melvin이 액자에 넣었습니다.
Dresher는 1950년 RAND에서 다음과 같이 징역형 보상으로 공식화되었습니다.
죄수의 딜레마 - 알 터커

두 플레이어의 최적화를 위한 KKT 조건에 유의하세요.
문제에는 자유 변수가 포함되어 있습니다.
제약.  이는 혼합상보성에는 문제가 되지 않습니다.
슬롯 나라에서 사용하는 형식이지만 이를 위해서는 약간의 대수적 체조가 필요합니다.
에 설명된 대로 LCP 프레임워크에 맞는 문제를 만듭니다.
CPS.

Cottle, R W 및 Pang, J-S 및 Stone, R E, 선형 상보성
문제, Academic Press, 샌디에고, 캘리포니아, 1992

키워드: 혼합 상보성 문제, 확장된 수학 프로그래밍,
          응용일반균형, 죄수의 딜레마, 게임이론
$offText

i '플레이어 1 전략' 설정 / 고백, 거부 /;

별칭(i,j);

테이블 A(i,j) '선수 1의 투옥 시간은 xAy'입니다.
            고백하다 거부하다
   고백하다 5 1
   거부 6 2;

매개변수 B(i,j) '플레이어 2의 투옥 시간은 xBy'입니다.
B(i,j) = A(j,i);

양수 변수
   x(i) '플레이어 1 전략'
   y(j) '플레이어 2 전략';

변수
   z1 '플레이어원 감옥'
   z2 '플레이어 2의 감옥 시간';

방정식
   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;

* MILES의 시작 값
x.l(i)$(ord(i) = 1) = 1;
y.l(j)$(ord(j) = 1) = 1;

모델 m '바이매트릭스 게임' / 모두 /;

파일 empinfo / '%emp.info%' /;
putClose empinfo
  '평형' /
  ' 최소 z1 x z1Def s1Def' /
  ' min z2 y z2Def s2Def' /;

emp를 사용하여 m을 해결합니다.
abort$(m.solveStat <> 1) 'EMP 모델에 대한 잘못된 해석';
abort$(m.modelStat > 2) 'EMP 모델에 대한 잘못된 modelstat';

매개변수 xRes(*,i), yRes(*,j);
xRes('emp',i) = x.l(i);
yRes('emp',j) = y.l(j);

* 이제 KKT 시스템을 명시적으로 공식화하고 공동으로 해결합니다.
* 플레이어 1과 2
변수
   u1 's1Def에 대한 이중 승수'
   u2 's2Def에 대한 이중 승수';

방정식
   dLdx(i) '플레이어 1에 대한 FOC: 파생 wrt x'
   dLdy(j) '플레이어 2에 대한 FOC: 파생 wrt y';

dLdx(i).. sumj, A(i,j)*y(j) - u1 =n= 0;

dLdy(j).. sumi, B(i,j)*x(i) - u2 =n= 0;

모델 kkt '바이매트릭스 게임에 대한 KKT 조건' / dLdx.x, dLdy.y, s1Def.u1, s2Def.u2 /;

* MILES의 시작 값
x.l(i) = 1$(ord(i) = 1);
y.l(j) = 1$(ord(j) = 1);

mcp를 사용하여 kkt를 해결합니다.
abort$(kkt.solveStat <> 1) 'MCP 모델에 대한 잘못된 해석 상태';
abort$(kkt.modelStat > 2) 'MCP 모델에 대한 잘못된 modelstat';

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

스칼라 t;
t = sumi, xRes('dif',i) + sumj, yRes('dif',j);
abort$(t > 1e-5) '솔루션이 동의하지 않음', xRes, yRes;