이 데모는 무엇을 보여주나?

1st Price Auction에서 DSP는 광고의 진짜 가치(True Value) V보다 낮게 입찰해야 이익을 남길 수 있습니다. 하지만 너무 낮으면 낙찰 자체가 안 됩니다. 이 시소 관계의 균형점 — 즉 기대 이익(Surplus)을 극대화하는 최적 입찰가 b* — 를 찾는 것이 Bid Shading의 핵심이며, 이 데모는 그 탐색 과정을 Golden Section Search로 시각화합니다.

Surplus 함수: s(b) = (V − b) × F(b|x)

차트에 그려진 곡선이 Surplus 함수입니다. 두 힘의 곱으로 구성됩니다:

이 두 값의 곱은 산 모양(단봉, unimodal)을 그립니다: b=0 근처에서는 이익은 크지만 낙찰 확률이 0에 가깝고, b=V 근처에서는 거의 항상 이기지만 이익이 0입니다. 봉우리가 정확히 하나라는 것이 수학적으로 증명되어 있으며 (Zhou et al., KDD 2021), 이 단봉성이 Golden Section Search를 사용할 수 있는 근거입니다.

Golden Section Search란?

단봉 함수에서 최대값을 찾는 가장 효율적인 구간 축소 알고리즘입니다. 이진 탐색(Binary Search)과 유사하지만, 매 반복마다 탐색 구간을 황금 비율(φ ≈ 1.618)로 축소하며, 함수 평가 1회만으로 구간을 줄일 수 있습니다.

알고리즘 단계

  1. 초기화: 탐색 구간 [a, b]를 설정 (a ≈ 0, b ≈ V)
  2. 구간 내에 두 점 x₁, x₂를 황금 비율로 배치:
    x₁ = b − (b−a)/φ,   x₂ = a + (b−a)/φ
  3. 두 점의 Surplus를 비교: s(x₁) vs s(x₂)
  4. s(x₁) > s(x₂)이면 최대값은 x₂ 왼쪽에 있으므로 b = x₂로 축소
  5. s(x₁) ≤ s(x₂)이면 최대값은 x₁ 오른쪽에 있으므로 a = x₁로 축소
  6. 구간 크기가 허용 오차 ε 미만이면 종료, 아니면 2번으로 반복

매 반복마다 구간이 1/φ ≈ 61.8%로 줄어듭니다. Convergence 차트(로그 스케일)에서 이 기하급수적 수렴을 직접 확인할 수 있습니다.

파라미터 해석 가이드

True Value (V)

pCTR × Conversion Value로 계산되는 광고의 진짜 가치입니다. 예를 들어 pCTR = 5%, 전환 가치 = $100이면 V = $5.00입니다. V가 시장 가격보다 훨씬 높으면 최적 입찰가도 높아지고 (여유가 있으므로), V가 시장 가격에 가까우면 아주 정밀한 shading이 필요합니다.

Market μ (로그노멀 위치)

시장 가격 분포의 중심을 결정합니다. 시장 중앙값 ≈ eμ이므로, μ = 0.8이면 중앙값 ≈ $2.23입니다. μ를 올리면 경쟁이 치열해져 최적 입찰가가 상승하고, Surplus가 줄어듭니다.

Market σ (로그노멀 스케일)

경쟁자 입찰가의 퍼짐 정도입니다. σ가 크면 경쟁자 가격의 불확실성이 높아 Surplus 곡선이 넓고 완만해집니다. σ가 작으면 곡선이 뾰족해져 최적 지점이 좁아집니다.

Tolerance ε

탐색 정밀도입니다. ε = $0.01이면 최적 입찰가를 $0.01 이내로 찾습니다. V = $5.00일 때 약 20회 반복이면 충분하며, 같은 정밀도를 Grid Search로 달성하려면 500개 그리드를 평가해야 합니다 (약 25배 차이).

왜 Grid Search 대신 Golden Section Search인가?

RTB에서는 수십억 건/일의 bid request마다 최적 입찰가를 실시간으로 계산해야 합니다. Distribution Network가 시장 분포 파라미터 (μ, σ)를 출력하면, Golden Section Search가 ~20회의 CDF 평가만으로 b*를 찾습니다. 전체 Bid Shading 모듈의 레이턴시가 10ms 이내에 완료되며, 이는 Grid Search로는 불가능한 속도입니다.

실험해볼 시나리오

시나리오 1: V를 시장 가격 근처로

V = $2.5, μ = 0.8 (중앙값 ≈ $2.23)으로 설정해보세요. True Value가 시장 평균에 가까우면 Surplus 곡선이 매우 낮고 좁아져, 최적 입찰가와 이익 모두 작아집니다. 이런 경매는 입찰 자체를 skip하는 것이 합리적입니다.

시나리오 2: 높은 정밀도

ε = $0.001로 줄여보세요. 반복 횟수가 늘어나지만, Grid Search 대비 효율성 격차는 더 벌어집니다. Results 패널의 Speedup 배수가 크게 증가하는 것을 확인할 수 있습니다.

시나리오 3: 변동성이 큰 시장

σ = 1.0으로 키워보세요. Surplus 곡선이 넓고 완만해져 최적 지점이 넓어집니다. 이런 시장에서는 정밀한 최적화보다 대략적인 shading도 충분히 효과적입니다.

참고

이 데모는 Bid Shading & Censored Data 포스트의 섹션 4 "최적 입찰가 계산: Surplus Maximization"을 시각화한 것입니다. Zhou et al. (Yahoo/Verizon Media, KDD 2021)의 Theorem 1에서 증명한 Surplus unimodality가 이 알고리즘의 이론적 근거이며, Bid Shading Visualizer의 Sweep 차트에서 동일한 단봉 곡선을 Monte Carlo로 확인할 수 있습니다.