브라에스 역설

최적설계 게임 개발 시뮬레이션 마지막 수정: 2026-08-28 04:31:08

1. 개요[편집]

브라에스 역설 Braess's paradox
제기	Dietrich Braess (1968)
현상	도로를 추가했는데 균형 통행시간이 늘어난다
원인	사용자 균형 ≠ 시스템 최적 — 혼잡 외부효과
고전 예제	4노드 · 수요 4000 · 65분 → 80분
손해 상한	아핀 지연에서 $4/3$ 배 (무정부의 대가)
어느 링크를 지울까	NP-난해 — 아핀에서 4/3 보다 나은 근사 불가
사촌	용수철·전기회로에서도 같은 현상 (Cohen–Horowitz 1991)

브라에스 역설(Braess’s paradox)은 교통망에 링크를 새로 추가했는데 모든 이용자의 균형 통행시간이 오히려 늘어나는 현상이다. 디트리히 브라에스가 1968년 독일어 논문에서 제시했다.¹

“막히니까 길을 더 놓자”는 직관이 정면으로 배신당하는 사례이고, 무엇보다 아무도 비합리적으로 행동하지 않았는데 벌어진다는 점이 고약하다. 각자는 여전히 자기에게 가장 빠른 길을 고르고 있고, 그 상태에서 이탈할 유인도 없다. 그런데 전원이 예전보다 늦게 도착한다. 원인은 워드롭 균형이 총 통행시간을 최소화하지 않는다는 사실 하나뿐이고, 나머지는 산수다.

2. 고전 예제[편집]

네 개의 노드 $s, v, w, t$ 와 네 개의 링크로 시작한다. 수요는 $s \to t$ 로 시간당 4000 대. 유량 $x$ 는 대/시, 통행시간은 분이다.

링크	통행시간 (분)	성격
$s \to v$	$x/100$	좁은 다리 — 막히면 느려진다
$s \to w$	$45$	넓은 우회로 — 늘 45분
$v \to t$	$45$	넓은 우회로 — 늘 45분
$w \to t$	$x/100$	좁은 다리 — 막히면 느려진다

경로는 두 개다. 위쪽 $s\to v\to t$ 는 $x/100 + 45$ , 아래쪽 $s\to w\to t$ 는 $45 + x/100$ . 완전히 대칭이므로 균형에서는 2000 대씩 갈라지고, 통행시간은 양쪽 모두

\frac{2000}{100} + 45 \;=\; 20 + 45 \;=\; \boxed{65\ \text{분}}

총 통행시간은 $4000 \times 65 = 260{,}000$ 대·분이다. 참고로 이 네트워크에서는 사용자 균형이 곧 시스템 최적이다. 한계비용 $2x/100 + 45$ 를 양쪽에서 같게 두어도 답은 그대로 2000 대씩이다.

이제 $v$ 와 $w$ 사이에 통행시간 0 인 초고속 연결로를 놓는다. 순수하게 선물이다 — 누구에게서 아무것도 빼앗지 않았다.

새 경로 $s\to v\to w\to t$ 가 생긴다. 이 경로는 “위쪽의 싼 절반”과 “아래쪽의 싼 절반”만 골라 쓴다. 전원이 이리로 몰렸다고 가정하면 $x_{sv} = x_{wt} = 4000$ 이므로

\frac{4000}{100} + 0 + \frac{4000}{100} \;=\; 40 + 40 \;=\; \boxed{80\ \text{분}}

이게 진짜 균형인지 확인해야 한다. 이탈해 보자. $s\to v\to t$ 는 $40 + 45 = 85$ 분, $s\to w\to t$ 는 $45 + 40 = 85$ 분. 둘 다 80분보다 나쁘다. 아무도 못 옮긴다. 유일한 워드롭 균형이 맞고, 통행시간은 65분에서 80분으로 23 % 늘었다. 링크를 추가해서.

S→A와 B→T가 x/100분, A→T와 S→B가 45분인 고전 4노드 망에 4000대/h를 배정해 사용자 균형을 MSA와 프랭크-울프로 실제로 반복해 푼다. 무비용 A→B를 개통하면 전원이 S-A-B-T로 몰려 65.00분이 80.00분으로 늘고, 시스템 최적 64.6875분에 대한 무정부의 대가가 1.2367이 된다. c₀ 슬라이더를 올리면 c₀=5에서 85.00분으로 최악을 지나 c₀=25에서 역설이 사라진다.

3. 왜 이런 일이[편집]

새 링크는 각자에게 “내 시간을 20분 줄이는 대신 남 4000명의 시간을 늘리는” 선택지를 하나 더 준 것이다. 개인의 계산에는 앞쪽만 들어가고 뒤쪽은 안 들어간다. 워드롭 균형에서 본 대로 이기적 선택은 통행시간 $t_a(x_a)$ 를 보지만 사회적 최적은 한계비용 $t_a(x_a) + x_a t_a'(x_a)$ 를 봐야 하는데, 그 차이인 외부효과 항이 정확히 새 링크를 매력적으로 만드는 크기만큼 무시된다.

그래서 선택지가 늘어난 것이 손해가 될 수 있다. 이건 개인 의사결정에서는 절대 안 일어나는 일이다(선택지가 늘면 최적값은 나빠질 수 없다). 균형에서만 일어나며, 이유는 다른 사람들의 선택지도 같이 늘어났기 때문이다.

역설이 성립하려면 두 조건이 필요하다. 첫째, 혼잡 민감한 링크와 둔감한 링크가 섞여 있어야 한다. 모든 링크가 상수면 균형이 곧 최단경로라서 링크 추가가 손해일 수 없다. 둘째, 새 링크가 혼잡 민감 구간을 이어 붙여야 한다. 위 예에서 $v\to w$ 는 두 개의 $x/100$ 링크를 직렬로 연결해 준다.

4. 무정부의 대가와의 관계[편집]

이 인스턴스의 숫자를 끝까지 계산해 보면 재밌는 게 나온다. 링크 추가 후 네트워크의 시스템 최적을 풀면, 정답은 “새 링크를 안 쓰는 것”이 아니다.

$s\to v$ 유량을 $a$ , 새 링크 $v\to w$ 의 유량을 $b$ 라 하자. 두 상수 링크의 비용 합이 $45(4000-a) + 45(a-b) = 180{,}000 - 45b$ 로 $a$ 에 무관해지는 덕분에, 혼잡 링크의 유량 $p = a$ 와 $q = 4000-a+b$ 로 바꿔 쓰면 총 통행시간이 깔끔하게 분리된다.

\text{TSTT} \;=\; \frac{p^2}{100} + \frac{q^2}{100} - 45p - 45q + 360{,}000

각각 미분하면 $p = q = 2250$ , 즉 $a = 2250$ , $b = 500$ 이고(둘 다 실행가능 범위 안이다) 총 통행시간은 258,750 대·분이다. 링크 추가 전의 260,000 보다 작다.

정리하면 이렇다.

상태	사용자 균형 (총 대·분)	시스템 최적 (총 대·분)
링크 추가 전	260,000 (1인당 65분)	260,000
링크 추가 후	320,000 (1인당 80분)	258,750

새 링크는 나쁜 링크가 아니다. 중앙에서 통제하면 500대만 흘려 보내 전체를 0.5 % 개선하는 데 쓴다. 나쁜 것은 링크가 아니라 그 링크가 만들어 낸 균형이다. 추가 후 무정부의 대가는 $320{,}000 / 258{,}750 \approx 1.237$ 이고, 아핀 지연 함수의 이론적 상한 $4/3 \approx 1.333$ 아래에 얌전히 들어간다.

역설의 “손해 배율”도 이 상한에 묶인다. 러프가든·타르도스(2002)의 정리에 의해 링크를 추가한 뒤의 균형 비용은 추가 전 최적 비용의 $4/3$ 배를 넘을 수 없고, 추가 전에는 균형과 최적이 같을 수 있으므로 아핀 지연에서 브라에스 역설이 통행시간을 4/3 배보다 더 늘리는 일은 없다. 위 예의 $80/65 = 16/13 \approx 1.231$ 이고, 혼잡 게임 문서의 단위 수요 판본은 $2 \div \tfrac32 = 4/3$ 으로 상한을 정확히 친다. 지연 함수가 고차 다항식이면 상한이 커지고, 임의의 증가함수를 허용하면 배율은 무한대로 갈 수 있다.

5. 그럼 링크를 지우면 되지 않나[편집]

논리적으로는 맞다. 균형 통행시간을 개선하려고 기존 링크를 제거하는 문제를 네트워크 설계 문제라고 부르는데, 러프가든(2006)이 이게 NP-난해임을 보였다.² 더 아픈 것은 근사 결과다 — 아핀 지연에서 최적의 $4/3$ 배보다 나은 근사를 다항시간에 얻는 것도 P=NP 가 아닌 한 불가능하고, 그 $4/3$ 은 “아무것도 안 하기”가 이미 달성한다. 즉 다항시간 알고리즘 중에는 “그냥 놔둬라”보다 확실히 나은 것이 없다.

이걸 정책 언어로 번역하면 이렇다. “어느 도로를 닫으면 좋아지는지”는 원리적으로 계산이 어렵고, 그럴 시간에 통행료를 매기는 게 낫다. 한계비용 통행료는 다항시간에 계산되고 무정부의 대가를 1 로 만든다(혼잡통행료). 링크를 지우는 것은 최선의 통행료가 할 수 있는 일의 부분집합만 할 수 있다.

한편 이 역설이 특이한 병리 현상이냐 하면 그렇지도 않다. 발리언트와 러프가든(2006)은 무작위로 생성한 대형 네트워크에서 브라에스 역설이 높은 확률로 나타난다는 결과를 냈다. 큰 도로망에는 지워서 이득이 되는 링크가 거의 항상 존재한다는 뜻이다.

6. 실제 도로에서[편집]

늘 인용되는 사례가 셋 있다.

서울 청계천 복원(2003–2005). 고가도로와 왕복 도로를 걷어냈는데 주변 소통이 우려만큼 나빠지지 않았다.
뉴욕 42번가(1990). 지구의 날에 폐쇄했는데 교통이 오히려 나아졌다는 보도.
슈투트가르트. 신설 도로가 상황을 악화시켜 되돌렸다는 이야기.

다만 이 사례들이 브라에스 역설의 인과적 증거는 아니다. 실제 도로망에서는 링크를 하나 지우면 통행 수요 자체가 줄거나(유발수요의 역), 출발 시각과 수단이 바뀌고, 신호 체계와 대중교통이 동시에 손질된다. 청계천의 경우 도심 대중교통 개편이 같은 시기에 있었다. 브라에스 역설은 수요 고정·경로만 선택이라는 정적 모형 안의 명제이고, 현실 사례는 그 모형 밖의 요인이 훨씬 많다. 교과서적 예화로는 훌륭하지만 “이 도로 폐쇄로 소통이 개선된 것은 브라에스 역설 때문”이라고 단정하는 문장은 학술적으로 지지되지 않는다.

7. 도로 말고 다른 곳에서[편집]

역설의 정체는 “혼잡 비용 + 분산 최적화”이므로 무대는 도로가 아니어도 된다.

용수철과 전기회로. 코헨과 호로위츠(1991)가 Nature 에 실은 예가 유명하다. 두 개의 용수철과 두 줄로 매단 추 사이를 잇는 줄을 자르면 추가 올라간다. 회로에서도 같은 배선으로 저항을 늘리는 구성이 가능하다.³
패킷 네트워크. 링크를 증설했더니 라우팅 균형이 나빠지는 사례가 이론적으로 동일하다. TCP 혼잡 제어의 균형이 워드롭 균형과 같은 구조를 갖기 때문.
게임과 군중 시뮬레이션. 각 에이전트가 경로 계획으로 최단경로를 뽑아 쓰는 시뮬레이션에서, 맵에 지름길을 뚫었더니 평균 이동시간이 늘어나는 현상이 그대로 재현된다. 이건 버그가 아니다. 여기서 A* 구현을 의심하기 시작하면 며칠이 날아간다. 레벨 디자인에서 “숏컷을 하나 열었더니 병목이 옮겨 붙어 전체가 느려지는” 밸런싱 문제도 같은 골격이다.

8. 재현할 때 조심할 것[편집]

모든 경로의 균형 조건을 확인하라. “새 경로가 더 싸다”만 보고 끝내면 안 된다. 위 계산에서 이탈 경로가 85분임을 확인한 단계가 증명의 절반이다.
동시 재배정은 진동을 만든다. 전원을 매 스텝 최단경로로 옮기면 65분과 80분 사이를 왔다 갔다 하며 안 멈춘다. 감쇠 스텝(교통 배정의 프랭크-울프·연속평균법)을 써야 균형에 앉는다.
원자적 모형에서는 값이 다르다. 차량 수가 유한하고 각자 덩어리 유량을 가지면 혼잡 게임의 원자적 판이 되고, 균형이 여러 개 생기며 배율도 커진다.
역설을 없앤 뒤 검증하라. 통행료를 매겨 균형이 시스템 최적으로 옮겨 갔다면, 위 예에서 총 통행시간이 258,750 으로 떨어지고 세 경로의 일반화 비용이 모두 90 분으로 같아지는 것을 확인할 수 있다(실제 통행시간은 67.5 · 67.5 · 45 분으로 서로 다르다). 이 두 숫자가 안 맞으면 통행료 계산이 틀린 것이다.

9. 관련 문서[편집]

Braess, D. (1968). “Über ein Paradoxon aus der Verkehrsplanung”. Unternehmensforschung 12, 258–268. 영어 번역본은 2005년에야 Transportation Science 에 실렸다. 37년이 걸린 셈인데, 그동안 영어권은 원문을 못 읽은 채로 이 역설을 열심히 인용하고 있었다. 한국어 표기는 “브레스 역설”로도 굴러다닌다. ↩
Roughgarden, T. (2006). “On the severity of Braess’s paradox: designing networks for selfish users is hard”. Journal of Computer and System Sciences 72(5). 제목이 결론이다. 그리고 이 논문의 진짜 메시지는 “역설을 고치는 게 어렵다”가 아니라 “고치려는 시도가 아무것도 안 하는 것보다 확실히 낫다고 보장할 수 없다” 는 쪽이다. 알고리즘 논문이 정책 담당자에게 줄 수 있는 가장 김빠지는 종류의 답. ↩
Cohen, J. E. & Horowitz, P. (1991). “Paradoxical behaviour of mechanical and electrical networks”. Nature 352, 699–701. 강의 시연으로도 자주 쓰이는데, 줄을 자르는 순간 추가 올라가는 걸 눈앞에서 보면 대부분 자기가 뭘 잘못 봤다고 생각한다. 비슷한 현상이 메조스코픽 전자수송에서도 보고된 바 있다(Pala 등, 2012). 스포츠 통계 쪽에서는 “농구팀의 에이스가 빠졌더니 팀 효율이 올라간다”를 같은 틀로 설명하려는 시도까지 있었다. ↩