GTO2-3-04: Limitations of VCG
VCG 메커니즘의 한계
지금까지 VCG 메커니즘의 장점에 대해 많이 다루었으며, 그럴 만한 이유가 있다.
그러나 VCG는 몇 가지 중요한 제약 사항을 가지고 있으며, 이 영상에서는 그 한계들을 소개할 것이다.
1. 프라이버시 문제 (Privacy)
VCG requires agents to fully reveal their private information
This private information may have value to agents that extends beyond the current interaction
– for example, the agents may know that they will compete with each other again in the future
It is often preferable to elicit only as much information from agents as is required to determine the social welfare maximizing choice and compute the VCG payments.
VCG는 에이전트가 자신의 개인 정보를 모두 메커니즘에 공개해야 하는 구조이다.
이 설정은 메커니즘이 결정한 선택과 지불만이 에이전트의 효용에 영향을 미친다는 모델을 전적으로 신뢰할 경우에는 문제가 없다.
하지만 현실에서는 에이전트들이 반복적으로 상호작용할 수 있으며, 그 과정에서 개인 정보를 공개하면 향후 경쟁에서 불리해질 가능성이 존재한다.
따라서 이러한 환경에서는, 최소한의 정보만 공개하고도 사회적 후생 극대화와 VCG 지불을 계산할 수 있는 메커니즘이 선호될 수 있다.
VCG는 이러한 최소 정보 공개 요건을 초과하는 정보를 요구하므로, 이런 경우 VCG는 적합하지 않다.
2. 담합에 취약함 (Susceptibility to Collusion)
VCG는 담합(collusion)에도 취약하다.
예를 들어 도로 건설 게임에서, 세 명의 에이전트가 있다고 하자.
– 도로를 건설하면 총 효용은 300이다.
– 건설하지 않으면 총 효용은 250이다.
따라서 도로는 건설된다.
이때 Agent 1은 VCG 지불 규칙에 따라 100을 받지만, 결국 250을 지불하게 되어 순지불 150을 하게 된다.
VCG는 개별적으로는 진실을 말하는 것이 지배 전략이라는 특성을 보장한다.
Agent 1이 존재하지 않으면, 도로가 만들어지지 않고 효용은 $250
Agent 1이 있으면 도로가 지어지고, 다른 에이전트(2, 3)의 효용 합은 $100
→ \(p_1\) = 250 – 100 = 150
즉, Agent 1은 $150을 지불함.
하지만 만약 Agent 1과 Agent 2가 서로 협의하여 자신들의 가치를 각각 $50씩 높여 보고한다면, 이들은 각자의 지불액을 $50씩 줄일 수 있다.
즉, 서로의 보고가 상대방의 지불을 줄이는 효과를 일으킨다.
Agent 1의 선언된 value가 커지면,
Agent 1은 “더 중요한 존재”가 돼서 시스템에서 빠졌을 때 더 큰 손해가 발생하는 것처럼 보임
그러면 실제로는 이렇게 됨:
- Agent 2의 지불액 계산시, Agent 1이 매우 중요한 사람이 됐기 때문에 Agent 2가 빠졌을 때 시스템이 유지될 수 있음.
- 이로 인해 Agent 2가 less pivotal(덜 중심적 역할을 한 사람)처럼 보이게 됨.
- 따라서 Agent 2의 지불액이 줄어듬.
그리고 마찬가지로:
Agent 2가 자신의 값을 올렸기 때문에 Agent 1도 덜 중요한 사람처럼 보이고, Agent 1의 지불액도 줄어듬.
What happens if agents 1 and 2 both increase their declared valuations by $50?
The choice is unchanged, but both of their payments are reduced.
Thus, while no agent can gain by changing his declaration, group can.
이러한 현상은 VCG가 개별 전략적 진실성은 유지하더라도, 집단적 담합에는 취약하다는 점을 보여준다.
→ VCG는 “얼마나 pivotal(중요한 역할을 했는가)“에 따라 지불액이 결정됨.
3. 검약성 부족 (VCG is not Frugal)
VCG는 때때로 과도한 지불을 발생시켜 비검약적(frugal하지 않다)이다.
예를 들어 이전의 라우팅 문제를 다시 보자.
VCG can end up paying arbitrarily more than an agent is willing to accept (or equivalently charging arbitrarily less than an agent is willing to pay)
Consider the effect of AC’s cost on the payment to AB.
- If the cost of this edge increased to 8, our payment to AB would increase to \(p_{AB} = (-12) – (-2) = -10\).
- If the cost were any \(x \geq 2\), we would select the path ABEF and would have to make a payment to AB of \(p_{AB} = (-4-x) – (-2) = -(x+2)\).
- The gap between agents’ true costs and the payments that they could receive under VCG is unbounded.
최단 경로의 비용이 5이고, 두 번째 최단 경로의 비용이 6이라고 하자.
이때 어떤 링크(예: AB)의 소유자에게 지불되는 금액은 자신의 보고와 무관하게, 두 번째 최단 경로의 비용에 따라 결정된다.
예를 들어, AC의 비용이 2에서 8로 증가하면, 두 번째 최단 경로는 12가 되며, 그에 따라 AB가 받는 금액도 6만큼 증가하게 된다.
즉, 다른 사람의 비용 변화가 본인의 수익에 영향을 미치는 구조이다.
이는 지불액과 실제 비용 간의 차이가 무한정 커질 수 있다는 뜻이다.
또한, 두 번째 최단 경로와의 차이를 기반으로 지불액을 추정하려 해도, 지불액은 여전히 해당 경로보다 훨씬 클 수 있음이 수학적으로 입증된다.
결과적으로, VCG는 비용 대비 과도한 보상을 유발할 수 있는 구조이다.
Are VCG’s payment at least close to the cost of the second shortest disjoint path?
The top path has a total cost of c.
VCG picks it, pays each of the k agents \(c(1+\epsilon) – (k-1)\frac{c}{k}\).
Hence VCG’s total payment is \(c(1+k \epsilon)\).
For fixed \(\epsilon\), VCG’s payment is \(\Theta(k)\) times (i.e., only a constant away from k times) the cost of the second shortest disjoint path.
에이전트 i의 제거가 사회적 비용에 끼치는 영향은?
에이전트 i가 없으면, 위쪽 경로 사용 불가능하므로, 전체 경로는 아래쪽 경로 \((s \to t)\)로 바뀜
아래쪽 경로의 비용은: \(c(1 + \varepsilon)\)
에이전트 i를 제외한 위쪽 경로의 나머지 k-1 에이전트의 비용은:
\((k-1)\cdot \frac{c}{k} = \frac{(k-1)c}{k}\)
따라서 VCG가 에이전트 i에게 지불하는 금액은:
\(p_i = c\left(1 + \varepsilon – \frac{k-1}{k}\right) = c\left(1 + \varepsilon – 1 + \frac{1}{k}\right) = c\left(\varepsilon + \frac{1}{k}\right)\)
각 에이전트마다 동일한 금액을 받으므로, 총 지급액은:
\(\text{Total payment} = k \cdot p_i = k \cdot c\left(\varepsilon + \frac{1}{k}\right) = c(k\varepsilon + 1) = c(1 + k\varepsilon)\)
두 번째 최단 경로(아래쪽 경로)의 비용은 \(c(1+\epsilon)\)
VCG 총 지불액은 \(c(1+k \epsilon)\)
따라서, \(\frac{\text{VCG total payment}}{\text{2nd shortest path cost}} = \frac{c(1 + k\varepsilon)}{c(1 + \varepsilon)} \approx \Theta(k)\)
→ \(\epsilon\)이 작을수록 VCG의 비용은 두 번째 최단 경로 비용의 약 k배까지 늘어날 수 있음
4. 수익 단조성 위배 (Revenue Monotonicity Violated)
Revenue monotonicity: revenue always weakly increases as agents are added.
직관적으로는, 메커니즘에 더 많은 참가자를 추가하면 총 수익이 증가해야 한다고 생각하기 쉽다. 하지만 VCG는 그렇지 않다.
예를 들어 도로 건설 예시에서,
– 건설 시 총 효용은 100
– 비건설 시 총 효용은 90
이므로 도로가 건설된다.
이때 Agent 2는 Agent 1이 없을 경우 90의 효용을 받으므로, Agent 2는 90을 지불하게 된다.
하지만 Agent 3를 추가로 투입하여, 그가 Agent 2와 동일한 효용을 가진다고 하면, 두 에이전트 중 누구를 제외하더라도 도로는 여전히 건설된다.
즉, 둘 다 피벗 에이전트가 아니므로, 지불하지 않는다. 결과적으로 총 수익은 90에서 0으로 감소한다.
게다가 에이전트가 자신을 둘로 나누어 보고하면, 마찬가지로 자신의 지불을 없앨 수 있다.
하지만 Agent 3가 추가될 경우 아무것도 지불할 필요가 없다.
Adding agent 3 causes VCG to make the same choice but to collect zero revenue!
Agent 2 could pretend to be two agents and eliminate his payment.
5. 수익 환급 불가능 (Cannot Return All Revenue to Agents)
- We may want to use VCG to induce agents to report their valuations honestly, but may not want to make a profit by collecting money from the agents.
- Thus, we might want to find some way of returning the mechanism’s profits back the agents.
- However, the possibility of receiving a rebate after the mechanism has been run changes the agents’ incentives.
- In fact, even if profits are given to a charity that the agents care about, or spent in a way that benefits the local economy and hence benefits the agents, the VCG mechanism is undermined.
- It is possible to return at least some of the revenues to the agents, but it must be done very carefully, and in general not all the money can be returned
어떤 경우에는 메커니즘이 실제로 돈을 걷는 것보다 사회적 선택을 하기 위한 도구로 사용되기를 원할 수도 있다.
이럴 경우, 걷은 돈을 에이전트에게 되돌려주고 싶을 수 있다.
하지만 이 과정이 잘못 설계되면, 에이전트들이 환급을 고려한 전략적 행동을 하게 되고, VCG의 인센티브 정렬 구조가 붕괴하게 된다.
예를 들어,
– 수익을 자선단체에 기부한다면, 에이전트가 자선단체에 대한 관심에 따라 전략을 바꿀 수 있다.
– 수익을 지역 사회에 환원하더라도, 결과적으로 유틸리티가 변하게 된다.
결국, 이러한 문제를 피하려면 돈을 ‘태우는(burn)’ 방식, 즉 아예 사용하지 않고 소각해야 한다.
일부 문헌에서는 일부 금액을 되돌리는 방법이 연구되어 있으나, 전액을 환급하는 것은 불가능하다.
요약
VCG 메커니즘은 진실 보고를 유도하고, 효율적인 결과를 만들어낸다는 탁월한 장점이 있지만, 다음과 같은 중요한 단점들도 함께 고려되어야 한다:
- 프라이버시 침해 가능성
- 담합에 대한 취약성
- 과도한 지불로 인한 비검약성
- 수익 단조성 위배
- 수익의 전면 환급 불가능성
이러한 문제점들은 VCG에만 국한된 것이 아니라, 다른 메커니즘에서도 공통적으로 발생할 수 있는 제약임을 함께 인식해야 한다.
따라서 메커니즘을 설계하거나 선택할 때, 이러한 요소들을 종합적으로 고려해야 한다.
References
Game Theory Online, (4/6), GTO2-3-04: Limitations of VCG, Dec 3, 2013, https://www.youtube.com/watch?v=YkyIftAKt3k