public

「後悔」を最小化するデジタル広告入札戦略が予算消化の最適化と市場安定をもたらす

スタンフォード大とコロンビア大の研究者によると、オンライン広告の入札時の「最善手」からの誤差を最小化する考え方のアルゴリズムにより、予算消化の速度を適正化でき、また入札者の採用が増えると、市場の安定性が増すことがわかりました。

3 months ago

Latest Post 倉庫で仕分けを自律的に行うCovariant.aiのロボット by Takushi Yoshida public

Key Takeaway

スタンフォード大とコロンビア大の研究者によると、オンライン広告の入札時の「最善手」からの誤差を最小化する考え方のアルゴリズムにより、予算消化の速度を適正化でき、また入札者の採用が増えると、市場の安定性が増すことがわかりました。

入札時に必要な情報はそろわない

デジタル広告の世界はとても複雑です。オンライン広告取引の流れとは、ウェブサイトをクリックすると、ページには広告用に空のボックスがいくつかあります。これらのスロットは、ユーザーに関するデータ(ブラウザが忠実に引き渡す)とともに、即座にアドエクスチェンジに情報を伝播します。オークションが開催され、勝者はスロットを埋めるために広告を送信します。 正しく機能すれば、ユーザーは遅延に気付くことさえありません。

一人の視聴者のディスプレイ広告に入札するためにマンパワーは使われていません。毎日何百万、何億ものトランザクションが発生しているため、すべてソフトウェアが実行します。競争上の優位性はしばしば、誰が最良のアルゴリズムを持っているかということになります。

問題は、どれが最良のアルゴリズムなのかは明らかではないということです。使用されているアルゴリズムにはさまざまな種類があり、それらが保証できる性能についてはほとんど知られていません。広告キャンペーンから生じるトラフィックや収益を確認することもできますが、これは多くの場合、使用中のアルゴリズムの品質ではなく、広告主の予算の量を反映したものに成りがちです。

今、これらの質問に対する答えがあります。スタンフォード大学のYonatan Gurとコロンビア大学のSantiago Balseiroは、"Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium"というタイトルの論文で、優れた広告市場アルゴリズムの3つの明確な基準を提示しました。彼らは、典型的な市場条件下でこれらの基準を満たし、可能な限り最高のパフォーマンスを提供することに非常に近い、比較的単純なアルゴリズムの種類を提示したのです。

彼らの考え方はアドテク企業にとって十分に現実的なものです。1回の広告表示で数円でも売れる可能性がありますが、1000のインプレッション(画面表示)を売り買いする市場では、莫大な金額に及びます。オンライン広告市場は現在、印刷広告とテレビ広告を大幅に上回っており、米国だけで年間約1,000億ドルの売上があります。

予算制約と支出のペース

これらのオークションが行われる多くの取引所があり、取引ごとに手数料をかけて、オーディエンス、広告主、メディアサイトをリアルタイムでマッチングしています。最大のものは、以前はDoubleClickと呼ばれていたGoogleアドマネージャーです。Googleは、メディアサイトの広告スペースの仲介者および販売者としてオンライン広告から利益を得ています。

広告主は通常これらのプラットフォーム上で予算制約のあるキャンペーンを実施しており、彼らは多くのオークションに参加しているため、通常、特定の期間(たとえば1日または1週間)には合計費用の制限があります。

キャンペーンの終わり近くに、適切なタイミングで予算を使い果たす方法でアルゴリズムを入札する必要があるため、これは事態を複雑にします。 未使用の資金を残してしまったり、すぐに使い切ってしまうと、実際に機会損失が生じます。概して、入札者は戦略的な入札行動をとりますが、これに予算制約が課せられた時、その入札戦略に混乱が生じがちです。

これは、現在業界で広く認知されている概念であり、システム提供側は、広告主がキャンペーン全体で支出を調整できるような設計を試みています。これについては以下のブログで説明済みです。

Googleの検索広告で学ぶオークションの理論と実践

実際、この問題の難しさと広告主にとってのその重要性のために、業界全体が予算消化のペース管理を含むオンライン入札サービスの提供を急いでいます。基本的にクライアントの入札を実行するための専門知識が求められており、取引所は、多くの場合追加料金でそのようなサービスを提供する場合もあります。

キャンペーンの目標はできるだけ効率的に入札することです。つまり、最も価値の高い顧客の広告スロットを獲得することで、予算から最大の利益を得ることができます。避けるべくは、入札に勝つために必要以上のお金をつかうこと(「勝者の呪い」と呼ばれます。上記ブログで確認ください)、それから、予算を想定期間よりもずっと早く使い切ってしまうことです。

基本的に、これは制約付きの最適化問題です。簡単ではありませんが、計算上は可能です。ただし、多くの重要なパラメータがリアルタイムで広告主に与えられていないという事実を除きます。

あなたは入札の対象とするオーディエンスに関するいくつかのデータを見るが、しかしあなたは後に来るかもしれないオーディエンスと比べてどれほど価値があるかわからない。次の視聴者はあなたのブランドにさらに適しているかもしれません。また、他に入札者がいくついるのか、予算や戦略は何か、特定のオーディエンスをどの程度重視しているのか、あるいは入札者間の競争がどう動的に変化するのか、など悩みはつきません。

言い換えると、オンライン広告主はどちらかについてよく知らなくても、現在と将来の機会のバランスをとる必要があります。また、これらの未知の要素のほとんどが明らかにされることはなく、常に変化するため、広告主はさまざまなアプローチを簡単にテストして、どれが最も効果的かを確認することはできません。

(このブログの主旨とそれますが、実際には、対象とされるオーディエンスは「こころ」の持ち主であることも重要です。こころはとても動的な性質をもち、そして不確実です。そのこころを持った群衆が、オンライン空間で戯れた時、予想がつかないことが起きます。このオーディエンスに生じ続ける変化は入札戦略の唐突な成功と破綻の両方をもたらすことがあります)。

「後悔」を最小化する問題設定

GurとBalseiroはある想定を置くことに決めました。キャンペーンの最後から最初に戻って、完璧な後知恵でそれを再生できるため、すべての視聴者とすべての競合他社の入札の価値を知っており、希望するオークションを厳選することができ、予算制約を考慮に入れながら勝つことができます。これは「後悔」(Regret)を最小化する問題設定です。

彼らが条件としたのは「かなり安定した市場」でした。この条件を所与として、GurとBalseiroはうまく数学を使用して、驚くほど単純なアルゴリズムのクラスを作ることができたのです。彼らは、その予算を好ましい速度で消化するための入札戦略アルゴリズムのことを「適応ペーシング(Adaptive Pacing)」と呼んでいるのです。

適応ペーシングの基本的な考え方は直感的です。最初に、目標支出率(オークションごとにいくら費やすか)を決め、その後、連続する各オークションでの入札額に応じて、入札単価を増減します。 あなたが勝った場合、あなたはあなたの次の入札を抑えます。 負けた場合は、あなたは次の入札を膨らませます。

重要なのは、広告主が市場に参加することで学ぶということです。未知数を考えると、最適なベンチマークと比較して、オークションごとに一定の金額を失うことになります。 しかし、キャンペーンの過程で、あなたは情報を蓄積します。オークションの数が増えると、平均損失をゼロに近づけることができます。それは、「漸近最適性」と呼ばれています。

別の戦略の必要性失くす均衡

もちろん、それは「安定した市場」を前提としています。物事がダイナミックになると、後から見た最高のパフォーマンスに合わせることができなくなる可能性があります。これは、キャンペーン中にトラフィックレベルや競争環境が変動した場合に発生する可能性があります。たとえば、新しい競合他社の参入や、既存の競合他社の予算の突然の変更などです。

そこで、GurとBalseiroは2番目の基準を提案しました。「アルゴリズムは、市場の状況が突然変化したときに、ベンチマーク可能な最大パフォーマンスを保証できるか」だった。それが安定しているか乱流であることが判明したかに関係なく、適応ペーシングはどちらの場合でも達成可能な最高のパフォーマンスを保証する、と2人は主張しています。

GurとBalseiroはまた、そのようなアルゴリズムを使用すると、市場の安定性が実際に誘発されることも示しました。特に、大規模なオンライン広告市場では、すべての競合他社が適合ペーシングを使用している場合、別の戦略に逸脱するインセンティブは誰にもありません。ゲーム理論では、これはナッシュ均衡として知られています。

おそらく最も驚くべきことは、適応ペーシングアルゴリズムの実装が非常に簡単なことです。 競合他社に関するデータは必要ありません。それはすべて、自分の勝敗に基づいています。さらに、それは計算上単純であり、1日に何千ものオークションに入札する場合に重要なのです。

アドテクノロジーの関連記事

参考文献

  1. Santiago Balseiro, Yonatan Gur. Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. Management Science Vol. 65, No. 9 (2019).
  2. Jkomiyama. バンディット問題について. Slideshare
  3. Ko Fujita. 多腕バンディット問題としての広告配信の最適化. Cyber Agent Developer Blog.

Photo: "Tsukiji Fish Market, Tokyo"by gadgetdan is licensed under CC BY-NC 2.0

Takushi Yoshida

Published 3 months ago