내시 균형

게임 개발 수치해석 마지막 수정: 2026-08-23 04:18:27

1. 개요[편집]

내시 균형 Nash equilibrium
정의	누구도 혼자 전략을 바꿔 이득을 못 보는 전략 조합
존재 정리	내시(1950) — 유한 게임에 혼합 전략 균형이 항상 존재
증명 도구	카쿠타니 고정점 정리(1950) / 브라우어 고정점 정리(1951)
2인 비영합 계산	렘키-호슨 피벗, PPAD-완전
2인 영합 계산	선형계획법 — 다항시간
완화 개념	상관균형(LP), 조대 상관균형

“네가 뭘 하든 나는 이게 최선”이 모두에게 동시에 성립하는 지점. 좋은 결과라는 뜻은 아니고, 아무도 먼저 움직일 이유가 없다는 뜻일 뿐이다.

내시 균형(Nash equilibrium)은 여러 플레이어가 각자 전략을 골랐을 때 어느 한 명도 나머지의 전략이 고정된 상태에서 자기 전략만 바꿔서는 보수를 늘릴 수 없는 전략 조합이다. 존 내시가 1950년 프린스턴 박사논문과 PNAS 논문에서 도입했고, 1994년 하사니·젤텐과 함께 노벨경제학상을 받았다.

게임의 표현·미니맥스 정리·게임 AI에서의 쓰임 같은 기본기는 게임 이론이 이미 다루고 있으니 여기서는 반복하지 않는다. 이 문서는 “균형이 존재한다”에서 “그래서 그걸 어떻게 계산하고, 계산한 값이 얼마나 나쁜가” 까지, 시뮬레이션·최적화 하는 사람이 실제로 부딪히는 쪽을 다룬다. 결론부터 말하면 존재는 1950년에 끝났고, 계산은 2006년에 “일반적으로는 어렵다”로 결론이 났다.

2. 정의[편집]

플레이어 집합 $N = \{1,\dots,n\}$ , 각자의 전략 집합 $S_i$ , 보수함수 $u_i$ 가 주어졌을 때 전략 조합 $s^* = (s_1^*,\dots,s_n^*)$ 가 내시 균형이라는 것은

u_i(s_i^*, s_{-i}^*) \ \ge\ u_i(s_i, s_{-i}^*) \qquad \forall i \in N,\ \forall s_i \in S_i

를 만족한다는 뜻이다. $s_{-i}$ 는 $i$ 를 뺀 나머지 전원의 전략이다. 동치인 표현이 하나 더 있는데, 최선 반응 대응(best-response correspondence) $B_i(s_{-i}) = \arg\max_{s_i} u_i(s_i, s_{-i})$ 를 정의하면 내시 균형은 정확히 $s^* \in B(s^*)$ 인 점, 즉 최선 반응 대응의 고정점이다. 이 한 줄이 존재 증명의 전부라 해도 과언이 아니다.

혼합 전략을 허용한다는 것은 $S_i$ 를 유한 집합에서 그 위의 확률단체(simplex) $\Delta(S_i)$ 로 넓힌다는 뜻이고, 보수는 기대값으로 확장한다. 여기서 중요한 성질 하나 — 균형에서 어떤 플레이어가 양의 확률을 주는 순수 전략들은 모두 같은 기대보수를 낸다. 안 그러면 낮은 쪽 확률을 높은 쪽으로 옮겨서 이득을 볼 테니까. 이 “무차별 조건”이 뒤에 나올 모든 계산 알고리즘의 골격이다.

3. 존재 정리[편집]

내시의 1950년 PNAS 노트는 카쿠타니 고정점 정리를 쓴다. 최선 반응 대응 $B$ 는

정의역 $\Delta = \prod_i \Delta(S_i)$ 가 비어 있지 않은 볼록 컴팩트 집합이고,
$B(s)$ 가 비어 있지 않고 볼록하며(선형 함수의 최대점 집합은 면(face)이므로),
$B$ 의 그래프가 닫혀 있다(상반연속).

이 세 조건이 카쿠타니 정리의 가설과 정확히 일치하므로 고정점이 존재하고, 그게 곧 균형이다. 이듬해 Annals of Mathematics 논문에서 내시는 같은 결과를 브라우어 고정점 정리만으로 다시 증명했다. 각 순수 전략의 확률을 “그 전략이 현재 평균보다 얼마나 좋은가”만큼 밀어 올리고 다시 정규화하는 연속 사상을 만들어, 그 고정점이 균형임을 보이는 방식이다.¹

증명이 고정점 정리에 기대고 있다는 사실은 그냥 역사적 취향이 아니라 경고다. 브라우어 고정점을 찾는 문제 자체가 계산적으로 어려운 문제이고, 실제로 내시 균형 계산의 복잡도는 정확히 그 어려움을 물려받는다.

4. 순수 균형과 혼합 균형[편집]

대표적인 2×2 게임 셋으로 균형의 성격이 어떻게 갈리는지 볼 수 있다.

게임	순수 균형	혼합 균형	성격
죄수의 딜레마	(배신, 배신) 하나	없음	유일하고, 파레토 열등
치킨 게임	(돌진, 회피)와 (회피, 돌진)	있음	비대칭 균형 둘 + 대칭 혼합 하나
조정 게임	(A, A)와 (B, B)	있음	어느 쪽으로 굳을지 이론이 못 정함

죄수의 딜레마는 배신이 강우월 전략이라 균형이 유일하고, 그 유일한 균형이 둘 다 협조하는 것보다 나쁘다. “균형 = 좋은 결과”라는 오해를 깨는 표준 반례라서 늘 첫 예제로 나온다. 치킨 게임은 순수 균형이 둘이라 어느 쪽이 실현될지 게임 이론만으로는 못 정하고, 조정 게임(사슴 사냥이 대표)은 한쪽이 보수 우월, 다른 쪽이 위험 우월이라 “합리적 플레이어라면 어느 쪽?”이 애매해진다.

5. 균형 다중성과 정련[편집]

균형이 여럿이면 예측력이 떨어지므로, 그럴듯하지 않은 균형을 걸러내는 정련(refinement) 개념들이 줄줄이 나왔다.

부분게임 완전 균형(젤텐 1965) — 전개형 게임의 모든 부분게임에서 내시 균형이어야 한다. “그런 짓 하면 나도 같이 죽는다”는 식의 믿기 힘든 위협(non-credible threat)을 후진 귀납으로 제거한다.
떨리는 손 완전 균형(젤텐 1975) — 상대가 아주 작은 확률로 실수한다고 가정해도 살아남는 균형만 인정한다. 불완전정보까지 확장한 것이 순차 균형(크렙스-윌슨 1982).
진화적 안정 전략(ESS, 메이너드 스미스·프라이스 1973) — 소수의 돌연변이 전략이 침입해도 밀려나는 균형. 합리성 대신 개체군 동역학으로 균형을 고르며, 그 동역학 모형이 복제자 동역학이다. 모든 ESS는 내시 균형이지만 역은 성립하지 않는다.

정련 개념은 반세기 넘게 늘어났지만 “이게 정답”인 하나로 수렴하지 못했다. 게임 밸런싱 실무에서 “메타가 굳었다”는 말은 결국 플레이어 집단이 학습과 관습으로 균형 하나를 골랐다는 뜻이고, 그 선택은 이론이 아니라 역사가 한다.

6. 2인 게임 계산 — 렘키-호슨[편집]

2인 게임(보수행렬 $A$ , $B$ 의 이중행렬 게임)의 균형 조건은 무차별 조건 + 상보 조건 형태로 적히는데, 이게 정확히 선형 상보성 문제(LCP)다. 그래서 강체 접촉 해석에서 쓰는 그 렘키 피벗 알고리즘의 사촌이 여기서도 나온다.

렘키-호슨 알고리즘(1964)은 두 플레이어의 최선반응 다면체 위를 걷는다. 대략:

각 정점에 “이 전략은 안 쓰인다” 또는 “이 전략이 최선반응이다”를 뜻하는 라벨 $1,\dots,m+n$ 을 붙인다. 모든 라벨을 다 가진 정점 쌍이 곧 균형이다.
자명한 시작점 $(0,0)$ 에서 라벨 하나 $k$ 를 일부러 버린다.
거의 완전 라벨링된(하나 빼고 다 가진) 정점들을 따라 피벗한다. 이 정점들이 이루는 그래프에서 각 정점의 차수는 1 또는 2이므로 경로는 갈라지지 않고, 시작점 반대쪽 끝은 반드시 균형이다.

이 논증은 구성적 존재 증명인 동시에, 비퇴화 게임의 균형 개수가 항상 홀수임을 덤으로 준다.² 종료는 보장되지만 경로 길이는 보장되지 않아서, 사바니와 폰 슈텡겔(2006)은 렘키-호슨이 지수적으로 많은 피벗을 밟는 게임족을 명시적으로 구성했다. 선형계획법의 단체법이 실무에서는 빠른데 최악 케이스가 지수인 것과 같은 그림인데, 렘키-호슨 쪽은 “그럼 다항시간 대안은?”이라는 질문에 아직 답이 없다는 점이 다르다.

작은 게임에서는 지지집합 열거(support enumeration)가 오히려 실용적이다. 양쪽 지지집합을 후보로 찍고 무차별 조건 연립방정식을 푸는 것을 반복하는데, 후보 수가 $2^m \cdot 2^n$ 이라 전략 10개 언저리까지가 한계다. Gambit 같은 도구가 이 둘을 기본으로 깔고 있다.

7. PPAD-완전[편집]

내시 균형은 반드시 존재한다. 그래서 “없다”는 답이 없고, 결정 문제로 물을 것이 없다. 이런 “답이 있는 건 아는데 찾기가 문제”인 탐색 문제들의 집합이 TFNP이고, 그 안에서 고정점류 논증으로 존재가 보장되는 부분류가 파파디미트리우(1994)의 PPAD(Polynomial Parity Argument, Directed)다. 이름 그대로 “방향 그래프에서 차수 1인 정점이 홀수 개”라는 패리티 논증이 정체이고, 완전 문제는 END-OF-LINE이다. 위에서 본 렘키-호슨의 경로 논증이 바로 그 패리티 논증이라는 점을 눈치챘다면 정확하다.

다스칼라키스·골드버그·파파디미트리우(2006) — 3인 이상 게임의 내시 균형 계산이 PPAD-완전.
첸·덩(2006) — 2인 게임도 PPAD-완전.

PPAD-완전이 P≠NP만큼 강한 하한은 아니지만, 실질적으로는 “다항시간 알고리즘을 기대하지 마라”로 읽힌다. 근사도 크게 낫지 않다. $\varepsilon$ -내시 균형(어떤 이탈로도 $\varepsilon$ 이상 못 버는 상태)은 립튼·마르카키스·메타(2003)가 준다항시간 $n^{O(\log n/\varepsilon^2)}$ 알고리즘을 주었지만 — 균형을 $O(\log n/\varepsilon^2)$ 크기 지지집합으로 근사할 수 있다는 표본 논증이다 — 진짜 다항시간에서 보장되는 상수 $\varepsilon$ 은 오랫동안 차크나키스·스피라키스(2007)의 0.3393이 벽이었다. 덤으로, “사회후생이 최대인 균형”, “균형이 둘 이상인가”, “지지집합 크기가 $k$ 이상인 균형” 같은 부가 조건이 붙으면 그때는 아예 NP-난해다(길보아·제멜 1989).

8. 영합게임과 상관균형은 왜 쉬운가[편집]

절망만 하기엔 이르다. 두 가지 중요한 특수·완화 케이스는 LP로 떨어진다.

2인 영합게임. $B = -A$ 이면 폰 노이만의 미니맥스 정리가 최대최소와 최소최대를 붙여 주므로, 행 플레이어의 최적 혼합 전략은

\max_{p \in \Delta,\ v} \ v \quad \text{s.t.}\quad (A^{\top}p)_j \ge v \ \ \forall j

라는 선형계획의 해다. 열 플레이어의 문제는 정확히 이것의 쌍대이며, 미니맥스 정리는 쌍대성 정리의 게임판이다.³ 따라서 내점법으로 다항시간에 풀리고, 균형 집합이 볼록이며(영합에서만!) 모든 균형이 같은 값을 준다. 비영합에서는 이 셋 다 깨진다 — 균형 집합은 비볼록, 값도 균형마다 다르다.

상관균형. 아우만(1974)은 신뢰할 만한 중재자가 결합분포 $p$ 에서 뽑아 각자에게 자기 몫만 귓속말해 주는 상황을 생각했다. 아무도 그 조언을 어길 유인이 없을 조건은

\sum_{s_{-i}} p(a, s_{-i})\left[u_i(a, s_{-i}) - u_i(a', s_{-i})\right] \ \ge\ 0 \qquad \forall i,\ \forall a, a' \in S_i

인데, 보다시피 $p$ 에 대해 전부 선형이다. 즉 상관균형 집합은 볼록 다면체이고, 그 위에서 무엇을 최적화하든 선형계획법이다. 정규형 크기에 대해 다항시간. 내시 균형들의 곱분포는 항상 상관균형이므로 존재도 공짜로 따라온다. 개념을 조금 넓혔더니 PPAD-완전이 LP로 내려앉는 이 대비가 알고리즘 게임 이론의 출발점이었다.

9. 학습으로 도달하기 — 무후회 동역학[편집]

계산이 어렵다면 플레이어들이 그냥 학습하게 두면 어떻게 될까. 각 플레이어가 온라인 학습 알고리즘(승수 가중치/헤지, 후회 매칭 등)을 돌려 외부 후회가 $o(T)$ 가 되도록 — 즉 “돌이켜 보니 한 가지 전략만 계속 쓸 걸 그랬다”는 아쉬움이 시간당 0으로 가도록 — 만드는 것은 쉽다. 승수 가중치의 후회는 $O(\sqrt{T \log n})$ 이다. 그러면 이렇게 된다.

외부 후회 → 조대 상관균형(coarse correlated equilibrium). 실제 플레이의 경험분포가 CCE 집합으로 수렴한다.
내부/스왑 후회 → 상관균형. 조금 더 강한 후회 개념(포스터·보라 1997, 하트·마스콜렐의 후회 매칭 2000)을 쓰면 경험분포가 상관균형 집합으로 수렴한다.
2인 영합에서는 내시로. 양쪽이 무후회면 시간평균 전략쌍이 미니맥스 균형에, 평균 보수가 게임 값에 수렴한다(프룬드·샤파이어). 포커 봇의 반사실적 후회 최소화(CFR)가 정확히 이 정리 위에 서 있다.

여기 시뮬레이션 하는 사람이 반드시 알아야 할 함정이 있다. 수렴하는 것은 시간평균이지 마지막 반복이 아니다. 승수 가중치를 돌린 두 플레이어의 현재 전략은 균형 주위를 영원히 감아 돌 수 있고, 평균만 가운데로 모인다. GAN 학습이나 자기대전 강화 학습에서 손실이 수렴 안 하고 진동하는 현상의 상당 부분이 이 구조적 이유다 — 경사하강법을 최소화 문제에 쓸 때의 직관이 안장점 문제에서는 통하지 않는다. 낙관적(optimistic) 변형처럼 마지막 반복 수렴을 목표로 하는 알고리즘군이 이 때문에 나왔다. 그리고 비영합·다인 게임에서는 무후회 학습이 내시로 간다는 보장이 아예 없다. 가는 곳은 (조대) 상관균형까지다.

10. 무정부의 대가[편집]

균형을 계산했다 치자. 그래서 그게 얼마나 나쁜가? 무정부의 대가(Price of Anarchy, PoA, 쿠추피아스·파파디미트리우 1999)는

\mathrm{PoA} = \frac{\text{최악 균형의 사회적 비용}}{\text{중앙집중 최적해의 비용}}

로 정의된다. 이 값이 1에 가까우면 “각자 이기적으로 굴게 놔둬도 별로 손해 안 본다”는 뜻이라, 분산 시스템 설계자에게는 대단히 실용적인 지표다.⁴

가장 유명한 결과가 이기적 경로 선택이다. 링크 지연이 유량의 아핀 함수인 비원자적(nonatomic) 교통망에서 라우가든과 타도시(2002)는 $\mathrm{PoA} \le 4/3$ 이라는 타이트한 상한을 증명했다. 지연 함수가 일반적이면 PoA는 무한대까지 갈 수 있지만, 대신 이런 이중기준 결과가 성립한다 — 균형 유량의 비용은 통행량을 두 배로 늘린 최적해의 비용보다 크지 않다. 도로 확장이 알고리즘적 개선보다 확실하다는 정리인 셈. 원자적 혼잡 게임에서 아핀 비용이면 PoA는 $5/2$ 다.

이 4/3이 정확히 튀어나오는 예가 브레스 역설이다. 출발지 $s$ 에서 목적지 $t$ 로 유량 1이 흐르고, 경로가 둘 있다. $s \to a$ 의 지연은 $x$ , $a \to t$ 는 $1$ ; $s \to b$ 는 $1$ , $b \to t$ 는 $x$ . 균형에서는 절반씩 갈라져 각자 $1/2 + 1 = 3/2$ 를 쓴다. 여기에 지연이 0인 지름길 $a \to b$ 를 추가하면, 모두가 $s \to a \to b \to t$ 로 몰리는 것이 유일한 균형이 되고 통행시간은 $1 + 0 + 1 = 2$ 로 늘어난다. 아무도 손해 볼 짓을 하지 않았는데 전원이 손해를 봤고, 비율은 $2 \div (3/2) = 4/3$ 로 정확히 상한을 친다. 서울에서 도로를 없앴더니 소통이 나아졌다는 사례들이 이 역설의 실사판으로 자주 인용된다.

균형이 여럿일 때 최선 균형을 기준으로 재는 것이 안정성의 대가(Price of Stability)이고, “설계로 좋은 균형을 유도할 수 있는가”를 따질 때 이쪽이 더 적절한 지표다.

11. 시뮬레이션에서 실제로 만나는 곳[편집]

밸런싱. 유닛 상성표를 보수행렬로 놓고 혼합 균형을 풀면 이론 픽률이 나온다. 3~10개 전략 규모면 지지집합 열거로 몇 밀리초. 실제 픽률이 이론값에서 크게 벗어나면 그건 밸런스 문제이거나, 플레이어가 아직 균형을 못 찾은 것이다.
교통·군중. 각 에이전트가 이기적으로 경로를 고르는 군중 시뮬레이션은 혼잡 게임이고, 그 균형은 네트워크 흐름 위의 워드롭 균형(1952) — 쓰이는 모든 경로의 통행시간이 같고 안 쓰이는 경로는 그보다 길다는 조건 — 으로 계산한다. 위에서 본 혼합 균형의 무차별 조건과 정확히 같은 형태다. 다익스트라 알고리즘이나 A* 알고리즘으로 각자 최단경로만 뽑아 쓰면 브레스 역설이 시뮬레이션 안에서도 그대로 재현된다.
다중 에이전트 학습. 자기대전은 학습 알고리즘 문제이기 전에 균형 계산 문제다. 2인 영합이면 이론이 든든하고, 그 밖에서는 무후회 학습이 데려다주는 곳이 상관균형까지라는 사실을 알고 시작하는 편이 낫다.
최적화 커플링. 두 설계 주체가 각자 목적함수를 최소화하는 상황(예: 공력 담당과 구조 담당)은 최적설계의 언어로 쓰면 그냥 게임이고, 번갈아 최적화하는 반복법은 최선반응 동역학이다. 수렴하면 균형, 진동하면 균형이 유일하지 않다는 신호다.

12. 관련 문서[편집]

논문 자체는 살벌하게 짧다. PNAS 노트가 한 페이지 남짓이고, 여기에 게임 이론의 절반이 들어 있다. 지도교수 터커가 “이거 그냥 카쿠타니 응용 아니냐”고 떨떠름해했다는 일화가 전해지는데, 응용이든 아니든 노벨상은 이쪽으로 갔다. ↩
퇴화(degenerate) 게임에서는 균형이 연속체로 나올 수 있어서 홀수 주장이 깨진다. 그리고 실무 보수행렬은 정수·반올림값으로 채워지기 때문에 퇴화가 기본값에 가깝다. 논문 정리를 코드에 그대로 옮기면 여기서 터진다. ↩
역방향도 성립한다. 임의의 LP를 적당한 영합게임으로 환원할 수 있어서 둘은 계산적으로 등가다. 폰 노이만과 댄치그가 1947년에 이 대응을 두고 나눈 대화가 LP 쌍대성 이론의 기원 설화로 돌아다닌다. ↩
이름을 붙인 사람들의 감각이 좋았다. “무정부의 대가”라고 하면 예산 심의에서 한 줄로 설명이 끝나는데, “이기적 균형의 사회후생 비율 상한”이라고 하면 슬라이드를 세 장 더 만들어야 한다. ↩