Online Matching and Ad Allocation 勉強会のメモ (自分用) です。
証明とか辛いのは省略しています。
Adwords problem の問題設定
- Online bipartite matching 問題の一般化
- 頂点 $u \in U$ は予算 $B_u$ を持つ
- 辺 $(u, v) \in E$ は入札額 $bid_{uv}$ を持つ
- 次々に到着する頂点 $v \in V$ と $u \in U$ をマッチングさせたい
- マッチング先の $u$ は、それまでに消化した予算が $B_u$ を超えていないことが条件となる
- この条件において、消化予算を最大化する問題が Adwords problem になる
- この状況はつまり、Sponsored search に相当する
- $u \in U$ は、広告主を表す
- $B_u$ は、広告主 $u$ の一日あたりの予算を表す
- $v \in V$ は広告枠 or クエリを表す
- この章では、広告枠 $v$ に広告主 $u$ の広告が配置された場合に $bid_{uv}$ を課金するものとしている
- これは first price auction かつ CPM 課金に相当するものだと思えばよさそう
- 実際の Sponsored search においては、second price auction だったり CPC 課金だったりする
5.1 The Small-Bids Assumption
- ここで「1日辺りの予算 $B_u$ に対して、入札額 $bid_{uv}$ はとても小さい」という仮定 small-bids assumption をおく
5.2 Adversarial order
GREEDY アルゴリズム
- $v$ が到着する都度、その $v$ に隣接する広告主 $u$ のうち、最大の入札額を示す広告主とマッチングさせる、というアルゴリズム
- 広告主 $u$ の消化済み予算を $S_u$ としたときに、一日あたりの予算 $B_u$ を超えないようにするために実際の入札額 $\widehat{bid_{uv}}$ を調整 (bid-capping) する
\widehat{bid_{uv}} = \min(bid_{uv}, B_u - S_u)
- しかしながら、small-bids assumption の仮定のもとではこの bid-capping を無視できる
- GREEDY アルゴリズムの競合比は $\frac{1}{2}$ となる
Theorem 5.3 の証明メモ
- アルゴリズムによって割り当てをした結果、生じた損失 (最適値からの乖離) は $Loss = \sum_{v \in V'} (opt_v - alg_v)$ で表される
- $opt_v$ は、$v$ を最適に割り当てた場合に得られる価値
- $alg_v$ は、$v$ をアルゴリズムに従って割り当てた場合に得られる価値
- $V'$ は、最適割り当てに対してアルゴリズムの割り当てが価値的に減少する、つまり $alg_v < opt_v$ の場合の $v$ の集合
- 割り当てが最適でない $v$ の集合、と言える
- この $Loss$ を、最適配置した場合の広告主 $u \in U$ ごとの損失 $Loss_u$ に分解する
- $V'_u$ は、$V'$ に含まれる $v$ のうち、最適解では $u \in U$ に割り当てられるものの集合
Loss_u := \sum_{v \in V'_u}{(opt_v - alg_v)} \\
Loss_u \le B_u - \sum_{v \in V'_u}alg_v
- (あとは省略)
BALANCE アルゴリズム
- GREEDY アルゴリズムが入札額のみに着目していたのに対し、BALANCE アルゴリズムは予算消化率に着目する
- 具体的には、すべての広告主の予算消化率を揃えるように、広告枠 $v$ に隣接する広告主 $u$ のうち、最も予算消化率の低い広告主を選んでマッチングさせる
Online b-Mathcing
- Adwords problem の特殊ケース
- すべての広告主の予算が $b$ に等しい
- また入札額は $1$ である
- この特殊ケースにおいては、BALANCE アルゴリズムが最適なアルゴリズムとなる
- 競合比は $1 - \frac{1}{(1 + 1/b)^b}$ となる
- これは $b \rightarrow \infty$ とすると、 $1 - \frac{1}{e}$ になる
MSVV アルゴリズム
- GREEDY と BALANCE のハイブリッドさせたようなアルゴリズムによって、より良い競合比が得られるのではないだろうか
- Mehta らによるアルゴリズム MSVV が、それに相当する
- AdWords and Generalized On-line Matching
- $x_u$ を、広告主 $u$ の予算消化率 $S_u / B_u$ とし、トレードオフ関数 $\psi(x_u)$ を次のように定義する
\psi(x_u) = 1 - e^{x_u - 1}
- この関数 $\psi(x_u)$ によって計算された値を $bid_{uv}$ に乗じた値を scaled bid とする
- マッチングでは、この scaled bid が大きいものを選択する
- この scaled bid は勝者を決定する処理においてのみ利用し、広告主が払うべき金額は $bid_{uv}$ のままである
- すべての広告主の入札額が等しい場合は、BALANCE アルゴリズムのように振る舞う
- 入札額に大きな隔たりがある場合は、GREEDY アルゴリズムのように振る舞う
- 入札額が高い広告主の予算消化率が大きく、一方で入札額の低い広告主の予算消化率が小さい場合はその限りではない
- 予算が無限大であれば、GREEDY アルゴリズムとして振る舞う
- このアルゴリズムの競合比は $1 - \frac{1}{e}$ であり、これは最適である
5.3 Random Order and IID
- GREEDY の競合比
- Random Order: $1 - \frac{1}{e}$
- Unknown IID: $1 - \frac{1}{e}$
- BALANCE の競合比
- (これ以降は気が向いたら追記する)