최적 경매 (Optimal Auction)

Photo by Eric TERRADE on Unsplash

희대의 역작이 다시 또 경매에 올라왔습니다. 이번에도 여러 입찰자들이 작품을 쟁취하기 위하여 구름같이 모여들었군요. 열 길 물 속은 알아도 한 길 사람 속은 모른다고, 입찰자들은 약았습니다. 각자 본인이 생각하는 가치가 있지만, 본인의 이득을 위해서라면 거짓말도 서슴지 않을 속내입니다. 지난 시간에는 이런 상황 속에서 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 경매 방식인 비크리 경매(Vickrey auction)를 공부하였습니다.

비크리 경매 (Vickrey Auction)

이번 포스트에서는 목표를 다르게 잡아 보고자 합니다. 그동안 경매사는 가장 높게 가치를 매겨주는 입찰자에게 물건을 넘겨 주었습니다. 그러다 보니 슬슬 본인의 통장 잔고가 비어가는 것을 느꼈습니다. 더 이상의 자선 사업은 그만해야겠다고 마음을 먹은 경매사는 이제부터 자신의 수익을 극대화하는 방향으로 경매를 진행하기로 결정했습니다. 과연 어떻게 하면 경매사의 목표를 달성할 수 있을까요?

들어가며

본문에 바로 들어가기 전에 초기 정보가 전혀 없는 일반적인 상황을 먼저 생각해 봅시다. 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 비크리 경매는 경매사가 입찰자에 대한 초기 정보가 전혀 없어도 잘 동작했습니다. 그렇다면 경매사의 수익을 최대로 만들고자 하는 현재 목표에서는 초기 정보가 없어도 괜찮을까요?

 

안타깝지만 그렇지 않습니다. 예를 들어 보죠. 경매에 참가한 입찰자가 한 명이라고 생각해 봅시다. 만약 비크리 경매에서와 같이 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 것이 목표라면, 어떤 방식으로던 입찰자에게 작품을 넘기기만 하면 모든 상황이 종료됩니다. 따라서 공짜로 작품을 넘기는 것도 최대의 가치를 이룩하는 방법이 되죠. 하지만 이는 경매사의 입장에서는 최악의 수입니다.

 

그렇다면 경매사가 취할 수 있는 최적의 수는 무엇일까요? 바로 입찰자가 생각하는 가치만큼의 가격에 작품을 판매하는 것이죠. 문제는 여기서 발생합니다. 입찰자가 생각하는 가치가 무엇인지 알 방도가 없기 때문입니다. 따라서 이번에는 이렇게 과도하게 제한적인 상황을 좀 풀어 주고자 합니다. 바로 입찰자가 생각하는 가치가 이미 모두에게 알려진 어떤 확률 분포를 따른다는 것이죠. 이 상황에서 우리의 목표는 경매사의 기대 수익을 최대화하는 것이 되겠습니다.

 

이번에는 경매에 두 명의 입찰자가 들어왔다고 합시다. 두 입찰자는 각각 독립적으로 \([0, 1]\) 사이에서 균등하게 뽑은 값을 물건에 대한 가치로 갖습니다. 이제 이 입찰자들에 대해서 비크리 경매를 수행해 봅시다. 그러면 경매사는 두 입찰자의 가치 중 더 적은 값을 수익으로 얻을 것이므로 \[ \mathbb{E}_{X_1, X_2 \overset{\mathrm{iid}}{\sim} U[0, 1]} [\min\{X_1, X_2\}] = 1/3 \]의 기대 수익을 얻게 됩니다.

 

과연 더 잘할 수 있을까요? 이번에는 같은 입찰자들에 대해 다음과 같은 경매를 진행해 보겠습니다. 똑같이 비크리 경매를 수행한 후 승자가 지불해야 하는 금액이 \(1/2\)보다 작은 경우에는 \(1/2\)에 구매하겠느냐고 또 제안을 합니다. 만약 해당 입찰자가 \(1/2\)보다는 높은 가치로 생각하고 있었다면 그 제안에 응했겠지만, 그렇지 않다면 구매를 포기할 것입니다. 즉, 일정 확률로 아무에게도 할당이 되지 않는 상황이 발생할 수 있습니다. 놀랍게도 이 방식은 \(5/12\)의 기대 수익을 얻게 됩니다.(계산은 생략합니다.) 따라서 경매사의 기대 수익을 높이기 위해 어떤 경우에는 아무에게도 물건을 넘기지 않는 전략도 필요합니다.

 

과연 더 잘할 수 있을까요? 이 질문의 답은 본문의 말미에 남겨 두었습니다. 

문제 정의

이번 절에서는 문제를 엄밀히 정의해 보겠습니다. 하나의 물건이 경매에 올라왔으며, 총 \(n\) 명의 입찰자가 경매에 참가한 상태입니다. 입찰자들의 집합을 \(N\)으로도 부르겠습니다. 각 입찰자 \(i\)가 생각하는 물건의 가치는 어떤 확률 분포에 따라 정해집니다. 해당 확률 분포에서 나올 수 있는 모든 값을 \(V_i := \left[ \underline{v_i}, \overline{v_i} \right]\)라고 하겠습니다. 해당 확률 분포의 확률 밀도 함수(probability density function)는 \(f_i : V_i \to [0, 1]\), 누적 분포 함수(cumulative distribution function)는 \(F_i : V_i \to [0, 1]\)이라고 하겠습니다. 각 입찰자들의 확률 분포는 서로 독립(mutually independent)이며, 모두에게 공개된 정보입니다. 단, 실제로 어떤 값이 뽑혔는지는 알지 못합니다.

 

경매는 각 입찰자들에게서 자신이 생각하는 물건의 가치를 경매사가 수집하는 것으로 시작합니다. 입찰자는 필요에 따라서는 자신이 생각하는 가치를 속여서 제출할 수도 있습니다. 경매사는 수집한 정보를 토대로 최대 한 명의 낙찰자에게 물건을 제공하며, 각 입찰자들에게서 돈을 요구합니다. 이때, 경매사는 필요하다면 아무에게도 물건을 넘기지 않을 수 있으며, 물건을 받지 못한 입찰자에게서도 돈을 요구할 수 있습니다. 경매사의 수익은 입찰자들에게서 거둔 돈의 총액입니다. 우리의 목표는 입찰자들의 확률 분포에 대한 경매사의 기대 수익을 최대화하는 것입니다. 단, 이 경매에서도 마찬가지로 입찰자들에게는 거짓을 고할 유인이 없어야 합니다.

표현 편의를 위한 기호

표현의 편의를 위해 모든 입찰가를 다음과 같이 벡터로 쓸 수 있습니다. \[ v := (v_1, \cdots, v_n) \] 또한, 어떤 입찰자 \(i\)를 제외한 나머지 입찰가를 \[ v_{-1} := (v_1, \cdots, v_{i - 1}, v_{i + 1}, \cdots, v_n) \]으로 표현하겠습니다. 비슷한 이치로 \[ V := V_1 \times \cdots \times V_n, \quad V_{-i} := V_1 \times \cdots \times V_{i - 1} \times V_{i + 1} \times \cdots \times V_n \]로 적겠습니다. 확률 밀도 함수 또한 서로 독립이라는 조건을 통해, \[ f(v) := \prod_{i \in N} f_i(v_i), \quad f_{-i}(v_{-i}) := \prod_{j \neq i} f_j(v_j)\]로 적도록 하겠습니다.

경매의 조건

각 입찰자 \(i\)에 대해, 수집된 입찰가가 \(v\)라고 했을 때, 이 입찰자가 물건을 얻었는지를 나타내는 변수를 \(x_i(v)\)로, 그때 지불해야 하는 금액을 \(p_i(v)\)로 정의하겠습니다. 경매에 올라온 물건은 하나입니다. 따라서 입찰자들이 어떤 식으로 입찰가를 제시하였든지 최대 한 명의 입찰자에게 물건이 제공되어야 합니다. 그러므로, 가능한 모든 입찰가 \(v \in V\)에 대해서, \[ \sum_{i \in N} x_i(v) \leq 1 \]을 만족해야 합니다. 물론 음수의 물건을 받을 수는 없으므로, 각 입찰자 \(i\)와 모든 입찰가 \(v\)에 대해, \[ x_i(v) \geq 0 \]을 만족해야 합니다. 이 조건을 우리는 할당(allocation) 조건이라고 부르겠습니다.

 

입찰자 \(i\)가 자신이 생각하는 물건의 가치를 \(v_i\)로 뽑았다고 해 봅시다. 이때 우리는 입찰자 \(i\)가 다음과 같은 기대 효용(expected utility) \[ U_i(x, p, v_i) := \int_{V_{-i}} \left[ v_i x_i(v) - p_i (v) \right] f_{-i}(v_{-i}) dv_{-i} \]을 얻는다고 가정하겠습니다. 만약 이 값이 0보다 작았다고 합시다. 그러면 이 입찰자는 \(v_i\)를 뽑았을 경우 해당 경매에 참가할 이유가 없습니다. 다르게 생각하면 기대 효용이 0보다 작아지는 구간이 \(V_i\)에 존재한다면 해당 입찰자는 참가하지 않았을 때보다 적은 효용을 얻을 수도 있는 모험을 감수해야 합니다. 본문에서는 모든 입찰자들이 이러한 모험을 하지 않는다고 가정하겠습니다. 즉, 모든 \(v_i \in V_i\)에 대해, \[ U_i(x, p, v_i) \geq 0 \]을 만족합니다. 이러한 조건을 개별적 합리성(individual rationality)이라고 부릅니다.

 

또한 우리는 경매에서 입찰자들이 거짓을 고하지 않기를 원합니다. 그러기 위해서는 입찰자가 실제로는 \(v_i\)를 뽑았지만 다른 값 \(s_i\)를 제출했을 때 얻을 수 있는 기대 효용이 진실을 고했을 때보다 크지 않으면 됩니다. 다시 말해, 임의의 입찰자 \(i\)와 임의의 가치 \(s_i, v_i \in V_i\)에 대해, \[ U_i(x, p, v_i) \geq \int_{V_{-i}} \left[ v_i x_i(s_i, v_{-i}) - p_i(s_i, v_{-i}) \right] f_{-i}(v_{-i}) dv_{-i} \]를 만족하면 됩니다. 이 조건을 유인 부합성(incentive compatibility)이라고 부릅니다.

 

앞에서 살펴 본 내용들을 토대로 우리는 경매사의 기대 수익을 최대화하는 문제를 다음과 같은 최적화 문제(optimization problem)로 표현할 수 있습니다.

\[ \begin{array}{lll} \text{maximize} & \displaystyle \int_V \left[ \sum_{i \in N} p_i(v) \right] f(v) dv & \\ \text{subject to} & \displaystyle \sum_{i \in N} x_i(v) \leq 1, & \forall v \in V, \\ &\displaystyle x_i(v) \geq 0, & \forall i \in N, \forall v \in V, \\ &\displaystyle U_i(x, p, v_i) \geq 0, & \forall i \in N, \forall v_i \in V_i, \\ & \displaystyle U_i(x, p, v_i) \displaystyle \geq \int_{V_{-i}} \left[ v_i x_i(s_i, v_{-i}) - p_i(s_i, v_{-i}) \right] f_{-i}(v_{-i}) dv_{-i}, & \forall i \in N, \forall s_i, v_i \in V_i. \end{array} \tag{P1} \]

단순한 동치 문제

위 최적화 문제를 바로 푸는 것은 대단히 어려워 보입니다. 따라서 이를 보다 간단히 만들 수 없는지를 먼저 생각해 보겠습니다. 이를 위해서 먼저 \(Q_i(x, v_i)\)를 \[ Q_i(x, v_i) := \int_{V_{-i}} x_i(v) f_{-i} (v_{-i}) dv_{-i} \]라고 하겠습니다. 이는 입찰자 \(i\)의 입찰가가 \(v_i\)였을 때 물건을 획득할 조건부 확률에 해당합니다.

 

이 정의를 활용하면 위 문제를 조금 더 단순하게 만들 수 있습니다. 마지막 유인 부합성 제약 조건의 우변을 살펴 보겠습니다. 우리는 다음의 등식을 얻을 수 있습니다.

\[ \begin{array}{rl} & \displaystyle \int_{V_{-i}} \left[ v_i x_i(s_i, v_{-i}) - p_i(s_i, v_{-i}) \right] f_{-i}(v_{-i}) dv_{-i} \\ & \displaystyle = \int_{V_{-i}} \left[ (v_i + s_i - s_i) x_i(s_i, v_{-i}) - p_i(s_i, v_{-i}) \right] f_{-i}(v_{-i}) dv_{-i} \\ & \displaystyle = \int_{V_{-i}} \left[ s_i x_i(s_i, v_{-i}) - p_i(s_i, v_{-i}) \right] f_{-i}(v_{-i}) dv_{-i} + \int_{V_{-i}} \left[ (v_i - s_i) x_i(s_i, v_{-i}) \right] f_{-i}(v_{-i}) dv_{-i} \\ & = \displaystyle U_i(x, p, s_i) + (v_i - s_i) Q_i(x, s_i) \end{array} \]

따라서 P1을 다음과 같이 변환해 보겠습니다.

\[ \begin{array}{lll} \text{maximize} & \displaystyle \int_V \left[ \sum_{i \in N} p_i(v) \right] f(v) dv & \\ \text{subject to} & \displaystyle \sum_{i \in N} x_i(v) \leq 1, & \forall v \in V, \\ &\displaystyle x_i(v) \geq 0, & \forall i \in N, \forall v \in V, \\ &\displaystyle U_i(x, p, v_i) \geq 0, & \forall i \in N, \forall v_i \in V_i, \\ & \displaystyle U_i(x, p, v_i) \geq U_i(x, p, s_i) + (v_i - s_i) Q(x, s_i), & \forall i \in N, \forall s_i, v_i \in V_i. \end{array} \tag{P2} \]

아쉽지만 이렇게 얻은 P2도 여전히 복잡합니다.

 

이제 다음의 최적화 문제를 생각해 봅시다.

\[ \begin{array}{lll} \text{maximize} & \displaystyle \int_V \left[ \sum_{i \in N} p_i(v) \right] f(v) dv & \\ \text{subject to} & \displaystyle \sum_{i \in N} x_i(v) \leq 1, & \forall v \in V, \\ &\displaystyle x_i(v) \geq 0, & \forall i \in N, \forall v \in V, \\ & Q_i(x,s_i) \leq Q_i(x, v_i), & \forall i \in N, \forall s_i \leq v_i, \\ &\displaystyle U_i(x, p, \underline{v_i}) \geq 0, & \forall i \in N, \\ & \displaystyle U_i(x, p, v_i) = U_i(x, p, \underline{v_i}) + \int_\underline{v_i}^{v_i} Q(x, z_i) dz_i, & \forall i \in N, \forall v_i \in V_i. \end{array} \tag{P3} \]

할당 조건은 그대로 남아 있지만, 개별적 합리성과 유인 부합성은 보다 단순하게 바뀌었습니다. 크게 두 부분이 눈에 띕니다.

• 세 번째 제약 조건의 직관적인 의미는 입찰자 \(i\)가 더 큰 값을 제출할 수록 얻을 확률이 높아지기만 한다는 것입니다.
• 마지막 제약 조건은 등식입니다. 즉, 이는 \(U_i(x, p, v_i)\)를 \(U_i(x, p, \underline{v_i})\)와 \(Q_i(x, z_i)\)로 특정 지을 수 있다는 의미죠.

이 문제를 정의한 이유는 놀랍게도 P2, 나아가 P1과 동치(equivalent)이기 때문입니다.

정리 1. 동치인 두 문제

---

P2와 P3는 동치이다. 다시 말해, 위 문제에서의 가능한(feasible) 해는 아래 문제에서도 가능하며, 아래 문제에서 가능한 해는 위 문제에서도 가능하다.

[증명] 먼저 P2의 가능한 해가 P3의 가능한 해임을 보이겠습니다. 일단 P3의 첫 번째, 두 번째, 네 번째 조건은 쉽게 증명이 가능합니다. 이제 입찰자 \(i\)를 하나 고정하고, 임의의 두 \(s_i, v_i\)를 생각해 보겠습니다. 단, \(s_i < v_i\)입니다. P2의 마지막 조건에 의해 \[ U_i(x, p, v_i) \geq U_i(x, p, s_i) + (v_i - s_i) Q_i(x, p, s_i) \]를 얻을 수 있습니다. 이제 \(s_i, v_i\)의 역할을 바꾸어서 넣으면 \[  U_i (x, p, s_i) \geq U_i(x, p, v_i) + (s_i - v_i) Q_i(x, p, v_i)\]를 대신 얻을 수 있습니다. 위 두 식을 정리하면 \[ (v_i - s_i) Q_i(x, p, s_i) \leq U_i(x, p, v_i) - U_i(x, p, s_i) \leq (v_i - s_i) Q_i(x, p, v_i) \]를 얻을 수 있습니다. 첫 번째 변과 마지막 변에서 P3의 세 번째 조건이 성립함을 알 수 있습니다. 마지막 조건을 살펴 보겠습니다. 앞에서 구한 부등식의 모든 변을 \(v_i - s_i\)로 나누어 봅시다. 그러면 \[ Q_i(x, p, s_i) \leq \frac{U_i(x, p, v_i) - U_i(x, p, s_i)}{v_i - s_i} \leq Q_i(x, p, v_i) \]가 되는 것을 알 수 있습니다. 이때 \(v_i \gets s_i +\)로 극한을 보내면 \(U_i(x, p, v_i)\)의 미분 계수가 \(Q_i(x, p, v_i)\)가 된다는 것을 알 수 있습니다. 따라서 P3의 마지막 조건 또한 만족함을 확인할 수 있습니다.

 

이제 P3의 가능한 해가 P2의 가능한 해가 됨을 보이겠습니다. P2의 첫 번째, 두 번째 조건은 쉽게 증명이 됩니다. 세 번째 조건 또한 어렵지 않습니다. \(x_i(v) \geq 0\)이므로 \(Q_i(x, p)\)는 항상 0보다 크거나 같습니다. 그러므로 P3의 네 번째, 다섯 번째 조건을 통해 \(U_i(x, p, v_i) \geq 0\)이 바로 도출됩니다. P2의 마지막 조건은 \[ U_i(x, p, v_i) - U_i(x, p, s_i) = \int_{s_i}^{v_i} Q_i(x, z_i) dz_i \geq (v_i - s_i) Q_i(x, s_i)\]를 통해 유도할 수 있습니다. 여기서 첫 번째 등식은 P3의 마지막 조건에서, 두 번째 등식은 P3의 세 번째 조건에서 \(Q_i(x, z_i) \geq Q_i(x, s_i)\)가 되어 성립합니다. ■

기대 수익

이전 절에서 우리는 복잡한 최적화 문제를 훨씬 단순하고 직관적인 형태로 바꾸는 것에 성공하였습니다. 이번 절에서는 이 형태를 토대로 경매사의 기대 수익을 다시 써 보도록 하겠습니다. 경매사의 기대 수익은 \[ \int_V \sum_{i \in N} p_i(v) f(v) dv \]입니다. 기댓값의 선형성(linearity of expectation)에 의해 우리는 이를 \[ \sum_{i \in N} \int_{V} [p_i(v) - v_i x_i(v) + v_i x_i(v) ]  f(v) dv = \sum_{i \in N} \left[ \int_V v_i x_i(v) f(v) dv - \int_{V_i} U_i(x, p, v_i) f_i(v_i) dv_i \right] \tag{1} \]와 같이 적을 수 있습니다. 이 식의 의미를 직관적으로 해석하자면 경매사의 기대 수익은 경매를 통해 발생한 기대 사회 잉여(expected social surplus)에서 각 입찰자의 기대 효용을 제외한 값이라는 것입니다. 

 

여기서 뒤의 항을 좀더 바꾸어 보도록 하겠습니다. P3의 마지막 조건에 의해 우리는 \[ \int_{V_i} U_i(x, p, v_i) f_i(v_i) dv_i = U_i(x, p, \underline{v_i}) + \int_\underline{v_i}^\overline{v_i} \left[ \int_\underline{v_i}^{v_i} Q_i (x, z_i) dz_i \right] f_i(v_i) dv_i  \]가 됨을 알 수 있습니다. 우변의 마지막 항의 적분 변수의 순서를 바꾸어 주면 \[ \begin{array}{rl} \displaystyle \int_\underline{v_i}^\overline{v_i} \left[\int_{z_i}^\overline{v_i} f_i(v_i) dv_i \right] Q_i(x, z_i) dz_i & \displaystyle = \int_\underline{v_i}^\overline{v_i} \left[ 1 - F_i(v_i) \right] Q_i(x, v_i) dv_i \\ & \displaystyle = \int_V \left[ 1 - F_i(v_i) \right] x_i(v) f_{-i}(v_{-i}) dv \\ & \displaystyle = \int_V \frac{1 - F_i(v_i)}{f_i(v_i)} x_i(v) f(v) dv \end{array} \]를 얻을 수 있습니다. 여기서 첫 번째 등식은 일관성을 위해 \(z_i\) 대신 \(v_i\)를 쓴 것뿐이며, 마지막 등식은 \(f_i(v_i)\)를 곱하고 나누어 준 것뿐입니다.

 

위에서 구한 것을 토대로 다시 식 1을 다시 적으면 우리는 경매사의 기대 수익이 \[ \int_V \sum_{i \in N} \left[ \left(v_i - \frac{1 - F_i(v_i)}{f(v_i)} \right) x_i(v) \right] f(v)dv - \sum_{i \in N} U_i(x, p, \underline{v_i}) \]이 됨을 알 수 있습니다. 여기서 한 가지 흥미로운 사실을 발견할 수 있습니다. 바로, 경매사의 기대 수익이 입찰자로부터 얻는 돈인 \(p\)에 직접적으로 연관되지 않는다는 것입니다. 대신, 어떤 두 경매 방식에 대해, 항상 동일한 승자를 정하고, 각 입찰자가 본인이 생각할 수 있는 최소의 가치를 적어 냈을 때의 기대 효용이 동일하다면 경매사의 기대 수익은 같습니다. 이러한 성질을 수익 동치 정리(revenue equivalance theorem)라고 부릅니다. 

정리 2. 수익 동치 정리

---

같은 환경의 서로 다른 두 경매 방식을 생각하자. 만약, 동일한 입찰가 \(v\)에 대해 동일한 입찰자를 선정하고, 각 입찰자 \(i\)에 대해 \(\underline{v_i}\)에서의 기대 효용이 동일하다면, 두 경매 방식에서 경매사의 기대 수익은 동일하다.

적절한 지불 방식

지금까지의 내용을 정리해 봅시다. 우리는 다음의 최적화 문제를 얻은 상태입니다.

\[ \begin{array}{lll} \text{maximize} & \displaystyle \int_V \left[ \sum_{i \in N} \left( v_i - \frac{1 - F_i(v_i)}{f_i(v_i)} \right) x_i(v) \right] f(v) dv - \sum_{i \in N} U_i(x, p, \underline{v_i})  \\ \text{subject to} & \displaystyle \sum_{i \in N} x_i(v) \leq 1, & \forall v \in V, \\ &\displaystyle x_i(v) \geq 0, & \forall i \in N, \forall v \in V, \\ & Q_i(x,s_i) \leq Q_i(x, v_i), & \forall i \in N, \forall s_i \leq v_i, \\ &\displaystyle U_i(x, p, \underline{v_i}) \geq 0, & \forall i \in N, \\ & \displaystyle U_i(x, p, v_i) \displaystyle = U_i(x, p, \underline{v_i}) + \int_\underline{v_i}^{v_i} Q(x, z_i) dz_i, & \forall i \in N, \forall v_i \in V_i. \end{array} \tag{P4} \]

그런데 수익 동치 정리에서도 알 수 있듯이, 기대 수익은 각 입찰자의 지불 금액에 크게 관련이 없습니다. 오히려 모든 입찰자 \(i\)에 대해 \(U_i(x, p, \underline{v_i}) = 0\)을 만족시켜 줄 수 있다면 목적 함수는 더 이상 \(p\)와는 아무런 관계가 없어 집니다. \(p\)가 필요한 지점은 마지막 두 제약 조건 때문입니다. 따라서 적절한 지불 방식 \(p\)를 직접 한번 만들어 봅시다.

 

먼저 \(U_i(x, p, \underline{v_i}) = 0\)을 만족시키면 좋다고 하였습니다. 이를 풀어 보면, \[ U_i(x, p, \underline{v_i}) = \int_{V_{-i}} [\underline{v_i} x(\underline{v_i}, v_{-i}) - p(\underline{v_i}, v_{-i})] f_{-i}(v_{-i}) dv_{-i} = 0 \]이어야 합니다. 만약, 우리가 \[ p(\underline{v_i}, v_{-i}) = \underline{v_i} x(\underline{v_i}, v_{-i}) \tag{2} \]로 둔다면 위 식은 항상 성립하게 됩니다. P4의 네 번째 제약 조건은 여기서 바로 유도할 수 있습니다.

 

마지막 제약 조건을 살펴 봅시다. 앞에서 \( U_i(x, p, \underline{v_i}) = 0 \)이 되도록 한다고 하였습니다. 따라서 우리는 \[ U_i(x, p, v_i) = \int_{V_{-i}} [v_i x(v) - p(v)] f_{-i}(v_{-i}) dv_{-i} = \int_\underline{v_i}^{v_i} Q(x, z_i) dz_i = \int_{V_{-i}} \int_\underline{v_i}^{v_i} x(z_i, v_{-i}) dz_i f_{-i}(v_{-i}) dv_{-i}\]를 만족시키기만 하면 됩니다. 만일 모든 \(v_{-i} \in V_{-i}\)에 대해, \[ v_i x(v) - p(v) = \int_\underline{v_i}^{v_i} x(z_i, v_{-i}) dz_i \tag{3} \]가 된다면, 우리는 위 식이 성립한다는 것을 알 수 있습니다. 

 

식 2와 3을 모두 만족시키는 방법은 각 입찰자 \(i \in N\), 임의의 \(v \in V\)에 대해, \[ p_i(v) = v_i x(v) - \int_\underline{v_i}^{v_i} x(z_i, v_{-i}) dz_i \tag{4} \]로 두는 것입니다. 그러면 P4의 마지막 두 제약 조건을 모두 만족할 뿐더러 목적 함수에서 \(U_i(x, p, \underline{v_i})\)의 영향도 없앨 수 있습니다. 이제 P4에서 해당하는 부분을 모두 제외한 다음의 최적화 문제를 생각해 봅시다.

\[ \begin{array}{lll} \text{maximize} & \displaystyle \int_V \left[ \sum_{i \in N} \left( v_i - \frac{1 - F_i(v_i)}{f_i(v_i)} \right) x_i(v) \right] f(v) dv \\ \text{subject to} & \displaystyle \sum_{i \in N} x_i(v) \leq 1, & \forall v \in V, \\ &\displaystyle x_i(v) \geq 0, & \forall i \in N, \forall v \in V, \\ & Q_i(x,s_i) \leq Q_i(x, v_i), & \forall i \in N, \forall s_i \leq v_i. \end{array} \tag{P5} \]

앞의 논의를 통해 우리는 다음의 결과를 얻을 수 있습니다.

정리 3. 최적 경매의 형태

---

P5의 최적해를 \(x\)라고 하고, 식 4에 이 \(x\)를 넣어서 얻은 것을 \(p\)라고 하자. 그러면 \((x, p)\)는 최적 경매이다.

레귤러 분포 (Regular Distribution)

P5와 식 4를 통해 우리는 최적 경매를 하나 찾을 수 있게 되었습니다. 하지만 P5는 딱 보기에 풀기 쉬워 보이지 않습니다. 하지만 특정한 조건이 있다면 우리는 이 문제를 훨씬 간단히 해결할 수 있습니다. 모든 입찰자 \(i\)에 대해서, \[ \phi_i(v_i) := v_i - \frac{1 - F_i(v_i)}{f_i(v_i)} \]가 증가하기만 한다고 합시다. 이러한 조건을 만족하는 확률 분포를 레귤러 분포(regular distribution)라고 부릅니다. (정규 분포라고 적고 싶었지만 normal distribution이 있어서 포기했습니다.)

 

균등 분포(uniform distribution), 정규 분포, 지수 분포(exponential distribution) 등 많은 분포들이 레귤러 분포에 속한다고 합니다. 물론 모든 분포가 레귤러 성질을 만족하는 것은 아닙니다. 실례로 다음의 확률 밀도 함수를 갖는 분포는 레귤러하지 않습니다. \[ f(v) := \begin{cases} 1/2, & 0\leq v < 1, \\ 1/4, & 1 \leq v \leq 3. \end{cases} \] 직접 계산해 보시기 바랍니다.

 

이제 다음과 같은 경매 방식을 생각해 봅시다. 아래에서는 할당 방법만 소개합니다. 지불 금액은 아래에서 식 4를 통해 얻을 예정입니다.

방법 1. 레귤러 분포 최적 경매

---

입력: 독립된 레귤러 분포 \(F_i\)를 갖는 입찰자 \(i \in N\)

출력: 낙찰자 선정 방법 \(x\)

 

1. 모든 입찰자 \(i\)로부터 \(v_i\)를 받는다.
2. 모든 입찰자들의 \( \phi_i(v_i) \)를 계산한다. 일반성을 잃지 않고 가장 큰 \(\phi_i(v_i)\)의 입찰자를 1이라고 하자.
3. \( \phi_1(v_1) \geq 0 \)일 때만 입찰자 1에게 물건을 준다 (즉, \(x_1(v) \gets 1\)). 그렇지 않으면 아무에게도 넘기지 않는다.

이렇게 할당하는 방법이 P5의 최적해임을 보이겠습니다. 먼저 제약 조건을 살펴 보죠. 위 방법을 보면 \(v\)가 어떻게 입력이 되든지 간에 최대 한 명의 입찰자에게만 물건을 할당합니다. 따라서 첫 번째 제약 조건은 성립함을 알 수 있습니다. 두 번째 제약 조건은 자명합니다.

 

마지막 제약 조건을 따져 봅시다. 어떤 입찰자 \(i\)에 대해, 다른 입찰자들의 입찰가가 \(v_{-i}\)로 고정된 상황을 가정해 봅시다. 임의의 \(s_i \leq v_i\)에 대해, 위 입찰자가 \(s_i\)를 제출했을 때 경매에서 승리했다면, \(\phi_i(\cdot)\)이 증가 함수라는 성질 때문에 분명 \(v_i\)를 제출했을 때에도 경매에서 승리했을 것입니다. 그러므로 \(s_i\)에서보다 \(v_i\)일 때 물건을 받을 확률이 높죠. 여기서 \(v_{-i}\)에 대한 가정을 풀어 준다면, \(Q_i(x, s_i) \leq Q_i(x, v_i) \)는 바로 얻을 수 있습니다.

 

이 방법이 최적해라는 것은 그리 어렵지 않습니다. \(v \in V\)가 어떻게 입력되었든지 간에 우리는 \(\phi_i(v_i)\)가 가장 큰 입찰자에게 0보다 작지 않을 때 물건을 몽땅 넘기기 때문입니다. 따라서 가능한 모든 경우에서 매번 최선의 선택을 하므로 이 방법 또한 최적입니다.

 

이렇게 위에서 얻은 할당 방법이 최적의 방법임을 알았습니다. 그럼 각 입찰자로부터 돈은 얼마큼 받으면 될까요? 식 4를 다시 가지고 오겠습니다.

\[ p_i(v) = v_i x_i(v) - \int_\underline{v_i}^{v_i} x_i(z_i, v_{-i}) dz_i. \]

먼저 입찰자 \(i\)가 아무것도 할당받지 못한 경우, 즉 \(x_i(v) = 0\)인 경우를 생각해 봅시다. 그러면 \(\phi_i(\cdot)\)가 증가한다는 조건에 의해 \(v_i\)보다 작은 어떤 \(z_i\)를 제출해도 \(x_i(z_i, v_{-i}) = 0\)이 될 것입니다. 따라서 \(p_i(v) = 0\)입니다.

 

이제 입찰자 \(1\)이 물건을 쟁취한 경우를 생각해 봅시다. 일반성을 잃지 않고 입찰자 2가 두 번째로 큰 \(\phi_i(v_i)\)를 갖고 있었다고 해 보죠. 그러면 \(v_{-1}\)이 고정된 상태에서 입찰자 \(1\)은 얼마나 낮은 값을 낼 때까지 물건을 할당 받을 수 있을까요? 만약 \(\phi_2(v_2) \geq 0\)이라면 \( \phi_1(z_1) = \phi_2(v_2) \)가 되는 \(z_1\)일 것입니다. 반대로 \(\phi_2(v_2) < 0 \)이라면 \( \phi_1(z_1) = 0 \)이 되는 지점이겠죠. 다시 말해, \[v_1^\circ := \phi_1^{-1}(\max\{ \phi_2(v_2), 0 \})\]보다 크거나 같은 \(z_1\)을 가지면 할당을 받게 될 것입니다. 이를 정리하면 \[ p_1(v) = v_1 x_1(v) - \int_\underline{v_i}^{v_i} x_i(z_i, v_{-i}) dz_i = v_1 - (v_1 - v_1^\circ) = v_1^\circ \] 만큼 내면 된다는 사실을 확인할 수 있습니다.

동일한 분포를 갖는 경우

마지막으로 모든 입찰자가 동일한 레귤러 분포를 갖는 경우를 고려해 보겠습니다. 그러면 \( \phi(v_2) \geq 0 \)인 경우에 입찰자 1이 지불하는 금액은 \[ \phi^{-1}(\phi(v_2)) = v_2\]가 됩니다. 즉, 두 번째로 높은 입찰가에 해당하죠. 반대로 \(\phi(v_2) < 0\)이라면 승자는 \( \phi^{-1}(0) \)의 금액만큼 지불해야 합니다. 이 상황을 좀더 직관적으로 설명하자면 이는 판매자가 \(\phi^{-1}(0)\)의 입찰가로 참가한 상태에서 비크리 경매를 수행한 것과 같습니다.

 

서론에서 두 입찰자가 독립적으로 각각 \(U[0,1]\)에서 물건의 가치를 뽑는 경우를 생각해 보겠습니다. \(U[0, 1]\)의 \(\phi\)를 계산하면 \[ \phi(v) = 2v - 1 \]이 되는 것을 알 수 있습니다. 따라서 판매자가 \( \phi^{-1}(0) = 1/2 \)의 입찰가로 참가한 상태에서의 비크리 경매는 판매자에게 최대의 기대 수익을 가져다 줍니다. 이는 서론에서 제시한 방법이 실지로 최적 경매라는 사실을 알려 줍니다.

마치며

이것으로 최적 경매에 대한 설명을 마칩니다. 경매 및 메커니즘 설계는 경제·경영학을 필두로 한 사회과학 분야에서 시작했지만 현재는 컴퓨터과학 분야에서도 활발히 연구가 되는 주제입니다. 요즘 이와 관련하여 학교에서 세미나를 진행하고 있습니다.  관심 있으신 분들은 아래 링크로 방문하시기 바랍니다.

Yonsei CS Theory Student Group

이번에 어쩌다 보니 예정에 없던 최적 경매를 주제로 발표를 하게 되었습니다. 예전부터 언젠간 블로그에 적어야 겠다고 생각하기도 했고, 발표 준비를 마치고 나니 이대로는 약간 아쉬운 마음이 들기도 해서 블로그에도 포스팅을 합니다. 물론 토요일은 휘리릭 사라졌지만, 괜찮습니다. 내일은 일요일이거든요.

 

본문의 최적 경매는 크게 몇 가지 정도 발전시킬 방향이 있습니다.

1. 본문에서의 경매는 모든 입찰자가 자신의 가치를 적어 경매사에게 제출하고, 경매사는 바로 낙찰자를 결정하는 방식으로만 진행된다고 가정하였습니다. 세상에는 다양한 종류의 경매 방식이 있습니다. 과연 그러한 경우를 포함해서도 본문의 방식이 최선일까요?
2. 본문에서는 경매로 나온 물건이 하나뿐이라는 가정을 합니다. 혹시 여러 개의 물건이 나오고, 입찰자들 또한 여러 개의 물건을 원하는 상황에는 어떻게 될까요?
3. 본문에서는 입찰자들의 효용이 \(v_i x_i(v) - p_i(v)\)와 같이 선형적(linear)입니다. 비선형 효용의 경우에는 어떻게 될까요?
4. 본문에서는 입찰자들의 확률 분포가 레귤러하다는 가정을 했을 때에만 간단한 경매 방법을 제시합니다. 혹시 레귤러하지 않은 분포에 대해서도 쉬운 경매 방법을 제시할 수 있을까요?

이제부터는 위 질문에 대한 답을 공부해 보고자 합니다. 이 중 몇 개는 이미 알고 있고, 또 몇 개는 학교에서 진행하는 학생 세미나에서 다룰 것 같습니다. 위 내용들에 대해서 잘 공부한 다음, 블로그에 정리해 보도록 하겠습니다.

 

읽어 주셔서 고맙습니다. :)

참고 문헌

[1] Roger B. Myerson. "Optimal auction design." Mathematics of operations research 6, no. 1 (1981): 58-73.

 

[2] Jason D. Hartline. "Mechanism design and approximation." (2013) Link: https://jasonhartline.com/MDnA/