PR402 - 7: Reserve Price Optimization for First Price Auctions

 오늘 리뷰할 논문은 Reserve Price Optimization for First Price Auctions (Feng et al., ICML 2021 Accepted)입니다. 개인적으로는 ICML에 어셉될 정도는 아닌 것 같은데 리뷰는 해보겠습니다.

Link - https://arxiv.org/abs/2006.06519

Intro:

Auction은 Advertisement에서 상당히 많이 사용되는 가격 책정 방식입니다. 구글 애드센스와 같은 기업들이 이런 방식을 사용하는데, 광고배너 같은 곳에 홍보를 할 때 고정된 금액이 있는 것이 아니라 최소금액(Reserve Price)을 공급자가 제시하고, 이를 bidder들이 받아서 bid를 한 후 최고 금액을 제시한 bidder가 광고를 할 수 있게 되는 방식입니다. 예전에는 second price 방식을 많이 사용하였다고 하는데 요즘은 first price로 다시 옮겨오는 추세라고 합니다. 

경제학적으로는 공급자가 제시하는 최소 금액이 수요자의 willing to pay에는 영향을 끼치지 않아야 하는데, 현실에서는 그렇지 않기 때문에 이를 Demand component와 Bid component로 구분하여 reserve price에 영향을 받는다고 가정하였습니다. 미술품 경매를 시작하는데 똑같은 그림이라도 그림에 대해서 시작가가 만원인 경우와 100만원인 경우에 경매 최종가가 (현실에서는) 달라지는 것을 생각하시면 될 것 같습니다.

논문의 핵심적인 내용은 공급자의 revenue를 적은 variance와 높은 convergence rate로 극대화하는 내용입니다. 

Contents:

우선 Problem formulation은 auction이 갖는 기본적인 형태를 따라서 이루어집니다.

세팅에 따른 알고리즘은 다음과 같습니다.

자세한 notation은 논문을 참조하시면 좋을 것 같습니다. 간단하게 요약하자면, 시작가를 살짝 올려서 계산해보고, 시작가를 살짝 내려서 계산해봐서 대충 해당 지점에서의 gradient의 근사치를 추려서 다음 시작가를 조정하는 방식입니다.

여기서 도출되는 gradient estimation의 variance를 줄이기 위해 이런저런 방식을 도입하였는데, theoritical하게 증명한 후, 이를 experiment를 통해 확인하는데 그 내용이 별로입니다. 개인적으로 data를 생성하는 과정에 있어서 임의로 distribution을 짜서 data를 생성하고 이를 통해 실험하는 방식을 굉장히 안 좋아하는데, 여기서는 data를 직접 만들어서 사용해서 맘에 들지 않았던 것 같습니다. 저는 그런 경우를 그냥 그 distribution에 대한 학습이지 일반적으로 증명된 것이 아니라고 생각합니다. 예전에 봤던 논문 중에도 굉장히 실망했던 것 중에 하나가 RNN과 LSTM을 사용해서 trading하는 모델을 만드는 논문이 있었는데, data generation을 임의의 주기를 갖는 3개의 sine function을 합성해서 만들어놓고 이를 바탕으로 수익률을 따지길래 충격받았던 기억이 있습니다;; 아무튼 data generation을 통해 experimental하게도 gradient estimation 부분에서의 variance 감소 및 average revenue 상승을 증명했습니다. Auction data가 쉽게 구해지지 않아서 reproducible하지 않다는 점은 아쉽습니다.

그렇지만 구글 팀과 협업해서 낸 논문이기 때문에 아마 구글 본연의 데이터를 갖고서도 실험해봤겠죠! 어느 정도 실효성 있는 결과를 내서 이렇게 theoritical하게 증명도 하고 data generation을 통해 간접적으로 보여주고 싶지 않았나 하는 생각이 듭니다. 오늘은 이만 짧게 마치겠습니다.