상관 균형

게임 개발 최적설계 마지막 수정: 2026-08-26 04:31:47

1. 개요[편집]

상관 균형 Correlated Equilibrium
제안	로버트 아우만 (1974) — 베이지안 해석은 1987
장치	신호기(correlation device)가 결합분포에서 뽑아 각자 몫만 귓속말
조건	권고를 따르는 것이 조건부 최선반응
기하	비어 있지 않은 볼록 다면체 — 내시 균형들을 모두 포함
계산	정규형 크기에 대해 선형계획, 다항시간 (내시는 PPAD-완전)
완화판	조대 상관 균형(CCE) — 신호를 보기 전에 이탈을 결정
학습	스와프 무후회 → CE · 외부 무후회 → CCE

아무도 명령할 권한이 없는데, 다들 신호등이 시키는 대로 한다. 그리고 그게 각자에게도 최선이다.

상관 균형(correlated equilibrium)은 모든 행동 조합 위의 결합확률분포 $p$ 중에서, 중재자가 $p$ 로부터 행동 조합 하나를 뽑아 각 플레이어에게 자기 몫의 행동만 사적으로 권고했을 때 누구도 그 권고를 어길 유인이 없는 분포다. 로버트 아우만이 1974년 논문 「Subjectivity and Correlation in Randomized Strategies」에서 도입했고, 1987년에는 공통 사전확률을 가진 베이지안 합리적 플레이어들의 플레이 분포가 언제나 상관 균형이 된다는 재해석을 붙였다.¹

내시 균형 문서가 이 개념을 “LP로 떨어지는 완화 개념”으로 한 절 다루고 있고 무후회 학습 문서가 수렴 대상으로 언급하고 있으니, 여기서는 그 사이에 낀 본론을 채운다. 왜 곱분포가 아닌 결합분포를 허용하는 것만으로 계산 복잡도가 PPAD-완전에서 다항시간으로 무너지는가, 그리고 그 대가로 무엇을 얻고 무엇을 잃는가가 이 문서의 주제다.

2. 정의[편집]

플레이어 $i$ 의 행동집합을 $A_i$ , 전체 행동조합 집합을 $A = \prod_i A_i$ 라 하자. 분포 $p \in \Delta(A)$ 가 상관 균형이라는 것은, 모든 플레이어 $i$ 와 모든 행동 쌍 $a_i, a_i' \in A_i$ 에 대해

\sum_{a_{-i} \in A_{-i}} p(a_i, a_{-i})\Bigl[\,u_i(a_i, a_{-i}) - u_i(a_i', a_{-i})\,\Bigr] \;\ge\; 0

이 성립한다는 뜻이다. 해석은 이렇다. “ $a_i$ 를 하라”는 귓속말을 들은 순간 플레이어 $i$ 는 상대들의 권고에 대한 사후분포 $p(\cdot \mid a_i)$ 를 갖게 되는데, 그 사후분포 아래에서 권고대로 $a_i$ 를 하는 것이 어떤 다른 $a_i'$ 보다 낫다는 조건이다. 부등식 양변에 $p(a_i) > 0$ 을 곱해 조건부확률을 지운 형태가 위 식이며, 그래서 $p$ 에 대해 완전히 선형이다. 이 한 가지 사실이 문서 나머지 전부를 지배한다.

핵심은 정보의 비대칭이다. 각자는 자기 권고만 보고 남의 권고는 못 본다. 만약 모두가 모든 권고를 본다면 상관은 아무 힘도 못 쓰고 순수 균형 위의 공개 추첨(public randomization)에 불과해진다. “나는 내 신호만 안다”는 제약이 오히려 균형의 범위를 넓히는 구조가 이 개념의 묘미다.

내시 균형과의 포함 관계는 즉시 나온다. 내시 균형 $\sigma = (\sigma_1,\dots,\sigma_n)$ 의 곱분포 $p(a) = \prod_i \sigma_i(a_i)$ 를 넣으면 사후분포가 사전분포와 같아지고( $a_i$ 를 알아도 남에 대해 새로 아는 것이 없으므로) 위 조건은 내시 조건 그 자체가 된다. 즉 모든 내시 균형은 상관 균형이고, 내시 균형의 존재는 이미 알려져 있으므로 상관 균형 집합은 항상 비어 있지 않다.

더 흥미로운 것은 그 반대다. 하트와 슈마이들러(1989)는 상관 균형의 존재를 고정점 정리 없이 증명했다 — 상관 균형 집합이 공집합이라고 가정하고 LP 쌍대성(혹은 미니맥스 정리)을 쓰면 모순이 나온다. 내시의 존재 증명이 카쿠타니·브라우어에 의존해서 계산적으로도 PPAD의 저주를 물려받은 것과 정면으로 대비되는 대목이다. 존재 증명이 초등적이면 계산도 대개 쉽다는 알고리즘 게임 이론의 경험칙이 여기서 정확히 맞는다.

3. 신호등과 치킨[편집]

가장 짧은 예가 교차로다. 두 운전자가 각각 「진행」과 「정지」를 고르는데, 둘 다 진행하면 충돌해서 최악, 둘 다 정지하면 시간을 버리고, 하나만 진행하면 그쪽이 이득이다. 순수 내시 균형이 두 개(누가 가느냐)인데 대칭성 때문에 어느 쪽인지 정할 수 없고, 혼합 균형은 양의 확률로 충돌한다. 신호등은 결합분포 $\{(\text{진행},\text{정지}), (\text{정지},\text{진행})\}$ 에 각각 1/2을 주고 각자에게 자기 등만 보여 준다. 초록불을 본 사람은 상대가 빨간불임을 확신하니 진행이 최선이고, 빨간불을 본 사람은 상대가 온다는 것을 아니 정지가 최선이다. 아무도 벌금이나 물리적 차단 없이 신호를 지킬 유인을 갖는다 — 신호등은 강제 장치가 아니라 상관 장치다.

이 예는 아직 내시 균형들의 볼록결합일 뿐이다. 진짜 힘은 다음 예에서 나온다. 표준 치킨 게임을 보수 행렬로 쓰면 (행이 플레이어 1)

	회피	돌진
회피	6, 6	2, 7
돌진	7, 2	0, 0

내시 균형은 순수 둘 $(7,2)$ · $(2,7)$ 과 각자 회피 2/3로 섞는 혼합 하나 $(14/3, 14/3)$ 이다. 혼합 균형의 사회후생은 $28/3 \approx 9.33$ 이고, 순수 균형들의 볼록결합으로 얻을 수 있는 후생도 최대 $28/3$ 을 넘지 못한다.

이제 $(\text{회피},\text{회피})$ , $(\text{회피},\text{돌진})$ , $(\text{돌진},\text{회피})$ 셋에 각각 1/3을 주는 분포를 보자. 「회피」를 권고받은 플레이어는 상대가 회피·돌진일 확률이 반반이라고 믿으므로 회피의 기대보수 $\tfrac12(6)+\tfrac12(2)=4$ 가 돌진의 $\tfrac12(7)+\tfrac12(0)=3.5$ 보다 크고, 「돌진」을 권고받으면 상대가 반드시 회피이므로 $7 > 6$ 이다. 상관 균형이 맞다. 그런데 각자의 기대보수는 $\tfrac13(6+2+7)=5$ , 후생은 10으로 내시 균형 볼록껍질의 바깥이다.

최적화를 더 밀어붙일 수도 있다. 확률을 $p(\text{회피},\text{회피})=a$ , $p(\text{회피},\text{돌진})=p(\text{돌진},\text{회피})=b$ , $p(\text{돌진},\text{돌진})=0$ 으로 두면 제약은 $a \le 2b$ 하나이고, 후생 $12a+18b = 12-6b$ 는 $b$ 가 작을수록 좋으므로 $b=1/4$ , $a=1/2$ 에서 최대가 된다. 각자 5.25, 후생 10.5. 이때 「회피」 권고를 받은 플레이어는 회피와 돌진이 정확히 무차별해진다 — 제약이 딱 붙는 지점이 최적이라는, LP의 교과서적 풍경이다.

신호기가 하는 일은 “둘 다 회피”라는 파레토 우월한 조합을 등장시키되, 그것을 확신할 수 없을 만큼만 잡음을 섞는 것이다. 잡음이 없으면(항상 둘 다 회피) 배신 유인이 생기고, 잡음이 너무 많으면 후생이 준다. 그 절충점을 정확히 찾아 주는 것이 아래의 선형계획이다.

4. 왜 다항시간인가[편집]

정의식이 $p$ 에 선형이고 $p$ 가 단체(simplex) 위에 있으므로, 상관 균형 집합은

\Bigl\{\, p \in \mathbb{R}^{|A|}_{\ge 0} \;:\; \textstyle\sum_a p(a) = 1,\quad \text{각 } (i, a_i, a_i')\text{에 대한 이탈 제약}\,\Bigr\}

라는 볼록 다면체다. 변수는 $|A| = \prod_i |A_i|$ 개, 이탈 제약은 $\sum_i |A_i|(|A_i|-1)$ 개. 정규형 게임의 입력 크기 자체가 $n\prod_i|A_i|$ 개의 보수값이므로, 이 LP는 입력 크기에 대해 다항이다. 선형계획법의 내점법으로 풀면 되고, 게다가 다면체 위에서 사회후생·특정 플레이어 보수·최대최소 공평성 무엇을 최적화하든 여전히 LP다.

이 대비가 알고리즘 게임 이론의 출발점이었다.

개념	집합의 기하	계산
내시 균형	비볼록, 여러 성분	2인 이상 PPAD-완전
상관 균형	볼록 다면체	LP — 다항시간
조대 상관 균형	더 큰 볼록 다면체	LP — 다항시간
2인 영합 내시	볼록(영합에서만)	LP — 다항시간

내시 균형이 어려운 이유는 결국 $p$ 가 곱분포여야 한다는 요구 때문이다. $p(a)=\prod_i \sigma_i(a_i)$ 라는 제약이 다항식 비선형성을 만들고, 그 비선형성이 브라우어 고정점의 어려움을 그대로 상속한다. 그 제약 하나를 놓아 주면 문제가 통째로 선형이 된다. “플레이어들의 무작위화가 독립이어야 한다”는 요구는 개념적으로는 자연스러워 보이지만 계산적으로는 대단히 비싼 요구였던 셈이다.

물론 다항시간이라는 말에는 단서가 붙는다. $n$ 명이 각자 $m$ 개 행동을 가지면 변수가 $m^n$ 개다 — 정규형 입력 자체가 그 크기라 “입력 대비 다항”은 맞지만, 게임이 그래프·혼잡 게임처럼 간결하게 표현되면 정규형을 쓰는 순간 지수 폭발이다. 파파디미트리우와 라우가든(2008)은 이런 간결 표현 게임 다수에서 상관 균형 하나를 다항시간에 찾을 수 있음을 보였다(타원체법을 “희망을 걸고” 돌리는, 이름부터 재미있는 ellipsoid-against-hope 논증). 다만 최적 상관 균형을 찾는 것은 같은 설정에서 NP-난해다. “하나 찾기는 쉽고 좋은 것 찾기는 어렵다”는 구도가 여기서도 반복된다.

5. 조대 상관 균형[편집]

제약을 한 번 더 느슨하게 할 수 있다. 조대 상관 균형(coarse correlated equilibrium, CCE)은 신호를 보기 전에 참가 여부를 결정하는 상황이다. 즉 모든 $i$ 와 모든 $a_i' \in A_i$ 에 대해

\mathbb{E}_{a \sim p}\bigl[u_i(a)\bigr] \;\ge\; \mathbb{E}_{a \sim p}\bigl[u_i(a_i', a_{-i})\bigr]

만 요구한다. 상관 균형이 “권고를 듣고 나서도 어길 유인이 없다”는 조건부 조건이라면, CCE는 “장치에 참여할지 말지를 미리 정한다”는 무조건부 조건이다. 조건부 이탈이 무조건부 이탈보다 강력하므로 $\text{Nash} \subseteq \text{CE} \subseteq \text{CCE}$ 이고, 세 포함 모두 일반적으로 진부분집합이다.

CCE가 개념적으로 어색해 보이는데도 대접받는 이유는 딱 하나, 학습이 거기로 간다는 것이다. 무후회 학습 문서에 정리된 대응이 정확히 이 계층을 재현한다.

모든 플레이어가 외부 후회를 $o(T)$ 로 만들면 → 결합 행동의 경험분포가 CCE 집합으로 수렴.
모든 플레이어가 내부·스와프 후회를 $o(T)$ 로 만들면 → 경험분포가 CE 집합으로 수렴(하트·마스콜렐 2000, 포스터·보라 1997).

증명은 놀랄 만큼 짧다. 후회의 정의식과 균형의 정의식이 같은 부등식의 시간평균이기 때문이다. 외부 후회 $R_T/T \le \varepsilon$ 은 “고정 행동 $a_i'$ 로 통째로 바꿔도 $\varepsilon$ 이상 못 번다”인데, 이것이 경험분포에 대한 CCE 조건의 $\varepsilon$ -완화판 그 자체다. 내부 후회는 “내가 $a_i$ 를 낸 라운드들에서만 $a_i'$ 로 바꿔도” 이므로 그대로 조건부 조건, 즉 CE 조건이 된다. 후회 개념을 강화하면 균형 개념이 강화된다 — 이 사전이 있으면 두 분야를 왔다 갔다 하는 데 다른 도구가 거의 필요 없다.

여기에 실무적으로 중요한 따름정리가 붙는다. 헤지 알고리즘이나 미러 하강 같은 흔한 학습기를 각자 돌리는 것만으로도 CCE 근처에는 간다. 중재자도, LP 솔버도, 상대 보수함수에 대한 지식도 필요 없다. 상관 균형이 “다항시간에 풀린다”보다 더 강한 실전 명제는 사실 이쪽이다 — 분산된, 비연동(uncoupled) 동역학으로 도달 가능하다. 반면 일반합 게임의 내시 균형은 하트·마스콜렐(2003)에 의해 비연동 동역학으로는 원리적으로 도달 불가능하다.

6. 무정부의 대가가 CCE까지 살아남는다[편집]

상관 균형·CCE가 이론적 장식이 아니라는 결정적 증거는 무정부의 대가 쪽에서 나왔다. 라우가든의 매끄러움(smoothness) 틀은 게임이 $(\lambda,\mu)$ -매끄럽다는 부등식 하나로부터 PoA 상한 $\lambda/(1-\mu)$ 를 유도하는데, 그 증명이 균형의 정의를 거의 안 쓴다. “각자가 어떤 고정 이탈보다 나쁘지 않다”는 무조건부 부등식만 있으면 논증이 돌아가고, 그건 정확히 CCE 조건이다.

결과적으로 매끄러움으로 증명된 PoA 상한은 순수 내시 균형뿐 아니라 혼합 내시, 상관 균형, CCE, 그리고 무후회 학습의 시간평균 궤적 전체에 그대로 적용된다. 아핀 비용 혼잡 게임의 PoA $5/2$ 가 대표 사례다. 시뮬레이션 하는 사람에게 이게 왜 좋은 소식이냐면 — 에이전트들이 균형에 수렴했는지 확인할 필요가 없어진다. 각자 무후회 학습기를 돌리게 두고 시간평균 후생을 재면, 그 값이 이미 이론 상한 안에 들어 있음이 보장된다. 균형 계산이라는 어려운 문제를 우회해서 성능 보증만 챙기는 셈이다.

7. 신호기를 실제로 누가 돌리나[편집]

“믿을 만한 중재자”라는 가정이 불편하다면, 그걸 없애는 세 갈래가 있다.

물리적 공용 신호. 교통 신호등, TDMA 슬롯 배정, 램프 미터링, 클라우드 자원 스케줄러의 우선순위 토큰. 이미 세상에 널려 있고, 대부분 “공정성”의 언어로 설계됐지만 실제로 하는 일은 상관 균형의 구현이다.
저렴한 대화(cheap talk). 플레이어들끼리 구속력 없는 사전 통신만으로 중재자를 흉내 낼 수 있다는 결과들이 1990년대에 나왔다. 3인 이상이면 상당히 일반적인 상관 균형을 통신 프로토콜로 재현할 수 있고, 2인이면 암호학적 공정 동전던지기를 끌어와야 한다.
공용 무작위성. 모두가 같은 시각의 블록 해시나 공개 난수 비컨을 보되, 각자 자기 몫만 복호할 수 있게 하는 구성. 분산 시스템에서 신호기 없이 상관을 만드는 실용적 방법이다.

한편 전개형 게임으로 넘어가면 이야기가 다시 복잡해진다. 신호를 게임 시작 전에 한 번 주느냐, 매 의사결정 지점마다 주느냐에 따라 개념이 갈리고(전개형 상관 균형·소통 균형), 이들 사이의 계산 난이도도 서로 다르다. 불완전정보 게임의 균형 계산 실무는 이쪽보다는 반사실적 후회 최소화처럼 2인 영합에 특화된 도구로 굴러가고 있고, 다인 게임의 상관 균형 계산은 여전히 열린 영역에 가깝다.

8. 시뮬레이션·설계 관점의 요점[편집]

밸런싱에서 “혼합 균형 픽률”을 계산했다면 한 번 더 물어봐라. 플레이어들이 정말 독립적으로 무작위화하는가, 아니면 패치 노트·티어표·매치메이킹이라는 공용 신호를 보고 있는가. 후자면 관측 픽률이 내시가 아니라 상관 균형 쪽에 가까울 수 있다.
다중 에이전트 시뮬레이션의 목표를 CCE로 낮춰 잡아라. 3인 이상 일반합에서 내시를 찾겠다는 것은 PPAD-완전 문제를 풀겠다는 말이다. 각자 무후회 학습기를 돌리고 경험 결합분포를 기록하는 것이 실현 가능하고 이론적으로도 정직한 목표다.
경험분포를 저장해라. 여기서 수렴하는 것은 개별 전략이 아니라 결합 행동의 경험분포다. 각자의 주변분포만 로그로 남기면 상관 자체가 사라져서, 애초에 CE인지 확인할 수 없다.
설계 변수로 써라. 메커니즘 설계 관점에서 신호기는 공짜 정책 수단이다. 이전지출도 강제력도 없이 사회후생을 내시 볼록껍질 바깥으로 밀어 올릴 수 있으면, 그건 규제 없이 얻는 개선이다. 다만 위 치킨 예에서 보듯 개선의 대가는 사고 확률이 아니라 무차별성이다 — 최적 CE는 항상 누군가의 이탈 제약이 딱 붙는 지점이라, 보수 추정이 조금만 틀려도 균형이 아니게 된다.²
LP 크기를 미리 재라. 6명이 각자 5개 행동이면 변수가 $5^6 = 15625$ 개로 아직 우습지만, 8명 8행동이면 1600만 개다. 간결 표현 게임이면 정규형을 만들지 말고 전용 알고리즘이나 학습 동역학으로 가야 한다.³

9. 관련 문서[편집]

아우만은 1974년 논문에서 이 개념을 “주관적 확률을 가진 플레이어들이 각자 다른 정보를 볼 때 무슨 일이 벌어지는가”라는 질문의 부산물로 꺼냈다. 정작 세상이 알아본 것은 20년쯤 뒤 알고리즘 쪽 사람들이 “어? 이거 LP인데?”를 발견하고서였다. 경제학 개념이 계산복잡도 덕에 재발견된 대표 사례. ↩
최적 상관 균형이 다면체의 꼭짓점(또는 면)에 놓인다는 것은 LP의 상식이고, 그 꼭짓점은 정의상 이탈 제약 여러 개가 등호로 붙는 지점이다. 즉 최적 CE는 언제나 아슬아슬하다. 보수를 소수점 둘째 자리까지 추정해 놓고 최적 CE를 실제 정책으로 굴리면, 추정 오차가 그대로 이탈 유인으로 바뀐다. 실무에서는 제약에 여유(slack) $\varepsilon$ 을 강제로 넣은 $\varepsilon$ -CE를 푸는 편이 안전하다. ↩
“다항시간”이라는 단어를 볼 때마다 지수가 몇인지, 그리고 무엇에 대한 다항인지를 확인하는 습관은 이 분야에서 특히 값어치를 한다. 상관 균형 LP는 정규형 크기에 대해 다항인데, 정규형 크기 자체가 플레이어 수에 대해 지수다. 논문 초록의 “polynomial time”과 내 노트북에서 돌아가는지 여부는 별개의 사건이라는 뜻. ↩