- 논문 링크 (2020년)
이직한 회사에서 bid shading 알고리즘 개발을 새로운 업무로 맡게 되었다. 필자는 광고 도메인으로 이직을 했다. 현재 광고 분야는 first price auction이 주류를 이루고 있으며 이 경매 형태에서는 지나치게 큰 입찰 가격을 방지하기 위해 입찰에 이기면서 적당한 가격으로 깎는 bid shading 알고리즘의 중요성이 커지고 있다. 필자는 이 bid shading 알고리즘이 매우 생소하기 때문에 논문을 읽으며 내용을 정리하고자 한다.
AI가 다 해주는데 왜 하냐? 라고 물을 수 있다. 맞는 말이다. 사실 필자보다 AI가 비교할 수 없을 정도로 똑똑하고 알고리즘을 잘 이해하고 있다. 그러나 왜인지 모르게 AI에게 정리를 해달라고 하면 머리에 남지 않는다. 이해는 되는데 머리에 안 남는다. 따라서 간단하게라도, 핵심 내용만이라도 블로그에 정리하여 기록으로 남기기로 결심했다.
Summary
Verizon Media DSP에서 나온 논문이다. censored auction인 상황에서 surplus을 최대화하는 문제를 다룬다. winning price의 cdf을 추정하고 binary search 알고리즘을 통해 이론적으로 surplus을 최대화하는 입찰가(bid)를 찾는다. 아마도 이 논문이 two-step으로 surplus을 최대화하는 입찰가를 찾는 알고리즘을 제안하는 첫 논문인 것으로 보인다.
Main Idea
$b_i$는 입찰가, $V_i$는 트래픽의 가치, $g_i$는 할인율 (일종의 ratio), $\hat{b}_i$는 가장 높은 타 DSP의 입찰가로 정의한다. bid shading은 DSP가 개발하는 알고리즘이므로, 타 DSP을 생각한다. 여기서 자회사를 제외한 타 DSP의 입찰가가 중요하다. 만약에 자회사의 입찰가 > 타 DSP의 입찰가 라면, 타 DSP의 입찰가까지 깎을 수 있다. 반면, 자회사의 입찰가 < 타 DSP의 입찰가 라면, 타 DSP의 입찰가까지 입찰가를 올려야한다. 따라서 $\hat{b}_i$가 minimum bid price to win, 즉 한 경매에서 이기기 위한 최소 금액이 되는 것이다.
surplus는 아래와 같이 정의된다. 앞으로 많이 나올 것이므로 이해하고 넘어가야 한다.
$g_i V_i$가 shading된 가격인데, 이 가격이 $\hat{b}_i$보다 커야 경매에서 이기고, 그 차액만큼 이득으로 가져간다. 모든 경매에 대해서 얻을 수 있는 이득의 합이 surplus이고, 이를 최대화하는 것이 bid shading 문제의 목적이다.
보통 $V_i$는 ctr, cvr 등을 통해서 정해지므로 fix 값이라고 생각하자. 여기서 변수는 $g_i, \hat{b}_i$이다. notation을 조금 더 단순하게 아래와 같이 가져가보자.
목표는 위의 surplus을 최대화하는 입찰가를 찾는 것이다.
이 식이 논문의 핵십이다. 사실, 변수가 $b, \hat{b}$이므로 기대값이 indicator function에만 적용되는 것이 100% 이해되지 않는다. 아마도 two-step으로 풀 요량이었고, 따라서 $\hat{b}$는 분포 가정을 하고, $b$는 추후에 최적화로 푸는 것을 생각했을 것 같다.
최적화 단계는 아래와 같다.
왜 cdf을 추정할까? DSP 입장에서는 winning price을 모르는 경우가 대부분이기 때문이다. 경매에서 이기더라도, fpa에서는 타 DSP의 입찰 가격을 알 수 없다. 경매에서 지는 경우는, 더욱이 자회사보다 더 높은 입찰 가격을 알 수 없다. 따라서 자회사의 입찰 가격보다 높냐, 낮냐를 통해 cdf을 추정할 수 있을 뿐이다. 만약에 winning price을 알 수 있다면 상황은 달라진다. 이는 나중에 생각하자.
만약에 $\hat{b}$의 분포를 알고 있다면, cdf도 유도할 수 있으므로, MLE 등을 통해 파라미터를 추정할 수 있다. 이는 후속 논문에서 나오고, 일단 이 논문에서는 pdf를 모른다는 가정하에, cdf가 가지는 확률을 logistic regression을 추정한다. 모델의 파라미터를 추정하는게 아니다!
여기서 $F$를 logistic function으로 가정한다. 이제 surplus을 최대화하는 $b*$을 찾는다.
증명을 통해 이 값을 최대화하는 $b*$가 특정 구간 내에 존재함을 밝힐 수 있다. 따라서 최적화 해를 bisection 알고리즘을 통해 구할 수 있다.
이 알고리즘 자체가 중요한게 아니고.. 후속 논문에서 이 세팅이 그대로 쓰인다는 것이 중요하다.
Conclusion
censored auction에서 cdf 확률 추정과 surplus 최대화를 통해 최적의 입찰 가격을 찾는 논문이다. 후속 논문과의 연계성이 중요하므로 기초를 잘 다져두자.
댓글