Two important concept in Game Theory

게임 이론에서 2가지 중요한 컨셉 : 베스트 리스폰스, 도미넌트 스트래터니

- 베스트 리스폰스 : 다른플레이어가 어떤 선택을 할 지를 고려했을 때의 한 플레이어의 입장에서 최선의 선택

 

S : 플레이어 A의 전략

T : 플레이어 B의 전략

P1(S,T) : 플레이어A가 S, T일 경우 받을 보상 (PayOff)

P2(S,T) : 플레이어B가 S, T일 경우 받을 보상 (PayOff)

 

이때 Best Response란 P1(S,T) >= P1(S', T)일 때의 플레이어 A가 선택할 S를 말한다.

즉, 플레이어B가 T를 고른다고 가정했을 때 플레이어 A가 B를 이기거나 비길 수 있도록 택하는 전략이다.

혼자 결정하는 것이 아니기 때문에, 전략이 조합이 모든 것을 결정함.

 

-> 상대의 전략 t를 확인했을 때, S말고 S'를 선택했을 때 이득이 없는 상황이 될 때  S가 베스트 리스폰스다.

 

Strict best response란? 

P1(S,T) > P1(S', T)인 경우 플레이어 A가 선택할 S를 말한다.

그냥 best response는 비길 때도 포함하지만 strict가 붙으면 무조건 이기는 전략을 말한다.

플레이어 B의 모든 전략에 Best Response인 것을 말한다.

 

Strictly Dominant Strategies 란?

플레이어 B의 모든 전략에 Strict Best Response인 것을 말한다.

= 상대가 어떤 선택을 하든 베스트 리스폰스가 있을 때!

 

• 두 회사가 있다.
• 각 회사는 저가 상품 (Low pirced)으로 마케팅할 수 있고, 고급 상품 (Upscale)으로 마케팅할 수 있다.
• 아래 각 회사의 선택에 따른 이익 비율(Payoff)가 있다.

- 게임 이해

과연 두 회사는 어떤 선택을 할까?

이 게임은 한 회사만 Strictly dominant strategy를 갖고, 다른 회사는 갖지 않을 것이다.

위 payoff표를 보면 회사 A는 무조건 저가 상품으로 시장을 공략할 것이다 (strictly dominant strategy)

그러나 회사 B는 회사 A에 따라 전략이 바뀌기 때문에 strictly dominant strategy를 가질 수 없다.

한 회사만 SDS를 갖는다면 과연 둘의 결과를 예측할 수 있을까?

 

가능하다.

왜냐하면 회사 B는 rational play에 따라 더 이익이 남는 곳을 선택할 것이다.

회사 A는 무조건 저가 상품으로 시장 공략을 할 것이기 때문에, B는 고급 상품으로 시장 공략을 해 이윤을 남길 것이다.

따라서 회사 B는 울며 겨자먹기 식으로 무조건  고급 상품으로 시장 공략을 할 것이라고 예측할 수 있다.

 

회사 1은 유명한 브랜드 → 직접 경쟁을 하면 전체 세일즈의 80%를 가져가고, 회사2는 하꼬 회사 → 20%만 가져가게 된다.

 

두 회사 다 로우 프라이스드로 간다. → 전체 마켓의 60%정도를 차지하는 마켓. 그걸 나눠 가져야 하는 상황이 됨.

두 회사다 업스케일의 경우엔 시장이 전체의 40% → 비율이 8:2니까 똑같이 32, 8이 됨.

 

 

- 게임 이해

클라이언트가 3명!

회사 2개인데 클라이언트는 3명. 어느 클라이언트를 공략할 것인가 고르는 것.

• 두 회사가 같은 클라이언트에 접근하면 반씩 나눠준다.
• 펌1은 작은회사라 혼자서는 안됨. 혼자하면 페이오프가 0임.
• A클라이언트는 큰 클라이언트라 같이 가야지 감당 가능.
• 크기? A : 8, B,C : 2임.

이걸 읽고 그림을 그리는데. 각 플레이어의 전략이 3가지임.

A,A → 반반이니까 44나눠주겠지. 나머지도 다 이해되지?

펌2번은 큰회사라서 혼자 BC에 접근하면 처리 가능한데, A에 혼자 접근할 땐 안됨. 이걸 읽고 그림을 그리는 것 자체가 쉽지않음.

 

그 다음 해야할 일은 예측을 해 보는것.

펌1입장에서는 펌2를 따라가야함. 상대의 전략에 따라서 펌1이 가져야 될 전략이 달라짐.

펌2입장에서는 펌1이 A하면 B, B하면 C, C하면 B겠지.

→ 두 플레이어 다 스트릭틀리 도미넌트 스테리터지가 없음.

→ 어떡하지?

 

플레이어 1이 S, 플레이어 2가 T라는 전략을 선택했다.

S가 T, T가 S에 대해. 즉 상호간에 베스트 전략이 되면 이것을 Nash Equilibrium이라 한다.

-> 다른 전략으로 바꿨을 때의 인센티브가 없다면 변경을 멈추게 됨 = 이퀼리브리엄 상태가 됨.

 

왜 서로에게 베스트 리스폰스가 아니면 이퀼리브리엄이 아닐까?

이퀼리브리엄 → 움직이지않고 가만히 있는 상태 : 아니라는건 누군가가 움직일 것이라는 얘기.

 

이 전략들이 실제로 게임에서 사용될 것이라 둘 다 믿지 못함

왜? 적어도 한 플레이어는 다른 전략으로 옮겨타는게 이득이니까. 그리고 이걸 둘 다 알고있음.

각 플레이어가 내쉬 이퀼리브리엄이 되는 전략을 선택할것이다라고 믿게되면, 기꺼이 그렇게 선택할 것이다.

 

따라서 서로의 전략에 따라 달라진다.

if ) 1번 회사가 A를 선택하고 2번 회사도 A를 선택한다면?

A,A가 nash equilibrium인지 체크 할 수 있어야 함.

-> 서로 A일 때가 가장 이득. 옮겼을 때의 인센티브가 없음.

if ) B,B는? -> 펌2는 C로 옮겨갈 것!

 

- 게임 이해

멀티플 이퀼리브리아인 상황.

 

• 두 가지 내쉬 균형이 존재한다.
  • (파워포인트, 파워포인트)
  • (키노트, 키노트)

Focal point : 외부적 요인으로 하나 선택!

• 다수의 내쉬 균형 중 1개를 선택하기
  • 몇몇 게임에서 참여자가 내쉬 균형 중 하나에 집중하도록 하는 이유가 있었다.
  • 예를 들어, 분할되지 않는 국경 도로에서 밤에 운전중인 두 운전자

 

밤에 운전중이라면. 눈치껏 오른쪽으로 붙겠지..?

 

- 게임 이해

변종 case : 페이오프가 바뀌는 것!

 

- 스태그헌트

한 사람이 큰 쪽, 한 사람이 작은 쪽으로 선택하면 miscoordinate된 것. 동일한 타겟으로 간 것을 코디네잇이라고 함.

 

• 만약 두 참여자들이 비협력적일 때, 높은 payoff를 원하는 한 명이 낮은 payoff를 원하는 다른 한 명보다 더 많은 노력을 기울여야 한다.
• 실제로 더 낮은 payoff를 원하는 한 명은 어떤 노력도 기울이지 않는다.

 

 

코디네이션은 같은 전략을 선택했을 때 서로에 이득이되는 경우. 안티 코디네이션은 서로 피해야되는 상황.

공격적으로 선택하는 것을 호크 전략, 쫄보가 도브 전략

 

먹이의 총량이 6임. 호크는 5를 가져감. 둘 다 호크하면 상이 엎어지고 난리나는 것.

→ 그럼 도브로 이동해야겠지… 00이었는데 상대가 5를 갖게 되지만 어쨋든 1이라도 보니까. 개인의 이득을 극대화 하겠다는 것.

 

• 2개의 내쉬 균형이 존재한다.
  • (소극적 행동, 공격적 행동)
  • (공격적 행동, 소극적 행동)

 

프레젠테이션 게임을 Hawk-Dove 게임으로 한다면,

상대가 프레젠테이션을 준비한다면 난 Exam으로 가야함

-> 상대가 Exam한다면 난 프레젠테이션으로 가야함.

-> 이런 상황을 치킨게임이라고 한다.

 

 

 

SDS, Nash Equi를 이용하여 예측하는건 Randomness가 없음. 최선만 존재함.

 But, 전략을 MIX하게된다. 가위바위보는 SDS도 NE도 없음.

 

 

• 무작위의 가능성을 포함하는 전략들의 집합이 커진다.
• 일단 참여자들이 무작위로 행동을 하게 되면, 내쉬 균형은 항상 존재한다.
• 예를 들어, 공격-방어 게임(Attack-defense games)에서 참여자는 공격자와 방어자가 있고 공격자의 전략은 A와 B가 있을 때 방어자는 A에 대한 방어와 B에 대한 방어 두 가지 전략을 갖는다.
• 여기서 전략 집합 중 어느 하나를 선택해도 상대가 예측해서 더 나은 전략을 세우기 때문에 계속 순환하는 상황이 발생한다. 이에 대한 해결책으로 전략 집합을 크게 만들어 무작위로 섞는 것이다.

 

같은 면을 내미는 것을 MATCH -> 1이 2에 페니를 줌

다른 면을 내밀면 -> 2가 1에 페니를 줌

 

1은 매치를 싫어하기에 뒤집고, 그럼 2가 또 매치하기 위해 뒤집고 -> NE가 없고, 어느 컴비네이션도 만족하지 않음.

 

NE : 상대의 전략을 아는 상황에서도 두 플레이어 누구 하나 다른 전략으로 바꿨을 때 인센티브가 없는 상황

-> 상대의 전략을 알면 이용. 내 전략은 알리면 안됨.

 

따라서 확률을 생각해야함. 플레이어는 각 행동 H,T를 선택하는게 아니라 확률을 뽑는 것임.

 

어떤 확률에 따라 이기고 지고 한다 -> 전략이 Mixing되어야함 ->  Payoff의 기대값을 구해야한다.

• Mixed Strategy: 전략 H와 T 사이에 누군가는 무작위로 선택한다.
  • H를 낼 확률 : T를 낼 확률 = i : j 라고 할 때 (i+j=100)으로 정해서 전략을 선택
• 무작위 행동
  • 확률적으로 전략을 선택
  • 전략 집합은 0~1 사이의 숫자로 표현되고 선택지 H와 T 사이에 mixing이 있다.
  • 두 전략을 섞는 것 (Mixed Strategy) → 확률이 0 또는 1이라면 전략 H 또는 T를 수행하는 것이다.
  • 이를 두 가지 pure strategies 라고 한다.

• p: H를 선택하는 사람이 낼 확률
• q: T를 선택하는 사람이 낼 확률
• 참여자 2가 H를 선택할 확률이 q일 때, 
  • 참여자 1의 payoff 기댓값은 (-1)*q+1*p = (-1)*q + 1*(1-q) = 1-2*q 가 된다.
  • 첫번째 항: -1과 1은은 참여자 그룹이 HH,HT를 선택했을 때 결과, q는 참여자 2가 H를 선택할 확률
  • 두번째 항: 1과 -1은 참여자 그룹이 TH,TT를 선택했을 때 결과, (1-q)는 참여자 2가 T를 선택할 확률
• p와 q를 찾는 것이 내쉬 균형을 찾는 것이다.

-> 플레이어 2는 상대가 H,T를 고를 때 나올 기댓값이 같도록 만들어야함. 따라서 q=1/2.

-> 그래야 플레이어 2가 플레이어 1에 의해 exploit(이용)되지 않는다.

-> 플레이어 2가 결정할 때 나오는 payoff 기대값이 같도록 해줘야 상대가 대응을 못하겠지?

 

• Equilibrium with Mixed Strategy
  • 내쉬 균형: 각각 서로에게 최선의 선택인 전략 쌍들(베스트 리스폰스) -> mixed strategy에서도 동일하게 적용되어야함.
  • 어떠한 pure strategy도 내쉬 균형을 구성할 수 없다
• 참여자 1의 최선의 선택이 참여자 2에 의해 만들어진 전략 q일 수 있나?

 

1-2q ≠ 2q-1이라면 p,q중에 뭐가 더 좋은지 플레이어 1 입장에서 판단하여 베스트 리스폰스가 나올 수 있음.

즉, 1-2q = 2q -1 을 갖게 하면 내쉬 균형에 대한 확률을 얻는다

 

Mixed Strategy Equilibrium 의 의미

• 참여자 2에 의해 전략 q=½ 인 경우: 참여자 1은 전략 H 또는 T 사이의 확률로 플레이하는 것이 비효율적이게 된다. 헤드를 내미나 테일을 내미나 똑같다. 즉, 전략 q=½ 는 참여자 1에 의해 non-exploitable 이라고 한다.
• 실제로 왜 우리가 무작위를 도입해야하는지에 대한 이유는 각 참여자가 그들의 행동이 예측 불가능하길 원하기 때문이다. 그래서 그들의 행동으로부터 상대가 이득을 취할 수 없다.
• 두 가지 선택의 확률이 서로서로에게 최선의 선택이다.
• 내쉬는 모든 이러한 게임은 적어도 하나 이상 mixed-strategy equilibrium을 가진다고 증명했다.

 

미식축구케이스.

 

• 방어가 정확하게 공격 플레이(Pass or Run)와 매치한다면, 공격은 0 yards를 얻는다.
• 공격이 방어가 경로를 막는 동안 수행되면, 공격은 5 yards를 얻는다.
• 공격이 방어가 수행을 막는 동안 수행되면, 공격은 10 yards를 얻는다.

 

 

• pure strategy를 갖는 내쉬 균형은 없다. 공격, 방어 둘 다 행동을 무작위로 선택해야 한다.
• p = 공격이 pass하는 확률
• q = 방어가 pass를 막을 확률
• 내쉬의 결과로부터, 적어도 하나는 mixed-strategy equilibrium이 존재해야 한다.

 

→ 예측이 힘든거 아니야?

퓨어 스트 네시 이퀼리 있냐 확인하였으나 → 4가지 컴비네이션 중에 있겠지? → 돌다보니 다 돌고, 없넹.

→ 어쩔 수 없이 랜더마이즈 해야겠다.

 

[방어가 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=⅔ 

 

이 나온 값들을 식에 넣어보면, 오펜스의 페이오프는 10/3, 디펜스의 페이오프는 -10/3가 나옴.

그럼 왜 패스는 1/3만하고 런을 2/3 하느냐. 이 상황이 페이오프 기댓값이 제일 높기때문.

만약 공격측이 패스확률을 더 높인다면, 디펜스하는쪽에서도 변화를 주겠지 → 공격측의 기대값이 더 안좋아짐.

p값을 1/2로 예를들어 집어넣으면 5/2(<10/3) 나옴.

 

 

• 전문 축구에서 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를 구한다.