Bilateral Trade and Myerson-Satterthwaite Theorem (1)

이 글에서 보이고자 하는 정리가 무엇인지 말하기 전에 문제를 하나 정의하고자 한다.

 

Bilateral Trade

사람1(판매자, seller)와 사람2(구매자, buyer)가 있다. 현재 상황은 사람1이 사람2에게 물건을 파는 상황이다. 사람1은 속으로 '이 물건의 가치가 얼마나 되지?'라고 생각한다. 그리고 잠시 후에 $v_1$의 값이 머릿속에서 떠올랐다. 사람2도 마찬가지로 $v_2$의 값이 머릿속에 떠올랐다. (물건이 입력으로 주어졌을 때 머리가 값을 출력했다고 보면 좋을 것 같다.)

 

(아직까지는 누가 얼마를 내고 얼마를 받고는 생각하지 말고 일단은) 어찌어찌 물건이 사람1에서 사람2에게 전달되었다고 생각하자. 이것을 사회의 관점에서 보았을 때, 물건이 그것의 가치를 $v_1$으로 생각하는 사람에서 그것의 가치를 $v_2$으로 생각하는 사람으로 이동했다고 볼 수 있다. 따라서 사회가 이 trade에서 얻은 surplus는

$$v_2-v_1$$

이다. 여기에 추가적인 설정을 하고자 한다. 앞서 각 사람이 머리 속에서 값을 떠올렸다고 했는데, 이때 각 사람의 머릿속의 분포를 알 수 있다고 가정해서, 이를 특정 분포에서 값을 뽑았다고 말할 것이다. 사람의 머리 속 분포를 아는 것은 매우 비현실적일 수 있으니, 판매/구매 히스토리를 모아서 어떤 분포를 만들고 그것을 대신 사용한다고 생각하자. 이 히스토리는 모두에게 공개되어 있어서 누가 어떤 분포를 따르는지 알 수 있다고 가정할 것이다.

 

문제 세팅을 다시 기술해보자. 사람1과 사람2의 분포는 각각 $[a_1,b_1],[a_2,b_2]$의 범위에서 정의된다고 할 것이고 각각에 대한 probability density function을 각각 $f_1,f_2$로, cummulative density function을 각각 $F_1,F_2$라고 부를 것이다. 이때 $f_1$과 $f_2$는 범위 내에서 연속이면서 양의 density를 갖는다고 가정할 것이다. 앞서 말한 것처럼 각 사람의 분포는 공개되어 있다. 하지만 trade가 일어나기 전에 각 분포에서 뽑히는 (혹은, 원래 표현대로 하자면 각자 머릿속으로 떠올리는) 값 $v_1,v_2$는 혼자만이 알고 있다. 

 

세팅이 완료되었다. 이제 각 사람은 자신의 효용(의 기댓값)을 최대화시키기 위해 노력을 한다. (Trade가 일어났을 때 사람1의 효용은 판매 가격에서 $v_1$을 뺀 것이고 사람2의 효용은 $v_2$에서 구매 가격을 뺀 것이다. Trade가 일어나지 않으면 둘 다 효용은 0이다.)

 

Mechanism

사실 위의 설명만으로는 "그래서 trade는 어떻게 이루어지는데?"가 명확하지 않다. 앞서 제껴뒀던 "누가 얼마를 내고 얼마를 받고" 문제를 생각해보자. 간단한 trade 메커니즘을 생각해보고자 한다.

Seller Pricing Mechanism
1. 판매자(사람1)가 가격 $r$을 제시
2. 구매자(사람2)가 제시된 가격을 보고 trade를 할지 말지 결정, trade를 한다면 $r$을 사람1에게 지불

이때 사람1은 자신의 효용의 기댓값을 최대화시키기 위해 최적은 가격을 고를 것이다. 수식으로 표현해보자. Trade가 일어나면 사람1의 효용은 $r-v_1$이고 일어나지 않으면 효용은 0임을 기억하자. Trade가 언제 일어날지 생각해보면, 사람2 입장에서 제시된 가격이 자신이 생각하는 가치($v_2$)보다 작으면 무조건 trade할 것이고 크면 하지 않을 것이다. 사람1은 $v_2$를 직접적으로 알 수 없으니 확률변수 $V_2$로 생각할 것이다. 그렇다면 사람1 입장에서 가격 $r$을 제시했을 때 얻는 효용의 기대값은

$$(r-v_1)\cdot Pr[V_2>r]=(r-v_1)\cdot (1-Pr[V_2\le r])$$

이다. 이때 사람2의 분포에 대한 정보를 알고 있으니 위 식을 다음과 같이 적을 수 있다.

$$(r-v_1)\cdot (1-F_2(r))$$

사람1은 이 값을 maximize하는 $r$을 사람2에게 제시하는 것이다.

 

마찬가지로 사람2가 판매 가격을 먼저 제시하는 메커니즘을 생각할 수 있다.

Buyer Pricing Mechanism
1. 구매자(사람2)가 가격 $r$을 제시
2. 판매자(사람1)가 제시된 가격을 보고 trade를 할지 말지 결정, trade를 한다면 $r$을 사람2에게 받음

비슷한 과정으로 사람2는 자신의 효용의 기댓값을 최대화시키는 가격, 즉 다음 수식을 maximize하는 $r$을 고를 것이다.

$$(v_2-r)\cdot Pr[V_1\le r]=(v_2-r)\cdot F_1(r)$$

 

Direct Mechanism

복잡하지만 더 일반화된 메커니즘을 생각해보자. 일종의 플랫폼인데 사람1과 사람2이 제시(report)한 값을 보고, trade를 할지 안 할지랑 그때 사람1이 받을 가격, 사람2가 지불할 가격을 결정해준다. 아래 그림에 이를 더 구체적으로 설명해 놓았다.

이 메커니즘은 $(p,x_1,x_2)$로 정의된다. 사람1과 사람2가 플랫폼에 report한 값을 각각 $v_1^{\prime },v_2^{\prime }$라고 하자. (이 값은 꼭 자신의 실제 값 $v_1,v_2$가 아니어도 된다.) 이 메커니즘은 $p(v_1^{\prime },v_2^{\prime })$의 확률로 trade를 하기로 결정하고 나머지의 확률로 trade를 하지 않기로 결정한다. (Trade가 일어났을 때) 사람1이 받을 금액은 $x_1(v_1^{\prime },v_2^{\prime })$로, 사람2가 지불할 금액은 $x_2(v_1^{\prime },v_2^{\prime })$로 정해진다. (이 두 값은 꼭 같을 필요가 없다. 만약 사람2가 지불하는 금액이 사람1이 받는 금액보다 크면, 그 차이만큼은 수수료로서 이 메커니즘(플랫폼)이 갖는 것으로 생각해도 된다. 반대의 경우는 이 메커니즘이 보조금으로서 지불하는 것으로 생각할 수 있다.) 여기서 중요한 점은 메커니즘 또한 실제 $v_1,v_2$를 알지 못하고 분포 정보 $F_1,F_2$만 알고 있다는 점이다.

 

왜 일반화인가?

이것이 왜 앞의 두 간단한 메커니즘의 일반화인지 설명하고자 한다. 다음의 간단한 메커니즘 $(p,x_1,x_2)$을 생각해보자.

• 만약 $v_1^{\prime }<v_2^{\prime }$라면 $p(v_1^{\prime },v_2^{\prime })=1$이고 아니면 $p(v_1^{\prime },v_2^{\prime })=0$이다. (고로 deterministic한 메커니즘이다.)
• $x_1(v_1^{\prime },v_2^{\prime })=x_2(v_1^{\prime },v_2^{\prime })=v_1^{\prime }$

사람2의 입장에서 이 메커니즘을 생각해보자. 자신이 어떤 값을 report하든 가격에 영향을 주지 않음을 확인할 수 있다. 이로부터 사람2의 최선의 전략, 즉 자신의 효용을 최대화하는 방법은 자신의 실제 값을 report하는, 즉 truthful reporting임을 알 수 있다. 예를 들어 이 물건의 값을 5라고 생각했지만 7이라고 report했을 때 만약 상대가 6을 report했다면 trade가 이루어지고 1의 손해가 발생한다. 만약 3이라고 report했는데 상대가 4를 report했다면 1의 이득을 얻을 수 있었지만 trade가 발생하지 않는다.

 

이제 사람2는 truthful reporting을 한다는 가정을 깔고 사람1의 입장에서 생각해보자. 사람1은 Seller Pricing Mechanism에서 설정했을 가격을 report하는 것이 최선의 전략이다. 즉 report할  $v_1^{\prime }$값을 $argmax[(r-v_1)\cdot (1-F_2(v_1))]$ 으로 설정하는 것이다. 최선의 전략인 이유는 만약 더 큰 값을 report했다면 원래는 trade를 할 수 있었지만 못하는 손해가 가격을 높게 책정해서 얻는 이득보다 크고, 더 작은 값을 report했다면 원래 report할 값을 고른 방식에 의해 효용이 최대화되지 않기 때문이다.

 

물론 수식으로 보이지 않았지만 위가 성립한다면 Seller Pricing Mechanism에서의 결과와 이 간단한 메커니즘에서의 결과가 동일함을 알 수 있고 마찬가지의 방법으로 Buyer Pricing Mechanism도 그러함을 보일 수 있다.

 

왜 "direct" 메커니즘인가?

메커니즘이 결정에 있어서 "직접적"이기 때문이다. Indirect mechanism의 예는 다음과 같다. 두 사람이 동시에 값을 report하고 구매자의 report가 판매자의 report보다 크면 둘의 중간값을 가격으로 설정하는 것이다. 여기서 메커니즘은 결정에 있어서 "간접적" 역할로 남는다.

 

Notations

이제 Myerson-Satterthwaite 정리가 뭔지 설명하기 위한 용어들을 정의하고자 한다. 

1. Bayesian Nash Equilibrium (BNE)
2. Bayesian (Nash) Incentive Compatible (BIC)
3. Revelation principle
4. Individually Rational (IR)
5. Weakly/Strongly Budget Balanced (WBB, SBB)
6. ex post efficient

1. Bayesian Nash Equilibrium

어떤 game에서 각 player $i$들의 strategy $s_i$를 모은 집합을 strategy profile $S$이라고 하자. Strategy profile $S$가 만약 모든 player $i$에 대해서 $s_i$가 $i$를 제외한 나머지 player들의 strategy에 대한 최선의 대응이라면 $S$는 Bayesian Nash Equilibrium (BNE)이라고 부른다.

예시로 이해해보자. 현재 game은 bilateral trade이다. Player는 사람1, 사람2 이렇게 두 명이 있다. 아까 Seller Pricing Mechanism과 동일한 결과를 내는 간단한 direct mechanism을 $M$이라고 하자. 이때 메커니즘만 정의한 것이 아니라 각 사람의 reporting 전략도 생각을 했다. 다시 적자면, 사람1의 strategy $s_1$은 $v_1$이 주어졌을 때 자신의 효용 기댓값을 최대화시킬 가격을 report하는 것이었고, 사람2의 strategy $s_2$는 $v_2$를 있는 그대로 report하는 것이었다.

 

여기서 strategy profile $S=\{s_1,s_2\}$는 BNE일까? 다시 말해, 각 사람의 전략은 다른 사람의 전략에 대한 최선의 대응, 즉 각자의 효용의 기댓값을 최대화하는 전략일까? 그렇다! 

 

2. Bayesian Incentive Compatible

Bayesian Nash Equilibrium의 정의를 안다면 Bayesian (Nash) Incentive Compatible (BIC)의 정의는 간단하다.

Bayesian incentive compatible (BIC) 메커니즘은 truthful reporting이 Bayesian Nash Equilibrium를 이룰 때를 말한다.

다시 말하자면, 내가 이 게임의 한 player고 다른 사람들이 truthful reporting을 한다는 것이 기대된다면, 나도 truthful reporting을 하는 것이 최선의 대응, 즉 나의 효용을 최대화시킨다는 것이다. 위의 예시에서 해당 메커니즘은 BIC를 만족할까? 그렇지 않다! 사람2는 truthful reporting이 BNE에서의 전략이지만, 사람1의 전략은 truthful reporting이 아니기 때문이다.

 

3. Revelation Principle

다음 개념을 소개하기 위해 우리는 BNE가 존재하는 임의의 (Bayesian) mechanism $M$을 하나 생각할 것이다. 재밌는 사실이 알려져 있는데, 그것은 $M$과 동일한 결과를 내면서 BIC를 만족하는 mechanism $M^{\prime }$을 만들 수 있다는 것이다. 이것이 가능함을 말하는 원칙이 바로 Revelation principle이다. 기본적인 아이디어는 $M$의 BNE strategy profile을 $M^{\prime }$의 과정으로 포함시키는 것이다.

 

아까의 예시를 살펴보자. 우리가 다음의 함수를 $r(v)\in {argmax}_r[(r-v_1)\cdot (1-F_2(r))]$라고 정의한다면, 해당 메커니즘에서 BNE strategy profile을 $\{s_1(v_1)=r(v_1),s_2(v_2)=v_2\}$라고 적을 수 있다. 이때 우리가 $M^{\prime }$을 다음과 같이 설정했다고 생각하자.

• 만약 $r(v_1^{\prime })<v_2^{\prime }$면 $p(v_1^{\prime },v_2^{\prime })=1$이고 아니면 $p(v_1^{\prime },v_2^{\prime })=0$으로 설정한다.
• $x_1(v_1^{\prime },v_2^{\prime })=x_2(v_1^{\prime },v_2^{\prime })=r(v_1^{\prime })$

정리하자면 $M$에서 원래 사람1이 계산하던 가격을 $M^{\prime }$에서는 메커니즘이 대신 해주는 것이다. 이러한 메커니즘에서는 $\{v_1,v_2\}$가 BNE를 이룬다. 그리고 BNE에서의 모든 사람의 strategy가 truthful reporting이므로 이 메커니즘은 BIC를 만족한다.

 

Revelation principle에 따라서 앞으로 우리는 BNE strategy profile이 존재하는 메커니즘에서 BIC 메커니즘을 두고 논의를 진행할 것이다.

 

4. Individually Rational

모든 player는 자신의 효용을 최대화하려고 노력한다. 하지만 어떨 때에는 그럼에도 불구하고 어떤 player는 음의 효용을 가질 수도 있다. 우리는 모든 player가 항상 음이 아닌 효용을 가질 때 그 메커니즘을 individually rational (IR)이라고 부른다. 따라서 IR이면서 BIC인 메커니즘에서는 다른 사람들에 truthful reporting을 한다면, 자신도 truthful reporting을 하는 것이 효용을 최대화하고 그 값은 음수가 아니라는 것이다.

 

5. Weakly/Strongly budget balanced

Seller/Buyer Pricing Mechanism을 생각해보자. 사람1이 받는 금액과 사람2가 받는 금액은 어떤 경우에서든지 항상 동일하다. 이런 경우를 Strongly budget balanced (SBB)라고 부른다. 하지만 일반적인 direct mechanism에서는 $x_1$ 함수에 의해 정해지는 사람1이 받는 금액, $x_2$함수에 의해 정해지는 사람2가 낼 금액이 다를 수 있다. 이때 어떤 상황에서든지 사람2가 내는 금액보다 이 사람1이 받는 금액이 크지 않다면 그런 메커니즘을 Weakly budget balanced (WBB)라고 부른다. WBB 성질은 다시 말해서 플랫폼(메커니즘)이 수수료를 떼어 가는 일은 있어도 보조금을 지급하는 일은 없다는 뜻이다.

 

6. ex post efficient

'ex post'의 사전전 의미는 '사후의'라는 뜻이다. 가능한 모든 경우에 대해 그것의 trade 메커니즘이 끝나고 모든 것을 알게 되었다고 생각하자. 이때 각자의 private 값을 봤을 때, $v_2$가 $v_1$보다 큰 경우에 trade가 항상 일어나고 그렇지 않은 경우에 trade가 항상 일어나지 않았다면, 그러한 메커니즘을 ex post efficient라고 한다.

 

Myerson-Satterthwaite Theorem

이제 Myerson-Satterthwaite Theorem을 적을 준비가 되었다. Bilateral trade에서 $f_1$과 $f_2$가 각각 $[a_1,b_1],[a_2,b_2]$에서 continuous하면서 positive density를 갖는다는 가정을 했음을 기억하자. 이때 구간 $[a_1,b_1]$과 구간 $[a_2,b_2]$ 가 겹치지 않는다고 해보자. 이때 $b_1\le a_2$라면, 즉 사람2가 물건에 항상 더 높은 가치를 둔다면, $(b_1+a_2)/2$의 가격으로 trade를 하는 메커니즘은 ex post efficient하고 $b_2\le a_1$이라면, 즉 사람1이 물건에 항상 더 높은 가치를 둔다면, trade를 하지 않는 메커니즘이 ex post efficient하다. 따라서 구간이 겹치지 않는다면 나름 자명한 메커니즘을 고안할 수 있다.

 

따라서 우리는 $a_2<b_1,a_1<b_2$를 가정해서 두 구간이 겹친다고 가정할 것이다. 해당 설정에서 Myerson-Satterthwaite 정리는 다음과 같다고 말한다.

(Myerson and Satterthwaite, 1984)
No BIC, IR, WBB mechanism can be ex post efficient.

 

즉 메커니즘이 BIC, IR, WBB 조건을 만족시키면서 ex post efficient할 수는 없다는 것이다.

 

다음 포스트에서 이것의 증명과 이와 관련해서 최근에 새롭게 알려진 사실을 소개하고자 합니다.

 

 

---

Q. 메커니즘은 항상 BND strategy profile이 있는가?

일반적으로 그렇지 않지만 특정한 상황에서는 항상 존재한다는 것이 알려져 있다. Nash Theorem의 variant를 하나 살펴보고자 한다. (다음을 참고. https://economics.mit.edu/files/4874, 17번째 slide)

Consider a finite incomplete information (Bayesian) game.
Then a (mixed) strategy Bayesian Nash equilibrium exists.

 

Incomplete information은 다른 player의 "정보"를 완전히 알 수 없는 것을 말한다. Finite game은 player의 수가 finite하고 각 player가 취할 수 있는 strategy의 수가 finite하고 finite round에 끝나는 게임을 말한다. 우리가 다루고 있는 bilateral trade는 다른 사람의 private 값을 알 수 없고 분포만 알 수 있으므로 incomplete하고, 사람의 수가 2명으로 finite하고 한 round에 끝나기 때문에 finite round를 가지지만 strategy의 수는 무한하기에 finite game이라고 보기는 어렵다. (자신의 값을 그대로 report해도 되고 0.1을 더해서 report해도 되고 0.001을 더해서 report를 해도 되기 때문이다.) 따라서 위 정리의 조건을 약간 확장해서 적고자 한다.

Consider a Bayesian game with continuous strategy spaces and continuous types. If strategy sets and type sets are compact, payoff(utility) functions are continuous and concave in own strategies, then a (pure) strategy Bayesian Nash equilibrium exists.

 

여기서 type는 자신의 private 값을 말한다. 즉 사람1의 type은 $v_1$이고 사람2의 type은 $v_2$이다. 각 사람의 가능한 type는 continuous하고 compact하다. 사람1은 $[a_1,b_1]$에서 자신의 값이 골라지고, 사람2는 $[a_2,b_2]$에서 자신의 값이 골라지기 때문이다. Strategy는 continuous하지만 compact하지 않다. 하지만 만약 사전에 적당히 큰/작은 값을 골라 그것으로 report할 수 있는 값에 bound를 준다면 원래 문제를 크게 바꾸지 않으면서 compact 성질까지 만족시킬 수 있을 것이다.

Utility function은 concave한가? 이것은 $p,x_1,x_2$를 어떻게 설정하느냐에 따라 다르다. 만약 utility function이 각자의 strategy에 concave하도록 만들 수 있다면 우리는 그 메커니즘에 BNE strategy profile이 존재한다고 말할 수 있을 것이다. 그리고 그렇다면 revelation principle에 의해 우리가 생각하는 메커니즘이 BIC 메커니즘이라고 생각해도 무방할 것이다.