今さら聞けないオークション理論とDSP入札ロジック

こんにちは。DSP(Demand-Side Platform)配信ロジックの開発に携わる新卒2年目の若手エンジニアohyan(@ohyan)です。

DSPはその名の通り、広告主や広告代理店など広告を配信したい側が使うインターネット広告配信プラットフォームです。媒体社(メディア)の広告枠を持つプラットフォームも存在していてSSP(Supply-Side Platform)と呼ばれます。DSPとSSPはRTB(Real-time Bidding; リアルタイム入札)で広告枠と広告のエクスチェンジを行っています。

この記事は、RTBの土台であるオークション理論および当社のDSPの入札ロジックについて説明します。

目次

RTBについて

まずはRTBについて簡単に説明します。

f:id:koki_ohyan:20200714181221p:plain

  1. メディアが広告表示リクエストをSSPに送ります。
  2. SSPが複数のDSPに広告枠に対する入札リクエストを送ります。
  3. DSPが表示したい広告と入札金額をSSPに返します。
  4. 一番入札金額の高い広告を広告枠に表示させます。

オークション理論

財の価値

入札者にとっては、オークション対象(オークション理論では財と呼ばれる)の価値を正しく見積もることが重要であり、その価値は3種類に分類できます。

  • 私的価値
  • 共通価値
  • 相互依存価値(相関価値)

それぞれの価値について簡単に説明します。

私的価値

各入札者が財に対して独自の評価基準で見積もりし、競合者の評価価値に左右されません。

例
* 財:ゲーム攻略サイトの広告枠
* 入札者A:自社化粧品の認知を高めるために広告を出したい入札者
* 入札者B:ゲームアプリの新規ユーザーを獲得するために広告を出したい入札者

入札者AとBは各自の基準で枠の価値を評価し、相手の評価基準を考慮する必要がありません。上記の状況であれば、おそらく入札者Bにとってこの広告枠の価値が高いであろうことが推測できます。

RTBの場合、DSPの保有する商材によって、広告枠に対する価値の見積もりが大きく変わります。適切な広告枠に適切な広告を出すことで広告配信効果と資金効率があがります。ここで財の評価基準として、広告配信効果を表すCTR(Click Through Rate)やCVR(Conversion Through Rate)が良く使われます。

共通価値

共通価値はすべての買い手において財の価値が一致するものです。石油や木材といったような自然資源はすべての入札者にとって、同等な価値があります。入札時に真の価値が判明できていないケースであれば、推定する必要があります。

相互依存価値(相関価値)

私的価値と共通価値の間に相互依存価値が存在します。自分の評価基準で財を評価しますが、他の入札者の評価基準も参考にして価値を推定します。

オークションタイプ

自分の評価価値に他の入札者の入札情報を使うことが可能かどうかについては、競売プロセス(オークションタイプ)に依存しています。概ね、オークションタイプは4種類に分けられます。

  • 公開入札
    • 公開競り上げ式
    • 公開競り下げ式
  • 封印入札
    • ファーストプライスオークション
    • セカンドプライスオークション

よく知られているのはおそらく「公開競り上げ式オークション」でしょう。最も低いレベルから価格が釣り上げていき、入札者がどのタイミングでオークションから降りてもよく、最終的に入札者が1人になる時点でオークション終了となります。約定金額(支払う金額)が最後の入札金額となります。

一方、インターネット広告のRTB市場は封印入札となっています。つまり、競争者の入札金額を知らずに自分の入札金額を提示することです。封印入札の中には、一番入札金額の高い入札者が自分の入札金額で支払う(ファーストプライスオークション)と、2番目の高い入札金額で支払う(セカンドプライスオークション)の2種類のプロトコルがあります。RTB市場は、セカンドプライスオークションが利用されてきましたが、ここ数年海外のSSPをはじめファーストプライスオークションが中心になりつつあります。

RTB入札戦略・ロジック

DSPは各自の保有している商材を広告枠に表示する価値が、私的価値に当てはまります。

RTBにおけるDSPの最適な入札戦略とは、利得が最大になる入札行動を取ることです。そしてこの場合の利得とは、私的価値とSSPへ支払う金額の差を指します。

セカンドプライスオークション

セカンドプライスオークションの場合、他の入札者の金額を考慮する必要がなく真の私的価値で入札すれば最適な戦略になります。

ここでは、なぜ最適な戦略になるかについて簡単に説明します。

パラメータは下記通り表記します。

  • v を私的価値
  • v - s を私的価値より低い金額
  • v + s を私的価値より高い金額
  • p を他の入札者の一番高い入札金額

まずは、私的価値より低く入札する場合を考えましょう。2番目高い入札金額は、図に示した通り3パターンがあります。

f:id:koki_ohyan:20200714000928p:plain

  1. p > v:負けます。入札金額がvかv-sか、とは関係ありません。
  2. v > p > v - s:負けます。vで入札していたらオークションに勝っていました。v-pの利得も得られたでしょう。
  3. v - s > p:勝ちます。入札金額がvかv-sか、とは関係ありません。

つまり、私的価値より低く入札するのは、私的価値そのままでの入札と同じ結果をもたらすか、それより悪い結果をもたらします。

次は私的価値より高くする入札する場合を考えます。同じく、3つのパターンがあります。

f:id:koki_ohyan:20200714000933p:plain

  1. p > v + s:負けます。入札金額がvかv+sか、とは関係ありません。
  2. v + s > p > v:勝ちます。約定金額は私的価値より高いpになるため、p-vの損失が発生します。
  3. v > p:勝ちます。入札金額がvかv+sか、とは関係ありません。

つまり、私的価値より高くに入札するのも、私的価値そのままでの入札と同じ結果をもたらすか、それより悪い結果をもたらします。

このように私的価値そのままで入札することが最適解となります。

セカンドプライスオークションの場合には、入札者にとって期待される収益に応じて財を正しく見積もることが重要です。

具体例 として、当社DSPがインプレッションの価値をどうやって評価するかについて、CPC(Cost per Click)を目標KPIとする案件を例として説明します。

  • 1クリックの価値は広告主が決めますが、その価値は目標CPCと呼びます。
  • インプレッションからクリックに至る確率も必要とされて、CTRと呼びます。
  • 広告主にとって、1インプレッションにあたる期待収益は目標CPC * 予測CTRになります。

これらを踏まえると、DSPにはその価値をリアルタイムで推論するためのCTR予測器を作るという課題が設定できます。そして、広告枠Xに広告yを出す時のCTRは、広告主の属性広告枠の属性オーディエンスの属性で決まります。 CTR予測器では、これらの属性を含んだ過去の配信実績データを使って学習し、DSP配信サーバーへの広告表示リクエストに対して、リアルタイムでCTR予測値を求めていきます。

ファーストプライスオークション

ファーストプライスオークションの場合はセカンドプライスオークションとは違い、私的価値のままで入札すると利得が0になります。このような場合において、他の入札者の入札金額を推定することが最適な行動を取ることにつながります。このような状態はナッシュ均衡とも呼ばれます。

また、ファーストプライスオークションでは1つの広告枠に対して複数回の表示権利をオークションで売買します。このような繰り返しオークションでは、財の価値(他社の最高入札金額)を統計的に推定することができます。最高入札金額分布が分かれば、利得を最大化する入札ロジックが可能になります。

ここでは、この入札戦略について説明します。

パラメータは下記通り表記します。

  • v を私的価値
  • x を入札金額
  • z を競合者の最高入札金額

ファーストプライスオークションの利得 Profitは、私的価値と入札金額の引き算結果になります。他社の入札金額より低い場合は、広告を表示する権限が得られなくて利得が0になります。

\begin{align*} Profit= \begin{cases} v - x & \text(x > z) \\ 0 & (\text{otherwise}) \end{cases} \end{align*}

入札金額に対するオークション勝率と期待利得の概念を導入します。他社の最高入札金額の分布が分かれば、それの累積分布関数は勝率関数となります。そして、利得と勝率の掛け算結果は期待利得です。1つの例をあげます。

私的価値 := 200円 
Case1: 入札金額 := 200円 → 利得0円、勝率100%、期待利得0円 
Case2: 入札金額 := 150円 → 利得50円、勝率80%、期待利得40円 
Case3: 入札金額 := 100円 → 利得100円、勝率50%、期待利得50円 
Case4: 入札金額 := 50円 → 利得150円、勝率10%、期待利得15円

ここで、入札金額に対するオークションの勝率は w(x)  \rightarrow [0, 1] として定義すると、最大化したい期待利得は  w(x)(v - x)になります。定義された勝率関数が微分可能な関数であれば、期待利得も微分可能で高速に最適化計算が行えます。

このようにファーストプライスオークションの場合、入札金額決定ロジックではCTR予測器やCVR予測器以外に、競合者の最高入札金額を推定できるように事前に勝率関数の推定パラメータが必要とされます。

具体例 として、当社DSPがどのように分布を求めるかについて例をあげたいと思うのですが、実際のところSSPによってファーストプライスオークションで得られる情報が異なることがあります。

例えば、SSP Aはオークションに負けたときの最高入札金額を送ってくれ、SSP Bは広告枠ごとの最高入札金額を集計し、中央値と平均値を送ってくれます。SSP Aの場合だと、事前に何を対象にして(枠の種別やオーディエンスタイプなど)、どのような分布(正規分布や対数正規分布など)を作るのかを実験で決めておく必要があります。SSP Bの場合のように枠ごとの中央値と平均値がすでにわかる場合は、分布の種類を決めれば配信サーバーが広告表示リクエストに乗せている情報を用いて最高入札金額の分布を推定できます。このように各SSPの特性も踏まえたロジック開発が必要となっています。

ファーストプライスオークションの入札ロジックに関して詳しくは需要があればまた書きたいと思います。

入札ロジックの開発

前述の通り、広告表示リクエストに対して私的価値を正しく評価(予測)することはDSPのロジック開発における大事な仕事です。一方、RTBというような繰り返しオークションでは他のDSPの入札金額を推定することができるので、利得を最大化するロジックを作っています。予算・目標KPI(CPCやCPAなど)の制約の元で入札ペースを調節し、配信ボリュームを最大化する事もしています。そして、予測器によって広告表示価値を予測しているので、予測が期待通り動けば実績KPIが設定した目標値に着地できます。

しかし予測値の誤差によって、広告案件の実績KPIが目標KPIと乖離する場合があります。このような場合、KPIの乖離を埋めるために運用上は入札金額を上げ下げするオペーレションが必要となりますが、このオペレーションを自動化するためにフィードバック制御を用いた入札金額の調節を行なっています。

そしてDSPは膨大な広告枠の在庫を保有しているため、広告案件と広告枠の組み合わせパターンは極めて多くなります。それはDSPを運用する人たちが各パターンを把握して調整することはほぼ不可能な量なので、入札ロジックの開発は極めて重要になるのです。

まとめ

この記事はRTBの土台となっているオークション理論を紹介し、オークションプロトコルに応じて求められる適切な入札戦略が異なることと、当社DSPがオークションプロトコルごとに設計した入札ロジックの例について説明しました。

当社DSPの入札ロジックはまたまた発展途上ですが、これから配信データを駆使し広告主の訴求に応じてより良い配信ロジックを作っていきたいですね。

より深い内容に興味があるならこれらの文献が参考になります。