길을 하나 더 냈는데 다들 더 오래 걸린다 — 브라에스 역설

길 하나를 더 냈는데, 다들 더 오래 걸렸다

집에서 회사까지 가는 길이 두 갈래다. 한쪽은 좁은 다리를 건너 빠지는 길이고, 다른 쪽은 멀리 돌지만 넓은 길이다. 다리는 차가 몰리면 금세 느려지고, 넓은 길은 차가 좀 늘어도 시간이 잘 안 는다. 그래서 두 길에 걸리는 시간이 대충 비슷해지고, 아침마다 사람들은 반반으로 갈려 나간다.

어느 날 시에서 두 갈래 사이를 가로질러 잇는 짧은 연결도로를 놓았다. 개통식 아침에는 현수막이 걸리고, 지역 뉴스에 우회로가 뚫렸다는 소식이 뜬다. 선택지가 하나 늘었고, 새 길은 짧고 한산하다.

그런데 개통 다음 주, 출근길이 전보다 오래 걸린다. 위로 도는 사람도, 아래로 도는 사람도, 새 길로 질러가는 사람도 다 같이 늦어졌다. 집에서 나서는 시각을 앞당겨야 지각을 면할 정도인데, 길은 그대로고 차도 늘지 않았다. 운전자들끼리 서로 탓할 일도 아니다. 다들 평소처럼 빠른 쪽을 골랐고, 바뀐 것은 지도 위에 선이 하나 늘었다는 것뿐이다.

이 장면이 그대로 계산되는 망이 있다. 브라에스(D. Braess)가 1968년에 내놓은 네 지점짜리 도로망이다.

9분을 더 쓰게 만든 것은 길의 품질이 아니다. 새 길은 열린 첫날 실제로 가장 빠른 길이었고, 운전자들도 실수하지 않았다. 각자 그 순간 가장 빨라 보이는 길을 골랐을 뿐이다. 그런데 각자 빠른 쪽을 고르다 보면 모두가 처음보다 나쁜 자리에 도착할 수 있다. 유령 정체 편에서는 차가 많아서 막히는 일을 다뤘는데, 이번 편은 길이 많아서 막히는 일이다.

평형과 최적이 갈릴 때 — 브라에스 역설

브라에스가 그린 망은 네 지점과 다섯 구간으로 되어 있다. 출발지 a와 도착지 z가 양 끝에 있고, 그 사이에 b와 c가 하나씩 놓인다. 구간마다 통행시간이 정해져 있는데, 차가 늘 때 그 시간이 커지는 속도는 서로 다르다.

그림 1에서 구간은 두 종류다. a→b와 c→z는 좁은 다리여서, 차가 한 대 늘 때마다 통행시간이 10분씩 늘어난다. a→c와 b→z는 넓지만 먼 길이다. 기본이 50분으로 길고, 차가 한 대 늘어도 1분밖에 안 는다. 혼잡에 민감한 구간과 둔한 구간이 하나씩 짝을 이루고 있는 셈이다.

이 구간을 지나는 시간당 차량 수, 즉 흐름을 $\varphi$라고 두면 다섯 구간의 통행시간은 이렇게 적힌다.

식 1의 첫 줄이 좁은 다리이고, 둘째 줄이 넓고 먼 길이다. 셋째 줄은 조금 뒤에 놓을 지름길이다. 원문은 이 시간에 단위를 붙이지 않았는데, 이 글에서는 읽기 편하게 분이라고 부른다.

지름길이 없을 때 a에서 z로 가는 길은 둘뿐이다. a-b-z와 a-c-z인데 둘은 생김새가 똑같아서, 시간당 6대가 3대씩 갈리면 양쪽 모두 83분이다. 여기서 한 대가 반대쪽으로 옮겨 가면 그쪽 좁은 다리가 그만큼 느려져서, 옮긴 사람 자신이 손해를 본다. 그래서 흐름은 3대씩 갈린 자리에서 멈춘다.

이렇게 아무도 혼자 길을 바꿔서 이득을 보지 못하는 상태를 평형이라고 한다. 교통 쪽에서는 와드롭 1원칙(Wardrop’s first principle)이라는 이름으로 부르고, 조건은 한 줄이다. 실제로 쓰이는 길들의 통행시간이 전부 같다. 줄 서기로 바꿔 말하면 어느 창구로 옮겨도 기다리는 시간이 같아진 상태이고, 옆줄이 더 빠른 이유 편에서 본 줄 고르기와 같은 자리다.

평형 옆에 나란히 둘 값이 하나 더 있다. 모두의 통행시간을 합했을 때 그 합이 가장 작은 배치, 즉 최적이다. 지름길이 없는 이 망에서는 둘이 같은 자리에 있다. 3대씩 갈린 배치가 평형이면서 동시에 최적이고, 한 대당 83분이다. 평형과 최적이 겹쳐 있으면 아무 문제가 없다 — 각자 고른 결과가 이미 전체의 최선이기 때문이다. 이 글이 보려는 것은 그 둘이 갈라지는 경우다.

이제 b와 c 사이에 지름길을 놓는다. 경로가 하나 늘어난다. a-b-c-z로 가면 좁은 다리 둘을 연달아 지나고, 그 사이는 짧은 지름길로 건넌다. 3대씩 갈려 있던 상태에서 이 새 경로를 재 보면 70분이다. 83분짜리 길을 타던 사람 눈에는 13분 빠른 길이 생긴 셈이다.

한 사람이 옮겨 가면 그 사람은 실제로 빨라진다. 문제는 그 계산을 모두가 같이 한다는 데 있다. 지름길이 하는 일은 길을 하나 더 주는 것이 아니라, 혼잡에 민감한 두 구간을 한 경로에 묶어 주는 것이다. 지름길을 타는 차는 a→b와 c→z를 둘 다 지나므로, 한 대가 옮겨 갈 때마다 좁은 다리 둘이 동시에 무거워진다. 흐름이 멈추는 자리는 세 경로가 2대씩으로 갈린 지점이다. 지름길을 놓기 전과 놓은 뒤를 나란히 두고 세 경로의 시간을 재 보면 이렇다.

def times(x1, x2, x3):
    """경로별 통행시간 — x1=a-b-z, x2=a-c-z, x3=a-b-c-z 에 실린 시간당 차량 수."""
    ab = 10 * (x1 + x3)   # a→b  : 10φ
    cz = 10 * (x2 + x3)   # c→z  : 10φ
    bz = 50 + x1          # b→z  : 50+φ
    ac = 50 + x2          # a→c  : 50+φ
    bc = 10 + x3          # b→c  : 10+φ (지름길)
    return ab + bz, ac + cz, ab + bc + cz

print("3·3·0 :", times(3, 3, 0))
print("2·2·2 :", times(2, 2, 2))

3·3·0 : (83, 83, 70)
2·2·2 : (92, 92, 92)

첫 줄의 70이 개통 첫날 지름길이 내건 값이고, 둘째 줄의 92가 다들 옮겨 간 뒤의 값이다. 최적은 그동안 제자리에 있다. 6대를 3대씩 나누고 지름길을 아무도 쓰지 않으면 한 대당 83분이고, 그 배치가 총 통행시간을 가장 작게 만든다.

그런데 2대씩 갈린 상태에서는 아무도 혼자서 그리로 돌아갈 수 없다. 세 경로가 전부 92분이라 갈아타 봐야 줄어드는 시간이 없기 때문이다. 그 배치로 돌아가려면 지름길을 쓰던 2대가 한꺼번에, 그것도 서로 다른 두 길로 갈라져 나가야 한다. 각자 알아서 움직이는 사람들에게는 그럴 방법이 없다.

각자 최선을 고른 끝자리가 모두의 최선과 다를 수 있다. 그리고 새로 놓은 길 하나가 그 차이를 만들어 낼 수 있다. 이것을 브라에스 역설(Braess’s paradox)이라고 부른다. 길이 나빠서가 아니라 길이 하나 더 생겨서 모두가 늦어진 것이다.

손해는 아무 때나 나지 않는다 — 교통량의 창

지금까지는 시간당 6대일 때의 이야기다. 오가는 차 대수를 바꾸면 결론도 바뀐다. 지름길이 늘 손해를 내는 것은 아니고, 손해가 나는 교통량 구간이 따로 있다.

그림 2의 한산한 쪽부터 보자. 시간당 2대 자리에서는 지름길이 없는 쪽이 61.0분, 있는 쪽이 52.0분이다. 지름길이 9.0분을 벌어 준다. 좁은 다리 둘을 연달아 지나도 2대로는 다리가 붐비지 않기 때문이다.

반대쪽 끝에서는 지름길이 아무 일도 하지 않는다. 시간당 20대면 지름길이 있으나 없으나 160분으로 같다. 좁은 다리가 이미 너무 붐벼서 지름길 경로를 고르는 사람이 아무도 없다.

손해가 나는 구간은 그 사이다. 시간당 2.58대와 8.89대 사이에서만 지름길이 있는 쪽이 느리다.

창 안에서 흐름이 갈리는 방식도 식 하나로 적힌다. 위·아래로 도는 두 경로를 각각 $x$대가, 지름길 경로를 $y$대가 쓴다고 하자. 차가 늘수록 지름길을 쓰는 몫이 줄고, 8.89대에서 0이 된다.

식 2의 $y$가 그 몫이고, 그 값이 0이 되는 자리에서 창이 닫힌다.

평형까지 어떻게 가는지도 볼 수 있다. 시간당 6대의 흐름을 6,000명으로 잘게 쪼개 매일 출근시키고, 그중 5%가 전날 가장 빨랐던 경로로 갈아탄다고 두자. 30일째에 지름길을 연다.

그림 3의 점선 왼쪽, 개통 전 30일 동안은 두 경로가 절반씩 나눠 갖는다. 지름길이 열리면 며칠 만에 세 경로가 3분의 1씩으로 갈라지고, 통행시간은 앞에서 계산한 92분 근처에서 오르내린다. 진동이 남는 이유는 모두가 같은 "어제 가장 빨랐던 길"을 보고 움직이기 때문이다. 새 길이 손해인지는 그 길만 봐서는 알 수 없다. 손해가 나는 자리를 정하는 것은 길이 아니라 지금 그 위를 흐르는 양이다.

얼마나 손해인가 — 무질서의 대가

손해의 크기는 평형에서 모두가 쓴 시간의 합을, 최적 배치에서 썼을 시간의 합으로 나눠서 잰다. 이 비를 무질서의 대가(price of anarchy)라고 부른다.

식 3가 1이면 각자 고른 결과가 이미 최선이라는 뜻이고, 1.2면 최적보다 20%를 더 쓴다는 뜻이다. 이 망은 시간당 6대에서 1.11이다. 창 안을 훑어 가장 나쁜 자리를 찾아도 약 1.24에서 멈춘다.

이 값에는 천장이 있다. Roughgarden과 Tardos는 2002년 논문에서, 모든 구간의 통행시간이 흐름의 1차식이면 각자 고른 경로들의 총 통행시간이 최적의 4/3배를 넘지 못한다는 것을 증명했다. 그 논문이 첫머리에 든 예에서는 4/3가 딱 맞는다.

그림 4에서 전부 열려 있으면 92분이다. 지름길을 막으면 83분으로 줄어든다. 나머지 넷은 막을 때마다 112.2분이거나 116분으로 오히려 늘어난다. 다섯 중에서 막아 두는 편이 나은 구간은 지름길 하나뿐이다.

Youn 연구팀은 2008년에 같은 계산을 보스턴 간선도로 모형에 걸었다. 방향 있는 구간 246개와 교차로 88개짜리 망이고, 통행시간은 실측이 아니라 지연 함수로 계산한 값이다.

런던과 뉴욕의 간선도로 망에도 같은 계산을 걸었다. 하나를 막으면 평형 통행시간이 줄어드는 구간이 보스턴에 6개, 런던에 7개, 뉴욕에 12개 있었다. 네 지점짜리 망에서도 마찬가지다. 지름길 하나를 지우는 것만으로 이 망의 손해는 통째로 사라진다. 도로망을 손보는 방법에 길을 새로 놓는 것만 있는 것은 아니라는 뜻이다.

청계천은 정말 그 사례였을까

브라에스 역설을 설명하는 글에 거의 빠지지 않고 나오는 사례가 서울 청계천이다. 도심 고가도로를 걷어낸 그 공사다. 길을 없앴더니 오히려 흐름이 좋아졌다는 이야기로 인용된다.

초록이 사실로 적는 변화는 하나다. 고가도로를 걷어내면서 양방향 4차로가 2차로로 줄었다는 것이다. 널리 인용되는 이야기와 1차 자료가 늘 같은 말을 하지는 않는다.

2026년에 올라온 사전 공개 논문 한 편은 Diacamma indicum이라는 개미에서 같은 역설을 실험으로 관찰했다고 보고한다. 길잡이 개미가 군체를 느리게 만드는 상황에서도 가장 짧은 길을 고른다는 것이다. 저자들은 이 결과가 개체의 이기심 없이도 역설이 나타날 수 있음을 보인다고 적는다.

그러니 이 역설을 부르는 재료는 이기심이 아니다. 개체가 자기 기준으로 최선을 고르는 규칙과 전체의 최선이 어긋나기만 하면, 운전자든 개미든 같은 일이 벌어진다.

다시, 그 개통식 아침

처음의 개통식으로 돌아가 보자. 테이프를 끊은 사람도, 새 길로 처음 들어선 운전자도 잘못한 것이 없다. 길은 실제로 짧고 빨랐고, 각자는 빠른 쪽을 골랐다. 그런데도 다 같이 늦어질 수 있다.

늘 그런 것은 아니고, 갈리는 자리는 세 군데다. 지금 그 도로에 몇 대가 흐르는지가 먼저다. 한산하면 새 길이 시간을 벌어 주고, 이미 꽉 차 있으면 아무도 그 길을 쓰지 않는다.

그다음은 새 길이 무엇과 무엇을 잇느냐다. 혼잡에 민감한 구간 둘을 한 줄로 이어 붙이면, 그 둘을 연달아 지나는 경로가 새로 생긴다. 마지막은 우리가 지금 보고 있는 것이 평형인지 최적인지다. 평형은 혼자서는 빠져나올 수 없는 자리여서, 더 나은 배치가 옆에 멀쩡히 있어도 저절로 그리로 가지 않는다.

세 가지 모두 새 길만 들여다봐서는 답이 안 나온다. 길의 폭이나 포장 상태가 아니라, 그 길이 들어갈 망 전체와 지금 그 위를 흐르는 양을 같이 놓고 재야 나온다. 그러니 길을 더 내면 나빠진다는 이야기도 아니다. 같은 지름길이 한산한 시간대에는 시간을 벌어 준다.

나쁜 쪽 평형은 저절로 찾아온다는 점도 덧붙일 만하다. 아무도 전체를 계산하지 않고, 각자 어제 더 빨랐던 길로 조금씩 옮겨 가기만 해도 며칠이면 그 자리에 닿는다. 누가 그리로 몰아간 것이 아니라, 각자 제 이득을 따라간 결과가 그 자리에 쌓인 것이다.

같은 셈은 도로 밖에서도 선다. Youn 연구팀은 전선 하나를 끊었더니 회로가 전기를 더 잘 통하게 된 경우가 물리 쪽에 보고돼 있다며, 이 역설과 나란히 둔다. Roughgarden과 Tardos의 4/3 상한도 도로만을 위해 증명된 것이 아니라, 망을 각자 골라 쓰는 이용자 일반을 대상으로 한 것이다.

그래서 어디선가 새 길이 열린다는 소식을 들으면, 그 길이 얼마나 빠른지보다 그 길이 어디와 어디를 잇는지가 먼저 눈에 들어온다. 브라에스가 1968년에 네 지점짜리 그림으로 보인 것이 그 이야기였다.

더 읽기

• D. Braess, A. Nagurney, T. Wakolbinger, "On a Paradox of Traffic Planning", Transportation Science 39(4), 446–450 (2005) — http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/Paradox-BNW.pdf
• T. Roughgarden, É. Tardos, "How Bad is Selfish Routing?", Journal of the ACM 49(2), 236–259 (2002) — https://theory.stanford.edu/~tim/papers/routing.pdf
• H. Youn, M. T. Gastner, H. Jeong, "Price of Anarchy in Transportation Networks: Efficiency and Optimality Control", Phys. Rev. Lett. 101, 128701 (2008) — https://arxiv.org/abs/0712.1598