전략 (게임 이론)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
전략 (게임 이론)은 게임 이론에서 플레이어가 게임을 플레이하는 방식을 정의하는 개념이다. 전략 집합은 플레이어가 사용할 수 있는 모든 전략을 포함하며, 유한하거나 무한할 수 있다. 순수 전략은 플레이어가 가능한 모든 상황에 대해 취할 행동의 완전한 계획을 의미하며, 혼합 전략은 순수 전략의 조합을 무작위로 선택하는 전략이다. 행동 전략은 각 정보 집합에 가능한 행동 집합에 대한 확률 분포를 할당하며, 쿤의 정리에 따라 혼합 전략과 밀접한 관련이 있다.
더 읽어볼만한 페이지
- 게임 이론 - 대연정
대연정은 의원내각제 또는 이원집정부제 국가에서 대립하는 거대 정당들이 국가적 위기 극복, 정치적 봉쇄, 또는 비례대표제 하의 연립 내각 구성의 필요에 따라 연합하는 정부 형태로, 정치적 안정과 국민 통합에 기여할 수 있지만 유권자 선택권 제한 및 소수 정당 약진의 우려도 있다. - 게임 이론 - 완전 정보
완전 정보 게임은 게임 이론에서 모든 플레이어가 게임의 모든 정보를 공유하는 게임을 의미하며, 체스, 틱택토, 오목 등이 이에 해당한다. - 수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다. - 수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다. - 경제학에 관한 - 노예제
노예제는 한 사람이 타인에게 소유되어 재산처럼 취급받으며 의지에 반해 노동을 강요당하고 보수 없이 사회적 이동이 제한되는 제도로, 고대부터 널리 존재했으나 18세기 이후 폐지 운동으로 대부분 국가에서 금지되었지만 현대에도 다양한 형태로 남아있다. - 경제학에 관한 - 민간 부문
민간 부문은 이윤 추구를 목표로 하는 경제 주체들로 이루어진 영역으로, 국가 경제 체제에 따라 비중과 역할이 다르며, 고용 창출의 원천이 되지만 여러 문제점을 야기하여 국가의 규제를 받는다.
| 전략 (게임 이론) | |
|---|---|
| 게임 이론에서의 전략 | |
| 정의 | 게임 상황에서 플레이어가 취할 수 있는 모든 가능한 행동 계획 |
| 유형 | 순수 전략: 각 상황에서 특정 행동을 결정적으로 선택하는 전략 혼합 전략: 각 행동에 확률을 부여하여 확률적으로 선택하는 전략 |
| 중요성 | 게임의 결과를 예측하고 최적의 의사 결정을 내리는 데 필수적인 요소 |
| 관련 개념 | |
| 내쉬 균형 | 모든 플레이어가 자신의 전략을 바꿀 유인이 없는 상태, 즉 서로에게 최선의 전략을 선택하는 조합 |
| 죄수의 딜레마 | 협력적인 선택이 모두에게 최적이지만, 개인적인 이익을 추구하면 오히려 나쁜 결과로 이어지는 게임 상황 |
| 예시 | |
| 가위바위보 | 각 플레이어는 가위, 바위, 보 중 하나를 선택하는 전략을 사용하며, 혼합 전략을 통해 예측 불가능성을 높일 수 있음 |
| 협상 게임 | 각 플레이어는 자신의 이익을 극대화하기 위해 협상 전략을 사용하며, 상대방의 전략에 따라 다양한 결과를 얻을 수 있음 |
| 참고 문헌 | |
| 서적 | 로버트 아우만, 게임 이론 (Palgrave Macmillan, 2017) |
2. 전략 집합
플레이어의 '''전략 집합'''은 플레이어가 사용할 수 있는 전략을 정의한다. 전략 집합은 유한하거나 무한할 수 있다.
응용 게임 이론에서 전략 집합의 정의는 게임을 동시에 해결 가능하고 의미 있게 만드는 기술의 중요한 부분이다. 게임 이론가는 두 명 이상의 플레이어 간의 마찰과 같은 전체 문제에 대한 지식을 사용하여 전략 공간을 제한하고 해결을 용이하게 할 수 있다.
예를 들어, 엄밀히 말하면 최후통첩 게임에서 플레이어는 다음과 같은 전략을 가질 수 있다: ''(1달러, 3달러, 5달러, ..., 19달러)의 제안 거부, (0달러, 2달러, 4달러, ..., 20달러)의 제안 수락''. 이러한 모든 전략을 포함하면 매우 큰 전략 공간과 다소 어려운 문제가 발생한다. 대신 게임 이론가는 전략 집합을 {모든 제안 ≤ ''x'' 거부, 모든 제안 > ''x'' 수락; ''x''는 (0달러, 1달러, 2달러, ..., 20달러)}로 제한할 수 있다고 생각할 수 있다.
2. 1. 유한 전략 집합
플레이어가 선택할 수 있는 전략의 수가 유한한 경우를 의미한다. 가위바위보 게임이 대표적인 예시이다. 가위바위보 게임에서 각 플레이어는 가위, 바위, 보 중 하나의 전략을 선택할 수 있으므로, 유한한 전략 집합을 갖는다.[1]2. 2. 무한 전략 집합
플레이어가 선택할 수 있는 전략의 수가 무한한 경우이다. 케이크 자르기 게임이 대표적인 예시인데, 케이크 자르기 게임은 {케이크의 0%에서 100% 사이 어디에서든 자르기}와 같이 경계가 있는 연속적인 전략 집합을 갖는다.[3]2. 3. 동적 게임 및 베이즈 게임에서의 전략 집합
동적 게임이나 베이즈 게임처럼 일정 시간 동안 진행되거나 플레이어 간에 서로 불완전한 정보를 가진 게임에서는 전략 집합이 더 복잡한 형태를 띤다. 이러한 게임에서 전략 집합은 플레이어가 게임을 하는 방법에 대해 로봇 또는 에이전트에게 제공할 수 있는 가능한 규칙이나, 가능한 모든 개인 정보에 대해 어떤 행동을 할지에 대한 규칙으로 구성된다.[1] 예를 들어 최후통첩 게임에서 두 번째 플레이어의 전략 집합은 제안을 수락하거나 거부할 수 있는 모든 가능한 규칙으로 구성된다.[1]3. 순수전략과 혼합전략
순수전략은 경기자가 마주칠 수 있는 모든 상황에 대해 취할 행동을 결정하는, 게임 진행 방식에 대한 완전한 정의이다. 반면 혼합전략은 각 순수 전략에 확률을 할당하여, 플레이어가 순수 전략을 무작위로 선택하게 한다. 확률은 연속적이므로 플레이어가 사용할 수 있는 혼합 전략은 무한히 많다. 특정 순수 전략이 확률 ''1''로 선택되고 다른 모든 전략이 확률 ''0''으로 선택되는 경우, 순수 전략을 혼합 전략의 퇴화된 경우로 간주할 수 있다.
존 포브스 내시는 모든 유한 게임에 균형이 존재함을 증명했다. 내시 균형은 모든 플레이어가 순수 전략을 사용하는 ''순수 전략 내시 균형''과, 적어도 한 명의 플레이어가 혼합 전략을 사용하는 ''혼합 전략 내시 균형''으로 나눌 수 있다. 동전 던지기 게임은 순수 전략 내시 균형이 없는 게임의 예시이다. 그러나 조정 게임, 죄수의 딜레마, 사슴 사냥처럼 순수 전략 내시 균형을 가지는 게임도 많다. 또한, 게임은 순수 전략과 혼합 전략 균형을 모두 가질 수도 있다.
3. 1. 순수전략 (Pure Strategy)
순수전략은 경기자가 취할 수 있는 모든 행동의 완전한 계획(complete contingent plan)을 의미한다.[10] 경기자의 전략은 각 정보집합에서 어떤 행동을 취할 것인지에 대한 완전한 계획이다.[11]순수 전략은 플레이어가 어떻게 게임을 진행할지에 대한 완전한 정의를 제공한다. 이는 플레이 중에 관찰한 내용을 바탕으로 하는 구체적인 단일 계획으로 생각할 수 있다. 특히, 플레이어가 직면할 수 있는 모든 상황에 대해 어떤 행동을 취할 것인지 결정한다. 플레이어의 전략 집합은 해당 플레이어가 사용할 수 있는 순수 전략의 집합이다.
3. 2. 혼합전략 (Mixed Strategy)
혼합전략은 경기자가 선택할 수 있는 여러 순수전략을 특정 확률에 따라 무작위로 선택하는 전략이다. 경기자는 자신이 선택할 수 있는 여러 조합을 일정한 확률에 따라 무작위로 선택한다.순수 전략은 플레이어가 게임을 어떻게 진행할지에 대한 완전한 정의를 제공한다. 순수 전략은 플레이 중에 관찰한 내용을 바탕으로 하는 구체적인 단일 계획으로 생각할 수 있다. 특히, 플레이어가 직면할 수 있는 모든 상황에 대해 플레이어가 취할 행동을 결정한다. 플레이어의 전략 집합은 해당 플레이어가 사용할 수 있는 순수 전략의 집합이다.
혼합 전략은 각 순수 전략에 확률을 할당하는 것이다. 혼합 전략을 사용하는 이유는 종종 게임이 해당 게임에 대한 순수 전략을 지정하는 데 있어 합리적인 설명을 허용하지 않기 때문이다. 이를 통해 플레이어는 순수 전략을 무작위로 선택할 수 있다. 확률은 연속적이므로 플레이어가 사용할 수 있는 혼합 전략은 무한히 많다.
특정 순수 전략이 확률 ''1''로 선택되고 다른 모든 전략이 확률 ''0''으로 선택되는 경우, 순수 전략을 혼합 전략의 퇴화된 경우로 간주할 수 있다. 완전 혼합 전략은 플레이어가 모든 순수 전략에 엄격히 양의 확률을 할당하는 혼합 전략이다. (완전 혼합 전략은 균형 정제와 같은 떨리는 손 완전 균형에 중요하다.)
3. 2. 1. 혼합전략의 예시: 가위바위보
가위바위보는 혼합전략을 사용하는 대표적인 게임이다. 각 경기자는 가위, 바위, 보 세 가지 전략을 구사할 수 있으며, 경기자가 두 명이라고 가정했을 때 게임의 보수 행렬은 아래 표와 같다. 승자는 1점을 얻고, 패자는 1점을 잃으며, 비기면 모두 0점이다.| rowspan=2 colspan=2| | 경기자 B | |||
|---|---|---|---|---|
| 가위 | 바위 | 보 | ||
| 경기자 A | 가위 | (0, 0) | (-1, 1) | (1, -1) |
| 바위 | (1, -1) | (0, 0) | (-1, 1) | |
| 보 | (-1, 1) | (1, -1) | (0, 0) | |
가위바위보 게임에서는 순수전략 내쉬 균형이 존재하지 않는다. 각 경기자는 자신이 선택할 수 있는 행동을 무작위로 구사하는 혼합전략을 이용해야 한다. 각 경기자는 상대방이 어떤 행동을 할 확률을 기반으로 자신이 선택할 확률을 결정하는데, 각 경기자는 가위, 바위, 보를 각각 1/3만큼 배분한다.
3. 2. 2. 혼합전략 내쉬 균형 (Mixed Strategy Nash Equilibrium)
혼합전략은 경기자가 선택 가능한 여러 순수전략을 특정 확률에 따라 무작위로 선택하는 전략이다. 경기자는 상대방이 어떤 행동을 할 확률을 예측하고, 그에 따라 자신의 행동 확률을 조절하여 최적의 결과를 얻는다.[12][13]혼합전략에서 경기자의 최적 반응은 상대방의 기대 보수를 무차별하게 만드는 확률을 선택하는 것이다. 만약 상대방이 얻게 될 보수의 기대값이 무차별하지 않다면, 상대방은 보수 기대값이 가장 높은 행동만을 구사하는 순수전략을 사용하게 된다.[10]
예를 들어 가위바위보 게임에서는 순수전략 내쉬 균형이 존재하지 않으므로, 각 경기자는 가위, 바위, 보를 각각 1/3의 확률로 선택하는 혼합전략을 사용해야 한다.
축구의 페널티킥 상황을 예로 들어보자. 키커는 골대의 왼쪽이나 오른쪽으로 찰 수 있고, 골키퍼는 어느 방향으로 막을지 결정해야 한다. 이 경우에도 순수 전략 균형은 존재하지 않는다. 키커의 혼합전략 균형은 골키퍼가 왼쪽으로 쏠릴 확률을 g라고 했을 때, 왼쪽 킥과 오른쪽 킥의 기대 보상이 같아지도록 하는 확률을 찾는 것이다. 계산 결과 g=2/3 이다. 마찬가지로 골키퍼는 키커가 왼쪽으로 찰 확률 k가 1/3 일때 혼합전략을 사용한다. 따라서 혼합전략 균형은 (Prob(왼쪽으로 킥) = 1/3, Prob(왼쪽으로 쏠림) = 2/3)이다.[3]
Chiappori, Levitt, and Groseclose(2002)는 실제 프로 선수들의 페널티킥 데이터를 분석하여 선수들이 무작위로 행동하며, 키커는 선호하는 방향으로 45%의 시간 동안 킥하고 골키퍼는 해당 방향으로 57%의 시간 동안 쏠리는 것을 발견했다.[3]
3. 2. 3. 혼합 전략의 의의
혼합전략은 경기자가 선택할 수 있는 여러 순수전략 조합에 확률을 부여하여 무작위로 행동을 선택하는 전략이다. 경기자는 자신이 선택할 수 있는 여러 조합을 일정한 확률에 따라 무작위로 선택한다.혼합전략을 사용하는 대표적인 게임으로 가위바위보를 들 수 있다. 가위바위보 게임에서는 순수전략 내쉬 균형이 존재하지 않으므로, 각 경기자는 무작위로 행동을 선택하는 혼합전략을 사용해야 한다.
혼합전략에서 경기자의 최적 반응은 상대방이 얻을 보수의 기대값을 무차별하게 만드는 확률을 선택하는 것이다.[12][13] 만약 상대방의 보수 기대값이 무차별하지 않다면, 상대방은 보수 기대값이 가장 높은 행동만 선택하는 순수전략을 사용하게 된다.
어떤 행동을 선택할 확률 조합이 혼합균형에 있다면, 경기자가 선택하는 행동에서 얻는 기대 보수는 무차별하게 된다.[10]
축구 페널티킥에서 키커는 골대 왼쪽이나 오른쪽으로 찰지 결정하고, 골키퍼는 어느 방향으로 막을지 결정해야 한다. 이 게임에는 순수 전략 균형이 없다. 키커의 혼합 전략 균형은 왼쪽 킥과 오른쪽 킥의 보상이 같지 않으면 무작위로 행동하지 않는다는 사실에서 찾을 수 있다.
존 포브스 내시는 모든 유한 게임에 균형이 존재함을 증명했다. 내시 균형은 모든 플레이어가 순수 전략을 사용하는 *순수 전략 내시 균형*과, 적어도 한 명의 플레이어가 혼합 전략을 사용하는 *혼합 전략 내시 균형*으로 나눌 수 있다. 내시는 모든 유한 게임이 내시 균형을 갖는다는 것을 증명했지만, 모든 게임이 순수 전략 내시 균형을 갖는 것은 아니다. 동전 던지기 게임은 순수 전략 내시 균형이 없는 게임의 예시이다. 그러나 조정 게임, 죄수의 딜레마, 사슴 사냥처럼 순수 전략 내시 균형을 가지는 게임도 많다. 또한, 게임은 순수 전략과 혼합 전략 균형을 모두 가질 수도 있다.
4. 행동전략 (Behavior Strategy)
행동 전략은 각 정보 집합에서 가능한 행동에 대한 확률 분포를 할당하는 전략이다. 혼합 전략이 게임 트리 전체에서 결정론적 경로를 무작위로 선택하는 것이라면, 행동 전략은 확률적 경로를 선택하는 것으로 볼 수 있다.
혼합 전략과 행동 전략의 관계에 대한 더 자세한 내용은 해당 하위 섹션을 참조하라.
4. 1. 혼합전략과 행동전략의 관계
혼합 전략이 순수 전략에 확률 분포를 할당하는 반면, '''행동 전략'''은 각 정보 집합에 가능한 행동 집합에 대한 확률 분포를 할당한다. 두 개념은 정규형 게임의 맥락에서 매우 밀접하게 관련되어 있지만, 확장형 게임에 대해서는 매우 다른 함의를 갖는다. 대략적으로 혼합 전략은 게임 트리를 통해 결정론적 경로를 무작위로 선택하는 반면, 행동 전략은 확률적 경로로 볼 수 있다.혼합 전략과 행동 전략의 관계는 쿤의 정리의 주제이며, 전통적인 게임 이론적 가설에 대한 행동적 관점이다. 쿤의 정리는 완전 기억을 가진 유한한 확장형 게임에서 모든 플레이어와 모든 혼합 전략에 대해, 모든 전략 프로필(다른 플레이어의)에 대해 혼합 전략과 동일한 종단 노드에 대한 분포를 유도하는 행동 전략이 존재한다는 것을 확립한다. 그 반대도 사실이다.
등가의 필요조건으로 완전 기억이 필요한 이유에 대한 유명한 예는 피치오네(Piccione)와 루빈스타인(Rubinstein) (1997)의 ''부주의한 운전자'' 게임에서 제공된다.[9]
4. 1. 1. 완전 기억의 중요성: 부주의한 운전자 게임
완전 기억은 게임 내 모든 플레이어가 과거의 모든 행동을 기억하고 상기할 수 있는 능력으로 정의된다. 불완전 기억을 가진 유한 게임에서는 행동 전략과 동등한 혼합 전략이 존재하지 않으므로 완전 기억이 필요하다. 이는 피치오네(Piccione)와 루빈스타인(Rubinstein)이 공식화한 '부주의한 운전자' 게임에서 자세히 설명되어 있다.[9]'부주의한 운전자' 게임은 집으로 가기 위해 고속도로에서 두 번째 출구로 나가야 하지만, 그 지점에 도착했을 때 자신이 어떤 교차로에 있는지 기억하지 못하는 불완전 기억을 가진 운전자의 의사 결정에 기반한다.[9]
완전 정보(즉, 불완전 정보)가 없으면 플레이어는 이전의 의사 결정을 알지 못한 채 각 결정 노드에서 선택을 한다. 따라서 플레이어의 혼합 전략은 행동 전략이 할 수 없는 결과를 만들어낼 수 있으며, 그 반대도 마찬가지이다. 이는 '부주의한 운전자' 게임에서 입증된다. 완전한 기억과 정보를 가지고 있다면, 운전자는 자신이 어느 교차로(또는 결정 노드)에 도착했는지 알고 있기 때문에 [계속 진행, 출구]라는 단일 순수 전략을 갖는다. 반면에, 계획 최적 단계만 살펴보면, 최대 보상은 두 교차로 모두에서 계속 진행함으로써 달성되며, p=2/3에서 최대화된다.[9]
4. 2. 결과 동등성 (Outcome Equivalence)
결과 동등성은 상대방의 순수 전략과 관련하여 플레이어 i의 혼합 전략 및 행동 전략을 결합한다. 결과 동등성은 플레이어 i가 취하는 모든 혼합 및 행동 전략에 대해, 플레이어 i의 상대방이 플레이하는 모든 순수 전략에 대한 응답으로 혼합 및 행동 전략의 결과 분포가 동일해야 하는 상황으로 정의된다. 이 동등성은 다음 공식으로 설명할 수 있다. (Q^(U(i), S(-i)))(z) = (Q^(β(i), S(-i)))(z), 여기서 U(i)는 플레이어 i의 혼합 전략을 설명하고, β(i)는 플레이어 i의 행동 전략을 설명하며, S(-i)는 상대방의 전략이다.[8]참조
[1]
문서
"Game Theory: Lecture 1 Transcript"
Open Yale Courses
2007-09-05
[2]
서적
Game Theory. In: Palgrave Macmillan
Palgrave Macmillan
2017-03-22
[3]
학술지
Testing Mixed-Strategy Equilibria when Players Are Heterogeneous: The Case of Penalty Kicks in Soccer
http://pricetheory.u[...]
[4]
서적
Frontiers of Economics
Basil Blackwell
[5]
학술지
Comments on the interpretation of Game Theory
[6]
학술지
Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points
[7]
학술지
Epistemic Conditions for Nash Equilibrium
[8]
학술지
Outcome-equivalence of self-confirming equilibrium and Nash equilibrium
https://www.scienced[...]
2012-05-01
[9]
Arxiv
The Absent-Minded Driver Problem Redux
2017
[10]
서적
게임이론: 전략과 정보의 경제학
박영사
2018
[11]
서적
Strategy: An Introduction to Game Theory
https://archive.org/[...]
W. W. Norton
2013
[12]
서적
미시경제학
시그마프레스
2016
[13]
서적
Games of Strategy
W. W. Norton
2015
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com