GTO2-3-03: VCG Example
VCG 메커니즘 작동 예시
– Selfish routing example
이제 VCG, 즉 Vickrey-Clarke-Groves 메커니즘이 실제로 어떻게 작동하는지를 하나의 예제를 통해 살펴보자.
 |  |
이 예시는 라우팅, 즉 경로 선택 문제이다.
화면에는 방향성이 있는 네트워크가 있으며, 각 링크에는 이동 비용(혹은 길이)이 주어져 있다.
우리의 목표는 정점 A에서 정점 F까지 가는 최단 경로를 찾는 것이다.
겉으로 보기에 명백하게, 최단 경로는 바로 ABEF 이 경로이다.
따라서 A에서 F까지 가장 빠르게 가고자 하는 여행자가 선택할 경로도 이 경로가 된다.
How much will AC have to pay?
- The shortest path taking AC’s declaration into account has length 5, and imposes cost -5 on agents other than AC. The shortest path without AC’s declaration also has length 5. Thus,
\(p_{AC} = (-5) – (-5) = 0\). - This is what we expect, since AC is not pivotal.
- Likewise, BD, CE, CF and DF will all pay zero.
링크 소유자의 지불 – 예: AF 링크
VCG 메커니즘에 따르면, AF 링크의 소유자는 얼마를 지불해야 할까?
직관적으로 보면, 이 링크는 최단 경로에 포함되어 있지 않기 때문에, 지불도, 보상도 받을 이유가 없어야 한다.
VCG 메커니즘의 계산에 따라 확인해보자.
- 최단 경로는 링크 AC의 비용 선언에 따라 총 비용이 5이다.
- 만약 AC가 존재하지 않았더라도, 여전히 최단 경로는 동일하며 비용도 5이다.
즉, AC의 참여 여부가 결과에 아무런 영향을 주지 않았으므로, AC의 지불액은 0이다.
이 논리는 최단 경로에 포함되지 않은 다른 모든 링크들에도 똑같이 적용된다.
화면에서 파란색으로 표시된 모든 링크들은 지불도 보상도 발생하지 않는다.
최단 경로에 포함된 링크의 지불 계산
이제 최단 경로에 실제로 참여한 링크에 대해 살펴보자.
먼저 링크 AB를 예로 들어 보자.
현재 최단 경로의 총 비용은 1 + 1 = 2이다 (BE + EF).
만약 AB가 없었다면, 최단 경로는 다음과 같이 변경된다:
A → C → D → F
비용은 2 + 3 + 1 = 6이다.
How much will AB pay?
- The shortest path taking AB’s declaration into account has length 5, and imposes cost 2 on other agents.
- The shortest path without AB is ACEF, which has cost 6.
- Thus \(p_{AB} = (-6) – (-2) = -4\).
따라서 AB 링크의 소유자는 사회 전체에 4만큼의 비용 절감을 제공한 셈이다.
즉, 그는 4의 보상을 받게 된다.
그의 실제 비용이 3이라면, 1의 순이익(profit)을 얻게 된다.
→ 여기에서 “AB 스스로의 비용”은 계산에서 제외된다.
왜냐하면 VCG에서는 각 에이전트가 자신이 사회에 얼마나 피해를 주는지를 기준으로 비용을 지불하게 만들기 때문이다. 따라서 자신의 비용은 지불할 필요가 없고, 자신의 존재 유무에 따라 다른 사람들의 유틸리티(혹은 비용)이 얼마나 달라지는지를 보는 것이다.
링크 BE의 경우
How much will BE pay? \(p_{BE} = (-6) – (-4) = -2\).
BE가 없었다면 최단 경로는 여전히 6이었을 것이다. (ACEF)
BE가 포함된 현재의 최단 경로는 3(AB) + 1(EF) = 4이다. 따라서 BE가 사회에 기여한 가치는 6 – 4 = 2이다.
즉, BE 링크의 소유자는 2의 보상을 받고, 비용이 1이었다면 1의 순이익을 얻는다.
링크 EF의 경우
How much will EF pay? \(p_{EF} = (-7) – (-4) = -3\)
EF는 조금 다른 결과가 나온다.
- EF가 없었다면 가능한 최단 경로는 7이었을 것이다. (ABDF)
- EF가 있을 경우, 최단 경로는 3(AB) + 1(BE) = 4이다.
차이는 7 – 4 = 3이며, 따라서 EF는 3의 보상을 받는다. 그의 비용이 1이라면, 순이익은 2이다.
요약 및 해석
VCG 메커니즘 하에서, 각 링크의 보상 또는 지불 금액이 서로 다른 이유는
그 링크가 없었을 경우 사회 전체가 얼마나 손해를 보는가, 즉 사회적 영향력 때문이다.
이는 일종의 시장 지배력(Market Power) 개념이다.
어떤 링크는 대체 가능하므로 영향력이 낮고,
어떤 링크는 대체 불가능하므로 사회에 큰 가치를 제공하며 더 많은 보상을 받는다.
따라서 보상이 달라지는 것은 공정성 문제가 아니라 사회적 기여도에 기반한 차등 보상 구조이다.
이것이 바로 VCG 메커니즘이 실제로 작동하는 방식이다.
References
Game Theory Online, (3/6) GTO2-3-03: VCG Example, Dec 3, 2013, https://www.youtube.com/watch?v=luh_xkxKdrY