비크리 경매 (Vickrey Auction)

Photo by Element5 Digital on Unsplash

희대의 역작이 경매로 올라왔고, 여러 입찰자들이 이 작품을 구매하기 위해 모여들었습니다. 작가는 자신의 가치를 실제로 가장 높게 쳐주는 사람에게 자신의 작품을 넘기기를 바라고 있습니다. 우리는 경매사로서 작가의 바람에 부응해야 합니다. 이를 위해서 우리는 모든 입찰자로부터 각자가 생각하는 작품의 가치를 종이에 적어서 제출해 달라고 부탁하였습니다. 가치가 기록된 종이는 입찰자들에게 공유되지 않고 오로지 신뢰 받는 경매사인 우리만 알게 됩니다. 하지만 입찰자들은 너무도 "이기적"이어서 만약 가치를 속여서 적는게 자신에게 이득이 된다면 기꺼이 그럴 것입니다. 이러한 무한 경쟁의 상황에서 과연 어느 입찰자에게 얼마의 금액으로 작품을 판매해야 실제로 가장 높은 가치를 쳐주는 입찰자에게 작품이 돌아가게 할 수 있을까요?

 

문제를 정확히 정의해 봅시다. \(n\) 명의 입찰자가 있으며, 입찰자 \(i\)는 경매에 부쳐진 작품의 가치를 \(v^*_i \in \mathbb{R}_+\)로 생각하고 있다고 합시다. 하지만 실제 가치는 아무도 모르며, 대신 각 입찰자 \(i\)는 자신이 \(v_i \in \mathbb{R}_+\)의 가치로 생각하고 있다고 우리에게 입찰가를 알려 줍니다. 즉, 두 값은 같지 않을 수도 있습니다. 우리는 수집한 \(v_i\)들을 기반으로 경매의 승자를 결정하고 특정 비용 \(p \in \mathbb{R}_+\)를 승자에게 청구합니다. 청구할 금액이 입찰가와 같을 필요는 없습니다. 우리의 목표는 실제 가치 \(v^*_i\)를 가장 높게 쳐준 입찰자가 경매에서 승리하도록 만드는 것입니다. (여러 명 있으면 아무나 한 명이면 됩니다.)

 

그럼 각 입찰자는 어떻게 자신의 입찰가를 결정할까요? 낙찰 이후에 만약 입찰자 \(i\)가 승리하였다면, 이 입찰자는 자신이 처음에 생각한 작품의 가치 \(v^*_i\)에서 청구된 비용 \(p\)를 제한 만큼, 즉 \(v^*_i - p\) 만큼 이득을 얻었다고 생각할 것입니다. 반대로 패배한 경우에는 얻은 것도, 잃은 것도 없으므로 0의 이득을 얻었다고 생각할 것입니다. 다시 말해, 입찰자 \(i\)의 효용 \(u_i\)는

\[ u_i = \left\{ \begin{array}{ll} v^*_i - p & \text{if } i \text{ wins,} \\ 0 & \text{otherwise} \end{array}\right. \]

로 정의할 수 있습니다. 앞에서 우리는 각 입찰자가 "이기적"이라고 하였습니다. 이를 앞에서 정의한 효용의 관점에서 설명하면, 각 입찰자는 효용 \(u_i\)가 최대가 되도록 입찰가 \(v_i\)를 적어낸다는 뜻입니다.

---

먼저 승자를 정하는 방법을 생각해 봅시다. 가장 자연스러운 방법은 가장 높은 입찰가를 제시한 입찰자에게 작품을 주는 것입니다. 만약 모든 입찰자들이 정직하게 실제로 자신이 생각하는 가치를 입찰가로 제출했다면, 즉 모든 \(i\)에 대해 \(v_i = v^*_i\)라면, 이는 실제로 우리의 목표를 달성하는 방법이 됩니다. 문제는 입찰자들은 정직하지 않고 이기적이라는 것이죠. 과연 이 상황에서도 입찰자들이 정직하게 자신이 생각하는 가치를 적어 내도록 만들 수 있을까요?

 

아직 우리가 결정하지 않은 부분이 있습니다. 바로 청구할 금액 \(p\)입니다. 이제부터 몇 가지 청구 방식을 살펴 보면서 과연 해당 청구 방식이 입찰자들에게 정직하게 행동하도록 만들 수 있는지 따져 봅시다.

자선 방식

생각할 수 있는 가장 멍청한 방식은 비용을 청구하지 않는 것입니다. 즉, \(p = 0\)인 것이죠. 이는 실지로 매우 멍청한 방법입니다. 비용이 나오지 않으니 모든 입찰자들은 낙찰되기 위해 최대한 높은 가격을 부를 것입니다.

최고가 청구 방식

이번에는 적어낸 금액 그대로 비용을 청구하는 방식을 생각해 보겠습니다. 따라서 입찰자 \(i\)가 \(v_i\)의 입찰가로 낙찰되면 \(p = v_i\)로 하는 것이죠. 이 방식은 일견 합리적으로 보입니다. 하지만 큰 문제가 있죠. 만약 입찰자가 정직하게 자신이 생각하는 가치 \(v^*_i\)를 입찰가로 적어내면 이 입찰자가 얻는 효용은 항상 0이라는 점입니다. 반대로 자신이 생각하는 가치보다 낮은 금액으로 적어내서 만일 낙찰이 되면 0보다 큰 효용을 얻게 됩니다. 따라서 정직하게 행동하지 않을 유인이 충분하죠.

차고가(次高價) 청구 방식

최고가 청구 방식의 맹점은 입찰자가 정직하게 행동하면 효용이 언제나 0이라는 것입니다. 따라서 낙찰될 입찰자는 입찰가를 가능한 낮춰서 부를 것입니다. 과연 얼마큼 낮춰서 부를 때까지 효용이 있을까요? 만약 두 번째로 높은 입찰가보다는 조금 높게 입찰가를 부르면 최대의 효용을 얻을 수 있습니다. 따라서 그 일을 그냥 경매사인 우리가 대신 해 주는 것은 어떨까요? 즉, 승자에게 두 번째 높은 입찰가를 비용으로 청구하는 것이죠. 그러면 놀랍게도 모든 입찰자들이 정직하게 행동할 것을 기대할 수 있습니다.

정리 1. 정직한 행동에 대한 유인

---

어떤 입찰자 \(i\)에 대해서, 다른 모든 입찰자들의 입찰가가 (정직하게든 정직하지 않게든) 결정된 상태에서 혼자 정직하게 행동하지 않는다고 효용 \(u_i\)가 증가하지 않는다.

[증명] 먼저 입찰자 \(i\)가 정직하게 입찰가를 \(v^*_i\)로 제출했을 때에도 낙찰되지 않았다고 생각해 봅시다. 그러면 분명 다른 어떤 입찰자 \(i'\)이 \(v_{i'} \geq v^*_i\)의 최고 입찰가를 제출했다는 뜻입니다. 이 경우, \(v_{i'}\)보다 낮은 입찰가를 제시한 경우에는 당연히 낙찰되지 않으므로 효용은 0으로 동일합니다. 만약 \(v_{i'}\)보다 높은 가격을 제시했다면 입찰자 \(i\)가 낙찰되겠지만, 비용이 \(p = v_{i'}\)가 되어 입찰자의 효용은 \(u_i = v^*_i - v_{i'} \leq 0\)이 됩니다. 

 

이제 입찰자 \(i\)가 정직하게 입찰가를 제출했을 때 낙찰되는 경우를 생각해 봅시다. 이때 두 번째로 높은 입찰가를 \(v_{i'} \leq v^*_i\)이라고 하겠습니다. 그러면 이 입찰자의 효용은 \(u_i = v^*_i - v_{i'} \geq 0\)이 됩니다. 만약 이 입찰자가 \( v_{i'} \)보다 높은 입찰가를 제시했다면 어차피 입찰자는 \(v_{i'}\)을 비용으로 낼 것이므로 효용의 변화는 없습니다. 반대로 그보다 낮은 가격을 제시했다면 경매에서 패배하게 되어, 효용이 0이 됩니다. ■

---

이렇게 각 입찰자들로부터 비밀리에 입찰가를 받고 가장 높은 입찰가를 제시한 입찰자에게 두 번째로 높은 입찰가를 비용으로 청구하는 경매 방식을 비크리 경매(Vickrey auction) 혹은 차고가 밀봉 경매(second-price sealed-bid auction)이라고 부릅니다. 이 방식이 다른 방식에 비해 특별히 흥미로운 점은 모든 입찰자들로 하여금 각자의 실제 가치를 입찰가로 적어 내도록 유인할 수 있다는 것입니다. 이렇게 혼자서는 정직하게 행동하지 않는다고 해서 해당 입찰자의 효용이 증가하지 않는, 따라서 각 입찰자가 정직하게 행동하는 유인을 제공하는 방식을 일컬어 유인부합적 메커니즘(incentive-compatible mechanism) 혹은 정직한 메커니즘(truthful mechanism)이라고 부릅니다. 다음 포스트에서는 이 내용에 대해 좀더 깊이 다뤄 보도록 하겠습니다.

 

요즘 경제학이나 게임 이론에서 사용되는 알고리즘을 공부하고 있습니다. 흥미로운 내용이 무척 많이 있더군요. 잘 정리해서 많이 공유할 수 있도록 하겠습니다. 고맙습니다. :)

참조

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