게임 이론 개요
- 게임 참여자들이 어떤 결과를 가질 때 얻는 심리적 만족감은 개개인의 결정 뿐만 아니라 모든 참여자들로부터 만들어진 결정에 의존
- 게임의 3가지 재료
- Players (참가자)
- Strategies (전략): 참가자들의 행동
- Payoffs (각 참가자들이 얻는 결과): 모든 참가자들이 선택한 전략에 의존한다.
[G1] Exam-or-Presentation Game
- 2명이 한 팀 일 때, 2명 모두 발표를 준비하면 발표 100점, 시험 80점을 받고 평균 90점을 얻는다. 반대로 2명 모두 시험을 준비하면 시험 92점, 발표 84점을 받고 평균 88점을 얻는다. 한 명만 시험을 준비하고 다른 한 명이 발표를 준비한다면 결과는 다음과 같다.
- 발표를 준비한 한 명은 발표 92점이지만 시험은 80점을 얻고 평균 86점을 얻는다.
- 시험을 준비한 한 명은 여전히 발표 92점을 얻는다. 그 이유는 다른 한 명이 준비한 발표에 의해 혜택(benefit)을 얻는 것이다. 이 사람은 시험도 92점을 얻으므로, 결국 평균 92점을 얻는다.
-
- 위의 예시에서 payoff 는 각 참가자들이 시험에서 얻는 점수의 평균이다.
- 상대방의 선택을 분리해서 생각해보자. 먼저 상대가 시험을 공부할 것을 알고 내가 시험 공부해서 88점을 얻거나 발표 준비를 하면 86점을 얻는다는 사실을 알면 시험 공부를 할 것이다. 반대로 상대가 발표를 준비할 것을 알고 내가 발표를 준비해서 90점을 얻거나 시험 공부하면 92점을 얻는다는 사실을 알면 시험 공부를 할 것이다. (시험 공부의 결과가 점수가 더 높음) 결과적으로 참가자는 상대가 어떤 선택을 하던지 시험 공부를 할 것이다.
- 결국 평균 성적은 88점을 받을 것으로 기대된다. 그 이유는 시험 공부를 하는 것이 상대에 대한 strictly dominant strategy 이기 때문이다.
- Strictly dominant strategy: 참가자가 다른 참가자들이 하는 행동을 고려하지 않고 자신의 전략들 중 최선의 전략만 선택하는 것
- Striking phenomenon: 만약 모두 발표를 선택(평균 90점)할거라 생각하고 내가 발표를 하더라도 상대방은 결국 시험 공부(상대의 시험 점수는 92점)를 하기 때문에 평균 점수는 89점을 얻는다. 결국 평균 90점을 얻는 것은 성립될 수 없다.
- Rational Play(이성적인 플레이): 모든 참가자들은 자신의 이익을 극대화하려 한다.
[G2] The Prisoner’s Dilemma
- 용의자 2명이 자백(confess)을 하는 경우와 자백을 하지 않는 경우에 대한 payoff가 다음과 같다.
- 결국 자신의 이익만 극대화하는 선택을 하므로, 둘 다 자백하여 [-4, -4]를 선택하게 된다.
- 용의자 중 한 명이 자신의 선택에 대해 판단하는 방법: 용의자 2가 자백을 할 때 용의자 1이 자백하면 -4 안하면 -10을 얻는다는 사실을 알면 용의자 1은 자백(-4 > -10)을 할 것이다. 반대로 용의자 2가 자백을 하지 않을 때 용의자 1이 자백을 하면 0 안하면 -1을 얻는다는 사실을 알면 용의자 1은 자백(0 > -1)을 할 것이다. 결과적으로 “자백하기”는 strictly dominant strategy 이다.
[G3] Performance-Enhancing Drugs Game
- 해석: 운동선수 2가 약물을 복용하지 않을 경우 운동선수 1이 약물을 복용하면 4를 얻고 복용안하면 3을 얻는다는 사실을 알았을 때 운동선수 1은 약물을 복용(4 > 3)할 것이다. 반대로 운동선수 2가 약물을 복용할 경우 운동선수 1이 약물을 복용하면 2를 얻고 복용안하면 1을 얻는다는 사실을 알았을 때 운동선수 1은 약물을 복용(2 > 1)할 것이다.
- 약물 복용(drug)은 strictly dominant strategy 이다.
- Arms races(무기 경쟁): 두 경쟁자가 경기를 하기 위해 점점 위험한 무기고를 사용한다.
[G4] Exam-or-Presentation Game with an easier exam
- 해석: 상대가 시험 공부를 했을 경우 참가자는 시험 공부를 하면 92점을 받고 시험 공부를 안하면 96점을 받는다는 사실을 알았을 때 참가자는 시험 공부를 하지 않는다. 반대로 상대가 시험 공부를 하지 않았을 경우 참가자는 시험 공부를 하면 94점을 받고 시험 공부를 안하면 98점을 받는다는 사실을 알았을 때 참가자는 시험 공부를 하지 않는다. 결론적으로 상대의 선택이 무엇이든 시험 공부를 하지 않는 것이 참가자에게 좋은 점수를 준다.
게임 이론에서 중요한 두 가지 개념
- Best Response: 다른 참가자의 전략이 무엇인지에 대해 관찰할 수 있을 때 참가자가 하는 최선의 선택
- Dominant Strategy (우월전략): 다른 참가자의 모든 전략에 대해서 최선의 선택이 되는 전략 (한 참가자가 여러 개의 우월전략을 가질 수 있다. 상대의 전략에 따라 최선의 선택이 다름)
- Strictly dominant Strategy (강한 우월전략): 다른 참가자의 모든 전략에 대해서 엄격히 최선의 선택이 되는 전략 (1개만 존재한다. 상대의 전략이 무엇이든 최선의 선택은 1가지)
[G5] Marketing Strategy Game
- 전체 중 60% 정도의 낮은 가격을 선호하는 사람들과 전체 중 40% 정도 고급적인 버전을 선호하는 사람들이 있다. 회사 1은 매우 많은 인기 있는 브랜드이고 두 회사가 직접적으로 시장에서 경쟁할 때, 회사 1은 판매 중 80%를 차지하고 회사 2는 20%를 차지한다.
- 만약 한 회사가 주어진 시장에서 하나의 제품만 생산한다면 모든 판매를 얻는다. 두 회사가 다른 시장에서 제품을 판매한다면, 그들은 각각 그 시장에서 모든 판매를 담당한다.
- 가격이 낮은 시장을 대상으로 한다면 payoff는 0.6이고 고급적인 버전의 시장을 대상으로 한다면 payoff는 0.4이다. 만약 두 회사가 모두 낮은 가격의 시장을 대상으로 한다면 회사 1은 80%를 차지하고 payoff는 0.48 (=0.6 x 0.8)이다. 반대로 회사 2는 20%를 차지하고 payoff는 0.12 (=0.6 x 0.2)이다. 유사하게 두 회사가 고급적인 버전의 시장을 대상으로 한다면 회사 1은 payoff를 0.32 (=0.4 x 0.8) 이고 회사 2는 payoff를 0.08 (=0.4 x 0.2) 를 얻는다.
- 회사 1은 0.48이 제일 크므로, 낮은 가격의 시장에 진입하는 것이 strictly dominant strategy이다.
- 회사 2는 dominant strategy를 가지지 않는다. 낮은 가격의 시장에 진입하는 것은 회사 1이 고급적인 버전의 시장을 대상으로 할 때 최선의 선택이 되고, 고급적인 버전의 시장에 진입하는 것은 회사 1이 낮은 가격의 시장을 대상으로 할 때의 최선의 선택이다.
[G6] A Three-Client Game - 모든 참가자가 SDS(Strictly-Dominant-Strategy)가 없는 경우
- 두 회사가 같은 고객에 접근한다면, 그 고객은 각각 경영권을 절반씩 갖게 된다. 회사 1은 혼자 경영권을 얻기에는 너무 작아서, 회사 2가 다른 고객에게 접근하는 동안 한 고객에게 접근한다면 회사 1은 payoff를 얻지 못한다. 회사 2는 고객 B 또는 고객 C에 접근한다면 그들만의 완전한 경영권을 얻는다. 그러나 고객 A는 너무 큰 고객이고, 두 회사 모두 고객 A에 접근한다면 오직 그 회사들과 거래해야만 한다. 그 이유는 고객 A가 너무 크기 때문이다. 가치 8을 가지고 거래를 하는 경우(두 회사는 각각 가치 4를 얻음) 와 B또는 C를 경영하는 경우에 가치 2를 얻는 경우 (두 회사는 각각 가치 1을 얻음)
- 회사 1과 회사 2 모두 전략 A를 선택하는 경우, 서로 최선의 선택을 한 것이다. (내쉬 균형)
- Nash Equilibrium (내쉬 균형): 참가자 1이 전략 S를 고르고, 참가자 2가 전략 T를 고르는 경우, 전략 S가 전략 T에 대해 최선의 선택이고 전략 T도 전략 S에 대해 최선의 선택일 경우 (S, T)는 내쉬 균형이라고 한다. (균형상태)
- Nash Equilibrium = Equilibrium in belief.
- 왜 최선의 선택이 아닌 전략들의 쌍은 평형(equilibrium)이 아닌가?
- 적어도 한 명의 참여자는 다른 전략을 선택할 것을 알기 때문에, 참여자들이 실제 게임에서 이러한 전략들이 사용될 지는 확신할 수 없다. 만약 각 참여자들이 다른 참여자들은 내쉬 균형의 일부인 전략을 실제로 수행한 다고 믿는 경우, 그 때 참여자는 내쉬 균형의 일부 전략을 수행할 의지가 있다.
[G7] Coordination Game - Multiple Equilibria
- 팀원 2명이서 프로젝트 발표를 함께하기 위해 슬라이드를 각각 준비하고 있다. 한 명이 연락이 안되어서 지금 당장 슬라이드를 준비해야하는 상황이다. 파워포인트와 키노트 중 하나를 선택해야 한다.
- 두 가지 내쉬 균형이 존재한다.
- (파워포인트, 파워포인트)
- (키노트, 키노트)
- 다수의 내쉬 균형 중 1개를 선택하기
- 몇몇 게임에서 참여자가 내쉬 균형 중 하나에 집중하도록 하는 이유가 있었다.
- 예를 들어, 분할되지 않는 국경 도로에서 밤에 운전중인 두 운전자
[G10] Stag Hunt Game - 기본적인 조직 게임에서의 변수
- 두 참여자들이 비협력적일 때, 높은 payoff를 원하는 한 명이 낮은 payoff를 원하는 다른 한 명보다 더 많은 노력을 기울여야 한다.
- 실제로 더 낮은 payoff를 원하는 한 명은 어떤 노력도 기울이지 않는다.
[G11] Exam-or-Presentation Game (Stag Hunt version)
- 내쉬 균형이 2개 존재한다.
- (발표, 발표)
- (시험, 시험)
- 여기서 만약 더 높은 payoff의 내쉬 균형(나의 payoff가 높지 않을 수 있다.)을 선택하려고 한다면 다른 참여자들보다 시험 공부를 선택할 경우 나는 더 낮은 성적을 얻을 수 있다.
[G12] Hawk-Dove Game - Multiple Equilibria (anti-coordination)
- 두 동물이 대회에서 음식이 어떻게 나누어질 지 결정하도록 했다고 하자. 각 동물은 공격적으로 또는 소극적으로 행동을 선택할 수 있다. (Hawk or Dove strategy) 만약 두 동물 모두 소극적인 행동을 선택했다면, 공평하게 음식을 나눠가지고 각각 payoff 를 3씩 얻는다. 만약 한 동물이라도 공격적으로 행동하고 다른 하나가 소극적으로 행동했다면, 공격적인 동물이 음식의 대부분을 얻게되고 payoff를 5를 갖는 반면, 소극적인 동물은 payoff를 1을 갖는다. 그러나 두 동물 모두 공격적으로 행동한다면 음식은 사라지고 없을 것이다. 이 경우 payoff는 둘 다 0이다.
- 2개의 내쉬 균형이 존재한다.
- (소극적 행동, 공격적 행동)
- (공격적 행동, 소극적 행동)
- 다른 종류의 게임
내쉬 균형이 없는 게임 - Mixed Strategies
- 무작위의 가능성을 포함하는 전략들의 집합이 커진다.
- 일단 참여자들이 무작위로 행동을 하게 되면, 내쉬 균형은 항상 존재한다.
- 예를 들어, 공격-방어 게임(Attack-defense games)에서 참여자는 공격자와 방어자가 있고 공격자의 전략은 A와 B가 있을 때 방어자는 A에 대한 방어와 B에 대한 방어 두 가지 전략을 갖는다.
- 여기서 전략 집합 중 어느 하나를 선택해도 상대가 예측해서 더 나은 전략을 세우기 때문에 계속 순환하는 상황이 발생한다. 이에 대한 해결책으로 전략 집합을 크게 만들어 무작위로 섞는 것이다.
[G14] Matching Pennies Game (단순한 공격-방어 게임)
- 동전 맞추기 게임, 참여자는 앞과 뒤 중 하나를 선택한다. 동전을 맞추면 맞춘 사람에게 동전을 주어야 하고, 못 맞춘다면 못 맞춘 사람이 문제자에게 동전을 주어야 한다. 이 게임은 zero-sum 게임(제로 섬은 게임이나 경제 이론에서 여러 사람이 서로 영향을 받는 상황에서 모든 이득의 총합이 항상 제로 또는 그 상태를 말한다)이라고도 불린다.
- 다른 전략들: 참여자들 중 한 명이라도 행동을 바꾸는 경우 (한 명은 payoff로 -1을 얻고 전략을 바꾼 한 명이 payoff로 +1을 얻기 때문이다.)
- 내쉬 균형이 없는 경우 참여자는 그들의 동전을 서로서로 계속 뒤집는다. 그러므로 단순히 H또는 T를 가지면서 Matching Pennies Game에서 내쉬 균형이 존재하지 않는 것이다. 만약 서로서로의 전략을 알 수 있어서 어떤 참여자도 대체 전략으로 바꿀 수 있는 동기를 가지지 않는다면 내쉬 균형은 형성한다. 그러나 동전 뒤집기 게임에서는 참여자 1이 참여자 2가 H 또는 T를 고를 것이라는 것을 안다. 따라서 참여자는 반대를 선택하는 것으로 이를 이용할 수 있다.
- 현실에서는 참여자들이 상대가 자신의 행동을 예측하는 것을 어렵게하려고 한다.
- Mixed Strategy: 전략 H와 T 사이에 누군가는 무작위로 선택한다.
- H를 낼 확률 : T를 낼 확률 = i : j 라고 할 때 (i+j=100)으로 정해서 전략을 선택
- 무작위 행동
- 확률적으로 전략을 선택
- 전략 집합은 0~1 사이의 숫자로 표현되고 선택지 H와 T 사이에 mixing이 있다.
- 두 전략을 섞는 것 (Mixed Strategy) → 확률이 0 또는 1이라면 전략 H 또는 T를 수행하는 것이다.
- 이를 두 가지 pure strategies 라고 한다.
- Mixed Strategy 로부터 Payoffs
- 각 참여자는 몇몇 확률을 가지고 +1을 얻고, 남은 확률을 가지고 -1을 얻는다.
- payoff의 기댓값을 사용한다.
- p: H를 선택하는 사람이 낼 확률
- q: T를 선택하는 사람이 낼 확률
- 참여자 2가 확률 q이고, 참여자 1이 pure strategy H를 선택했다면,
- 참여자 1의 payoff 기댓값은 (-1)*q+1*p = (-1)*q + 1*(1-q) = 1-2*q 가 된다.
- 첫번째 항: -1은 참여자 1이 H를 선택할 확률이고, q는 참여자 2가 H를 선택할 확률
- 두번째 항: 1은 참여자 1이 H를선택할 확률이고, (1-q)는 참여자 2가 T를 선택할 확률
- p와 q를 찾는 것이 내쉬 균형을 찾는 것이다.
- Matching Pennies game의 Mixed Strategy 버전
- 전략 = H를 선택하는 확률
- Payoff = 4 가지 pure 결과( [H,H], [H,T], [T,H], [T,T] )로부터 payoff의 기댓값
- Equilibrium with Mixed Strategy
- 내쉬 균형: 각각 서로에게 최선의 선택인 전략 쌍들 (여기서는 확률로 표현)
- 어떠한 pure strategy도 내쉬 균형을 구성할 수 없다.
- 참여자 1의 최선의 선택이 참여자 2에 의해 만들어진 전략 q일 수 있나?
즉, 1-2q = 2q -1 을 갖게 하면 내쉬 균형에 대한 확률을 얻는다.
- Mixed Strategy Equilibrium 의 의미
- 참여자 2에 의해 전략 q=½ 인 경우: 참여자 1은 전략 H 또는 T 사이의 확률로 플레이하는 것이 비효율적이게 된다. 즉, 전략 q=½ 는 참여자 1에 의해 non-exploitable 이라고 한다.
- 실제로 왜 우리가 무작위를 도입해야하는지에 대한 이유는 각 참여자가 그들의 행동이 예측 불가능하길 원하기 때문이다. 그래서 그들의 행동으로부터 상대가 이득을 취할 수 없다.
- 두 가지 선택의 확률이 서로서로에게 최선의 선택이다.
- 내쉬는 모든 이러한 게임은 적어도 하나 이상 mixed-strategy equilibrium을 가진다고 증명했다.
[G15] Run-Pass Game - More on Mixed Strategy Equilibrium
- 방어가 정확하게 공격 플레이(Pass or Run)와 매치한다면, 공격은 0 yards를 얻는다.
- 공격이 방어가 경로를 막는 동안 수행되면, 공격은 5 yards를 얻는다.
- 공격이 방어가 수행을 막는 동안 수행되면, 공격은 10 yards를 얻는다.
- pure strategy를 갖는 내쉬 균형은 없다. 공격, 방어 둘 다 행동을 무작위로 선택해야 한다.
- p = 공격이 pass하는 확률
- q = 방어가 pass를 막을 확률
- 내쉬의 결과로부터, 적어도 하나는 mixed-strategy equilibrium이 존재해야 한다.
[방어가 pass를 막을 확률 q를 선택한 경우]
- 공격이 pass할 때의 payoff 기댓값은 0*q+10*(1-q)=10-10q 이다.
- 첫번째 항: 0은 (방어가 pass 막을 때) 공격이 pass할 확률, q는 방어가 pass를 막을 확률
- 두번째 항: 10은 (방어가 run 막을 때) 공격이 pass할 확률, 1-q는 방어가 run을 막을 확률
- 공격이 run할 때의 payoff의 기댓값은 5*q+0*(1-q)=5q이다.
- 첫번째 항: 5는 (방어가 pass 막을 때) 공격이 run할 확률, q는 방어가 pass를 막을 확률
- 두번째 항: 0은 (방어가 run 막을 때) 공격이 run할 확률, 1-q는 방어가 run을 막을 확률
- 방어가 두 전략 사이에 변함없게 하려면 10-10q=5q 가 되도록 q=⅔ 이어야 한다.
[공격이 pass하는 확률 p를 선택한 경우]
- 방어가 pass를 막을 때의 payoff 기댓값은 0*p+(-5)*(1-p)=5p-5 이다.
- 첫번째 항: 0은 (공격이 pass일 때) 방어가 pass를 막을 확률, p는 공격이 pass할 확률
- 두번째 항: -5는 (공격이 run일 때) 방어가 pass를 막을 확률, 1-p는 공격이 run할 확률
- 방어가 run을 막을 때의 payoff 기댓값은 (-10)*p+0*(1-p)=-10p 이다.
- 첫번째 항: -10은 (공격이 pass일 때) 방어가 run을 막을 확률, p는 공격이 pass할 확률
- 두번째 항: 0은 (공격이 run일 때) 방어가 run을 막을 확률, 1-p는 공격이 run할 확률
- mixed-strategy equilibrium에서 나타날 수 있는 가능한 확률 값: p=⅓, q=⅔
- 공격의 payoff 기댓값 = 10/3
- 방어의 payoff 기댓값 = -10/3
[G16] Penalty-Kick Game
- 전문 축구에서 1400개의 페널티 킥의 분석을 기반으로, Palacios-Huerta는 4가지 기본 결과 (kicker가 왼쪽 또는 오른쪽을 목표로 했는지, 그리고 goalie가 왼쪽 또는 오른쪽으로 막으려 했는지) 각각에 대해 점수를 매기는 경험적 확률을 결정했다.
- 기본적인 동전 뒤집기 게임과 관련된 몇 가지 주목해야 할 대조되는 점이 있다. 첫번째, kicker는 goalie가 정확한 방향으로 막으려할 때마다 점수를 얻을 좋은 기회를 합리적으로 가진다. 비록 goalie에 의한 정확한 선택이 여전히 이러한 확률을 완전히 줄일지라도 말이다. 두번째, kicker는 일반적으로 오른쪽 방향으로 공을 찼고 여기서 점수를 얻을 기회는 왼쪽을 목표로 하는 것과 오른쪽을 목표로 하는 것 사이에서 완전히 대칭적이지 않았다.
- 여전히 동전 뒤집기의 기본적인 전제가 여기서도 나타난다. pure strategies에서 균형이 없는 것, 그리고 게임 플레이 시 무작위로 행동하는 것
- goalie가 왼쪽 방향을 막을 때의 확률을 q라고 한다면, 확률 q로 두 선택지 사이에 kicker는 다르지 않다는 걸 만들 필요가 있다. → 0.58 * q + 0.95 * (1-q) = 0.93q + 0.70(1-q) → 이 수식을 풀면 q=0.42 이다. 유사하게 p=0.39 이다.
-
내쉬 균형이 있는지 검사 (하나가 최대 이득을 얻을 때, 다른 하나가 최대 이득을 얻는 전략이 하나라도 없는 경우 내쉬 균형은 존재하지 않는다.)
-
mixed-strategy 로 균형을 찾아야 한다. 확률 p와 q를 정의
-
각 p와 q를 이용해서 비례식을 만들고, 계산해서 p와 q를 구한다.
'Software Application > Game Theory' 카테고리의 다른 글
| 게임 이론을 이용한 네트워크 트래픽 모델링 (0) | 2019.12.26 |
|---|