Myerson’s Lemma와 Auction Design

 

 

Single-Parameter Environment

Auction(경매)의 한 형태를 살펴보도록 하자. $n$명의 bidder(응찰자)들이 있고 각 bidder $i$는 경매에서 다룰 물건에 대해 각자가 생각하는 true valuation $v_i$가 있다. 이 $v_i$는 $i$만 알고있는 "private"한 정보이다. 즉, 이 값은 $i$가 아닌 다른 bidder나 auctioneer(경매인)에게는 공개되지 않는다.

 

경매가 시작되면 각 bidder는 물건에 대해 $b_i$만큼을 bidding한다. 경매인은 모든 bidder들로부터 bidding 금액을 받고 그 정보로 (1) 누구에게 물건을 줄지와 (2) 그 물건에 대해 받은 bidder가 지불해야할 가격을 정한다.

 

(1) Allocation

(1)번을 수식적으로 표현해보자. $x_i$를 bidder $i$가 물건을 땄는지 안땄는지를 나타내는 0-1 변수로 생각하자. 그러면 

$$\sum_{i=1}^n{x_i}\le 1$$

라고 적을 수 있다. 등호가 아닌 부등호인 이유는 (1)번 과정에서 경매인은 누구에게도 물건을 팔지 않아도 되기 때문이다.

경매의 상황에 따라 물건이 하나가 아니라 여러개일 수 있다. 만약 동일한 물건이 총 $k$개가 있고 각 bidder는 최대 하나의 물건만 얻을 수 있다고 하면 $x$는 여전히 0-1 vector인 상태에서 수식은 다음과 같이 된다.

$$\sum_{i=1}^n{x_i}\le k$$

또, 상황에 따라서 물건이 $k$개가 있는데 서로 동일하지 않을 수도 있다. 가령 인터넷에서 $k$개의 광고 slot이 있는데 user들의 click-through-rates (CTRs)가 각 slot마다 다를 수 있다. 사람들이 $j$번째 slot을 클릭할 확률을 $\alpha_j$라고 하자. (현실에서는 어떤 광고가 들어섰는지에 따라 클릭의 빈도가 달라지겠지만 여기서는 그렇지 않다고 가정한다. 또한 WLOG $\alpha_1\ge \cdots \ge \alpha_k$라고 가정하자.) $v_i$가 bidder $i$가 생각하는 click 하나의 true valuation이라면, $x_i$를 다음과 같이 정할 수 있다.

$$x_i = \begin{cases} \alpha_j,& \text{if bidder } i \text{ assigned to slot } j\\ 0,& \text{otherwise} \end{cases} $$

(이제 $x_i$는 물건을 받는지 여부라기보다 받는 물건의 양으로 생각하는 것이 더 적절할 것 같다.)

(2) Payment

(1)번에서와 같이 (2)번도 수식적으로 표현할 수 있다. $p_i$를 bidder $i$가 물건을 땄을 때 내야할 금액이라고 할 것이다. (우리는 $p_i\ge 0$이라고 가정을 할텐데 만약 그렇지 않다면 판매자가 bidder에게 역으로 돈을 주는 것과 같기 때문이다.)

---

Vector $b$를 모든 bidder들의 bidding을 원소로 하는 vector라고 부를 것이다. 우리가 하고 싶은 것은 $b$가 주어졌을 때 어떻게 $x, p$를 정해야 하는가? 즉 $x(b), p(b)$를 어떻게 설정해야 하는가?에 대한 답을 찾는 것이다.

혹자는 "가장 돈을 많이 내겠다고 한 사람에게 물건을 주고 그 물건에 대한 값은 내겠다고 한 만큼으로 하면 되는 것 아닌가?"라고 생각할 수 있다. 당연히 할 수 있는 질문이고 그러한 형태의 auction을 "First-Price Auction"이라고 부른다. "Second-Price Auction"이라는 형태도 있는데 이것은 first-price auction과 동일하지만 물건에 대한 값을 두번째로 높았던 bidding 금액만큼만 지불하게끔 한다. 예를 들어, 내가 100만원을 bidding했는데 그것이 최고 금액이었고 두번째로 높았던 bidding 금액이 85만원이었다면 (1) 내가 물건을 타고 (2) 물건의 값으로는 85만원을 내는 것이다. (물론 판매자가 안팔기로 결정하면 얻지 못할 수 있다.)

다시 처음의 질문으로 돌아가서 어떻게 $x(b), p(b)$를 설정해야 하는지 고민해보자. 사실 질문이 모호하다. "얻고자 하는게 뭔데? Objective가 뭔데?가 빠져있기 때문이다. 그것에 대해 얘기해보도록 하겠다.

 

Obejctive

• (dominant strategy = truthful bidding) 모든 bidder의 dominant strategy, 즉 자신의 utility를 maximize하는 전략이 자신이 생각하는 true valuation인 $v_i$만큼을 bidding하는 것이어야 한다. 
• (non-negative utility) 그렇게 bidding을 한 bidder는 마이너스 utility를 갖지 않는 것이 보장되어 있다.
• Bidder들이 truthful bidding을 하면 social surplus가 maximize된다.
• 그러한 auction이 무엇인지 polynomial time에 찾을 수 있다.

첫 두 조건을 묶어 DSIC (dominant-strategy incentive-compatible)라고 부른다. 여기서 dominant strategy는 다른 참여자가 어떠한 전략을 취하든, 이 전략이 나의 보수(여기서는 utility)를 최대화 한는 것을 말한다. 즉 다른 사람들이 어떻게 bidding을 하든 나는 내가 생각하는 $v_i$만큼 bidding을 하는 것이 나의 utility를 maximize한다는 것이다.

 

Utility

Bidder $i$의 utility를 $u_i$라고 하자. 경매에서 물건을 따지 못하면 utility는 0이고 물건을 딴다면 내가 생각하는 true valuation에서 지불해야하는 금액을 뺀 것이 utility가 된다. 내가 생각하는 물건 하나당 true valuation은 $v_i$이고 얻는 물건의 "양"은 $x_i(b)$이다. 지불해야 하는 금액은 $p_i(b)$이므로 bidder $i$의 utility를 다음과 같이 정의할 수 있다.

$$u_i(b):=v_i\cdot x_i(b) - p_i(b)$$

우리는 이 정보로부터 $p_i(b)$의 upper bound를 $b_i\cdot x_i(b)$로 정해줄 수 있다. 왜냐하면 만약 그렇지 않았다면 truthful bidder의 utility는 negative가 되기 때문이다.

 

Social Surplus

만약 bidder들이 truthful bidding을 하면, auction을 디자인하는 입장에서 bidder들의 (private한) true valuation이 뭔지 몰라도 (마치 알았던 것 마냥) 가장 높은 true valuation을 가진 bidder혹은 bidder들의 set을 찾아낸다는 것이다. 즉 $b$와 $v$가 같다면

$$\sum_{i=1}^n{v_i\cdot x_i(b)}$$

이 maximize되는 것이다.

 

---

이제 위 objectives를 만족하는 $x, p$가 어떻게 생겼는지 생각을 해보자. 그 전에 두 가지 중요한 정의를 할 것이다.

Definition. Implementable Allocation Rule

(Single parameter environment에서) 한 allocation rule $x$가 주어졌을 때, $(x,p)$를 DSIC가 되게끔하는 payment rule $p$가 존재하면, $x$는 implementable하다고 부를 것이다.

Definition. Monotone Allocation Rule

(Single parameter environment에서) 한 allocation rule $x$가 주어졌을 때, 모든 $i$와 $b_{-i}$에 대해서 $x_i(z,b_{-i})$의 값이 $z$가 증가함에따라 nondecreasing하다면, $x$는 monotone하다고 부를 것이다.

여기서 $b_{-i}$는 $b$에서 $i$에 해당하는 bidding을 제외한 vector이고 $z$는 $b_i$를 나타내는 값에 해당한다. 따라서 $x_i(z,b_{-i})$는 $b_i=z$이고 나머지는 $b_{-i}$인 bidding vector가 주어졌을 때 $i$로의 allocation을 의미한다.

Monotone allocation rule에 대해 예시를 들면, 앞에서 잠깐 소개한 first-price auction과 second-price auction은 모두 monotone한 allocation rule을 따른다. 한 bidder를 fix하고 나머지 bidding을 고정시킨 채 그 bidder의 bid를 높이면 allocation 값이 증가하기 때문이다. 그러나 만약 두번째로 높은 금액을 bid한 사람이 물건을 얻는 다면 그것은 monotone하지 않다. 마찬가지로 한 bidder를 fix하고 나머지 bidding을 고정시킨 채 그 bidder의 bid를 높이면 allocation 값이 언젠가는 감소하기 때문이다.

 

 

이제 Myerson's Lemma를 소개하도록 하겠다.

Myerson's Lemma

(Sigle parameter environment를 하나 고정하자.)

• $x$가 implementable한 것과 monotone한 것은 필요충분 관계이다.
• (b_i=0이 p_i(b)=0임을 뜻한다는 가정하에)만약 $x$가 monotone하다면 $(x,p)$를 DSIC로 만드는 unique한 $p$가 존재한다.
• 위의 unique한 $p$를 구하는 explicit formula를 찾을 수 있다.

 

증명

이것을 다음 step을 거쳐서 증명할 것이다.

(A) $x$가 monotone하지 않으면 implementable하지 않음을 보인다.

(B) $x$가 monotone하면 가능한 payment는 unique함을 보인다.

(C) 그 unique한 payment $p$는 $(x,p)$를 DSIC하게 만든다.

 

우선 $(x,p)$가 DSIC하다면 만족해야 할 조건을 찾을 것이다. (여기에는 $x$가 monotone하다거나 implementable하다는 가정은 들어가지 않는다.) DSIC 조건을 만족한다면 모든 $i$에 대해서 $b_{-i}$가 어떠하더라도 truthful bidding이 utility를 maximize해야 한다. 따라서 우리는 임의의 bidder $i$와 임의의 bidding vector $b_{-i}$를 고정할 것이다. Notation을 편하게 하기 위해 $x_i(z,b_{-i})$와 $p_i(z,b_{-i})$를 각각 $x_i(z), p_i(z)$라고 적도록 하겠다.

 

이제 아무 $0\le z < y$에 대해 다음 경우들을 생각해보자.

[Case 1] True valuation = $z$, False bid = $y$

[Case 2] True valuation = $y$, False bid = $z$

DSIC에 따라 true valuation으로 bidding했을 때의 utility가 그렇지 않을떄의 utitliy보다 크거나 같아야 한다. 이를 두 케이스에 적용해서 수식으로 적으면 다음과 같다.

$$\text{[Case 1] }u_i(z)=z\cdot x_i(z) - p_i(z) \ge z\cdot x_i(y) - p_i(y)=u_i(y)$$

$$\text{[Case 2] }u_i(y)=y\cdot x_i(y) - p_i(y) \ge y\cdot x_i(z) - p_i(z)=u_i(z)$$

두 식 모두 한쪽을 $p_i(y)-p_i(z)$로 만들어서 정리해보면 각각 lower bound와 upper bound를 구할 수 있다.

$$z \cdot [x_i(y) − x_i(z)] \le p_i(y) − p_i(z) \le y \cdot [x_i(y) − x_i(z)]$$

 

Part (A)

이제 $x$가 monotone하지 않았다고 가정해보자. 그렇다면 $x_i(y)-x_i(z)$의 값이 음수가 되는 $z,y$가 존재할 것이다. 그러면 위 수식에서 $-z \le -y$를 만족하게 되는데 $z<y$에 어긋나게 된다. 따라서 $(x,p)$를 DSIC하게 만드는 payment $p$가 존재하지 않는다.

 

Part(B)

이제 $x$가 monotone하다고 가정을 하자. 추가적으로 $x$가 piecewise-constant한 function이라고 가정을 하겠다. 예를 들어 물건이 하나인 auction에서 highest bid bidder가 물건을 받는 0-1 경우에는 $b_{-i}$중에서 highest bid까지는 $x_i(z)$가 0이고 그 이후부터 1일 것이다. 만약 상황이 인터넷 광고 slot auction이었다면 $i$의 bid가 $k$-th highest가 되기 전까지는 0일 것이고 그 이후부터는 $j$-th highest bid인 경우에는 $x_i(z)=\alpha_j$일 것이다. 

FIgure. Example of piecewise-constant function

이제 위의 DSIC 조건 수식에서 $z$를 고정하고 매우 작은 $\epsilon$에 대해 $y$를 $z+\epsilon$이라고 생각해보자. 만약 $z$가 "flat"부분에 있었다면 $p_i(y) − p_i(z)$로 가능한 값은 0이다. 만약 $z$가 "breakpoint"였다면 $p_i(y) − p_i(z)$로 가능한 값은 $z \cdot [x_i(y) − x_i(z)]$이다.

따라서 만약 $x_i$가 piecewise-constant하고 $[0,b_i]$에 있는 breakpoint들이 $z_1,\dots,z_\ell$라고 한다면 $p_i$에 대한 식을 다음과 같이 적을 수 있다.
$$ p_i(b_i)=\sum_{j=1}^\ell{z_j \cdot [\text{jump in }x_i(\cdot)\text{ at }z_j]}$$

($p_i(0)=0$이라는 Myerson's Lemma의 두번째 statement의 가정때문에 $p$가 unique하게 결정된다.) 이것을 시각화 한다면 다음과 같을 것이다.

Figure. Visualization of $p_i(b_i)$

그림을 보면 $p_i$에 대한 insight가 더 생긴다. Monotone한 $x$가 주어졌을 때 bidder $i$가 내야할 가격은 0부터 $x_i(b_i)$까지 세로축과 $x_i$ 함수 사이의 넓이이다. (엄밀히 말해서 세로축을 기준으로 함수를 보면 끊어져 있기 때문에 넓이가 정의가 안되지만 끊어져 있다면 둘을 이었다고 생각하면 된다.) 여기서 우리는 $x_i$가 piecewise-constant하다는 가정을 드러낼 수 있다. (엄밀히 적기 위해선 적분을 써야 하는데 그정도까지는 불필요하다 생각하여 생략한다.)

 

Part(C)

이제 이 $p$가 DSIC하게 만듦을 보이면 된다. 마찬가지로 truthful bidding이 utility를 maximize함을 보이면 된다. 다음 그림으로 이것이 성립함을 보일 수 있다.

Figure. When $b=v, b>v, b<v$

$b_i=v_i$인 경우 노란 영역의 utility를 얻는다. $b_i>v_i$인 경우 노란 영역에서 빨간 영역을 뺀 영역의 untility를 얻고, $b_i<v_i$인 경우 노란 영역의 utility를 얻는데 이는 첫번째의 utility보다 작다. 이것으로 Myerson's Lemma가 증명이 된다.

 

---

Auction Desgin

Vickrey auction으로도 알려져 있는 second-price auction과 앞에서 인터넷 광고 slot auction으로 소개한 Sponsored search auction은 Myerson's Lemma의 special case로 바로 적용이 가능하다.

 

 

Reference - Algorithmic Game Theory (Standford CS364A, Fall 2013) (Lecturer: Tim Roughgarden)