비크리-클라크-그로브스 메커니즘 (Vickrey-Clarke-Groves Mechanism)

Photo by Ibrahim Rifath on Unsplash

여러분이 한 사회의 정책 결정권자라고 해 봅시다. 여러분이 정책 후보들을 사회 구성원들에게 소개하면, 각 구성원은 이를 듣고 어느 후보를 선호할지 마음 속으로 결정합니다. 그러고는 여러분에게 알려 주죠. 여러분은 구성원들에게서 전달 받은 선호표를 통해 가장 '합리적'인 정책을 결정해야 합니다.

 

문제는 구성원들은 너무도 '이기적'이어서 여러분에게 거짓말을 할 수도 있다는 것입니다. 예컨대 이런 상황을 가정해 봅시다. 어떤 구성원이 정책 A는 무지막지하게 싫어하고 반대로 정책 B는 엄청 좋아합니다. 그런데 아무리 생각해도 정직하게 알려 줘서는 정책 A가 선택될 것 같다고 느낍니다. 따라서 차라리 차선으로 좋아하는 정책 C를 제일 좋아한다고 거짓으로 알려 줍니다. 만일 구성원 몇몇이 위와 같이 느끼고 행동했다면, 여러분은 잘못된 정보를 토대로 사회 구성원들의 합의를 이끌어 내게 됩니다. 이는 사회 구성원들이 '실제로' 생각하는 것을 반영하지 못하므로 비합리적이고 비효율적이라고 말할 수 있겠습니다.

 

따라서 결정권자인 여러분은 구성원들에게 정직하게 자신의 속마음을 알려주도록 '유인'해야 합니다. 그런 방법이 가능할까요? 안타깝게도 각 구성원들이 정직하게 행동하도록 유인하면서 민주적으로 합리적인 조건을 만족하는 합의 방법은 존재하지 않는다는 것이 잘 알려져 있습니다.

정리 1. 기바드-사데르스웨이트 정리(Gibbard-Satterthwaite theorem)

---

정책 후보가 세 개 이상일 때, 어떤 사회 선택 함수가 모든 구성원들로 하여금 정직하게 행동하도록 유인하는 성질을 만족한다면, 그 함수에는 반드시 독재자가 존재한다.

아직 위 정리에 대해서 포스트를 하지 않았지만, 이와 매우 관련된 애로우의 불가능성 정리에 대해서는 포스트를 한 적이 있습니다. 궁금하신 분은 아래 포스트를 참고하시기 바랍니다.

2022.01.13 - [알고리즘 & 게임 이론/Mechanism design] - 애로우의 불가능성 정리 (Arrow's Impossibility Theorem)

애로우의 불가능성 정리 (Arrow's Impossibility Theorem)

 

이번에는 구성원들에게서 각 정책 후보로부터 자신이 얻을 이득을 '원 단위'로 환산한 것을 대신 제출하도록 해 봅시다. 이 정보를 토대로 여러분은 정책을 하나 결정하게 되고, 이 정책으로 이득을 얻은 구성원들에게서 일정 금액의 '세금'을 걷도록 합시다. 과연 이 상황에서도  상기한 정리와 유사하게 모든 구성원들이 정직하게 행동하도록 유인하면서 가장 합리적인 합의를 이끌어 내는 것이 불가능할까요? 놀랍게도 세금을 적절하게 걷는 것으로 구성원들이 거짓말할 유인을 만들지 않으면서 '경제적으로 효율적인' 정책을 결정할 수 있습니다.

 

기실, 이 상황은 경매와 유사합니다. 어떤 물건이 경매에 나오면 입찰자들은 해당 물건이 얼마큼의 가치가 있는지를 마음속으로 판단하고 경매인에게 그 가치를 알려 줍니다. 이때, 입찰자들은 거짓말을 칠 수 있습니다. 경매인은 수집한 가치를 토대로 낙찰자를 선정하고 낙찰자에게 일정 금액의 비용을 청구합니다. 지난 포스트에서 비크리 경매(Vickrey auction)를 통하면 모든 입찰자들이 경매인에게 거짓을 고할 유인이 없다는 것을 증명하였습니다.

2021.12.04 - [알고리즘 & 게임 이론/Mechanism design] - 비크리 경매 (Vickrey Auction)

비크리 경매 (Vickrey Auction)

아마도 이 방법을 확장한다면 구성원들이 정직하게 행동하도록 유인하면서 효율적인 정책을 결정하는 방법을 만들 수 있을 것입니다. 아래에서 이를 확인해 보겠습니다.

문제 정의

현재 고려하는 문제를 다음과 같은 모델로 표현해 보겠습니다. 정책 후보 집합을 \(A\)라고 부르겠습니다. 구성원은 총 \(n\) 명이 있으며, 각각 구성원 \(1\)부터 \(n\)이라고 부르겠습니다. 구성원의 집합은 \(I\)라고 하겠습니다. 구성원 \(i \in I\)는 각 정책 후보 \(a \in A \)에 대해 \(v^*_i(a) \in \mathbb{R}_+\)의 가치가 있다고 생각합니다. 동시에 정책 결정권자인 우리에게 각 후보 \(a \in A\)의 가치 \(v_i(a) \in \mathbb{R}_+ \)를 적어 냅니다. 이때, 각 구성원은 자신의 이해(利害)에 따라 거짓으로 적어 낼 수 있습니다. 곧, \(v_i \neq v^*_i\)일 수 있습니다. 단, 논의를 간단히 하기 위해 가치는 음수가 아니라고 가정하겠습니다.

 

모든 구성원으로부터 가치가 적힌 종이를 받으면 우리는 정책 후보 하나를 선정합니다. 이를 선정하는 알고리즘을 \( f(v_1, \cdots, v_n) \)라고 하겠습니다. 우리의 목표는 선정된 후보가 구성원들이 얻는 '실제' 가치의 합이 최대가 되는 것입니다. 다시 말해,

\[ f(v_1, \cdots, v_n) = \arg\max_{a \in A} \sum_{j \in I} v^*_j(a) \]

를 만족하도록 만드는 것입니다. 경우에 따라 \(f(v)\)로 줄여 쓸 수 있습니다.

 

구성원이 정직하게 행동하도록 만들기 위해 정책 결정권자인 우리가 할 수 있는 일은 세금을 매기는 것입니다. 구성원들이 \(v_1, \cdots, v_n\)의 가치를 적어 냈을 때, 구성원 \(i\)가 내야 할 세금을 \(p_i(v_1, \cdots, v_n)\) (아니면 \( p_i(v) \))이라고 하겠습니다. 이렇게 구성원들이 제출한 \(v_1, \cdots, v_n\)을 입력으로 하면서 정책을 하나 선정하는 알고리즘 \(f\)와 세금 \(p_1, \cdots, p_n\)을 통틀어 메커니즘(mechanism)이라고 일컫습니다.

 

모든 구성원은 개인적으로, 그리고 이기적으로 행동합니다. 만약 구성원 \(i\)를 제외한 나머지 구성원들이 \(v_1, \cdots, v_{i - 1}, v_{i + 1}, \cdots, v_n\)을 (정직하게든 거짓으로든) 제출했다고 합시다. 그때, 이 구성원이 \(v_i\)를 어떻게 적어 내든지,

\[ v^*_i(f(v_1, \cdots, v^*_i, \cdots, v_n)) - p_i(v_1, \cdots, v^*_i, \cdots, v_n) \geq v^*_i(f(v_1, \cdots, v_i, \cdots, v_n)) - p_i(v_1, \cdots, v_i, \cdots, v_n)\]

을 만족한다면, 다른 말로, 정직하게 알려 줬을 때 얻는 효용(utility)이 그렇지 않을 때보다 항상 작지 않다면, 이 구성원은 거짓을 고할 이유가 없습니다. 위 식은 너무 장황하므로 이를 다음과 같이 줄여 쓰겠습니다. \(i\)를 제외한 구성원들을 \(-i\)라고 부르겠습니다. 따라서 \(v_{-i}\)는 앞에서의 \( v_1, \cdots, v_{i - 1}, v_{i + 1}, \cdots, v_n \)을 의미합니다. 그러면 위 식은

\[ v^*_i( f(v^*_i, v_{-i} )) - p_i(v^*_i, v_{-i}) \geq v^*_i(f(v_i, v_{-i})) - p_i(v_i, v_{-i}) \]

로 줄여서 쓸 수 있습니다. 어떤 메커니즘 \(f, p_1, \cdots, p_n\)이 모든 구성원에 대해 위 식을 만족한다면, 우리는 이 메커니즘을 유인 부합적 메커니즘(incentive-compatible mechanism)이라고 부릅니다. 우리의 목표는 곧 실제 가치의 합이 최대가 되도록 하는 유인 부합적 메커니즘을 찾는 것이죠.

비크리-클라크-그로브스 메커니즘(Vickrey-Clarke-Groves mechanism)

서두에 우리가 찾을 메커니즘이 비크리 경매와 비슷하다고 언급했습니다. 비크리 경매에서는 일단 입찰자들이 정직하게 가격을 제출했다고 가정하고, 가장 비싼 금액을 적어 낸 사람에게 낙찰시킵니다. 이후, 두 번째로 비싼 금액을 낙찰자에게 비용으로 청구합니다.

 

같은 원리로 정책을 결정할 때 모든 구성원들이 정직하게 자신이 생각하는 가치를 제출했다고 믿어 봅시다. 즉, 제출된 가치를 기준으로 가장 가치의 합이 최대가 되도록 정책을 결정하는 것이죠. 다시 말해,

\[ f(v) = \arg\max_{a \in A} \sum_{j \in I} v_j(a) \]

로 정하겠습니다.

 

이제 구성원들에게 부과할 세금을 매겨 봅시다. 임의의 구성원 \(i\)를 고려해 보겠습니다. 만약 \(i\)가 구성원이 아니었다고 가정하겠습니다. 그러면 적어 낸 정보를 토대로 나머지 구성원들이 얻을 가치의 총합은 분명

\[ h_i(v_{-i}) := \max_{a \in A} \sum_{j \in I \setminus \{i\}} v_j(a) \tag{1} \]

였을 것입니다. 이 값을 \(h_i(v_{-i})\)라고 하겠습니다. 하지만 실제로 얻은 가치의 총합은 적어 낸 정보를 기준으로

\[ \sum_{j \in I \setminus \{ i \}} v_j(f(v_1, \cdots, v_i, \cdots, v_n)) \]

가 됩니다. 따라서 \(i\)가 참여함으로써 다른 이들이 얻을 가치를 위 식에서 아래 식을 뺀 만큼 빼앗아 갔다고 말할 수 있습니다. 사회를 위해 그 값을 보전해 달라는 의미에서 이를 이 구성원의 세금으로 하겠습니다. 곧,

\[ p_i(v) = h_i(v_{-i}) - \sum_{j \in I \setminus \{i\}} v_j(f(v)) \tag{2} \]

입니다.

 

이것으로 메커니즘 \(f, p_1, \cdots, p_n\)의 정의를 모두 마칩니다. 놀랍게도 이 메커니즘은 실제 가치의 합이 최대가 되도록 하는 유인 부합적 메커니즘입니다. 이를 증명해 봅시다. 일단 만약 모든 구성원들이 정직하게 행동했다면 \(f\)는 그 정의 상 구성원이 얻는 가치의 합이 최대가 되는 정책을 결정합니다. 따라서 모든 구성원들이 거짓을 행할 유인이 없다는 것을 보이면 모든 증명이 끝납니다.

정리 2. 유인 부합성

---

이 메커니즘 \(f, p_1, \cdots, p_n\)은 유인 부합적이다.

[증명] 임의의 구성원 \(i\)에 대해, 다른 구성원들이 (진짜든 가짜든) \(v_{-i}\)를 써서 제출했다고 합시다. 이 구성원이 실제 자신이 생각한 가치 \(v^*_i\)를 제출했다면, 이 구성원의 효용은

\[ v^*_i ( f(v^*_i, v_{-i}) - p_i( v^*_i, v_{-i} ) = v^*_i ( f(v^*_i, v_{-i}) ) + \sum_{j \in I \setminus \{i\}} v_j(f(v^*_i, v_{-i})) - h_i(v_{-i}) \tag{3}\]

로 적을 수 있습니다. 반면, 이 구성원이 아무 \(v_i\)를 제출한 경우, 이 구성원의 효용은

\[ v^*_i ( f(v_i, v_{-i}) ) - p_i(v^*_i, v_{-i}) = v^*_i( f(v_i, v_{-i}) ) + \sum_{j \in I \setminus \{i\}} v_j(f(v_i, v_{-i})) - h_i(v_{-i}) \tag{4} \]

으로 쓸 수 있습니다. 앞에서 \(f\)는 제출된 가치에 대해 그 합이 최대가 되도록 정의되었습니다. 따라서, \(v^*_i, v_{-i}\)에 대해서는 \( f(v^*_i, v_{-i}) \)가 그 합을 최대로 만듭니다. 이를 통해 식 3이 식 4보다 크거나 같다는 사실을 이끌어 낼 수 있습니다. ■

 

이로써 위 메커니즘이 우리가 원하는 메커니즘이라는 사실을 증명하였습니다. 그런데 사실 정리 2의 증명에서 \( h_i(v_{-i}) \)는 전혀 사용되지 않았습니다. 따라서 해당 함수를 아무렇게나 정의해도 위 메커니즘은 유인 부합적입니다. 그러면 식 1처럼 정의한 이유는 따로 있을까요?

정리 3. \(h_i(v_{-i})\)의 좋은 성질

---

\(h_i(v_{-i})\)를 식 1처럼 정의하면, 임의의 구성원 \(i\)가 얻는 효용과 내는 세금이 모두 음이 아니다. 다시 말해, 구성원 \(i\)가 사회를 이탈할 이유가 없으며, 우리가 구성원 \(i\)에게 역으로 세금을 보전해 줄 필요도 없다.

[증명] 논의를 간단히 하기 위해 모든 구성원이 정직하게 행동했다고 가정하겠습니다. 정리 2에 의해 이 가정이 괜찮다는 것을 알 수 있습니다. 먼저 첫 번째 명제를 생각해 봅시다. 구성원 \(i\)의 효용은

\[ v^*_i ( f(v^*)) - p_i( v^*) = \sum_{j \in I} v^*_j(f(v^*)) - \max_{a \in A} \sum_{j \in I \setminus \{i\}} v^*_j(a) \]

입니다. 이때, 우변의 \( \max_{a \in A} \sum_{j \in I \setminus \{i\}} v^*_j(a) \)를 이루는 후보를 \(b\)라고 하겠습니다. 그러면, \[ \sum_{j \in I} v^*_j(f(v^*)) \geq \sum_{j \in I} v^*_j(b) \geq \sum_{j \in I \setminus \{i\}} v^*_j(b) \]가 되어 구성원 \(i\)의 효용이 음이 아니라는 사실을 알 수 있습니다. 여기서 첫 번째 부등식은 \(f\)의 정의에 의해, 두 번째 부등식은 문제 정의에서 \( v^*_j(b) \geq 0 \)라고 했기 때문에 성립합니다.

 

두 번째 명제는 \( h_i(v^*_{-i}) \)가 \( i \)가 없는 사회에서 이룰 수 있는 가치의 합의 최대치이고, \( f(v^*) \)는 선정할 수 있는 후보 중 하나라는 사실을 통해 쉽게 확인할 수 있습니다. 식 1과 식 2를 참고하세요. ■

 

어떤 \( h_i(v_{-i}) \)가 정해지든 정리 2에 의해 이 메커니즘은 구성원이 얻는 가치의 합을 최대화하는 유인 부합적 메커니즘입니다. 이 메커니즘 자체를 비크리-클라크-그로브스 메커니즘(Vickrey-Clarke-Groves mechanism)이라고 일컫습니다. 추가적으로 \( h_i(v_{-i}) \)를 식 1과 같이 정의하면 정리 3을 통해 보장되는 좋은 성질들이 있습니다. 이렇게 가격을 정하는 방법을 클라크 피벗 규칙(Clarke pivot rule)이라고 부릅니다. 참고로 메커니즘이나 피벗은 마뜩한 우리말 번역이 떠오르지 않아 그냥 그대로 옮겨 적었습니다.

비크리 경매와의 관계

앞에서 비크리-클라크-그로브스 메커니즘을 구상할 때 비크리 경매의 아이디어를 차용했었습니다. 그렇다면 비크리 경매를 이 메커니즘으로 해석할 수 있을까요? 당연히 가능합니다. 각 입찰자 \(i\)가 낙찰되는 상황은 정책 후보에 대응합니다. 즉, \(a_i\)를 입찰자 \(i\)가 승리한 상황이라고 한다면,

\[ A = \{ a_i \mid i \in I \} \]

로 쓸 수 있습니다. 각 입찰자 \(i\)가 경매에 올라온 물건을 \( w^*_i \)의 가치로 생각한다고 합시다. 그러면 모든 정책 후보 \(a \in A\)에 대해 이 입찰자는

\[ v^*_i(a) = \left\{ \begin{array}{ll} w^*_i, & \text{if } a = a_i, \\ 0, & \text{otherwise} \end{array} \right. \]

의 가치로 생각한다고 볼 수 있습니다. 또한 각 입찰자 \(i\)가 \(w_i\)를 적어서 경매사에게 보내는 것은

\[ v_i(a) = \left\{ \begin{array}{ll} w_i, & \text{if } a = a_i, \\ 0, & \text{otherwise} \end{array} \right. \]

에 대응합니다.

 

\(f\)의 정의와 \(v_i\)의 형태를 통해 우리는 \(f\)가 가장 큰 \(w_i\)를 제출한 입찰자에게 물건을 낙찰시킨다는 것을 확인할 수 있습니다. 만약 구성원 \(i\)가 낙찰자라면, \( h_i(v_{-i}) \)는 이 구성원을 뺀 나머지 중에서 제출된 가장 높은 가격에 해당하고 이 구성원이 참여했을 때는 나머지 구성원들이 얻는 가치는 0이라는 사실을 통해서 두 번째로 높은 가격을 세금으로 낸다는 것을 알 수 있습니다. 반대로 구성원 \(i\)가 패찰자라면 자신이 참여하든 말든 낙찰자는 동일하므로 내는 세금은 없습니다. 이는 비크리 경매와 동일하다는 사실을 확인할 수 있습니다.

마치며

이것으로 모든 구성원들의 선호를 통일된 기준(곧, 돈)으로 나타낼 수 있을 때, 구성원들이 정직하게 행동하도록 유인하면서 사회가 얻는 가치의 합을 최대화하는 정책을 선정하는 방법인 비크리-클라크-그로브스 메커니즘에 대한 설명을 마칩니다.

 

만약 임의의 \( v_1, \cdots, v_n \)이 주어졌을 때, 가치의 합 \( \sum_{i=1}^n v_i(a) \)를 최대화시키는 후보 \(a \in A\)를 빠른 시간 안에 뽑는 알고리즘이 존재한다면, 이 알고리즘을 \(n + 1\) 번 수행하는 것을 통해서 우리는 비크리-클라크-그로브스 메커니즘을 구현할 수 있습니다. 따라서 컴퓨터 과학의 시선에서는 다음의 연구 주제들을 떠올릴 수 있습니다.

• 만약 가치의 합을 최대화시키는 후보를 빠른 시간에 구할 수 없을 때는 어떻게 할 것인가? 유인 부합성을 유지하면서 최적해 대신 근사해를 구할 수는 있겠는가?
• \(n + 1\) 번보다 점근적으로(asymptotically) 적은 횟수의 알고리즘을 수행하여 \( p_1, \cdots, p_n \)을 구할 수 있겠는가?

찾아 보니 관련하여 많은 연구가 진행된 것 같더군요. 좋은 내용은 나중에 공유해 보겠습니다.

 

고맙습니다. :)

참조

[1] Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.