게임 이론을 이용한 네트워크 트래픽 모델링

 

균형에서의 트래픽

• 고속도로 네트워크는 각 엣지가 이동 시간을 분 단위로 레이블되어져 있다. x는 도로를 지나는 차량의 수이다. 4000대의 차량이 A에서 B로 이동해야할 때, 균형(equilibrium)에서 2가지 경로로 나뉘고 이동 시간은 65분이다.

• Equilibrium traffic(균형 트래픽) 트래픽 모델은 실제 운전자들을 참여자(player)로 보는 게임이고, 각 참여자의 가능한 전략은 A에서 B로 가능한 경로로 구성된다. 위 예시에서는 각 참여자가 두 가지 전략만을 가진다. 그러나 더 큰 네트워크에서는 각 참여자마다 많은 전략이 있을 수 있다. 참여자에 대한 payoff는 이동 시간의 음수이다. 이동 시간이 길수록 좋지 않기 때문에 음수를 사용한다.
• 다른 트래픽들 dominant strategies, mixed strategies, Nash equilibrium with mixed strategies 의 표기는 모두 2인 게임에 대한 정의와 직접적인 유사성을 가지고 있다. 이 트래픽 게임에서는 일반적으로 dominant strategy는 존재하지 않는다. 위의 예제에서는 모든 다른 참여자들이 다른 경로를 이용한다면 어떤 경로가 참여자의 최선의 선택일 거라는 가능성을 가질 수도 있다. 이 때 그 게임은 내쉬 균형을 가진다. 그러나, 두 경로들 사이에 공평하게 운전자들이 이동 시간을 맞추는(balance) 전략의 몇몇은 내쉬 균형이고, 이들은 오직 Nash equilibria이다.
• 왜 동등한 밸런스가 내쉬 균형을 산출하는가?
  • 우리는 두 경로 사이의 동등한 밸런스를 가지고 어떤 운전자도 다른 경로로 이동하지 않을 것이라는 사실을 관찰한다. (즉, 항상 모든 선택들 중 최선의 선택이 되는 것)
• 왜 모든 내쉬 균형이 동등한 밸런스를 가지는가?
  • 두번째 질문에 대한 답변으로, 운전자 x가 위의 경로를 사용하거나 아래 경로를 사용하는 전략의 목록을 고려해볼 수 있다. 그때 x가 2000이 아니라면, 두 경로는 동등하지 않은 이동시간을 가질 것이고, 이동시간이 긴 경로에 있는 어떤 운전자도 더 짧은 경로로 바꾸려고 할 것이다. 그러므로, x가 200이 아닌 전략들의 목록은 내쉬 균형이 될 수 없고, x는 2000인 어떤 전략의 목록도 내쉬 균형이다.
• Braess’s Paradox

• 이전 고속도로 네트워크 그림에서 C에서 D로 가는 경로로 매우 빠른 엣지가 추가되었다. 비록 고속도로 시스템이 업그레이드되어졌지만, 모든 차량들이 C와 D를 통과하는 경로를 사용하기 때문에  균형에서의 이동 시간은 80분이다. 즉, 경로 C-D를 이용하는 것이 모든 운전자에게 dominant strategy가 된다.
• 위의 그림에서는 유일한 내쉬 균형이 존재한다. 그러나 모두에게 좋지 않은 이동 시간을 준다. 균형에서, 모든 운전자는 C와 D를 통과하는 경로를 이용한다. 그리고 그 결과, 모든 운전자의 이동 시간은 80분(4000/100 + 0 + 4000/100 = 80)이다. 이 경로가 균형인 이유는, 이동 시간에 있어 해당 경로보다 더 빠른 경로가 없기 때문이다. (얻는 benefit이 없음) 지금과 같이 C와 D를 스치고 지나가는 차량들로 인해 다른 경로들은 85분이 걸린다. 유일한 균형인 이유는 C에서 D로 가는 엣지의 생성(C와 D를 통과하는 경로)이 실제로 모든 운전자들에게 dominant strategy를 만들어주었기 때문이다. 현재 트래픽 패턴과 무관하게 C와 D를 거치는 경로로 바꾸면 benefit을 얻는다.
• 이러한 현상(는 교통 네트워크에 자원을 추가하고 가끔 평형에서 성능을 해칠 수 있음)은 먼저 디트리히 Braess에 의해 언급되었다. 많은 변칙들이 있는 실생활에서 실제로 나타나기 위해서는 올바른 조건의 조합이 필요하다. 그러나 실제 교통망(공공원을 건설하기 위한 6차선 고속도로의 파괴가 실제로 도시 안팎으로 이동시간을 향상시킨 한국, 서울 등)에서 경험적으로 관찰되어 왔다. 트래픽 크기는 변경 전후에 거의 동일하게 유지됨 → 실제로 6차선 고속도로 대신 공원을 지어서 차량의 이동 시간이 개선된 예

• 총 이동 시간 = 개별 차량 이동시간 * 차량의 수로 계산된다.
  • 위 그림 (b)는 8*4 = 32이다. 개별 차량 이동 시간은 내쉬 균형에서는 동일하다.
  • 따라서 x + 0 + x  = 8 이 성립하므로 x=4가 되어 차량의 수 4대와 동일하다.
• 균형에서의 트래픽 패턴 찾기
  • best-response dynamics 명확히 하나를 찾는 다음의 절차를 분석함으로써 균형은 존재한다는 사실을 증명할 수 있다. 절차는 어떤 트래픽 패턴으로부터 시작한다. 만약 균형이 있다면, 끝난 것이다. 마찬가지로 다른 이들이 행동하는 것이 엄격히 낮은 이동 시간을 제공하는 몇몇 대체 경로일 때, 적어도 한 명의 최선의 선택을 하는 운전자가 있다. 이러한 운전자를 선택하고 그 운전자가 이러한 대체 경로를 바꾸도록 한다. 지금 새로운 트래픽 패턴을 가지고 다시 균형인지 체크한다. 만약 아니라면, 그 때는 몇몇 운전자가 최선의 선택을 하도록 하고 계속해서 트래픽 패턴을 체크한다.
  • 이처럼 몇몇 운전자가 현재 상황에 맞는 최선의 선택을 일정하게 수행하도록 함으로써, 참여자의 전략을 동적으로 재수정한다. 만약 그 절차가 멈춘다면, 실제로 모두가 현재 상황에 대한 최선의 선택을 수행하고 있는 상태이므로 그 때 균형을 갖는다고 본다. 따라서 핵심은 어떠한 트래픽 게임의 인스턴스에서 best-response dynamics는 결국 균형에 이를 것이라는 것을 보인다는 점이다.
  • 대신, 초기에 약간 알기 어렵게 보인 대체적인 양을 정의할 것이다. 그러나 best-response dynamics의 단계를 추적하기 위해 이용될 수 있도록, 각각의 최선의 선택을 갱신하는 것과 함께 엄격하게 감소하는 특성을 가진다는 것을 보일 것이다. 이러한 양을 트래픽 패턴의 퍼텐셜 에너지라고 언급한다. 이는 다음과 같이 엣지별로 정의된다. 엣지 e는 현재 그 엣지를 지나는 운전자 x를 가지며, 그 때 엣지의 퍼텐셜 에너지를 다음과 같이 정의한다.

Te(1)은 그 엣지를 지나는 차량이 1대일 때의 이동 비용

Te(2)는 그 엣지를 지나는 차량이 2대일 때의 이동 비용

: 해당 간선의 시간 비용 또는 에너지는 해당 간선을 지나는 차량이 1~n대일 때의 이동비용의 합

• 엣지가 운전자가 한 명도 없다면, 퍼텐셜 에너지는 0이 될 것이다. 트래픽 패턴의 퍼텐셜 에너지는 그 때 단순히 모든 엣지들의 퍼텐셜 에너지의 합이다.
• 다음 그림에서 best-response dynamics가 사회적 최적에서 유일한 균형으로 움직이는 것처럼 5가지 트래픽 패턴에 대한 각 엣지의 퍼텐셜 에너지를 보인다.

• 운전자 x를 갖는 엣지의 퍼텐셜 에너지가 운전자가 그 엣지를 지나는 것의 전체 이동 시간이 아님에 주의해야 한다. T(x)의 이동 시간을 각각 가지는 운전자 x가 있기 때문에 전체 이동 시간은 x*T(x)이다. 여기서 T(x)는 운전자마다 다르다. 대신에 퍼텐셜 에너지는 운전자가 엣지를 하나씩 건널 것이라 상상하는 일종의 누적되는 양이다. 각 운전자는 오로지 스스로 지연을 느끼고 그 앞의 엣지를 건넌다.