내쉬 균형
아무도 전략을 바꿀 이유가 없는 상태
존 내쉬의 아름다운 마음
1950년, 프린스턴 대학의 21살 대학원생 존 내쉬(John Nash)가 27페이지짜리 박사논문으로 세상을 바꿨습니다. 그는 "모든 유한 게임에는 최소 하나의 균형이 존재한다"는 것을 증명했습니다.
내쉬 균형이란 "어떤 플레이어도 혼자서 전략을 바꿔서 더 나은 결과를 얻을 수 없는 상태"입니다. 쉽게 말해, "나 혼자 바꿔봤자 손해"인 상태가 내쉬 균형입니다.
- 내쉬 균형을 찾는 "최적반응" 방법을 익히기
- 복수 균형이 존재하는 게임에서 초점(focal point) 이해
- 순수전략 균형이 없을 때 혼합전략 균형 계산
- 교통 혼잡 게임과 Braess의 역설 체험
내쉬 균형이란?
내쉬 균형(Nash Equilibrium): 모든 플레이어가 상대의 전략을 알고 있을 때, 어떤 플레이어도 일방적으로 자신의 전략을 바꿔서 더 높은 보수를 얻을 수 없는 전략 조합.
1단계: 각 플레이어의 최적반응(Best Response)을 찾습니다.
- B가 전략1을 선택할 때 A의 최적 전략은? → 해당 보수에 밑줄
- B가 전략2를 선택할 때 A의 최적 전략은? → 해당 보수에 밑줄
- A가 전략1을 선택할 때 B의 최적 전략은? → 해당 보수에 밑줄
- A가 전략2를 선택할 때 B의 최적 전략은? → 해당 보수에 밑줄
2단계: 두 밑줄이 모두 그어진 칸이 내쉬 균형입니다.
내쉬 균형은 "가장 좋은 결과"가 아닙니다. 죄수의 딜레마에서 내쉬 균형은 (배신, 배신)이지만, (협력, 협력)이 모두에게 더 좋습니다.
내쉬 균형은 "안정적인 상태"입니다. 아무도 이탈할 이유가 없는 상태.
1. 내쉬 균형 찾기 도구
행렬 크기를 선택하고 보수를 입력하세요. "분석" 버튼을 누르면 각 플레이어의 최적반응이 밑줄로 표시되고, 두 밑줄이 만나는 지점이 내쉬 균형으로 하이라이트됩니다.
3x3 행렬을 생성하고, "랜덤 보수"를 눌러 다양한 게임을 분석해 보세요.
내쉬 균형이 0개, 1개, 2개 이상인 경우를 각각 찾을 수 있나요?
2. 좌표 게임: 어디서 만날까?
당신과 친구가 각각 영화관을 선택합니다. 같은 곳을 고르면 만날 수 있고(보수 1), 다른 곳을 고르면 못 만납니다(보수 0). 사전 연락 없이 어디를 골라야 할까요?
영화관을 선택하세요 (친구도 동시에 선택합니다):
토마스 셸링은 이런 상황에서 사람들이 "자연스럽게 떠오르는" 선택지를 고르는 경향이 있다는 것을 발견했습니다.
뉴욕에서 "어디서 만날까?"라고 하면 대부분 그랜드 센트럴 역을 떠올립니다.
이것이 초점(focal point) 또는 셸링 포인트(Schelling point)입니다.
가장 유명하거나, 가장 눈에 띄거나, 가장 '당연한' 선택지가 초점이 됩니다.
"서울에서 만나자"라고 했을 때, 당신은 어디를 선택하겠습니까?
대부분의 한국인이 같은 장소를 떠올린다면, 그것이 셸링 포인트입니다.
3. 혼합전략 균형: 동전 맞추기 게임
동전 맞추기(Matching Pennies): A는 같은 면이 나오면 이기고, B는 다른 면이 나오면 이깁니다. 이 게임에는 순수전략 내쉬 균형이 없습니다!
| B: 앞면 | B: 뒷면 | |
|---|---|---|
| A: 앞면 | (1, -1) | (-1, 1) |
| A: 뒷면 | (-1, 1) | (1, -1) |
해결책: 확률적으로 선택하는 혼합전략! A가 앞면을 낼 확률 p, B가 앞면을 낼 확률 q를 슬라이더로 조절하세요.
슬라이더를 움직여 보세요. A의 기대보수가 최대가 되는 p는?
B의 기대보수가 최대가 되는 q는?
4. 교통 혼잡 게임과 Braess의 역설
100명의 운전자가 A에서 B로 이동합니다. 두 경로가 있습니다. 모든 운전자가 한 경로로 몰리면 혼잡해집니다. 내쉬 균형은 어떤 상태일까요?
경로 1 (고속도로)
이용자: 50명
소요시간: -분
기본 20분 + 이용자수 x 0.4분
경로 2 (국도)
이용자: 50명
소요시간: -분
고정 40분 (혼잡 없음)
1968년 독일 수학자 Braess가 발견: 도로를 추가로 건설하면 오히려 교통이 더 나빠질 수 있다!
모든 운전자가 개인적으로 최적인 경로를 선택하면 (내쉬 균형), 전체적으로는 비효율적인 결과가 나올 수 있습니다.
새 도로가 개인의 최적 경로를 바꿔서 전체 혼잡을 악화시킬 수 있다는 것입니다.
슬라이더를 움직여서 경로 1과 경로 2의 소요시간이 같아지는 지점을 찾으세요.
그 지점이 바로 내쉬 균형입니다. 왜 그런가요?
내쉬 균형은 "아무도 혼자서 전략을 바꿔 이득을 볼 수 없는 상태"입니다. 최적반응을 찾아 교차점을 구하면 내쉬 균형을 찾을 수 있습니다.
복수 균형이 있을 때는 초점(셸링 포인트)이 중요하고, 순수전략 균형이 없을 때는 혼합전략을 사용합니다. 다음 장에서는 순서가 있는 게임, 즉 순차 게임을 분석합니다.