1．は じ め に
現在のインターネットには，至る所に広告が表示され ている．例えば Web ページをブラウザで開くと画面の 横のほうにバナー広告が表示されるし，検索エンジンに キーワードを入れるとキーワードに関連した広告が表示 される．動画を見ようとすると再生前にスキップできな い広告動画が挿入される．もはやインターネットで広告 を見ない日はないといっても過言ではない． インターネットを利用した広告を総称してインター ネット広告（internet advertisement）という．インター ネット広告は急速に成長している広告形式であり，2017 年には世界のインターネット広告費総額（23 兆円）が テレビ広告費総額（21 兆円）を超えると予想されてい る [Zenith 17]．日本のインターネット広告費（13 億円） はまだテレビ広告費（20 億円）に及ばないものの，毎 年着実に比率を増やしており，重要な広告メディアとし ての位置を確立している [電通 17]． これまでにさまざまなインターネット広告の形式が現 れている．1978 年に送信されたメール広告から始まり， 1994年に HotWired が取り入れたバナー広告，2002 年に Google が普及させた検索連動型広告，2008 年に YouTubeが導入した動画再生前広告と，インターネット の通信速度向上・計算機の性能向上・ユーザの利用形態 変化に応じて年々新しい広告が登場している．ここ数年 のトレンドはスマートフォンなどのモバイル端末向けの 広告といわれている [IAB 17]． 本稿では主にディスプレイ広告（display advertising） と呼ばれる「Web ページ上に設置された広告枠に表示す るタイプの広告」に注目する．ディスプレイ広告は最も 基本的なインターネット広告の一つであり，テキスト広 告・バナー広告・動画広告などが含まれており，最近で はゲーム的な要素のある広告も出現している．典型的な ディスプレイ広告の例を図 1 に示す． ディスプレイ広告の収益モデルとして現在広く用いら れているものに直販（direct sales）とリアルタイム入札（real-time bidding）の二つがある [Yuan 13]．直販は主 に大手 Web サイトのトップページに表示する広告に用 いられており，テレビや新聞の広告と同様に，Web サイ ト所有者が広告主に広告枠を一定の期間貸し出すことに よる売上げを収益とする．一方で，リアルタイム入札は 主に中規模以下の Web サイトに表示する広告の際に用 いられている．Web サイト所有者は，ユーザが Web ペー ジを読み込むたびにそのユーザに対する「広告表示権」 をオークションにかけ，各広告主がそのオークションに 入札することによって表示する広告の決定を行い，広告 主より収益を得る．リアルタイム入札の詳細な動きは 2 章で紹介する． 本稿はディスプレイ広告に対するリアルタイム入札を 扱う．オークション型の広告は 2000 年頃に検索連動型 広告（検索結果に添えて表示するタイプの広告）に対し て提案されたものだが，2005 年頃にディスプレイ広告 に対する手法として登場し，2009 年から本格的に運用 され始めた．比較的最近提案されたモデルではあるもの の，効果が高い・小額から始められる・効果が計測しや すい，などのさまざまな理由から，またたく間にインター ネット広告における主要な収益モデルとなっている．リ アルタイム入札は広告の実務家にとって外すことのでき ない重要なトピックであることはもちろん，アカデミア の研究者から見ても面白い研究テーマであり，機械学習・
ディスプレイ広告に対するリアルタイム入札
Real-Time Bidding for Display Advertisements
前原 貴憲
理化学研究所革新知能統合研究センターTakanori Maehara RIKEN Center for Advanced Intelligence Research.
Keywords:
internet advertising, ad-auction, real-time bidding. 「広告と AI」アルゴリズム理論・ゲーム理論・経済学などのさまざま な領域が交わる複合領域となっている． 本稿の目的は，ディスプレイ広告に対するリアルタイ ム入札について，基本的な事項を説明することと，各プ レーヤの基本的な問題設定を，人工知能に関わる研究者 に向けて紹介することである．本稿が本分野の研究を始 めるための足掛かりとなればと期待している．
2．リアルタイム入札の概要
2･1 リアルタイム入札の概要 本章ではリアルタイム入札の基本的な流れを簡単化し て説明する．より現実的な状況は次節で説明する． あるユーザが広告枠のある Web ページをブラウザで 読み込み始めたとしよう．このときWebページ所有者は， 自分の Web ページの広告枠に適当な広告を表示するこ とで，その広告主から広告収入を得たいと考える．この とき「どの広告主の広告をいくらで表示するか」が問題 となるが，リアルタイム入札はこれを決定するための手 段である． ユーザに広告が表示されるイベントのことをインプ レッション（impression）という．リアルタイム入札では， Webページ所有者は訪れたユーザの情報（IP アドレス， OS/ブラウザ，etc.）を広告主達に提示し，そのユーザ に対して広告を表示する権利（すなわち，インプレッショ ンそのもの）をオークションにかける．そして，高額で 入札した広告主の広告を自分の広告枠に表示し，オーク ションメカニズムによって定まる落札額を収益として得 る． リアルタイム入札は広告主・ユーザ・Web ページ所有 者のそれぞれに対して利点がある．広告主にとっての最 大の利点は個人特化性（personalizability）である．広 告主は広告を出すかどうかをユーザの情報を見たうえで 決められるため，高い確率で興味をもってくれそうな ユーザに限定して広告を表示する，といったことが可能 になる．これはテレビや新聞などの従来の広告では実現 できない特性であり，現在リアルタイム入札が流行して いる最大の理由と考えられている．個人特化性はユーザ から見ても利点といえる．自分に最も高値をつけた広告 主の広告が表示されるため，自動的に自分が興味をもつ であろう広告が高い確率で表示されるようになる．この ことから，リアルタイム入札は広告主・ユーザ双方の満 足度が向上する仕組みといえる． 広告主にとってのもう一つ大きな利点は金額である． リアルタイム入札の取引は基本的にインプレッション単 位で行われるため，直販と比べて極めて小額から広告を 出すことが可能である．具体的な価格は条件しだいで大 きく変動するが，おおよそ 1 000 インプレッション当た り 100 ∼ 200 円程度をイメージしておけばよい．これは， 対象とするユーザ層が限られており，その層にさえ広告 が届けば十分，というタイプの広告に適している．なお， より広い層に届けたい広告であれば，リアルタイム入札 ではなく直販ベースの広告を出すほうが効果が高いとい われている． Webページ所有者にとっての利点は，広告契約手続き の簡略化である．個別に広告主と契約する必要がないの で手軽に導入できる．また，広告価格の相場はわかりに くいが，オークションにすることで自動的に価格調整が 行われ，適切な価格へと収束すると期待できる． リアルタイム入札では，名前のとおり，リアルタイ ム性が重要な要素となる．リアルタイム入札の一連の手 続きは，ユーザが Web ページを読み込み始めてから読 み込み終えるまでに終了しなければならないため，Web ページ所有者・広告主が意思決定に使える時間はわずか 数ミリ秒である．また，1 日に行われるリアルタイム入 札の取引は合計で 10 億回近くに上る．このような超高 速かつ大規模な取引を実現するためには，人工知能（ア ルゴリズム）を用いた自動取引が不可欠であり，人工知 能研究者が活躍できる領域といえる． 2･2 実際のリアルタイム入札市場 前節では簡単のため，Web ページ所有者が広告主相 手に直接オークションを開催するように説明したが，そ れでは Web ページ所有者・広告主双方に負担が大きい． そのため，実際にはアドエクスチェンジ（ad-exchange） と呼ばれる共通化された広告市場を介して，Web ページ 所有者は SSP（supply-side platform），広告主は DSP （demandside platform）と呼ばれる仕組みを利用して取 引を行う．SSP は Web ページに訪れたユーザの情報を もとに，Web ページ所有者の利益を最大化するように広 告リクエストをアドエクスチェンジに送るものであり， DSPはアドエクスチェンジを経由して届いた入札リク エストについて，広告主の利益が最も高くなるように入 札額を決定するものである． リアルタイム入札市場の基本的な動きを図 2 に示す． ユーザが Web ページを開いた瞬間，Web ページ所有者 は SSP に広告リクエストを送る（1）．SSP は Web ペー ジ所有者の利益を最大化するような広告リクエストをア ドエクスチェンジに送る（2）．アドエクスチェンジは自 図 2 リアルタイム入札市場の概要分に接続している DSP に入札リクエストを送る（3）． 各 DSP は自分が契約している広告主に入札リクエスト を送り，手元でオークションを開催し，最高額の入札を DSPの入札とする（4），（5）．アドエクスチェンジはオー クションを開催し，最高額で入札した DSP に広告表示 権を与え，課金する（6）．広告主の広告が SSP を経由 して Web ページに届き，広告枠に広告が表示される（7）， （8）．その後，Web ページは表示した広告に対する反応（画 面内に入った，クリックされた，etc.）を広告主に返す（9）． 図中で DSP とつながっている DMP（data management platform）というものは，ユーザの情報を管理・集約す る仕組みである．例えば，複数の Web ページを同一ユー ザが訪問したとき，それらのユーザ情報をひも付けるこ とでより精度の高いユーザ情報を得ることが可能とな る．
3．各プレーヤの基本的な問題設定
前章ではリアルタイム入札の基本的な動きを見た． そこにはユーザ・Web ページ所有者・広告主・SSP・ DSP・アドエクスチェンジ・DMP とさまざまなプレー ヤが登場していた．ユーザ以外のすべてのプレーヤは人 工知能であり，効果的な意思決定を行わせるためには数 学的なモデル化が不可欠となる． 以下では各プレーヤにおける基本的な問題設定を紹介 していく． 3･1 オークション設計 アドエクスチェンジにおける基本的な問題はオーク ション設計（auction design）である．できるだけ公平 かつ効率的なオークションメカニズムをつくることによ り，自アドエクスチェンジを利用する DSP/SSP が増え， その結果として収益の向上が期待できる． 現在運用されている多くのアドエクスチェンジでは第 二価格オークション（second price auction）を元にした オークションメカニズムが採用されている．そこで，ま ずは第二価格オークションについて簡単に述べる． 第二価格オークションとは，最も高い入札額を付けた 広告主が，2 番目に高い入札額を支払ってインプレッショ ンを落札するメカニズムのことをいう．第二価格オーク ションは理論的に好ましい性質をもつことが知られてい る． オークションが効率的（efficient）であるとは，ある インプレッションに対して複数の広告主が入札したと き，最も高値で入札した広告主が落札できることをいう． 第二価格オークションは定義から明らかに効率的であ る． オークションが耐戦略的（strategy-proof）であるとは， ある広告主がインプレッションを v〔円〕の価値がある と（心の中で）見積もっているとき，他の広告主がいく らで入札したとしても，その広告主にとって v 円で入札 することが合理的な判断となることをいう．耐戦略的で ないオークションでは他の広告主がいくらで入札するか の読みあいが発生してしまうため，広告主に余計な負担 をかけないためにも，オークションは耐戦略的であるこ とが望ましいといえる．実は，第二価格オークションは 耐戦略的でもあることが確認できる． さて，実際の入札オークションは単純なオークション にはなっておらず，いくつかの修正が必要となる．まず， SSPは自身の利益を最大化するため，オークションに 対して最低落札価格（reserve price）を設定できる．最 低落札価格が設定されていたとしても，基本的には各プ レーヤは自分の見積もりどおりに入札するのが合理的な 判断となる．SSP が解く最適な最低落札額を決定する問 題については 3･5 節で述べる． 次に，2･2 節で見たように，実際のリアルタイム入札 市場ではオークションは階層的に行われている．すなわ ち，第 1 段階として各 DSP が自分に登録している広告 主の間でオークションを行い，第 2 段階としてそれらの 勝者達がアドエクスチェンジでのオークションに参加す る． このような階層構造があるオークションでは，落札 者の支払う価格をどのように決定するべきかが課題とな る．仮に第 2 段階（アドエクスチェンジ）のオークショ ンの第二価格を支払額にしたとすると，落札者は DSP 内の第二価格よりも安い価格でインプレッションを落札 できる可能性が生じるため，Web ページ所有者の得られ る利得が減少してしまう．Feldman ら [Feldman 10] や Stavrogiannis and Gerding[Stavrogiannis 14]はこの ような階層構造からなるオークションの解析を行ってい る． 最後に，上述の議論では各オークションは独立として いたが，実際の広告オークションでは各広告主は一定の 予算をもっており，それを各インプレッションに適当に 配分している．そのため，複数のオークションは「予算 制約を介して互いに関係している」と見る必要がある． Balseiroら [Balseiro 15] はこのようなオークションを 予算制約付き繰返しオークションとして定式化し，新し い均衡概念を導入した． 3･2 ユーザ反応予測 広告主（または DSP）の基本的な問題は，各インプ レッションに対していくらで入札すれば自身の利益が最 大になるかを考える入札最適化問題（bid optimization problem）である．入札最適化問題を解くためには，2 種類の予測問題を解くことが重要になる [Zhang 15]．一 つ目は「インプレッションがどれだけの価値をもってい るかを推定する問題」である．これはユーザ反応予測問 題（user response prediction）として定式化できる．本 章ではこの問題について述べる．二つ目は「インプレッションに対していくら支払えば落札できるかを推定する 問題」である．これは入札ランドスケープ予測問題（bid landscape forecasting）として定式化でき，次節で述べ る．これら二つの推定値が得られているとき，入札最適 化問題はオンラインナップサック問題として定式化でき る．これは 3･4 節で述べる． さて，何をインプレッションの価値に設定するかは 広告の目的しだいであるが，典型的には広告をクリック する確率：クリックスルーレート（click through rate: CTR）もしくは，広告を経由して購買行動に至る確率： コンバージョンレート（conversion rate: CVR）を採 用することが多い．インプレッションの情報から CTR/ CVRを予測するタスクは CTR/CVR 予測（CTR/CVR prediction）と呼ばれており，リアルタイム入札におけ る最も基本的な問題として多くの研究がなされている． CTR 予測は KDD Cup 2012 Track 2 [KDD 12]，Kaggle Criteo Display Advertising Challenge [Kaggle 14]， Kaggle Avazu Click-Through Rate Prediction [Kaggle
15]などの機械学習系コンペティションでも繰り返し出
題されている重要な問題である．
各インプレッションには日時・ユーザの IP アドレス・
OS/ブラウザ情報・Web サイトの URL・広告の表示位置・
広告のジャンル，などのさまざまな情報が含まれている． CTR/CVR 予測はこれらの情報からユーザが実際にク リックするかどうかを予測する 2 値予測問題である．正 例（クリックしたデータ）と負例（クリックしなかった データ）の数に大きな偏りはあるものの，毎日 10 億近 いやり取りが行われているため，適当な前処理や後処理 を施すことで十分対応が可能である．そのため，CTR/ CVR 予測は機械学習のタスクとしては比較的扱いやす いものといえる．一方で，CTR/CVR 予測はわずかな精 度向上が収益に直結する部分でもあるため，現在予測モ デルの開発競争は熾烈を極めている． CTR/CVR 予測に対する最も基本的な手法はロジス
ティック回帰である [Lee 12, McMahan 13, Richardson 07]．インプレッションに含まれるほとんどの情報はカ テゴリカルなので，データをベクトル表現する際には各 属性値を別々の次元に対応させた高次元空間をつくり， データに対してそれがもっている属性値に 1 を立てるこ とで素ベクトルをつくることになる．このデータは次元 は大きいものの非ゼロ数は非常に少ないので，確率勾配 法などのアルゴリズムによって高速に学習でき，それな りに高い精度での予測が可能である． より高精度の予測を行うためには，高次元のベクトル を次元削減して利用することが有力である．次元削減の 手段としては，行列分解系の手法 [Juan 17, Menon 11, Oentaryo 14]・勾配ブースティング決定木を用いる手法 [He 14]・深層学習を用いる手法 [Chen 16, Zhang 16a] など，さまざまなものが検討されている． CTR/CVR予測において理論的に難しい点に，学習デー タが原理的にバイアスしてしまうことがあげられる．す なわち，広告主は自分が落札に成功したインプレッショ ンについては正解データが得られるが，自分が落札に失 敗したインプレッションについてのデータが得られない ため，手元のデータセットは必ず「自分が落札に成功し たインスタンス」という形で条件付けられたものとなっ ている．Zhang ら [Zhang 16c] は重点サンプリングを用 いてバイアスを除く手法を提案している． 3･3 入札ランドスケープ予測 入札オークションに参加している広告主が，自身が観 測した情報から他の参加者の状況を推定する問題を入札 ランドスケープ予測という．一般に，入札オークション では数百から数千の広告主がオークションに参加してお り，それぞれの行動を個別に予測するのは極めて難しい ため，入札ランドスケープ予測では入札オークションの 第二価格を確率変数だと考え，その確率分布を求める問 題として定式化することが標準的である．現在この問題 に関する研究は比較的少なく，既存研究は主にヒューリ スティックな解法に集中しているが，入札最適化を行う ためには欠かせない課題であり，今後発展していくと考 えている．
Zhangら [Zhang 14a] は実際の落札価格のデータに対
してカーブをフィットすることで 2 種類の落札確率関数 を得た．また，Cui ら [Cui 11] は落札価格を対数正規分 布の混合分布でモデル化し，勾配ブースティング決定木 を組み合わせることで混合分布を学習する手法を提案し た． 入札ランドスケープ予測で難しいのは，CTR 予測と 同様に，学習データが原理的に打ち切られてしまうこ とにある．このことを解消するため，Wu ら [Wu 15] は 得られていないデータの値を含めて予測する censored logistic regressionの枠組みを用いてランドスケープ予 測を行った．また，Wang ら [Wang 16] は生存分析と決 定木を組み合わせることで打ち切られたデータに対する 予測手法を提案している． 3･4 入 札 最 適 化 インプレッションに対する CTR 予測とランドスケー プ予測ができたとして，最後にやるべきことは実際に入 札最適化を行うことである． 広告主は適当な予算 B をもっているとする．各インプ レッション j に対し，CTR 予測によって期待利得 cjが， ランドスケープ予測によって落札可能額 ajが得られてい るとする．このとき，広告主が解くべき問題はオンライ ンナップサック問題（online knapsack problem）によっ て定式化できる．
min jcjxj s.t. jajxj B, xj∈ {0, 1}n. （1） ここで，オンラインというのはインプレッションが 到達するたびに入札するかどうかを決定しなければなら ず，一度行った決定は後から覆すことができない，とい うことを意味している． ナップサック問題は NP 困難な問題なので厳密解を得 ることは難しく，近似アルゴリズムの設計を目指すこと になる．ところが，オンラインナップサック問題では， 入力に仮定をおかなければ近似アルゴリズムを設計す ることすら不可能であることが示される．このことは以 下の例からわかる．総予算を 1 として，まず価値 1・価 格 1 のインプレッションが到達したとしよう．もしアル ゴリズムがこのインプレッションに入札しなかったとす ると，ここでインプレッションが終了した場合にアルゴ リズムの近似率は無限大になってしまう．一方で，もし アルゴリズムがこのインプレッションに入札したとする と，次に価値 1・価格 1 のアイテムが到達した場合にア ルゴリズムの近似率が無限大になってしまう． この問題を解決して意味のある結果を得るために，以 下の仮定を設定する． （1）各インプレッションの価格は総予算よりも十分小 さい：aj B ． （2）各インプレッションの単位価格当たりの価値 cj/aj は区間 [L, U] に含まれる． 一つ目はリアルタイム入札では通常成立する仮定であ る．また，二つ目も過去のデータセットから学習すれば L, Uの値を推定できるので成立するとしてよい． 以上の設定のもと，Zhou ら [Zhou 08] は次のような入 札アルゴリズムを提案した．関数ΦをΦ（z）＝（L/e）（Ue/ L）zと 定 義 す る．ただし e は自然対数の底である．j 番目のインプレッションが到達した際，もし cj/ aj Φ（zj）が成立していれば j に価格 ajで入札して落札する． ただし，zjはこの時点での予算の消費割合である．Zhou らはこのアルゴリズムが log（Ue/L）近似であることを 証明した．また，これよりも真に良い近似率をもつアル ゴリズムが存在しないことも示した． ここで面白いのは，第二価格オークションのもと，こ の戦略は入札ランドスケープがわからない場合にも実行 できることである．具体的には，広告主は j 番目のイン プレッションに対して cj/Φ（zj）で入札し続ければこの アルゴリズムを動かすのと同等の結果が得られる．実際， もしこの価格で入札して勝ったとすると，他の広告主が 付けた最高価格 ajは cj/Φ（zj） ajを満たしていたことに なる．第二価格オークションなので自身の支払額は ajと なり，このとき cj/ajΦ（zj）となる．同様に，もしこの 価格で入札して負けたとすると，cj/aj＜Φ（zj）となる． したがってアルゴリズムの挙動が元のアルゴリズムと一 致する． オンラインナップサック問題はアルゴリズム理論の 分野で豊富な研究結果がある．Agrawal ら [Agrawal 14]は上と同様の設定で，より一般的なオンライン線形 計画問題に対するアルゴリズムを与えた．Babaioff ら [Babaioff 15]はインプレッションがランダム順に到達す るとして近似アルゴリズムを与えた．インプレッション の価値と価格の分布が既知である場合の解析は古くから 知られている [Lueker 98]． 本稿著者の好みから，上では離散最適化に基づく入 札最適化法を紹介したが，これ以外にもさまざまなア プローチでの入札最適化法が提案されている．例えば， Zhangら [Zhang 16b] はフィードバック制御に基づく手 法を，Cai ら [Cai 17] は強化学習を用いて入札戦略を最 適化する手法を提案している． また，単に合計利得を最大化するだけでなく，広告 配信期間にわたって同じペースで配信を続ける [Lee 13]，同じユーザに一定回数以上広告を表示しない [Buchbinder 14]，複数のタイプの利得を同時に最適化 する [Geyik 16] などの制約付きの入札最適化問題も研究 されている． 3･5 最低落札価格最適化 Webページ所有者（SSP）の目的は，インプレッショ ンをできるだけ高値で広告主に売ることである．Web ページ所有者ができることとして，アドエクスチェン ジに広告を出す際の最低落札価格最適化（reserve price optimization）がある． Webページ所有者がオークションの最低落札価格を設 定することでインプレッションが売れ残る可能性が生じ る．しかし，売れ残りのロスと最低落札価格未満で落札 されるロスを比較して後者が勝る場合には，最低落札額 を設定することによる利得の向上が期待できる． 最適オークション理論 [Myerson 81, Riley 81] によれ ば，Web ページ所有者の利得を最大化する最低落札価格 は以下のように決定できる．広告主 1, …, k のインプレッ ションに対する見積額の分布を F1, …, Fkとし，同時分 布を F（x）＝F（x）…F1 （x）と置く．Web ページ所有者がk 考えるインプレッションの価値を v とするとき，最適最 低落札価格αは方程式 α =1− F (α) F (α) + v （2） の解として与えられる． 検索連動型広告では最適オークション理論の有用性が Ostrovsky and Schwarz [Ostrovsky 11]によって確認さ れている．一方で，ディスプレイ広告ではあまり大きな 利益の増加は確認されないことが Yuan ら [Yuan 14] に よって報告された．その主な原因は，広告主の見積額分 布 F（x）を予測するのが極めて困難だからと考えられて いる．
Yuanら [Yuan 14] は展開型ゲームに基づくヒュー リスティカルな最低落札決定法を提案し，その有用性 を実験的に確認した．Cesa-Bianchi ら [Cesa-Bianchi
15]は価格を適当な幅に刻み，多椀バンディット問題
（multiarmed bandit problem）として定式化することで， 機会損失を抑えるアルゴリズムを提案した．Alcobendas ら [Alcobendas Lisbona 16] は広告オークションを階層 構造からなるオークションと考えて最低落札価格を導出 した．
4．お わ り に
本稿ではインターネット広告の基盤技術となったリア ルタイム入札について概要を述べ，各プレーヤにとって の問題を紹介した． 本稿で説明したのはごく一部であり，これ以外にも多 くの問題が存在する．例えば広告コンテンツの自動生成 [Brunsman 10, Chatwin 12]，Web ページ上の広告配置 を自動化する問題 [Cheng 12, Tang 13]，bot などによ る意味のない広告クリックを検出する問題 [Springborn 13, Stone-Gross 11]，コンバージョンに至ったユーザに ついて各広告の影響度を推定する問題 [Shao 11, Zhang 14b]，アドエクスチェンジのセキュアな実装 [Angel 13] などがある．また，DMP の仕事についてはいっさい紹 介していないが，これは Elmeleegy ら [Elmeleegy 13] を参照されたい． リアルタイム入札は現在も実用・理論の両面で急速に 成長している領域である．そのため，この領域の研究者 は最新の研究結果を確認しておくことが重要となる．本 稿の参考文献欄を見ればわかるように，この分野の最新 の研究結果は主にデータマイニング系の国際会議で発表 さ れ て お り，KDD，ICDM，CIKM，WSDM，WWW などのトップ会議でも頻出のトピックとなっている．ま た，オークション系の話題は AAAI，IJCAI，AAMAS のような人工知能系トップ会議や，EC などの理論に近 い会議に出ることもある． より手軽な情報源として，上海交通大学の Weinan Zhang氏が管理している Web サイト＊1がある．ここに はリアルタイム入札に関する論文がまとめられており， この分野で論文を探したい場合はまずここを当たるとよ い． 謝 辞 本特集号への執筆を推薦していただいた株式会社サイ バーエージェントの川端貴幸氏に御礼申し上げます．◇ 参 考 文 献 ◇
[Agrawal 14] Agrawal, S., Wang, Z. and Ye, Y.: A dynamic nearoptimal algorithm for online linear programming,
Operations Research, Vol. 62, No. 4, pp. 876-890（2014） [Alcobendas Lisbona 16] Alcobendas Lisbona, M. A., Chammas, S.
and Lee, K.-C.: Optimal reserve prices in upstream auctions: Empirical application on online video advertising, Proc. 22nd
ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1395-1404（2016）
[Angel 13] Angel, S. and Walfish, M.: Verifiable auctions for online ad exchanges, Proc. 2013 ACM SIGCOMM Conf. on
Internet Measurement Conference, pp. 195-206（2013） [Babaioff 15] Babaioff, M., Dughmi, S., Kleinberg, R. and
Slivkins, A.: Dynamic pricing with limited supply, ACM Trans.
on Economics and Computation, Vol. 3, No. 1, p. 4（2015） [Balseiro 15] Balseiro, S. R., Besbes, O. and Weintraub, G.
Y.: Repeated auctions with budgets in ad exchanges: Approximations and design, Management Science, Vol. 61, No. 4, pp. 864-884（2015）
[Brunsman 10] Brunsman, L. J., Rajaraman, S., Deshwal, P., Wytock, M. D. and Kates, S.: Automatic Ad Creative Generation, US Patent App. 12/846, 315（2010）
[Buchbinder 14] Buchbinder, N., Feldman, M., Ghosh, A. and Naor, J.: Frequency capping in online advertising, J. of
Scheduling, Vol. 17, No. 4, pp. 385-398（2014）
[Cai 17] Cai, H., Ren, K., Zhang, W., Malialis, K., Wang, J., Yu, Y. and Guo, D.: Real-time bidding by reinforcement learning in display advertising, Proc. 10th ACM Int. Conf. on Web Search
and Data Mining（2017）
[Cesa-Bianchi 15] Cesa-Bianchi, N., Gentile, C. and Mansour, Y.: Regret minimization for reserve prices in second-price auctions, IEEE Trans. on Information Theory, Vol. 61, No. 1, pp. 549- 564（2015）
[Chatwin 12] Chatwin, R. E., Nukala, M. V., Coleman, A., Lokeswarappa, K. G. and Kondaji, S. R.: Real-Time Bidding and Advertising Content Generation, US Patent App. 13/725, 821 （2012）
[Chen 16] Chen, J., Sun, B., Li, H., Lu, H. and Hua, X.-S.: Deep CTR prediction in display advertising, Proc. 24th ACM
Multimedia Conference, pp. 811-820（2016）
[Cheng 12] Cheng, H., Manavoglu, E., Cui, Y., Zhang, R. and Mao, J.: Dynamic ad layout revenue optimization for display advertising, Proc. 6th Int. Workshop on Data Mining for Online
Advertising and Internet Economy, p. 9（2012）
[Cui 11] Cui, Y., Zhang, R., Li, W. and Mao, J.: Bid landscape forecasting in online ad exchange marketplace, Proc. 17th
ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 265-273（2011）
[電通 17] 電通：2016 年日本の広告費（2017）
[Elmeleegy 13] Elmeleegy, H., Li, Y., Qi, Y.,Wilmot, P.,Wu, M., Kolay, S., Dasdan, A. and Chen, S.: Overview of turn data management platform for digital advertising, Proc. VLDB
Endowment, Vol. 6, No. 11, pp. 1138-1149（2013）
[Feldman 10] Feldman, J., Mirrokni, V., Muthukrishnan, S. and Pai, M. M.: Auctions with intermediaries, Proc. 11th ACM
Conf. on Electronic Commerce, pp. 23-32（2010）
[Geyik 16] Geyik, S. C., Faleev, S., Shen, J., Sean O’Donnell, Kolay, S.：Joint optimization of multiple performance metrics in online video advertising, Proc. 22nd ACM SIGKDD Int.
Conf. on Knowledge Discovery and Data Mining, pp. 471-480
（2016）
[He 14] He, X., Pan, J., Jin, O., Xu, T., Liu, B., Xu, T., Shi, Y., Atallah, A., Herbrich, R. and Bowers, S., et al.: Practical lessons from predicting clicks on ads at facebook, Proc. 8th
Int. Workshop on Data Mining for Online Advertising, pp. 1-9
（2014）
[IAB 17] IAB: 2016 Internet Advertising Revenue Full-Year Report（2017）
[Juan 17] Juan, Y., Lefortier, D. and Chapelle, O.: Field-aware ＊1 https://github.com/wnzhang/rtb-papers
factorization machines in a real-world online advertising system, Proc. 26th Int. Conf. on World Wide Web, pp. 680-688 （2017）
[Kaggle 14] Kaggle: Criteo Display Advertising Challenge（2014） [Kaggle 15] Kaggle: Avazu Click-Through Rate Prediction（2015） [KDD 12] KDD: KDD Cup 2012, Track 2: Predict the
click-through rate of ads given the query and user information （2012）
[Lee 12] Lee, K.-C., Orten, B., Dasdan, A. and Li, W.: Estimating conversion rate in display advertising from past Prformance data, Proc. 18th ACM SIGKDD Int. Conf. on Knowledge
Discovery and Data Mining, pp. 768-776（2012）
[Lee 13] Lee, K.-C., Jalali, A. and Dasdan, A.: Real time bid optimization with smooth budget delivery in online advertising, Proc. 7th Int. Workshop on Data Mining for Online
Advertising, p. 1（2013）
[Lueker 98] Lueker, G. S.: Average-case analysis of off-line and online knapsack problems, J. of Algorithms, Vol. 29, No. 2, pp. 277-305（1998）
[McMahan 13] McMahan, H. B., Holt, G., Sculley, D., Young, M., Ebner, D., Grady, J., Nie, L., Phillips, T., Davydov, E. and Golovin, D., et al.: Ad click prediction: A view from the trenches, Proc. 19th ACM SIGKDD Int. Conf. on Knowledge
Discovery and Data Mining, pp. 1222-1230（2013）
[Menon 11] Menon, A. K., Chitrapura, K.-P., Garg, S., Agarwal, D. and Kota, N.: Response prediction using collaborative filtering with hierarchies and side-information, Proc. 17th ACM
SIGKDD Int. Conf. on Knowledge Discovery and Data Mining,
pp. 141-149（2011）
[Myerson 81] Myerson, R. B.: Optimal auction design,
Mathematics of Operations Research, Vol. 6, No. 1, pp. 58-73
（1981）
[Oentaryo 14] Oentaryo, R. J., Lim, E.-P., Low, J.-W., Lo, D. and Finegold, M.: Predicting response in mobile advertising with hierarchical importance-aware factorization machine, Proc.
7th ACM Int. Conf. on Web Search and Data Mining, pp.
123-132（2014）
[Ostrovsky 11] Ostrovsky, M. and Schwarz, M.: Reserve prices in internet advertising auctions: a field experiment, Proc. 12th
ACM Conf. on Electronic Commerce, pp. 59-60（2011） [Richardson 07] Richardson, M., Dominowska, E. and Ragno,
R.: Predicting clicks: Estimating the click-through rate for new ads, Proc. 16th Int. Conf. on World Wide Web, pp. 521-530 （2007）
[Riley 81] Riley, J. G. and Samuelson, W. F.: Optimal auctions,
The American Economic Review, Vol. 71, No. 3, pp. 381-392
（1981）
[Shao 11] Shao, X. and Li, L.: Data-driven multi-touch attribution models, Proc. 17th ACM SIGKDD Int. Conf. on
Knowledge Discovery and Data Mining, pp. 258-264（2011） [Springborn 13] Springborn, K. and Barford, P.: Impression fraud
in on-line advertising via pay-per-view networks, USENIX
Security, pp. 211-226（2013）
[Stavrogiannis 14] Stavrogiannis, L. C., Gerding, E. H. and Polukarov, M.: Auction mechanisms for demand-side intermediaries in online advertising exchanges, Proc. 2014
Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp.
1037-1044（2014）
[Stone-Gross 11] Stone-Gross, B., Stevens, R., Zarras, A., Kemmerer, R., Kruegel, C. and Vigna, G.: Understanding fraudulent activities in online ad exchanges, Proc. 2011 ACM
SIGCOMM Conf. on Internet Measurement Conference, pp.
279- 294（2011）
[Tang 13] Tang, L., Rosales, R., Singh, A. and Agarwal, D.: Automatic ad format selection via contextual bandits,
Proc. 22nd ACM Int. Conf. on Information and Knowledge Management, pp. 1587-1594（2013）
[Wang 16] Wang, Y., Ren, K., Zhang,W.,Wang, J. and Yu, Y.: Functional bid landscape forecasting for display advertising,
Joint European Conf. on Machine Learning and Knowledge Discovery in Databases, pp. 115-131（2016）
[Wu 15] Wu, W. C.-H., Yeh, M.-Y. and Chen, M.-S.: Predicting winning price in real time bidding with censored data, Proc.
21st ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1305-1314（2015）
[Yuan 13] Yuan, S., Wang, J. and Zhao, X.: Real-time bidding for online advertising: Measurement and analysis, Proc. 7th Int.
Workshop on Data Mining for Online Advertising, p. 3（2013） [Yuan 14] Yuan, S., Wang, J., Chen, B., Mason, P. and Seljan, S.:
An empirical study of reserve price optimisation in real-time bidding, Proc. 20th ACM SIGKDD Int. Conf. on Knowledge
Discovery and Data Mining, pp. 1897-1906（2014）
[Zenith 17] Zenith: Advertising Expenditure Forecasts March 2017（2017）
[Zhang 14a] Zhang, W., Yuan, S. and Wang, J.: Optimal real-time bidding for display advertising, Proc. 20th ACM SIGKDD Int.
Conf. on Knowledge Discovery and Data Mining, pp. 1077-1086
（2014）
[Zhang 14b] Zhang, Y., Wei, Y. and Ren, J.: Multi-touch attribution in online advertising with survival theory, Proc.
14th Int. Conf. on Data Mining, pp. 687-696（2014）
[Zhang 15] Zhang, W. and Wang, J.: Statistical arbitrage mining for display advertising, Proc. 21st ACM SIGKDD Int. Conf. on
Knowledge Discovery and Data Mining, pp. 1465-1474（2015） [Zhang 16a] Zhang, W., Du, T. and Wang, J.: Deep learning over multi-field categorical data, European Conf. on Information
Retrieval, pp. 45-57（2016）
[Zhang 16b] Zhang, W., Rong, Y., Wang, J., Zhu, T. and Wang, X.: Feedback control of real-time display advertising, Proc. 9th
ACM Int. Conf. on Web Search and Data Mining, pp. 407-416
（2016）
[Zhang 16c] Zhang, W., Zhou, T., Wang, J. and Xu, J.: Bid-aware gradient descent for unbiased learning with censored data in display advertising, Proc. 22nd ACM SIGKDD Conf. on
Knowledge Discovery and Data Mining, Vol. 22, pp. 665-674
（2016）
[Zhou 08] Zhou, Y., Chakrabarty, D. and Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems, Int. Workshop on Internet and Network Economics, pp. 566-576（2008） 2017年 5 月 22 日 受理
