技術要約：選択推定およびネスト識別のための実験的アソートメント

1. 問題定義

本論文は、離散選択モデリングにおける相互に関連する2つの課題に取り組んでいる。

1. 実験的アソートメント設計： $n$ 個の全アイテムに対して複雑な選択モデルを推定するためのデータを収集するために、少数の製品アソートメント（アイテムのサブセット）をどのように意図的に設計するか。既存の文献は、多くの場合、観察データ（アソートメントの変動が制御されていないもの）やランダム化実験に依存しているが、著者らはこれらが豊かな代替パターンを学習するには非効率であると主張している。
2. ネスト識別： ネステッド・ロジット（NL）モデル、特にアイテムを「ネスト（入れ子）」と呼ばれる近い代替品へと分割するモデルにおいて、既存の推定手順は通常、ネスト構造が既知であり固定されていることを前提としている。本論文は、事前の主観的な分類に頼ることなく、収集されたデータから正しいネスト分割を自動的に識別する方法を追求している。

核心となる動機は、標準的な多項ロジット（MNL）モデルが、現実的な代替パターン（例：顧客が遠いアイテムではなく、カテゴリ内の近い代替品に切り替わる現象）を捉えきれないことが多い点にある。ネステッド・ロジット・モデルはこれを捉えることができるが、アイテムのグルーピングを知る必要があり、その決定は主観的になりがちである。

2. 手法

A. 組合せ実験設計

著者らは、情報理論的に最適であると示された、$O(\log n)$ 個の異なるアソートメントのみを必要とする、構造化された非適応的実験設計を提案している。

• メカニズム： 各 $n$ アイテムに対し、$L = \lceil \log_2 n \rceil$ の長さを持つ一意のバイナリ符号を割り当てる。
• アソートメント構成： 各ビット位置 $\ell \in \{1, \dots, L\}$ について、2つの実験的アソートメントを作成する：
  1. $S_{\ell, -0}$：$\ell$ 番目のビットが '0' であるすべてのアイテムを含む。
  2. $S_{\ell, -1}$：$\ell$ 番目のビットが '1' であるすべてのアイテムを含む。
• 特性： この設計は、任意の異なるペア $(i, j)$ に対して、 $i$ を含み $j$ を含まない実験的アソートメント（およびその逆）が少なくとも1つ存在することを保証する。この「分離」特性により、アルゴリズムは一つのアイテムの除去が他のアイテムの売上にどのように影響するかを観察することができ、これが代替関係を特定する上で極めて重要となる。
• 効率性： この設計は、約 $2 \lceil \log_2 n \rceil$ 個の実験的アソートメントと1つのコントロール・アソートメント（全アイテムを提供）を使用する。これは、従来の設計（例：「leave-one-out」やペアワイズ設計）で必要とされる $O(n)$ または $O(n^2)$ 個のアソートメントよりも大幅に少ない。

B. ネスト識別アルゴリズム

著者らは、観察された選択確率（または売上データ）から隠れたネスト分割を復元する論理的演繹アルゴリズムを開発した。

• ブースト係数： アルゴリズムは、アソートメント $S$ におけるアイテム $i$ のブースト係数を、$S$ におけるそのアイテムの選択確率と、フルコントロール・アソートメント $[n]$ におけるそのアイテムの選択確率との比として定義する。
• 論理的演繹：
  • 小さなブースト： アイテムのブース係数が外部オプション（またはベースライン）と同じである場合、そのアイテムのネストが $S$ に完全に含まれていたことを意味する。これにより、アルゴリズムはそのアイテムが $S$ から欠落しているアイテムと同じネストには属していないことを導き出すことができる。
  • 大きなブースト： アイテムが大きく異なるブースト係数を示す場合、そのアイテムのネストが部分的に除去されたことを意味する。アソートメント内で同じ大きなブースト係数を共有するアイテムは、同じネストに属していると推論される。
• グラフ理論的アプローチ： アルゴリズムは、ペアごとのネスト所属を表す隣接行列を維持する。$O(\log n)$ 個のアソートメントを通じて反復処理を行い、ブースト係数の比較に基づいて行列を更新する。「One-Hop Transitivity（ワンホップ推移性）」および「Identify Missing Pairs（欠落ペアの特定）」操作を用いて、完全な分割を解決する。
• 堅牢性： ノイズのない設定に対して理論的な保証が提供されている。有限サンプル設定については、ノイズや不整合に対処するために、統計的テストフレームワーク（2標本の $z$ 検定を使用）とコミュニティ検出後処理（Walktrap アルゴリズム）を提案している。

C. パラメータ回復

ネスト分割が特定された後、非退化性の仮定が保持される限り、観察された選択確率から導出される線形システムを解くことで、残りのネステッド・ロジット・パラメータ（選好ウェイト $v_i$ および非類似パラメータ $\lambda_N$）を回復できることを本論文は示している。

3. 主な貢献

1. 最適な実験設計： 本論文は、$O(\log n)$ 個のアソートメントを用いる組合せ設計を導入し、ネステッド・ロジットのネスト構造の識別を保証する。著者らは、適応的設計であってもこれ以上は不可能であるという一致する下界（$\Omega(\log n)$）を証明している。
2. データ駆動型のネスト識別： 固定されたネストを想定する先行研究とは異なり、本論文はデータから直接ネスト分割を特定するアルゴologyを提供している。このアルゴリズムは、提案された実験設計の特定の構造を活用することで、ランダムまたは小規模なアソートメントでは不可能な演繹を可能にしている。
3. 優れた推定性能： 提案された設計は、数値ベンチマークにおいて、ランダム化設計やヒューリスティックな設計（「leave-one-out」など）を一貫して上回る。特に、データが限られている設定やモデルが誤設定されている設定において、推定誤差（RMSE）を大幅に減少させる。
4. 実社会への展開： 本手法は、7,000万人のユーザーと72種類のコンテスト・タイプを抱えるインドのファンタジースポーツ・プラットフォーム、Dream11に展開された。この実験は、MNLモデルや特徴量ベースのクラスタリングを用いたNLモデルよりも優れた予測を実現する、意味のあるネストを特定することに成功した。

4. 結果

数値ベンチマーク

• 誤設定の設定： 真の分布が複雑な分布（Ranked List）に従い、様々なモデル（MNL、NL、マルコフ連鎖）が推定される場合、提案された $O(\log n)$ アソートメントによる設計は、同数のアソートメントを用いたランダム化設計よりも一貫して低い RMSE を示した。これは、小規模なデータ領域において誤差を最大5.5%削減する。
• 適切設定の設定： 推定モデルが真のモデル（例：真の NL またはマルコフ連鎖）と一致する場合、提案された設計は、より多くの異なるアソートメント（最大 $T$ 個）を使用しているランダム化設計に対しても、優れた性能を示した。マルコフ連鎖の設定では、RMSE の減少率は 16.9% に達した。
• ネスト識別： フルパイプライン（設計 ＋ 識別アルゴリズム）は、Benson et al. (2016) の元の設計を用いた場合の RMSE を最大 46% 削減した。著者らは、この理由を、彼らの $O(n/2)$ サイズのアソートメントが、Benson et al. が使用したサイズ2またはサイズ3のアソートメントよりも高い情報量を持っていることにあるとしている。

Dream11 への展開

• 予測： データ駆動型のネスト（アルゴリズムによって特定されたもの）を用いたネステッド・ロジット・モデルは、標準的な MNL モデルおよび、コンテストの特徴量を用いた $k$-means クラスタリングによって決定されたネストを用いる NL モデルを上回った。
• 解釈可能性： 特定されたネストは経済的に解釈可能であった。例えば、アルゴリズムは、異なる参加費と賞金プールを持ちながら、同一の「勝者比率（Winner Ratio）」と「賞金比率（Prize Ratio）」を持つコンテストをグループ化した。これは、ユーザーが生の属性ではなく、正規化された指標を通じて価値を認識していることを示唆している。また、「勝者が一人（winner-take-all）」のコンテストをグループ化し、勝者の数に関する顕著性に関する微妙な行動パターンを特定した。

5. 意義と主張

本論文は、データ収集ステップ（実験設計）が、選択推定のパフォーマンスを決定する一次的な要因であり、選択モデル自体の選択よりも影響力が大きい可能性があると主張している。

• パラダイムの転換： 著者らは、文献が選択の推定における実験設計をほとんど無視しており、ランダム化または観察データにデフォルト設定していると主張している。本研究は、意図的な組合せ的アソートメントの配置が、代替パターンに関する情報をより多く抽出できることを示している。
• 効率性と複雑性： この設計は、アソートメントのサイズ $\approx n/2$ を用いて情報量を最大化しながら、情報理論的な最適性（$O(\log n)$）を達成している。これは、「leave-one-out」設計（効果が小さいためデータ効率が悪い）や、小さなペア設計（バイアスがあるか $O(n^2)$ の実験を必要とする）とは対照的である。
• 実用的有用性： 7,000万人のユーザーを対象としたプラットフォームでの展開成功は、この設計がスケーラブルであり、運用可能であることを示している（72個のアイテムに対してわずか14個の異なるアソートメントを必要とする）。得られたネストは、特徴量ベースのクラスタリングのみから導き出すのが困難であった、実行可能なビジネス上の洞察を提供した。

本論文は、理論的な正当性はネステッド・ロジットに特化しているものの、経験的な成功は一般的な選択モデルにも及ぶものであり、構造化された実験が、ランダム化よりも選択の代替パターンを学習するための優れた戦略であることを示唆して締めくくられている。