Assortment Planning with Sponsored Products

技術要約：スポンサー製品を伴うアソートメント・プランニング

問題提起
本論文は、電子商取引（eコマース）およびレコメンデーション・システムにおけるアソートメント・プランニング（品揃え計画）の問題を取り上げ、特に従来のオーガニック製品に加えてスポンサー製品を含める形へと範囲を拡張している。先行研究（例：Talluri and Van Ryzin 2004）は主にオーガニック製品に焦点を当ててきたが、スポンサー枠（例：Amazon、Facebook、Google上での配置）の台頭により、複雑な最適化の課題が生じている。プラットフォームは、広告主によって課される特定の制約を遵守しつつ、期待収益を最大化するように、$k$ 個の製品を選択し、配置する必要がある。

核心となる困難さは、プラットフォームの収益目標と、スポンサー製品の必須要件とのバランスを取る点にある。任意のポジションに配置できるオーガニック製品とは異なり、スポンサー製品は多くの場合、オークション・メカニズム（例：広告主が「トップ$m$」のポジションや、品質スコアに基づく特定のスロットに対して入札する等）から派生する厳格な配置制約を伴う。本問題は、**多項ロジット（MNL）**選択モデルの下で、期待収益を最大化する実行可能な製品シーケンスを見出すという、組合せ最適化タスクとして定式化される。

手法
著者らは、消費者の選択行動をMNLモデルを用いてモデリングしている。ここでは、特定のポジションにおける製品 $i$ の選択確率は、その製品固有の効用と、表示されている他のすべての製品の効用に依存する。選択確率の分母には選択された全アイテムの効用の総和が含まれるため、収益関数は非線形となる。

著者らは、制約条件に応じて2つのアルゴリズム的アプローチを提案している：

1. 基本制約に対する厳密解:
   制約がスポンサー製品の強制的な配置（各スポンサー製品 $i$ が有効なポジション $t \in R_i$ に割り当てられなければならない）のみである場合、本問題は割当問題として定式化される。著者らは、この制約行列が**全単模（totally unimodular）**であることを示している。その結果、整数制約を線形計画法（LP）定式化に緩和することで、問題を最適に解くことができ、これは整数解を与えることが保証される。

2. 拡張制約に対する近似アルゴリズム:
   本論文は、オーガニック製品の選択に関する追加の制約（容量（ナップサック）制約（総コスト $\le C$）や、分割マトロイド制約（特定のグループからのアイテム数の制限）など）を含むように問題を拡張している。

• 分解戦略: 最適解は、スポンサー製品による収益とオーガニック製品による収益の2つの部分に分解される。著者らは、2つの候補アソートメントを構築する：
  • 候補 I: （オーガニック製品を無視して）スポンサー製品のみを考慮して収益を最適化する。
  • 候補 II: まず、オーガニック製品の選択のために効用を「節約」するようにスポンサー製品の総重量（効用）を最小化し、次に、固定されたスポンサー選択を前提としてオーガニック製品のアソートメントを最適化する。
• ランダム選択: 最終的な解は、これら2つの候補のうち、より優れた方を選択する。理論的分析によれば、もしオーガニックの部分問題（P.5）が比率 $\beta$ 以内で近似可能であれば、全体のアルゴリズムは近似比 $\frac{\beta}{\beta+1}$ を達成する。
• 劣モジュラ最適化: 複雑な制約下でのオーガニック製品の部分問題（P.5）を解くために、著者らはシーケンシング問題を、製品とポジションのペアからなる基集合上の部分集合選択問題へと変換する。彼らは、結果として得られる効用関数が**単調かつ劣モジュラ（submodular）**であることを証明している。これにより、最新の劣モジュラ最大化アルゴリズムの適用が可能となる：
  • ナップサック制約については、比率 $\beta = 1/(1+\epsilon)^3$ を達成するアルゴリズムを利用する。
  • 分割マトロイド制約については、比率 $\beta = 1/(2+\epsilon)$ を達成するアルゴリズムを利用する。

主な貢献

• 問題の定式化: 本論文は、スポンサー製品の配置制約が存在する場合のアソートメント・プランニング問題を正式に定義した。これは、すべての製品をオーガニックと仮定したり、スポンサーの統合を無視したりすることが多かった既存の文献におけるギャップを特定したものである。
• 理論的保証: 理論的な境界を与えないディープラーニングによるヒューリスティック（例：Liao et al. 2022）とは異なり、本論文は厳密な近似保証を提供している。
• アルゴリズムの枠組み: 著者らは、プラットフォームの収益最大化と広告主の制約との間の溝を埋めるフレームワークを開発した。基本問題はLPを通じて多項式時間で解けることを証明し、オーガニック製品の容量または多様性制約を伴うより複雑なバリアントに対して、定数倍近似アルゴリズムを提供している。
• 劣モジュラ性の証明: 技術的な重要な貢献は、オーガニック製品の選択のための変換された効用関数が劣モジュラであるという証明であり、これによりNP困難な制約に対する効率的な近似アルゴリズムの使用が可能となっている。

結果
本論文は以下の理論的結果を確立している：

• 基本問題（スポンサー制約のみ）については、最適解を効率的に計算できる。
• 拡張問題（スポンサー制約 ＋ オーガニックの容量/マトロイド制約）については、提案されたアルゴリズムが以下の近似比を達成する：
  • ナップサック制約の場合：$\frac{1}{(1+\epsilon)^3 + 1}$
  • 分割マトロイド制約の場合：$\frac{1}{(2+\epsilon) + 1}$
  • （注：論文では、最終的な比率は、部分問題の近似比を $\beta$ とすると $\frac{\beta}{\beta+1}$ であると導出されている）。

意義と主張
著者らは、スポンサー製品の統合を明示的にモデリングすることで、本研究がアソートメント・プランニングの文献における決定的なギャップに対処していると主張している。本研究の意義は、プラットフォームの目標（収益最大化）と広告主の目標（特定の配置要件）という、しばしば相反する目標のバランスを取るための理論的保証を提供している点にある。本論文は、そのアプローチが、ヒューリスティックな性能ではなく、証明可能な数学的境界に基づき、全体的な収益戦略やユーザー体験を損なうことなく、スポンサー製品をシームレスに統合する方法を企業に提供するものであると断言している。本研究は、進化するeコマース・レコメンデーション・システムの領域における将来の研究のための基礎的なステップとして提示されている。