Revenue Maximization in Incentivized Social Advertising - todo314 @ ウィキ

Revenue Maximization in Incentivized Social Advertising

• Çigdem Aslay, Francesco Bonchi, Laks V. S. Lakshmanan, Wei Lu
• VLDB 2017

概要

• Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret VLDB'15の続き感
• Incentivized: ユーザにも収入の分け前を上げる設定
• 単調劣モジュラ最大化 with 分割マトロイド制約 (for 広告-シード配置) and 劣モジュラナップサック制約 (for 各広告主の予算)
• 2つの近似手法を提案して、RISで高速化

定式化

広告主の支払い総額		エンゲージメントへの支払い		各シードへの支払い
$$\rho_i(S_i)$$	$$=$$	$$\pi_i(S_i)$$	$$+$$	$$ c_i(S_i) $$
$$\leq B_i$$ 予算		$$cpe(i) \cdot \sigma_i(S_i)$$		$$ \sum_{u \in S_i}c_i(u) $$

• $$ c_i(u) $$は$$\sigma_i(\{u\})$$の単調関数
• ホスト側
  • 収入 $$ \pi_i(S_i) $$
  • 影響力高い人を使いたいけど高いので辛い
• maximize $$ \pi(\mathcal{S}) = \sum_{i \in [h]}\pi_i(S_i) $$ … ホストの収入
• subject to
  • $$ \rho_i(S_i) \leq B_i \quad \forall i $$ … 各広告主の予算上限
  • $$ S_i \cap S_j = \emptyset \quad \forall i \neq j $$ … 高々1つの広告
• 性質
  • πもcも単調劣モジュラ関数
  • $$ (u,i) $$（uはユーザ、iは広告）と考えると、分割マトロイド

アルゴリズム

• ① $$ \pi_i $$の増分最大の$$ (u^*,i^*) $$を選択
• ② $$ \pi_i / \rho_i $$の増分最大の$$ (u^*,i^*) $$を選択
• 解析を頑張ってそこそこきれいなバウンドが出ている？
• 高速化： い つ も の

  Thus a direct application of these algorithms is not possible

  • はい

実験

• はい余裕

まとめ

• いつもの流れという感じ
  • 似た研究の中では良い方だと思う

VLDB オンライン広告 影響最大化

2017/09/20