나에게 더 유리한 길로 옮겼는데, 왜 전체 비용은 늘어날까요?

내 이동 시간이 짧아졌다면 모두의 시간 합도 줄었을까요? 세 이용자가 두 길 A, B 중 하나를 고르는 자체 모형을 볼까요? A는 몇 명이 쓰든 비용 4, B는 그 길의 현재 인원 k가 각 이용자의 비용이에요. 실제 도로의 통행 시간을 측정한 수치가 아니에요.

A의 한 사람이 B로 옮기면 자신의 비용은 4에서 3으로 줄지만, 원래 B에 있던 두 사람의 비용은 2에서 3으로 늘어나요. 전체 합은 8에서 9가 돼요. 마지막 상태에서는 B의 누구도 비용 4인 A로 옮겨 이득을 볼 수 없어요. 개인이 더 나은 길로 옮기는 과정이 전체 비용을 계속 줄인다는 판단은 틀렸어요.

그렇다면 개인의 개선을 반복하면 끝없이 돌 수도 있을까요? 종료를 살펴볼 다른 합을 만들어요. 시설 e에 m명이 있을 때 실제 비용 합은 m c_e(m)입니다. 새 계산량은 첫 이용자부터 차례로 들어오는 비용들을 더해요.

사용자가 없으면 그 시설의 안쪽 합은 0입니다. 위 예에서는 Φ가 4+(1+2)=7에서 1+2+3=6으로 줄었어요. 이 값은 물리적 에너지나 실제 지불액이 아니라 변경을 추적하기 위한 수학적 계산량이에요.

일반 조건을 정확히 정할게요. 이용자 수와 시설 수는 유한해요. 각 이용자는 정해진 유한 목록에서 시설들의 집합 하나를 고르고, 그 집합의 비용을 더해 자신의 비용으로 세어요. 각 시설의 c_e(k)는 고정된 인원별 비음수 실수값이며 모든 이용자에게 같아요. 다른 사람의 선택은 그대로 두고 한 명만 바꿔요. 실제 도로 그림이나 비용의 일차식까지 필요하지 않아요.

이전 선택에서만 썼던 시설에서는 인원이 m_e에서 m_e−1로 줄어 잠재합에서 c_e(m_e)가 빠져요. 새 선택에서만 쓰는 시설에는 인원이 m_e+1이 되어 c_e(m_e+1)가 더해져요. 두 선택에 공통인 시설은 인원이 변하지 않아요. 따라서 정확히

오른쪽은 바꾸는 한 사람의 새 비용과 이전 비용의 차예요. 실제로 더 싼 선택으로만 바꾸면 Φ가 엄격히 감소해요. 전체 선택의 가능한 조합은 유한하므로 이전 조합을 다시 방문할 수 없어요. 이용자별 목록의 크기가 r₁,…,r_N이면 조합은 최대 r₁⋯r_N개여서 실제 변경 횟수는 그 값에서 1을 뺀 수를 넘지 않아요.

더 싼 변경이 있으면 계속한다는 규칙으로 멈췄을 때, 누구도 혼자 바꿔 비용을 줄일 수 없어요. 이것이 여기서 말하는 균형이에요. 멈춘다는 결론은 전체 비용이 최소라는 결론과 달라요. 예의 모두 B인 균형은 비용 9지만 A에 한 명을 남긴 배치는 8입니다.

‘엄격히’도 빼면 안 돼요. 한 이용자에게 비용이 항상 1인 두 길을 주고 동률 변경을 허용하면, 두 길을 계속 오갈 수 있어요. 잠재합은 1로 그대로예요. 두 사람이 동시에 바꾸거나 시설 비용이 사람마다 다른 경우도 방금 증명의 가정이 아니에요.

Easley와 Kleinberg는 전체 통행비용과 잠재합을 구별해요. 여기서는 원문의 네 노드 도판을 옮기지 않고 자체 두 길의 표와 유한 시설 선택의 증명을 구성했어요. 교사는 ‘개선’ 옆에 누구의 비용인지 쓰게 하고, 종료·균형·전체 최적을 각각 다른 결론으로 확인해요.

출처·착안: Easley·Kleinberg, Modeling Network Traffic using Game Theory, section8.3. 자체 조건·수치·문항·증명이며 실제 교통 성능 보고가 아니다.