---
title: WSDM2016報告会−論文紹介(Multi-Score Position Auctions)#yjwsdm
tags:  #yjwsdm  
author: [Yahoo!デベロッパーネットワーク](https://www.docswell.com/user/ydnjp)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/V7N5MGLDE8.jpg?width=480
description: 4/6にヤフー株式会社で開催されたWSDM報告会の発表資料です。 http://yahoo-ds-event.connpass.com/event/28441/
published: April 27, 16
canonical: https://www.docswell.com/s/ydnjp/5MREJK-2016-04-27-152528
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/V7N5MGLDE8.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/YJ9YNW4873.jpg)

本日紹介する論文
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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/GJ86KNQZED.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/LJL9ZPX17R.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/47MZV4L5JW.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/P7R62WKZE9.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/PJXMDPL1EX.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/3JKGXDLM7D.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LE3N5R32E5.jpg)

提案手法: 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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/8EDWDY467G.jpg)

実験
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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/V7P9X6VZJ8.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/2JVML3ZMJQ.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/5EGGX34XEL.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/4JQX85G5EP.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/K746295VE1.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/LJ1VMKW4EG.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/GJWL3D6ZE2.jpg)

DSA 𝛼, 1 で収入が上がることへの直感的な理由付け
GSP order : 入札額 𝑏 とクリック率 𝑒 の積 𝑏𝑒 が大きい順に割り当て
Click-probability order : クリック率 𝑒 が大きい順
Squashed-GSP order : 𝑏𝑒 𝛼 が大きい順（0 &lt; 𝛼 &lt; 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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/4EZMVGYLJ3.jpg)

Symmetric Nash Equilibrium
(Varian. 2006)
スロットを決めるためのランキング順に広告の番号を付与するものとする．
𝑖番目の slot の CTR を位置の寄与分𝑥𝑖 と広告の関連度𝑒𝑖 の積とし，真の価値を
𝑣𝑖 ，ランキングに用いるスコアを 𝑠𝑖 ，入札額を𝑏𝑖 としたとき Nash Equilibrium
となるための条件は次のようにかける
𝑠𝑗+1
𝑠𝑖+1
𝑒𝑖 𝑥𝑖 𝑣𝑖 −
𝑏 ≥ 𝑒𝑖 𝑥𝑗 𝑣𝑖 −
𝑏
∀𝑗 &gt; 𝑖
𝑠𝑖 𝑖
𝑠𝑖 𝑗+1
𝑠𝑗
𝑠𝑖+1
𝑒𝑖 𝑥𝑖 𝑣𝑖 −
𝑏𝑖 ≥ 𝑒𝑖 𝑥𝑗 𝑣𝑖 − 𝑏𝑗 ∀𝑗 &lt; 𝑖
𝑠𝑖
𝑠𝑖
∀𝑗 &gt; 𝑖 のときの条件をすべての 𝑗 について適用した次のような条件を満たす状態
を 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


