GTO2-3-02: Vickrey-Clarke-Groves Mechanisms: Definitions
Vickrey-Clarke-Groves(VGC) 메커니즘에 대해 이야기할 것이다.
이 메커니즘은 게임 이론에서 가장 많이 연구된 메커니즘 중 하나이다. 먼저 이 메커니즘이 제공하는 긍정적인 결과들에 대해 간략히 살펴보자.
A positive result – 기본 설정: 준선형 환경
Recall that in the quasilinear utility setting, a direct mechanism consists of a choice rule and a payment rule.
우리는 준선형(quasi-linear) 환경에서 작업할 것이다.
이는 직접 메커니즘(direct mechanism)에서, 사회가 선택 규칙(choice rule)과 지불 규칙(payment rule)을 개인들이 보고하는 선호(preferences)에 따라 결정하는 구조를 의미한다.
VCG 메커니즘의 가장 큰 장점은 다음과 같다:
- 진실을 말하는 것이 지배 전략(dominant strategy)이다.
(has truth as a dominant strategy (satisfies truthfulness, is strategy-proof))
즉, 다른 사람들이 무엇을 하든 상관없이, 개인은 자신의 효용을 최대화하기 위해 항상 진실을 말하는 것이 최선이다. - 선택된 결과는 효율적(efficient)이다.
(makes efficient choices (not including payments))
사회 전체의 효용의 총합을 최대화하는 결과를 선택한다는 뜻이다.
다만, 지불 총합이 항상 균형(balance)을 이루는 것은 아닐 수 있다.
And, under additional assumptions about the setting, can satisfy:
- weak budget balance
- interim individual rationality
역사적 배경
Vickrey는 경매 상황에서 처음으로 이 메커니즘을 정의하였으며, 이는 2등 가격 경매(second-price auction)의 일반화라고 볼 수 있다.
Clarke는 이를 일반 환경으로 확장하고, 피벗 메커니즘(pivotal mechanism)이라는 특수한 형태를 정의하였다.
Groves는 이들의 일반적인 형태를 포괄하는 이론적 틀을 정립하였다.
Groves 메커니즘
Definition (Groves mechanisms)
Direct mechanisms, \((\chi, p)\), such that
\(\chi(\hat{v}) \in \arg \max_x \sum_i \hat{v}_i(x)\)
\(p_i(\hat{v}) = h_i(\hat{v}_{-i}) – \sum_{j \neq i} \hat{v}_j (\chi(\hat{v}))\)
Some people refer to these as VCG mechanisms, although that name has more recently started to be used to refer to a specific mechanism within this class.
Groves 메커니즘이라는 일반적인 메커니즘 클래스를 보면, Groves 메커니즘이란 다음과 같은 구조를 가진 메커니즘을 말한다:
- 각 개인은 자신의 효용 함수(valuation function)를 메커니즘에 보고한다.
예: \(\hat{v}_1, \hat{v}_2, \dots, \hat{v}_n\) - 사회는 보고된 효용 함수들의 합을 최대화하는 선택지를 선택한다.
- 지불 규칙은 다음과 같은 방식으로 구성된다:
개인 i의 지불은 다음과 같다: \(p_i(\hat{v})\)
여기서 \(h_i\)는 개인 i를 제외한 나머지 사람들의 효용 함수에 기반한 어떤 함수이며, x는 선택된 결과이다.
이러한 구조를 가지는 메커니즘을 Groves 메커니즘이라 한다.
VCG 메커니즘 (The Vickrey-Clarke-Groves Mechanism)
Definition (A Vickrey-Clarke-Groves (VCG) mechanism, a.k.a. a Pivotal mechanism)
A Vickrey-Clarke-Groves mechanism or a pivotal mechanism is a Groves mechanism \((\chi, p)\), such that
\(\chi(\hat{v}) \in \arg \max_x \sum_i \hat{v}_i(x)\)
\(p_i(\hat{v}) = max_x \sum_{j \neq i} \hat{v}_j (x) – \sum_{j \neq i} \hat{v}_j (\chi(\hat{v}))\)
You get paid everyone’s utility the allocation that is actually chosen
– except your own, but you get that directly as utility
Then you get charged everyone’s utility in the world where you don’t participate
Thus you pay your social cost
VCG 메커니즘은 Groves 메커니즘의 특수한 형태이다.
여기서 함수 \(h_i\)는 다음과 같이 정의된다:
- 개인 i가 존재하지 않았을 때 사회가 얻는 총 효용
- 개인 i가 존재할 때 사회가 얻는 총 효용
지불은 이 둘의 차이로 결정된다.
즉, 개인이 사회에 끼친 영향(사회적 비용)을 지불하게 된다.
만약 개인 i의 존재가 다른 사람들에게 해가 된다면, 그는 더 많은 금액을 지불해야 한다.
반대로, 다른 사람들의 효용을 증가시켰다면 보상을 받을 수도 있다.
VCG discussion
Quertions:
- who pays 0?
agents who don’t affect the outcome - who pays more than 0?
(pivotal) agents who make things worse for others by existing - who gets paid?
(pivotal) agents who make things better for others by existing
진실은 지배 전략이다 (Truth is a Dominant Strategy)
– VCG and Groves Mechanisms: Truthrfulness
Theorem
Truth telling is a dominant strategy under any Groves mechanism including the pivotal mechanism (a VCG mechanism).
에이전트 i가 선택한 전략에 따라 얻는 효용 \(v_i\)에서 지불해야 할 금액 \(p\)를 뺀 것을 최대화하는 문제이다.
Groves 메커니즘의 핵심 이론은 다음과 같다:
개인의 지불은 자신이 아닌 다른 사람들의 보고에만 의존하므로, 자신의 효용을 진실하게 보고하는 것이 항상 최선이다.
Groves 메커니즘은 사회 전체의 효용의 합을 극대화하므로, 자신의 진짜 효용을 보고하는 것이 바로 그 결과를 유도하는 유일한 방법이다.
따라서, VCG 메커니즘은 진실 보고를 지배 전략으로 만드는 유일한 효율적인 메커니즘이다.
대우 정리 (The Converse Theorem)
– Groves Uniqueness
Green & Laffont (1970년대 후반)의 정리는 다음과 같다:
Theorem (Green-Laffont)
Suppose that for all agents any \(v_i: X \mapsto \mathbb{R}\) is a feasible preference.
Then an “efficient” mechanism \((\chi, p)\) (such that \(\chi(\hat{v}) \in \arg \max _x \sum_i \hat{v}_i(x)\)) has truthful reporting as a dominant strategy for all agents and preferences only if it is Groves mechanism: \(p_i(v) = h(v_{-i}) – \sum_{j \neq i} v_j (\chi(v))\)
개인들이 임의의 효용 함수를 가질 수 있는 환경에서, 메커니즘이 효율적인 결과를 선택하고, 진실 보고가 지배 전략이 되기를 원한다면, Groves 메커니즘만이 유일한 해답이다.
즉, 진실 유도성과 효율성을 동시에 만족하려면, 메커니즘은 반드시 Groves 형식이어야 한다.
요약 (Summary)
- Groves 메커니즘은 효율적인 선택을 하면서 진실 보고를 유도할 수 있는 구조이다.
- VCG 메커니즘은 그 중에서도 개인이 사회에 미치는 영향을 기반으로 지불을 계산하는 특수한 형태이다.
개인의 인센티브와 사회의 인센티브가 정렬되며, 외부효과를 내부화하여 효율적인 결과를 도출한다.
다만, 다음과 같은 주의점도 존재한다:
- 총 지불이 양수일 수 있으므로, 그 잉여금을 어떻게 처리할지 고민이 필요하다.
- 이를 다시 배분하려 하면 인센티브 구조가 깨질 수 있다.
이러한 이유로 VCG 메커니즘은 다양한 환경에서 벤치마크로 사용되며, 일부 조건에서는 한계가 있지만 매우 강력한 메커니즘으로 널리 연구되고 있다.
References
Game Theory Online, (2/6) GTO2-3-02: Vickrey-Clarke-Groves Mechanisms: Definitions, Dec 3, 2013, https://www.youtube.com/watch?v=kEjvysDPyUQ