혼잡 게임

1. 개요[편집]

혼잡 게임 Congestion game
제안	Robert W. Rosenthal (1973)
구조	비용이 «그 자원을 몇 명이 쓰는가» 에만 의존
핵심 정리	순수 내시 균형이 항상 존재 — 퍼텐셜 함수로 구성적 증명
동치	유한 정확 퍼텐셜 게임과 같은 부류 (몬데러-샤플리 1996)
동학	최적반응/개선 동학이 반드시 정지 — 다만 정지까지가 PLS-완비
비원자적 판	워드롭 균형 = 베크만 볼록계획의 해
유명한 사고	브라에스 역설 — 길을 놓았더니 다 같이 느려짐

혼잡 게임(congestion game)은 각 플레이어가 자원의 부분집합을 하나 고르고, 자기 비용이 «자기가 고른 자원 각각을 몇 명이 함께 쓰는가»의 함수 합으로만 결정되는 게임이다. 로버트 로젠탈이 1973년에 도입했고, 논문 제목 자체가 결론이다 — A class of games possessing pure-strategy Nash equilibria.¹

이 부류가 특별한 이유는 딱 하나다. 일반 게임에서는 순수 내시 균형이 존재한다는 보장이 없고(가위바위보를 떠올리면 된다) 존재하더라도 찾는 것이 PPAD-완전인데, 혼잡 게임에서는 순수 균형이 항상 존재하며 증명이 고정점 정리가 아니라 한 줄짜리 퍼텐셜 함수로 끝난다. 그리고 그 퍼텐셜은 시뮬레이션에서 실제로 계산해서 로그로 찍을 수 있는 값이다. 이 문서는 그 퍼텐셜이 어디서 오고, 어디까지 살아남고, 어디서 죽는지를 본다.

균형이 존재한다는 것과 그 균형이 좋다는 것은 완전히 별개다. 후자는 무정부의 대가가 다룬다.

2. 정의[편집]

• 자원(간선) 집합 $E$, 플레이어 $N=\{1,\dots,n\}$.
• 각 플레이어의 전략 집합 $S_i \subseteq 2^{E}$ — 즉 전략 하나가 자원의 부분집합이다.
• 자원마다 비용 함수 $c_e : \{1,\dots,n\} \to \mathbb{R}$. 인자는 그 자원을 쓰는 사람 수뿐이다.

전략 조합 $s=(s_1,\dots,s_n)$ 에서 자원 $e$ 의 부하 $n_e(s) = |\{i : e \in s_i\}|$ 를 정의하면 플레이어 $i$ 의 비용은

$$C_i(s) \;=\; \sum_{e \in s_i} c_e\big(n_e(s)\big)$$

다. “누가” 같이 쓰는지는 상관없고 “몇 명이” 쓰는지만 본다는 이 익명성이 정의의 전부이며, 뒤의 모든 성질이 여기서 나온다.

대표적인 특수형이 세 가지다. 네트워크 혼잡 게임은 $E$ 가 그래프의 간선이고 전략이 $s_i \to t_i$ 경로인 경우 — 교통·라우팅이 여기다. 대칭(symmetric)은 모든 플레이어의 전략 집합이 같은 경우, 단일 자원(singleton)은 각 전략이 자원 하나인 경우로 기계에 작업을 배정하는 부하 분산 모형이 이에 해당한다. 이 세 축을 어떻게 조합하느냐가 그대로 계산 난이도를 가른다.

3. 로젠탈 퍼텐셜 함수[편집]

로젠탈이 꺼낸 함수는 이것 하나다.

$$\Phi(s) \;=\; \sum_{e \in E} \; \sum_{k=1}^{n_e(s)} c_e(k)$$

생김새가 이상해 보인다. 실제 총비용 $\sum_i C_i(s) = \sum_e n_e(s)\,c_e(n_e(s))$ 와 전혀 다르다 — 후자는 “현재 부하에서의 비용 × 인원”인데 $\Phi$ 는 “1명일 때, 2명일 때, …, $n_e$ 명일 때의 비용을 전부 더한” 것이다. 사회적 비용도 아니고 누구의 효용도 아닌, 아무도 신경 쓰지 않는 회계 장부다.

그런데 플레이어 $i$ 혼자 전략을 $s_i$ 에서 $s_i'$ 로 바꾸면

$$\Phi(s_i', s_{-i}) - \Phi(s_i, s_{-i}) \;=\; C_i(s_i', s_{-i}) - C_i(s_i, s_{-i})$$

가 정확히 성립한다. 확인은 자원 단위로 하면 즉시 끝난다. $i$ 가 빠져나온 자원 $e \in s_i \setminus s_i'$ 에서는 부하가 $n_e$ 에서 $n_e-1$ 로 줄어 $\Phi$ 의 안쪽 합에서 항 $c_e(n_e)$ 하나가 사라지는데, 그건 $i$ 가 그 자원에 대해 내던 비용 그 자체다. 새로 들어간 자원에서는 항 $c_e(n_e+1)$ 이 하나 붙고, 그것이 $i$ 가 새로 내는 비용이다. 다른 플레이어의 비용 변화는 $\Phi$ 에도 $C_i$ 에도 잡히지 않는다. $\Phi$ 는 «남에게 끼친 피해»를 세지 않기 때문에 정확히 «나에게 온 비용»과 보조를 맞춘다.

여기서 존재 정리가 세 줄로 나온다. 전략 조합이 유한하므로 $\Phi$ 를 최소화하는 $s^{*}$ 가 존재한다. 어떤 플레이어가 $s^{*}$ 에서 혼자 이탈해 이득을 본다면 $\Phi$ 가 그만큼 줄어야 하는데 $s^{*}$ 는 최소점이므로 모순. 따라서 $\Phi$ 의 최소점은 순수 내시 균형이다.

$$\boxed{\ \arg\min_s \Phi(s) \ \subseteq\ \{\text{순수 내시 균형}\}\ }$$

역은 성립하지 않는다는 점이 중요하다. $\Phi$ 의 국소 최소점(한 명씩 바꿔서는 못 줄이는 점)이 균형이고, 그런 국소 최소점은 여러 개일 수 있다. 균형이 여럿이라는 사실, 그중 나쁜 것이 있을 수 있다는 사실이 여기서 이미 예고된다.

4. 정확 퍼텐셜 게임과의 동치[편집]

위 성질을 게임 일반으로 추상화한 것이 정확 퍼텐셜 게임이다. 함수 $\Phi$ 가 모든 $i$, 모든 $s_i, s_i'$ 에 대해

$$u_i(s_i, s_{-i}) - u_i(s_i', s_{-i}) \;=\; \Phi(s_i, s_{-i}) - \Phi(s_i', s_{-i})$$

를 만족하면 정확 퍼텐셜이라 부른다.² 로젠탈이 보인 것은 모든 혼잡 게임이 정확 퍼텐셜 게임이라는 것이고, 몬데러와 샤플리(1996)가 그 역을 보였다 — 모든 유한 정확 퍼텐셜 게임은 어떤 혼잡 게임과 동형이다. 즉 두 부류가 정확히 겹친다.

이건 단순한 미학적 결과가 아니라 분류 정리다. “내 모형에 퍼텐셜이 있는가”라는 질문과 “내 모형을 혼잡 게임으로 다시 쓸 수 있는가”라는 질문이 같은 질문이 된다. 그리고 정확 퍼텐셜을 못 찾겠다면, 그건 게으름이 아니라 원리적으로 없다는 뜻일 수 있다.

느슨한 판도 유용하다. 부등식의 부호만 맞으면 되는 서수적 퍼텐셜(ordinal potential)로 약화해도 존재 정리는 그대로 굴러가고, 실제로 “유한 개선 성질(FIP)을 갖는다 $\iff$ 일반화 서수적 퍼텐셜이 존재한다”가 성립한다. 존재 정리에 정말 필요한 것은 «이득이 나는 이탈은 반드시 어떤 스칼라 값을 단조롭게 움직인다» 뿐이라는 이야기다. 물리 쪽 사람에게는 리아푸노프 함수라고 하면 한 번에 통한다.

퍼텐셜이 죽는 지점도 분명하다.

• 가중 혼잡 게임 — 플레이어마다 트래픽 크기 $w_i$ 가 다르면 로젠탈 논증이 깨지고, 순수 균형이 아예 없는 예가 존재한다. 다만 비용이 아핀이거나 지수함수면 여전히 퍼텐셜을 만들 수 있다는 것이 알려져 있다.
• 플레이어별 비용 함수 — 같은 자원의 혼잡도가 사람마다 다르게 느껴지면 퍼텐셜은 사라진다. 그래도 전략이 단일 자원이면 순수 균형은 남는다(밀히타이히 1996).
• 자원 간 상호작용 — 비용이 다른 자원의 부하에도 의존하면 그 순간 그냥 일반 게임이다.

시뮬레이션 코드를 짤 때 이 목록은 곧 “내 루프가 영원히 안 멈출 수 있는 조건표” 다.

5. 최적반응 동학과 PLS-완비[편집]

퍼텐셜이 있으면 개선 동학(이득 나는 사람이 한 명씩 옮기기)은 반드시 유한 스텝에 정지한다. $\Phi$ 가 매 스텝 엄격히 감소하고 상태 공간이 유한하기 때문이다. 이것이 다중 에이전트 시뮬레이션에서 혼잡 게임이 사랑받는 이유다 — 수렴 진단이 «$\Phi$ 를 찍어 보면 된다»로 끝난다.

문제는 “유한”이 “빠르다”가 아니라는 것. 파브리칸트·파파디미트리우·탈와르(2004)가 정리한 지형이 지금도 표준 참고표다.

부류	순수 균형 계산
대칭 네트워크 혼잡 게임	다항시간 — 최소 비용 흐름으로 환원
비대칭 네트워크 혼잡 게임	PLS-완비
일반 혼잡 게임 (대칭 포함)	PLS-완비

PLS(Polynomial Local Search)는 “국소 최적을 찾는” 탐색 문제들의 부류다. 답이 반드시 존재한다는 것은 알지만 찾는 데 지름길이 없어 보이는, NP-완전과는 결이 다른 어려움이고, PPAD 와 사촌 관계다. PLS-완비라는 사실이 실무에 주는 함의는 두 가지다. 첫째, 개선 동학이 지수적으로 긴 경로를 밟는 인스턴스가 존재한다. 둘째, 그런 인스턴스에서는 균형에 도달하는 어떤 알고리즘도 사실상 그 경로를 걷는 것과 다르지 않다. 국소 탐색 휴리스틱 전반이 같은 벽에 부딪히는 것과 정확히 같은 구조다.

대칭 네트워크 판이 다항시간인 이유는 정확히 이 문서의 앞부분이다 — 로젠탈 퍼텐셜을 목적함수로 놓으면 그것이 간선별 분리 가능한 볼록 함수이고, 정수 유량 위의 볼록비용 최소비용 흐름 문제가 된다. 조각별 선형 볼록 비용을 평행 간선으로 쪼개는 표준 트릭이 그대로 통한다. “게임을 푼다”가 “흐름 문제를 푼다”로 바뀌는 이 환원이 알고리즘 게임 이론의 대표적 명장면 중 하나다.

6. 비원자적 판 — 워드롭 균형[편집]

플레이어 하나하나가 “무한히 작아서” 개인이 혼잡에 미치는 영향이 무시되는 극한이 비원자적(nonatomic) 혼잡 게임, 교통공학의 언어로는 교통 배정이다. 여기서의 균형 조건이 워드롭(1952)의 제1원리다.

실제로 쓰이는 모든 경로의 통행시간이 같고, 쓰이지 않는 경로의 통행시간은 그보다 크거나 같다.

이 조건이 내시 균형의 무차별 조건과 글자만 다르다는 점을 눈치챘다면 정확하다. 그리고 로젠탈 퍼텐셜의 연속 극한이 베크만 퍼텐셜이다 — 합을 적분으로 바꾸면 된다.

$$\Phi(f) \;=\; \sum_{e\in E} \int_{0}^{f_e} c_e(x)\,dx$$

$c_e$ 가 비감소·연속이면 $\Phi$ 는 볼록이고, 유량 보존 제약은 선형이므로 균형 = 볼록계획의 해다. 여기서 세 가지가 공짜로 따라온다.

• 존재. 컴팩트 볼록 집합 위의 연속 볼록 함수는 최소점을 갖는다.
• 본질적 유일성. $c_e$ 가 순증가면 $\Phi$ 가 엄격 볼록이라 균형 간선유량이 유일하다(경로 분해는 여러 가지일 수 있다).
• 계산. 프랭크-울프 계열 반복법으로 푼다. 각 반복이 “현재 통행시간으로 전원 최단경로 재배정” + “선형탐색으로 섞기”라서, 사실상 다익스트라 알고리즘을 돌리는 루프다. 교통 계획 소프트웨어의 심장부가 이것이다.

여기서 반드시 구분해야 할 것이 사용자 균형과 시스템 최적이다. 시스템 최적은 총 통행시간 $\sum_e f_e c_e(f_e)$ 를 최소화하는데, 그 1계 조건은 한계비용 $c_e(x) + x\,c_e'(x)$ 를 통행시간으로 삼은 워드롭 균형과 같다. 두 번째 항 $x c_e'(x)$ 가 내가 남에게 끼치는 지연이고, 이기적 개인은 그걸 안 낸다. 시스템 최적과 균형의 차이가 정확히 이 외부효과 하나이며, 그것이 다음 절과 무정부의 대가의 주제다.

7. 브라에스 역설[편집]

디트리히 브라에스가 1968년에 지적한, 이 분야에서 가장 유명한 반직관.³ 출발지 $s$ 에서 목적지 $t$ 로 유량 1 이 흐르고 경로가 둘이다. $s\to a$ 의 지연은 $x$, $a\to t$ 는 상수 $1$; $s\to b$ 는 $1$, $b\to t$ 는 $x$. 대칭이므로 균형에서는 절반씩 갈라지고 모두의 통행시간은 $\tfrac12 + 1 = \tfrac32$ 다.

이제 지연이 0 인 지름길 $a \to b$ 를 추가한다. 각자에게 $s\to a\to b\to t$ 는 항상 매력적이다 — 상단 절반과 하단 절반의 “싼 쪽”만 골라 쓰는 경로이기 때문이다. 전원이 그리로 몰리는 것이 유일한 균형이 되고, 통행시간은 $1+0+1 = 2$ 로 늘어난다. 확인해 보면 다른 경로도 전부 2 라서 아무도 이탈할 이유가 없다. 아무도 비합리적으로 굴지 않았고 네트워크 성능만 좋아졌는데 전원이 손해를 봤다. 비율은 $2 \div \tfrac32 = 4/3$.

역설의 정체는 마술이 아니라 외부효과다. 새 간선은 각자에게 “남의 혼잡을 늘리는 대신 내 시간을 줄이는” 선택지를 하나 더 준 것이고, 개인 최적화는 그 대가를 계산에 넣지 않는다. 같은 이유로 역설은 간선을 지우면 사라진다 — 도로를 폐쇄했더니 소통이 나아졌다는 사례들(서울 청계천 복원, 뉴욕 42번가 폐쇄 등)이 이 역설의 실사판으로 늘 인용되는데, 실제 도로망은 수요 변화·경로 선택 행태 등 변수가 많아 인과를 단정하기는 어렵다는 점은 짚어 두는 게 공정하다.

시뮬레이션 관점에서 진짜 중요한 것은 이것이 버그가 아니라는 사실이다. 에이전트가 각자 경로 계획으로 최단경로를 뽑아 쓰는 군중 시뮬레이션을 짜면, 맵에 지름길을 하나 놓았을 때 전체 소요시간이 늘어나는 현상이 정확히 재현된다. 그걸 보고 경로 탐색 코드를 뒤지기 시작하면 며칠을 버린다.

8. 시뮬레이션 실무에서[편집]

• $\Phi$ 를 로그로 찍어라. 개별 에이전트 비용은 진동해도 로젠탈/베크만 퍼텐셜은 단조 감소해야 한다. 늘어나는 순간이 보이면 그건 수렴 실패가 아니라 모형이 혼잡 게임이 아니라는 신호다(가중치, 플레이어별 비용, 자원 간 결합 중 하나가 들어갔다).
• 동시 갱신을 하지 마라. 퍼텐셜 논증은 한 번에 한 명이 바꿀 때만 성립한다. 전원을 동시에 최단경로로 재배정하면 다음 스텝에 전원이 반대편으로 몰리는 진동이 생긴다. 비원자적 판의 표준 처방이 프랭크-울프나 연속평균법(MSA) 같은 감쇠 스텝이고, 원자적 판이라면 무작위 순서로 한 명씩 돌리는 것이 안전하다.
• 균형이 여럿임을 전제하라. $\Phi$ 의 국소 최소점이 여럿이므로 초기 조건과 갱신 순서가 결과를 바꾼다. 리플리케이트를 여러 번 돌리고 분포를 보고해야지, 한 번 돌린 값을 “그 게임의 균형”이라 부르면 안 된다.
• 자원 재사용에 주의. 한 플레이어의 전략이 같은 자원을 두 번 포함하면($s_i$ 가 집합이 아니라 다중집합) 정의가 흔들린다. 경로가 단순 경로가 아닐 수 있는 그래프에서 자주 사고가 난다.
• 어디서 만나나. 게임 서버 선택·매치메이킹 큐, 부하 분산의 작업 배정, 무선 채널 선택, 경로 계획을 각자 돌리는 NPC 군집, HPC 잡 스케줄러의 노드 경합 — 전부 자원 공유 비용이 인원 수에만 의존하는 순간 이 문서의 도구가 그대로 통한다.

9. 관련 문서[편집]

• 무정부의 대가 · 내시 균형 · 상관 균형 · 게임 이론
• 워드롭 균형 · 브라에스 역설 · 교통 배정
• 최소 비용 흐름 · 네트워크 흐름 · 다익스트라 알고리즘
• 볼록 최적화 · 국소 탐색 · NP-완전 · 최적설계
• 무후회 학습 · 복제자 동역학 · 진화적 안정 전략
• 군중 시뮬레이션 · 경로 계획 · 부하 분산

10. Footnotes[편집]

1. Rosenthal, R. W. (1973). International Journal of Game Theory 2, 65–67. 세 쪽이다. 그리고 그 세 쪽으로 알고리즘 게임 이론이라는 분야의 절반이 굴러간다. 정작 로젠탈 본인은 이 결과를 대단하게 여기지 않았다는 이야기가 있는데, 30년쯤 뒤 전산학자들이 몰려와 발굴한 케이스라 놀랄 일은 아니다. ↩

2. “정확”이 붙은 이유는 부등식이 아니라 등식이기 때문이다. 부호만 맞으면 서수적(ordinal), 상수배까지 허용하면 가중(weighted) 퍼텐셜이 되고, 갈수록 성질이 약해진다. 논문에서 “potential game”이라는 단어를 보면 어느 판인지부터 확인하는 게 좋다 — 세 개가 다른 정리를 쓴다. ↩

3. Braess, D. (1968). “Über ein Paradoxon aus der Verkehrsplanung”. Unternehmensforschung 12, 258–268. 독일어 원문이라 영어권에서는 한참 뒤에야 널리 읽혔고, 2005년에야 영역본이 나왔다. 한국어 표기는 “브레스 역설”로도 굴러다닌다. 참고로 브라에스 본인은 교통공학자가 아니라 수학자였고, 이 논문은 그의 연구 이력에서 이례적인 외도에 가깝다. ↩