둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
페미위키:포크 프로젝트/리브레 위키/영합게임 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
페미위키:포크 프로젝트/리브레 위키/영합게임
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
== 정의 == [[게임 (수학)|게임]]의 참여자들의 이득의 합이 항상 0이면 그 게임을 '''영합게임''', 또는 '''제로섬 게임(zero-sum game)'''이라 한다. == 예시 == <!-- 추가바람 --> == 2인 영합게임 == 영합게임에서 참여자의 수가 2명일 때, 참여자를 각각 <math>P_1,P_2</math>라고 하자. 만약 <math>P_1,P_2</math>가 택할 수 있는 전략의 수가 각각 ''m,n''이면, 이 게임을 '''m×n직사각게임''' 또는 '''m×n게임'''이라 한다. <math>P_1,P_2</math>가 택하는 전략을 각각 <math>i,j</math>라 하고, 이때 <math>P_1</math>의 이득을 <math>a_{ij}</math>라고 하면, 다음 표 {| | | 1 | 2 | <math>\cdots</math> | ''n'' |- | 1 | <math>a_{11}</math> | <math>a_{12}</math> | <math>\cdots</math> | <math>a_{1n}</math> |- | 2 | <math>a_{21}</math> | <math>a_{22}</math> | <math>\cdots</math> | <math>a_{2n}</math> |- | <math>\vdots</math> | <math>\vdots</math> | <math>\vdots</math> | <math>\ddots</math> | <math>\vdots</math> |- | ''m'' | <math>a_{m1}</math> | <math>a_{m2}</math> | <math>\cdots</math> | <math>a_{mn}</math> |} 를 게임의 이득표(payoff table)이라고 한다. 그리고 [[행렬]] <math>A=[a_{ij}]</math>를 게임의 이득행렬(payoff matrix)이라고 한다. === 결정적 게임과 비결정적 게임 === 2인 영합게임에서 참여자들은 항상 최선의 전략을 사용하여 최대의 이득을 얻으려고 한다. 이때 각 참여자들은 상대방이 자신에게 가장 불리한 전략을 쓸 경우에 대비해 예상되는 손해를 줄이려고 행동한다고 가정한다. 그러면 <math>P_1</math>는 이득행렬의 행의 최솟값 중에서 최댓값을 얻는 전략을 선택할 것이고, 반대로 <math>P_2</math>는 이득행렬의 열의 최댓값 중에서 최솟값을 얻는 전략을 실행할 것이다. 따라서 미니맥스(minimax)와 맥시민(maximin)을 다음과 같이 정의할 수 있다: ''A''의 ''i''번째 행 <math>\mathbf{u}_i</math>의 최솟값을 <math>u_i</math>라 하고, ''j''번째 열 <math>\mathbf{v}_j</math>의 최댓값을 <math>v_j</math>라고 하자. 그러면 : <math>\operatorname{maximin}=\max\{u_1,u_2,\cdots,u_m\}</math> : <math>\operatorname{minimax}=\min\{v_1,v_2,\cdots,v_n\}</math> 이다. ==== 결정적 게임 ==== 미니맥스와 맥시민이 같은 게임을 결정적 게임(strictly determined game)이라고 한다. 만약 참여자에게 전략 <math>a,b</math>가 주어졌을 때 상대방의 전략에 상관없이 전략 ''a''를 선택했을 때 전략 ''b''보다 더 많은 이익을 얻는다고 하자. 그러면 ''a''를 우월한 전략(dominant strategy), ''b''를 열등한 전략(dominated strategy)이라고 한다. m×n게임의 이득표에서 열등한 전략을 소거하는 것을 축약(contraction)이라고 한다. 만약 축약된 게임이 결정적 게임이라면, 원래 게임도 결정적 게임이다. 예를 들어, 어떤 2인 영합게임의 이득행렬이 다음과 같이 주어졌다고 가정하자. : <math>\begin{bmatrix} 3 & 4 & 2\\ 1 & 2 & -1\\ 2 & 5 & -3 \end{bmatrix}</math> 그러면 <math>P_2</math>의 세 번째 전략은 첫 번째, 두 번째 전략보다 우월하다. 따라서 축약하면 : <math>\begin{bmatrix} 2\\ -1\\ -3 \end{bmatrix}</math> 이다. 따라서 이 게임은 <math>P_1</math>는 첫 번째 전략을 선택하고 <math>P_2</math>는 세 번째 전략을 선택하는 결정적 게임이다. ==== 비결정적 게임 ==== 결정적 게임이 아닌 게임을 비결정적 게임(non-strictly determined game)이라고 한다. m×n게임에서 본래의 전략을 순수전략(pure strategy)이라 하고, 순수전략을 혼합하여 택하는 전략을 혼합전략(mixed strategy)이라고 하며, 혼합전략은 열벡터로 나타낼 수 있다. <math>P_1</math>이 전략 1,2,...,m을 확률 <math>x_1,x_2,\cdots,x_m</math>으로 택하는 혼합전략을 행렬 <math>\mathbf{x}</math>, <math>P_2</math>가 전략 1,2,...,n을 확률 <math>y_1,y_2,\cdots,y_n</math>으로 택하는 혼합전략을 행렬 <math>\mathbf{y}</math>라고 하자. 그러면 : <math>\mathbf{x}=\begin{bmatrix} x_1 \\x_2 \\\vdots \\ x_m\end{bmatrix},\; \mathbf{y}=\begin{bmatrix}y_1 \\y_2\\ \vdots \\ y_n\end{bmatrix}</math> 으로 나타낼 수 있으며, 이때 <math>P_1</math>이 얻을 것으로 기대되는 이득, 즉 기대이득(expected payoff)은 [[이중선형형식]](bilinear form) : <math>E(\mathbf{x},\mathbf{y})=\sum_{i=1}^m\sum_{j=1}^n a_{ij}x_i y_j=\mathbf{x}^TA\mathbf{y}</math> 으로 나타낼 수 있다. <math>P_1</math>의 혼합전략 <math>\mathbf{x}</math>에 대해 <math>E_1(\mathbf{x}), M</math>를 다음과 같이 정의하자. : <math>E_1(\mathbf{x})=\min_{\mathbf{y}}E(\mathbf{x},\mathbf{y})</math> : <math>M=\max_{\mathbf{x}}E_1(\mathbf{x})=\max_{\mathbf{x}}\min_{\mathbf{y}}E(\mathbf{x},\mathbf{y})</math> 그리고 <math>E_1(\bar{\mathbf{x}})=M</math>이 되는 <math>\mathbf{x}</math>를 <math>\bar{\mathbf{x}}</math>라고 하자. 이때 <math>\bar{\mathbf{x}}</math>를 <math>P_1</math>의 맥시민 전략(maximin strategy)이라고 한다. <math>P_2</math>의 혼합전략 <math>\mathbf{y}</math>에 대해 <math>E_2(\mathbf{y}), m</math>를 다음과 같이 정의하자. : <math>E_2(\mathbf{y})=\max_{\mathbf{x}}E(\mathbf{x},\mathbf{y})</math> : <math>m=\min_{\mathbf{y}}E_2(\mathbf{y})=\min_{\mathbf{y}}\max_{\mathbf{x}}E(\mathbf{x},\mathbf{y})</math> 그리고 <math>E_2(\bar{\mathbf{y}})=m</math>이 되는 <math>\mathbf{y}</math>를 <math>\bar{\mathbf{y}}</math>라고 하자. 이때 <math>\bar{\mathbf{y}}</math>를 <math>P_2</math>의 미니맥스 전략(minimax strategy)이라고 한다. 그러면 <math>M=m</math>이고, 다음 식이 성립한다. : <math>\max_{\mathbf{x}}\min_{\mathbf{y}}E(\mathbf{x},\mathbf{y})=E(\bar{\mathbf{x}},\bar{\mathbf{y}})=\min_{\mathbf{y}}\max_{\mathbf{x}}E(\mathbf{x},\mathbf{y})</math> <math>P_1,P_2</math>의 i,j번째 순수전략 <math>\mathbf{x}_i,\mathbf{y}_j</math>를 다음과 같이 정의할 수 있다. : <math>\mathbf{x}_i=[\delta_{ik}]_{m\times 1},\;\mathbf{y}_j=[\delta_{kj}]_{n \times 1}</math> 이때 <math>\delta_{ij}</math>는 [[크로네커 델타]]다. 그러면 다음 식이 성립한다. : <math>\max_{\mathbf{x}}\min_{\mathbf{y}}E(\mathbf{x},\mathbf{y})=\max_{\mathbf{x}}\min\{E(\mathbf{x},\mathbf{y}_1),E(\mathbf{x},\mathbf{y}_2),\cdots,E(\mathbf{x},\mathbf{y}_n)\}</math> : <math>\min_{\mathbf{y}}\max_{\mathbf{x}}E(\mathbf{x},\mathbf{y})=\min_{\mathbf{y}}\max\{E(\mathbf{x}_1,\mathbf{y}),E(\mathbf{x}_2,\mathbf{y}),\cdots,E(\mathbf{x}_n,\mathbf{y})\}</math> == 같이 보기 == * [[비영합게임]] [[분류:게임 이론]]
페미위키:포크 프로젝트/리브레 위키/영합게임
문서로 돌아갑니다.
다른 언어