내쉬균형(Nash Equilibrium)

앞서 도출한 우월전략균형이나 강열등전략의 반복적제거는 우월전략이나 강열등전략이 있는 특수한 경우에서만 적용이 가능하다.

따라서 일반적인 상황에서도 적용할수 있는 균형개념이 필요하다.

---

균형

게임의 경기자들 중 외부적 충격없이(게임구조의 변화)는 아무도 자신의 전략을 수정할 유인이 없는 상태를 의미한다. 

내쉬 균형

2인 게임에서 전략명세 $(s_1^*,s_2^*)$가 다음을 만족하면 $(s_1^*,s_2^*)$는 내쉬 균형이다.

- 모든 $s_1\in S_1$에 대해 $u_1(s_1^*,s_2^*)\ge u_1(s_1,s_2^*)$가 성립

- 모든 $s_2\in S_2$에 대해 $u_2(s_1^*,s_2^*)\ge u_2(s_1^*,s_2)$가 성립

이때 각 경기자가 사용하는 전략 $s_1^*,s_2^*$를 균형전략이라고 한다.

-> 모든 경기자들이 현재 위치한 전략명세에서 단독이탈할 유인이 없는 상태

 

위의 내쉬균형을 $n$명에 대한 내쉬균형으로 확장하면 다음과 같다.

모든 경기자 $i$에 대해 다음 조건이 만족되면 전략명세 $(s_1^*,\cdots,s_n^*)$는 내쉬균형이다. 

- 모든 $s_i\in S_i$에 대해 $u_i(s_i^*,s_{-i}^*)\ge u_i(s_i,s_{-i}^*)$ ($s_{-i}$는 $s$를 제외한 경기자들의 전략을 의미)

 

위와 같은 정의로 인해 내쉬균형은 경기자들의 전략수정이 더이상 없는 안정적인 상태를 의미한다. 

 

내쉬 균형을 찾는 방법

1. 각 전략명세를 NE(내쉬균형)상태라고 가정했을 때 각 경기자들이 현재 상태에서 단독이탈할 유인(더 나은 보수를 주는 전략명세가 존재)

    이 있는지 확인한다.

2. 최적대응(Best Response)를 이용하여 NE(내쉬균형)찾기 

 

- 최적대응: 상대방 전략이 주어졌을 때 나의 보수를 극대화하는 전략을 최적대응이라고 한다. 

  주어진 2의 전략 $s_2$에 대한 1의 최적대응 $BR_1(s_2)$는 $u(s_1,s_2)$를 극대화하는 1의 전략 s_1을 가리킨다. 

  즉 $BR_1(s_2)\in S_1$은 다음을 만족하는 전략이다. 

  -> 모든 $s_1\in S_1$에 대해 $u_1(BR_1(s_2),s_2)\ge u_1(s_1,s_2)$

 

- 최적대응과 내쉬균형

   $(s_1^*,s_2^*)$가 내쉬균형이면 $s_1^*\in BR_1(s_2^*)$이고 $s_2^*\in BR_2(s_1^*)$이다.

   -> 나의 전략은 상대의 전략에 대한 최적대응이며 상대방 전략 또한 나의 전략에 대해 최적대응인 상태

        각 경기자들에 대해 모두 최적대응이 성립하여 누구도 전략을 수정할 유인이 없는 상태

 

 예시-1) 내쉬균형 정의를 이용해 내쉬균형 찾기

NE를 전략명세(T,N)로 선택했을 때 각각의 보수는 (1,1)이므로 경기자1은 보수가 2인 S로 경기자2는 보수가 2인 W로 전략을 수정할 유인이 존재하므로 NE가 성립되지 않는다.

NE를 전략명세(S,N)로 선택했을 때 각각의 보수는 (2,1)이므로 경기자1은 이탈유인이 없으며 경기자2 또한 W선택시 보수가 1로 같으므로 이탈할 유인이 없다 따라서 NE가 성립한다. 

NE를 전략명세 (T,W)로 선택했을 때 각각의 보수는 (0,2)이므로 경기자1은 S를 선택하여도 보수가 0으로 같으므로 이탈할 유인이 없고   경기자2는 W의 보수가 더 크기때문에 이탈할 유인이 없다 따라서 NE가 성립한다.

NE를 전략명세 (S,W)로 선택했을 때 각각의 보수는 (0,1)이므로 경기자1은 T를 선택하여도 보수가 0으로 같으므로 이탈할 유인이 없고    경기자2는 N선택시 보수가 1로 동일하므로 이탈할 유인이 없다. 따라서 NE가 성립한다.

 

위의 경우처럼 한 게임에 여러 내쉬균형이 존재할 수 있다.

 

예시-2) 최적대응을 이용해 내쉬균형 찾기

경기자2가 L을 선택했을 때 경기자1의 최적대응은 $BR_1(L)=\{B\}$이다.

경기자2가 R을 선택했을 때 경기자1의 최적대응은 $BR_1(R)=\{T,B\}$이다.

경기자1이 T를 선택했을 때 경기자2의 최적대응은 $BR_2(T)=\{R\}$이다.

경기자1이 B를 선택했을 때 경기자2의 최적대응은 $BR_2(B)=\{L,R\}$이다. 

각 경기자들의 최적대응전략이 교차하는 지점이 내쉬균형이다. 위에서는 전략명세 (B,L),(B,R),(T,R)가 내쉬균형이다. 

 

최적대응은 상대방의 전략에 대해 정의되며 이를 이용해 도출한 내쉬균형은 유일하지 않을 수 있다.