워드롭 균형

1. 개요[편집]

워드롭 균형 Wardrop equilibrium
제안	John Glen Wardrop (1952)
제1원리	사용자 균형(UE) — 쓰이는 경로의 통행시간이 모두 같다
제2원리	시스템 최적(SO) — 평균(=총) 통행시간이 최소
등가 문제	베크만 변환 (1956) — 링크별 적분의 합을 최소화하는 볼록계획
유일성	링크 유량은 유일(비용이 순증가일 때) · 경로 유량은 유일하지 않다
SO 로 가는 법	한계비용 통행료 $x_a t_a'(x_a)$ 부과
비대칭 확장	퍼텐셜이 없어 변분부등식으로 정식화

워드롭 균형(Wardrop equilibrium)은 도로망에서 각 운전자가 자기 통행시간만 최소화하도록 경로를 고를 때 도달하는 유량 배분이며, 존 글렌 워드롭이 1952년 논문에서 제시한 두 원리 중 제1원리로 정의된다.¹ 교통공학에서는 사용자 균형(User Equilibrium, UE)이라고 더 자주 부른다.

핵심은 이것이 내시 균형의 비원자적(nonatomic) 판본이라는 점이다. 플레이어가 유한 명이 아니라 “연속체”이고, 개인 한 명의 유량은 무한소라서 자기 선택이 링크 혼잡에 미치는 영향이 0 이다. 그 극한 덕분에 혼잡 게임의 로젠탈 퍼텐셜이 적분으로 바뀌고, 균형을 찾는 문제가 통째로 볼록 최적화로 내려앉는다. 이 문서는 그 변환이 왜 성립하고, 어디서 깨지고, 깨지면 무엇으로 대체하는지를 본다. 실제 반복 알고리즘은 교통 배정, 균형이 최적보다 얼마나 나쁜지는 무정부의 대가, 가장 유명한 반례는 브라에스 역설에 있다.

2. 두 원리 — 원문과 흔한 오해[편집]

워드롭이 쓴 문장은 짧다.

제1원리. 실제로 쓰이는 모든 경로의 통행시간이 같고, 쓰이지 않는 경로에서 차량 한 대가 겪을 통행시간은 그보다 작지 않다.

제2원리. 평균 통행시간이 최소가 된다.

기호로 옮기면 OD 쌍 $(r,s)$ 의 경로 $k$ 의 통행시간 $c_k^{rs}$ 와 최소 통행시간 $u^{rs}$ 에 대해

$$f_k^{rs} > 0 \ \Rightarrow\ c_k^{rs} = u^{rs}, \qquad f_k^{rs} = 0 \ \Rightarrow\ c_k^{rs} \ge u^{rs}$$

이고, 이 둘은 상보성 조건 $f_k^{rs}\,(c_k^{rs} - u^{rs}) = 0$ 한 줄로 합쳐진다.

오해가 세 가지 있다.

• “모든 경로의 통행시간이 같다”가 아니다. 안 쓰이는 경로는 더 느려도 된다. 이 부등식 쪽을 빼먹으면 균형 판정 코드가 존재하지도 않는 해를 찾다가 영원히 안 멈춘다.
• 제2원리는 사람들의 행동 원리가 아니다. 아무도 총 통행시간을 최소화할 유인이 없다. 제2원리는 비교 기준으로 존재하는 가상의 배분이며, 워드롭 본인도 두 원리가 다른 배분을 준다는 점을 지적하려고 나란히 썼다.
• “평균 최소”와 “총합 최소”는 같다. 수요 $q^{rs}$ 가 고정이므로 총 통행시간을 총 수요로 나눈 것이 평균이다. 수요가 통행시간에 반응하는 탄력수요 모형에서는 이 등가가 깨진다.

3. 베크만 변환[편집]

베크만·맥과이어·윈스틴(1956)이 찾아낸 것이 이 분야의 결정적 한 수다.² 링크 $a$ 의 통행시간이 자기 링크의 유량에만 의존하는 증가함수 $t_a(x_a)$ 라고 하자. 그러면 다음 볼록계획의 해가 정확히 워드롭 균형이다.

$$\min_{x} \ z(x) \;=\; \sum_{a \in A} \int_{0}^{x_a} t_a(w)\,dw$$

제약은 유량 보존과 비음수뿐이다 — 경로 유량 $f_k^{rs} \ge 0$, $\sum_k f_k^{rs} = q^{rs}$, 링크 유량은 $x_a = \sum_{rs}\sum_k f_k^{rs}\,\delta_{a,k}^{rs}$.

증명은 카루시-쿤-터커 조건을 쓰면 세 줄이다. 목적함수를 경로 유량으로 미분하면 연쇄법칙에 의해

$$\frac{\partial z}{\partial f_k^{rs}} \;=\; \sum_a t_a(x_a)\,\delta_{a,k}^{rs} \;=\; c_k^{rs}$$

즉 그래디언트 성분이 그냥 그 경로의 통행시간이다. 수요 제약의 승수를 $u^{rs}$ 라 두면 KKT 는 $f_k^{rs}(c_k^{rs}-u^{rs})=0$, $c_k^{rs}\ge u^{rs}$ 가 되고, 이것이 위의 제1원리 그대로다. 승수 $u^{rs}$ 는 균형 최소 통행시간이라는 물리적 의미까지 갖는다.

목적함수 $z$ 는 물리적 의미가 없다는 점을 강조해 둘 필요가 있다. 총 통행시간은 $\sum_a x_a t_a(x_a)$ 이지 $\sum_a \int_0^{x_a} t_a$ 가 아니다. 이 적분은 혼잡 게임의 로젠탈 퍼텐셜을 연속화한 것이고, 아무의 비용도 아닌 회계 장부다. 그럼에도 이걸 최소화하면 균형이 나온다는 것이 요점이다. 실무에서 이 값을 그대로 보고서에 “총 통행비용”이라고 적어 넣는 사고가 종종 나는데, 자릿수부터 틀린다.

4. 존재성과 유일성[편집]

볼록계획이 되면 세 가지가 공짜로 따라온다.

• 존재. 실행가능 집합은 유계 다면체(컴팩트 볼록)이고 $t_a$ 가 연속이면 $z$ 도 연속이라 최소점이 있다. $t_a$ 가 순증가일 필요도 없다 — 연속·비감소면 충분하다.
• 링크 유량의 유일성. $t_a$ 가 순증가면 $\int_0^{x_a} t_a$ 가 엄격 볼록이고 링크 유량의 합으로 표현되므로 $z$ 는 링크 유량에 대해 엄격 볼록이다. 따라서 균형 링크 유량 $x^\star$ 는 유일하다.
• 경로 유량의 비유일성. $x \mapsto f$ 는 다대일이므로 경로 유량은 일반적으로 유일하지 않다. 두 알고리즘이 같은 링크 유량에 수렴하고도 경로 분해가 완전히 다를 수 있다는 뜻이고, 경로별 통행량을 정책 근거로 쓰려는 순간 이게 문제가 된다. 유일한 답을 원하면 최대 엔트로피 경로 분해 같은 추가 원리를 얹어야 한다.

상수 통행시간 링크가 섞여 있으면(예: 용량이 사실상 무한한 우회로) $t_a$ 가 순증가가 아니므로 그 링크의 유량도 유일하지 않을 수 있다. 링크 유량 유일성 정리를 인용하기 전에 자기 네트워크에 상수 링크가 몇 개 있는지 세 보는 습관이 필요하다.

5. 사용자 균형과 시스템 최적 — 숫자로[편집]

수요 4000 대/시가 두 평행 링크로 나뉜다고 하자. A 는 상수 $t_A = 20$ 분(길지만 안 막히는 고속도로), B 는 $t_B = 10 + x/200$ (짧지만 막히는 국도).

UE. 둘 다 쓰이므로 통행시간이 같아야 한다. $10 + x_B/200 = 20 \Rightarrow x_B = 2000$, $x_A = 2000$. 모두 20 분. 총 통행시간은 $4000 \times 20 = 80{,}000$ 대·분.

SO. 목적은 $\sum_a x_a t_a(x_a)$ 의 최소화다. B 의 한계비용은

$$\tilde t_B(x) \;=\; t_B(x) + x\,t_B'(x) \;=\; 10 + \frac{x}{200} + \frac{x}{200} \;=\; 10 + \frac{x}{100}$$

이고, 이것을 $t_A = 20$ 과 같게 두면 $x_B = 1000$. 총 통행시간은 $3000\times 20 + 1000\times 15 = 75{,}000$ 대·분. 6.25 % 가 그냥 사라진다.

여기서 SO 의 1계 조건이 “한계비용을 통행시간으로 쓴 워드롭 균형”이라는 사실이 그대로 드러난다. 일반적으로

$$\frac{\partial}{\partial x_a}\sum_b x_b t_b(x_b) \;=\; t_a(x_a) + x_a t_a'(x_a)$$

이고, 두 번째 항 $x_a t_a'$ 가 내가 진입해서 나머지 모두에게 추가로 지운 지연의 총합, 즉 외부효과다. 이기적 운전자는 이걸 안 낸다. 그렇다면 내게 하면 된다 — 링크마다

$$\tau_a \;=\; x_a^{\mathrm{SO}}\,t_a'\!\left(x_a^{\mathrm{SO}}\right)$$

만큼 통행료를 물리면 사용자 균형이 시스템 최적과 일치한다. 위 예에서는 $1000 \times \tfrac{1}{200} = 5$ 분어치를 B 에 부과하면 된다. 실제로 그렇게 하면 B 의 일반화 비용이 $15+5=20$ 으로 A 와 같아지고, 아무도 옮길 이유가 없어진다. 1920년 피구가 제안한 처방이고 오늘날 혼잡통행료의 이론적 근거다.³

6. 변분부등식으로의 일반화[편집]

베크만 변환의 전제는 딱 하나였다 — $t_a$ 가 자기 링크 유량만의 함수. 이게 깨지면 어떻게 되는가.

현실의 교차로는 대칭이 아니다. 비보호 좌회전은 마주 오는 직진 유량에 막히고, 그 반대는 성립하지 않는다. 즉 야코비안 $\partial t_a/\partial x_b$ 가 비대칭이다. 푸앵카레 보조정리에 의해 비대칭 사상은 어떤 함수의 그래디언트도 아니므로, 최소화할 목적함수 자체가 존재하지 않는다.

그래도 균형 조건은 그대로 살아 있고, 변분부등식으로 쓰면 된다. 실행가능 링크 유량 집합 $\Omega$ 에 대해 $x^\star \in \Omega$ 를 찾되

$$\sum_{a} t_a(x^\star)\,\bigl(x_a - x_a^\star\bigr) \;\ge\; 0 \qquad \forall\, x \in \Omega$$

를 만족시킨다. $t = \nabla z$ 인 대칭 경우에는 이것이 정확히 $z$ 의 1계 조건으로 되돌아가고, 비대칭이면 최적화가 아닌 균형 문제로 남는다. 스미스(1979)와 다페르모스(1980)가 도입한 정식화이며, 오늘날 교차로 상호작용·다중 사용자 계급·탄력수요·혼잡통행료 설계가 전부 이 틀 위에 있다.

대가는 정직하게 치른다. 존재성은 $\Omega$ 가 컴팩트하고 $t$ 가 연속이면 그대로지만, 유일성은 $t$ 의 강단조성을 요구하고 그건 야코비안의 대칭부 양정치성으로 확인해야 한다. 알고리즘도 프랭크-울프 대신 사영법·외부경사법 계열로 갈아타야 하고, 수렴 판정에 쓸 볼록 목적함수가 없으므로 간극 함수를 따로 만들어야 한다.

7. 시뮬레이션에서 조심할 것[편집]

• 동시 갱신 금지. “현재 통행시간으로 전원을 최단경로에 재배정”을 그대로 반복하면 전원이 좌우로 몰리는 진동이 나온다. 감쇠(선탐색·연속평균법)가 필수이며, 자세한 처방은 교통 배정.
• 수렴 판정은 목적함수가 아니라 상대격차로. $z$ 는 물리적 의미가 없고 절대값도 크므로 ”$z$ 가 안 변한다”는 기준은 쓸모없다. 쓰이는 경로와 최단경로의 통행시간 차이를 재는 상대격차가 표준이다.
• UE 와 SO 를 같은 코드로 뽑아라. 통행시간 함수를 $t_a$ 에서 $t_a + x_a t_a'$ 로 바꿔 끼우면 같은 솔버가 SO 를 준다. 두 번 돌려 나눈 값이 그 네트워크의 무정부의 대가다. 별도 최적화기를 짜는 사람이 놀랍게 많다.
• 경로 유량을 결과로 보고하지 마라. 유일하지 않다. 링크 유량, 링크 통행시간, OD 최소 통행시간만이 재현 가능한 출력이다.
• 비원자성이 성립하는지 확인. 유량이 수십 대 규모인 마을 도로망이나 게임 NPC 수십 마리에는 비원자 극한이 안 맞는다. 그럴 땐 원자적 혼잡 게임으로 모형화해야 하고, 순수 균형이 여러 개 생기며 유일성이 사라진다.

8. 관련 문서[편집]

• 교통 배정 · 브라에스 역설 · 혼잡 게임
• 무정부의 대가 · 내시 균형 · 상관 균형 · 게임 이론
• 변분부등식 · 볼록 최적화 · 카루시-쿤-터커 조건
• 프랭크-울프 · 다익스트라 알고리즘 · 최소 비용 흐름 · 네트워크 흐름
• 혼잡통행료 · 교통 흐름 · 군중 시뮬레이션 · 경로 계획

9. Footnotes[편집]

1. Wardrop, J. G. (1952). “Some theoretical aspects of road traffic research”. Proceedings of the Institution of Civil Engineers, Part II, 1(3), 325–362. 발표 자리는 학술지가 아니라 토목학회 세미나였고, 두 원리는 논문 전체에서 한 쪽도 안 되는 분량이다. 나머지는 속도-교통량 관계와 신호 지연 같은 실무 이야기. 정작 그 한 쪽이 교통공학의 절반을 규정했다. ↩

2. Beckmann, M., McGuire, C. B., & Winsten, C. B. (1956). Studies in the Economics of Transportation. RAND 연구서로 나온 물건이라 교통공학계에는 한참 뒤에야 알려졌다. 저자 셋이 전부 경제학자였다는 점도 재밌는데, 덕분에 “균형”과 “외부효과”라는 언어가 처음부터 들어가 있었다. ↩

3. 이론이 아름다운 것과 정치적으로 통과되는 것은 완전히 별개다. 싱가포르(1975)·런던(2003)·스톡홀름(2007)이 실제로 도입했고, 뉴욕은 2007년부터 밀다가 2025년에야 시행했다. 경제학자들이 100년 동안 “이건 자명하게 옳다”고 말해 온 정책의 도입 속도가 대략 50년에 한 도시꼴이라는 뜻이다. ↩