WSDM2016報告会−論文紹介(Multi-Score Position Auctions)#yjwsdm

WSDM2016報告会 Multi-Score Position Auctions ヤフー株式会社 平澤 謙章 2016年04月06日

本日紹介する論文 D. Charles, N. R. Devanur and B. Sivan. Multi-Score Position Auctions. WSDM2016 • • • スポンサードサーチのためのオークションについて 収入と CTR の双方を向上させる（可能性がある） オークションの形式を提案 著者らは Microsoft, Microsoft Research に所属 論文URL http://dl.acm.org/citation.cfm?id=2835822 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 2

• http://dl.acm.org/citation.cfm?id=2835822

スポンサードサーチ 検索クエリに応じて，関連する広告をリスト表示 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 3

Position Auctions 課金額 表示場所 広告 入札額 ¥6/click Slot 1 英会話の Foo ¥8/click ¥4/click Slot 2 生花教室 ¥15/click ¥3/click Slot 3 英会話教室 ¥10/click English 教室 ¥6/click 入札状況と表示順位 に応じて課金額を決定 広告のクエリとの 関連性や入札額 (bid) に応じて配置を決定 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 広告媒体が決定 広告主が決定 4

Position Auctions の仕組みを決める基準 収入の最大化だけを目標にすると・・・ • ユーザの興味に近い広告が出ないと満足度が下がる • クリックが少ないわりに高い金を取られると広告主は不満を募 らせる 当論文ではユーザ・広告主側の利益の指標の一つとして CTR (Click Through Rate) を利用している 収入と CTR ともに高くなるオークションが好ましい Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 5

Generalized Second Price Auctions (GSP) 適当なスコアに従って並び替えた後に， その順位を維持するために最低限必要な金額を課金する方式． Ex. 入札額で順位を決定する場合 課金額 表示場所 広告 入札額 ¥9/click Slot 1 Ad 1 ¥8/click ¥8/click Slot 2 Ad 2 ¥6/click ¥6/click Slot 3 Ad 3 ¥15/click Ad 4 ¥9/click Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 7

Generalized Second Price Auctions (GSP) 適当なスコアに従って並び替えた後に， その順位を維持するために最低限必要な金額を課金する方式． Ex. 入札額×関連度で順位を決定する場合 (単位省略) 課金額 表示場所 広告 (単位省略) 入札額 × 関連度 9 / 2.0 = 4.5 Slot 1 Ad 1 8 × 0.75 = 6 6 / 1.0 = 6 Slot 2 Ad 2 6 × 2 = 12 3 / 0.75 = 4 Slot 3 Ad 3 15 × 0.2 = 3 Ad 4 9×1=9 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 8

GSP with squashing (Lahaie and Pennock. EC’07) 入札額を 𝑏, 関連度を 𝑒 として 𝑏𝑒 𝛼 を基にランク付け 収入，クリック率ともに前述の手法より良くなる 𝛼 = 0 ⇔ 入札額順の GSP 𝛼 = 1 ⇔ 入札額 × 関連度順の GSP 0 < 𝛼 < 1 はその中間 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 9

提案手法: Dual score auctions (DSA) 1位を決めるためのスコア関数のみ 𝑏𝑒 𝛼 とし，それ以外には 𝑏𝑒 𝛽 を用いる．これを DSA(𝛼, 𝛽) と表記する Ex. DSA(0, 1)の場合 (単位省略) 課金額 表示場所 広告 (単位省略) 入札額 × 関連度 max(8, 3 / 1) = 8 Slot 1 Ad 1 8 × 0.75 = 6 6/2=3 Slot 2 Ad 2 6 × 2 = 12 3 / 0.75 = 4 Slot 3 Ad 3 15 × 0.2 = 3 Ad 4 9×1=9 ※ スコア関数を表示場所分用意するさらに一般的な方式 (Multi-Score Position Auctions)も提案 されていましたが、実験・評価が行われていないこともあり、発表時間の都合により割愛します。 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 11

実験 DSA(𝛼, 𝛼) に対する DSA 𝛼, 1 の収入と CTR の増分を評価 DSA 𝛼, 𝛼 : GSP with squashing (𝑏𝑒 𝛼 によるランキング） DSA 𝛼, 1 : 最上位の広告を決定するときだけ 𝑏𝑒 𝛼 を利用 それ以外の時は 𝑏𝑒 によるランキング ２つの条件で評価 • First order effects 現状の入札状況のままオークション方式を変えた場合の評価 • Second order effects 均衡状態となり入札額が変化しなくなった状態での評価 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 12

First order effects 現在の入札額のままオークション方式を変更した場合 収入の増分 CTR の増分 ※ 論文より引用 • Bing を用いてランダムな並びで広告を掲示． • 調べたい方式と同じ並びの結果を抽出し，収入と CTR を計算 • 平衡点における結果ではないことに注意 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 13

Second order effects Symmetric Nash Equilibrium (SNE) での収入と CTR 合計の増分 ※ 論文より引用 収入の増分 CTR の増分 関連度 𝑒 の高い SNE を選択 広告主の考える真の価値 𝑣 × 関連度 𝑒 の高い SNE を選択 • 関連度と広告主が考える広告枠の価値の分布については，別論文が Yahoo Inc. のデータをもとに算出した分布を利用 • SNE は Nash 均衡の制約をさらに厳しくした均衡状態で，実際のデータでも 広告主の振る舞いがこれに近くなることがわかっている (Varian. 2006) Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 14

Second order effects Symmetric Nash Equilibrium (SNE) での収入と CTR 合計の増分 収入の増分 CTR の増分 ※ 論文より引用 広告主の考える真の価値 𝑣 ，関連度 𝑒 として 𝑣𝑒 𝛼 の高い SNE を選択 • 関連度と広告主が考える広告枠の価値の分布については，別論文が Yahoo Inc. のデータをもとに算出した分布を利用 • SNE は Nash 均衡の制約をさらに厳しくした均衡状態で，実際のデータでも 広告主の振る舞いがこれに近くなることがわかっている (Varian. 2006) Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 15

まとめ • • • • ランキングに用いるスコアを複数用意するオークション方式を 提案した DSA の中でも特に最上位の slot の決定の際だけ squashing を 行う場合について評価 Bing のデータを用いて一時的な効果をシミュレーションしたと ころ、収入と CTR ともに改善 Yahoo Inc. のデータを基にした平衡点の分析でも収入と CTR ともに改善させられる可能性を示した Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 16

ご清聴ありがとうございました Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 17

補足資料 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 18

DSA 𝛼, 1 で収入が上がることへの直感的な理由付け GSP order : 入札額 𝑏 とクリック率 𝑒 の積 𝑏𝑒 が大きい順に割り当て Click-probability order : クリック率 𝑒 が大きい順 Squashed-GSP order : 𝑏𝑒 𝛼 が大きい順（0 < 𝛼 < 1 とする） 簡単のため広告が二つだけのときを考えると、次の３つの場合がある 1. GSP order = Squashed-GSP order = Click-probability order 2. GSP order = Squashed-GSP order ≠ Click-probability order 3. GSP order = Click-probability order ≠ Squashed-GSP order GSP の収入に比べて GSP with squashing の収入が上がるのは 1. の場合のみ． 最上位の slot に割り当てられた広告は GSP order でも Click-probability order でも最大になっていることが多い．順位が下がると 2. や 3. の状況に近づく． ※ ただし、この考察はオークションの仕組みによって平衡点の入札額 𝑏 が変化すること を考慮していないので信憑性があるのかは不安（これは個人の感想です） Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 19

Symmetric Nash Equilibrium (Varian. 2006) スロットを決めるためのランキング順に広告の番号を付与するものとする． 𝑖番目の slot の CTR を位置の寄与分𝑥𝑖 と広告の関連度𝑒𝑖 の積とし，真の価値を 𝑣𝑖 ，ランキングに用いるスコアを 𝑠𝑖 ，入札額を𝑏𝑖 としたとき Nash Equilibrium となるための条件は次のようにかける 𝑠𝑗+1 𝑠𝑖+1 𝑒𝑖 𝑥𝑖 𝑣𝑖 − 𝑏 ≥ 𝑒𝑖 𝑥𝑗 𝑣𝑖 − 𝑏 ∀𝑗 > 𝑖 𝑠𝑖 𝑖 𝑠𝑖 𝑗+1 𝑠𝑗 𝑠𝑖+1 𝑒𝑖 𝑥𝑖 𝑣𝑖 − 𝑏𝑖 ≥ 𝑒𝑖 𝑥𝑗 𝑣𝑖 − 𝑏𝑗 ∀𝑗 < 𝑖 𝑠𝑖 𝑠𝑖 ∀𝑗 > 𝑖 のときの条件をすべての 𝑗 について適用した次のような条件を満たす状態 を Symmetric Nash Equilibrium と呼ぶ 𝑠𝑗+1 𝑠𝑖+1 𝑒𝑖 𝑥𝑖 𝑣𝑖 − 𝑏 ≥ 𝑒𝑖 𝑥𝑗 𝑣𝑖 − 𝑏 𝑠𝑖 𝑖 𝑠𝑖 𝑗+1 GSP では，SNE のうち収入が最小になる状態は Edelman et al. (2006) による local envy-free equilibrium と同義．一つ上の slot の広告と入札額を交換して も利益が出ない，という条件になっている．これは他の広告主の出費を増やすた めに自らの広告の入札額をギリギリまで上げるという戦略に相当している． Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 20