예제 1.1 ( 경기값과공정한경기 ) >> A = [5 3 9; 8 10 11; 6 2 8], P = [0 1 0], Q = [1 0 0]' % 3x3 행렬경기 A = 5 3 9 8 10 11 6 2 8 P = 0 1 0 Q = 1 0 0 >> E = P * A * Q % 경기자 R은항상 2행을선택하고 C는항상 1열을선택하면, % R은 $8을얻는것이보장되고 C는그만큼을잃을것이다. E = 8
>> A = [0-1 1; 1 0-1; -1 1 0] % 가위- 바위- 보경기의분배행렬 A = 0-1 1 1 0-1 -1 1 0 >> P=[1/3 1/3 1/3], Q=[1/3 1/3 1/3]' P = 0.3333 0.3333 0.3333 Q = 0.3333 0.3333 0.3333 >> E= P * A * Q % 모든선택확률이동일하면이경기는공정한경기이다. E = 0 >> E = [.50.25.25] * A * [1/3 1/3 1/3]' % 한사람이동일한확률인경우 E = 0 >> E = [.50.25.25] * A * [.25.50.25]' % 선택확률이서로다른경우 E = -0.0625
예제 2.3 ( 최상의전략과경기값 ) >> A = [4 5 6; 5 3 2] % 2x3 행렬경기의분배행렬 A = 4 5 6 5 3 2 >> Ps = [2/3 1/3], Qs = [2/3; 1/3; 0] % 최상의전략 Ps = 0.6667 0.3333 Qs = 0.6667 0.3333 0 >> Ps * A * Qs % 경기값은최상의전략에대한기대값이다. ans = 4.3333 >> Q=rand(size(Qs)); Q=Q/sum(Q), E=Ps*A*Q % 전략 Ps 는어떠한전략 Q 경우에도경기값보다큰분배값을준다. Q = 0.1183 0.7986 0.0831 E = 4.3610 >> for i=1:7; Q=rand(size(Qs)); Q=Q/sum(Q); E(i)=Ps*A*Q; >> E E = 4.5117 4.4215 4.4218 4.4210 4.5007 4.4983 4.4876 >> P=rand(size(Ps)); P=P/sum(P), E = P * A * Qs % 전략 Qs 는어떠한전략 P 경우에도경기값보다작은분배값을준다. P = 0.6953 0.3047 E = 4.3333
>> for i=1:7; P=rand(size(Ps)); P=P/sum(P); E(i)=P*A*Qs; >> E E = 4.3333 4.3333 4.3333 4.3333 4.3333 4.3333 4.3333
예제 2.6 ( 최상의전략과경기값 ) 땅에밀이나옥수수를심을수있는한농부가있다. 이농작물에대한이윤은정부가해외로수출하는데어떤정책을가지고있느냐에따라변하는데아래의지급행렬 (payoff matrix) 로보여진다. 만약 P * =(0.60 0.40) 와 Q * =(0.40 0.60) T 가농부와정부정책의최상의전략이라면농부에게기대되는이윤은얼마인가? >> A = [15 12; 13 18], Ps = [5/8 3/8], Qs = [6/8; 2/8] A = 15 12 13 18 Ps = 0.6250 0.3750 Qs = 0.7500 0.2500 >> E = Ps*A*Qs E =
14.2500 >> K = mean(mean(a)), B=A-K % mean(mean(a)) = sum(sum(a))/prod(size(a)) K = 14.5000 B = 0.5000-2.5000-1.5000 3.5000 >> Ps*B*Qs ans = -0.2500 >> Ps*B*Qs + K ans = 14.2500
예제 3.1 ( 결정된경기와순수전략 ) 밥과스티브는집합 {0, 1, 2} 로부터숫자를선택한다. 다음과같은분배행렬에대해밥과스티브에대한최상의순수한전략을결정해라. 이것은공정한경기인가? >> A = [0 2 4; -2 0 2; -4-2 0] % 분배행렬 A = 0 2 4-2 0 2-4 -2 0 >> ri = min(a')', r=max(ri) % 각행의최소원소중최대값 ri = 0-2 -4 r = 0 >> cj = max(a), c=min(cj) % 각열의최대원소중최소값 cj = 0 2 4 c = 0
예제 3.2 ( 결정된경기와순수전략 ) function [v, P, Q]=pure(A) % Find game value v, and pure strategies P,Q for strictly determined game % [v, P, Q]=pure(A) [m, n] = size(a); % Find minium elements for each row for i = 1:m ri(i) = A(i,1); for j = 2:n if ( A(i,j) < ri(i) ) ri(i) = A(i,j); % Find maximum elements of min(a(i,:)) r = ri(1); for i = 2:m if ( ri(i) > r )
r = ri(i); % Find minumum of column maximums = min( max(a(:,j)) ) c = Inf; for j = 1:n cj = A(1,j); imax_cj = 1; for i = 2:m if ( A(i,j) > cj ) cj = A(i,j); imax_cj = i; if ( cj < c ) c = cj; imax_c = imax_cj; jmax_c = j; % Check if r=max(min(a')) == c=min(max(a)) if ( r == c ) v = c; P = zeros(1,m); P(imax_c) = 1; Q = zeros(n,1); Q(jmax_c) = 1; else disp('not a strictly determined game'); v = []; P = []; Q = []; >> pure([4-2; -5 3]) Not a strictly determined game ans = [] >> [v, p, q] = pure([2 4 8; 9 7 10; 1 5 7]) v = 7 p = 0 1 0 q = 0 1 0
예제 3.3 ( 우열관계구하기 ) function A = domin(a); % Eliminate dominated rows and columns in game matrix % A = domin(a) [m, n] = size(a); idom = []; for i = 1:m for i2 = [1:i-1 i+1:m] if ( all(a(i,:)>=a(i2,:)) ) idom=[i2 idom]; A(idom,:) = []; jdom = []; for j = 1:n-1 for j2 = [1:j-1 j+1:n] if ( all(a(:,j)<=a(:,j2)) ) jdom=[j2 jdom]; A(:,jdom) = []; if ( m~=size(a,1) n~=size(a,2) ) A = domin(a); >> A = [7 8 2; 4 5 1; 5 6 6; 3 4 0] A = 7 8 2 4 5 1 5 6 6 3 4 0 >> domin(a) ans = 7 2 5 6
예제 4.2 (2x2 경기의혼합전략과경기값 ) 경기자들의최상의전략과경기 의값을결정하라. 이것은공정한경기 (fair game) 인가? >> A = [3-2; -4 7], adbc=a(1,1)+a(2,2)-a(1,2)-a(2,1) A = 3-2 -4 7 adbc = 16 >> format rat >> P = [A(2,2)-A(2,1) A(1,1)-A(1,2)] / adbc P = 11/16 5/16 >> Q = [A(2,2)-A(1,2); A(1,1)-A(2,1)] / adbc Q =
9/16 7/16 >> v = det(a) / adbc % 이것은공정한경기가아니다. v = 13/16 예제 4.4 (n n 경기에서전략과경기값 ) 다음과같은 3 3 행렬경기에서최상의전략과경기값을구하시오. function [v, P, Q] = nxn(a) % Find game value v, and optimal strategies P,Q for nxn game % [v, P, Q] = nxn(a) % it works only when % 1. det(a)~=0 % 2. All R_i have the same sign % 3. All C_j have the same sign [m, n] = size(a); % Compute Cofactor matrix for i = 1:m for j = 1:n
Cofac(i,j) = (-1)^(i+j) * det(a( [1:i-1 i+1:m], [1:j-1 j+1:n] )); R = sum(cofac'); C = sum(cofac)'; D = det(a); Rsum = sum(r); Csum = sum(c); if ( D~=0 & all(r/rsum>=0) & all(c/csum>=0) ) v = D / Rsum; P = R / Rsum; Q = C / Csum; else if (D==0); disp('this function is not valid since Det(A)==0'); if (any(r/rsum<0)); disp('this function is not valid since R/Rsum<0'); if (any(c/csum<0)); disp('this function is not valid since C/Csum<0'); v = []; P = []; Q = []; >> format rat >> A = [1 2 3; 6 1 2; 3 5 1] A = 1 2 3 6 1 2 3 5 1 >> [v P Q] = nxn(a) v = 12/5 P = 3/5 1/5 1/5 Q = 1/6 4/15 17/30 >> v = nxn([1 0 0; 0 1 0; 0 0-1]) This function is not valid since R/Rsum<0 This function is not valid since C/Csum<0 v = []
6 5 4 3 2 1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
예제 6.1 (Simplex Method) simplex method 를사용해서다음의행렬경기의경기자들의최상의전략을결정하고경기값을구하라. (( 답 )) 경기자 C는 를최상의전략으로가진다고가정하자. 그러면 또는, 이때, i=1,2,3 에대하여 x i = q i /v. 위의 linear constraints 에관한 N = x 1 +x 2 +x 3 = 1/v 을최대로하려고한다. >> A = [3 4 5; 4 2 1]
A = 3 4 5 4 2 1 >> [m, n] = size(a) m = 2 n = 3 >> format rat >> P = [ [A; -ones(1,n)] eye(m+1) [ones(m,1); 0] ] P = 3 4 5 1 0 0 1 4 2 1 0 1 0 1-1 -1-1 0 0 1 0 >> % Object 중음의값인 (-1) 을가진 1열원소중가장큰 (4) 로 pivoting >> P(2,:)=P(2,:)/P(2,1); >> P(1,:)=P(1,:)-P(1,1)*P(2,:); P(3,:)=P(3,:)-P(3,1)*P(2,:) P = 0 5/2 17/4 1-3/4 0 1/4 1 1/2 1/4 0 1/4 0 1/4 0-1/2-3/4 0 1/4 1 1/4 >> % Object 중음의값인 (-3/4) 을가진 3열원소중가장큰 (17/4) 로 pivoting >> P(1,:)=P(1,:)/P(1,3); >> P(2,:)=P(2,:)-P(2,3)*P(1,:); P(3,:)=P(3,:)-P(3,3)*P(1,:) P = 0 10/17 1 4/17-3/17 0 1/17 1 6/17 0-1/17 5/17 0 4/17 0-1/17 0 3/17 2/17 1 5/17 >> % Object 중음의값인 (-1/17) 을가진 2열원소중가장큰 (10/17) 로 pivoting >> P(1,:)=P(1,:)/P(1,2); P(2,:)=P(2,:)-P(2,2)*P(1,:); P(3,:)=P(3,:)-P(3,2)*P(1,:) P = 0 1 17/10 2/5-3/10 0 1/10 1 0-3/5-1/5 2/5 0 1/5 0 0 1/10 1/5 1/10 1 3/10 그러므로, x 1 = 1/5, x 2 = 1/10, x 3 = 0 이고, 1/v = 3/10, 즉, v = 10/3 이다. 또한, y 1 = 1/5, y 2 = 1/10 이다. j=1,2,3 에대하여 x j = q j /v 이고, i=1,2 에대해서 y i = p i /v 이기때문에, q 1 = 2/3, q 2 = 1/3, q 3 = 0 이고 p 1 = 2/3, p 2 = 1/3 이다. 그러므로, P=(2/3, 1/3), Q=(2/3, 1/3, 0) T 가각각경기자 R 과 C 의최상의전략이고, 경기의값은 v = 17/5 이다.