Localizing Preference Aggregation Conflicts: A Graph-Theoretic Approach Using Sheaves

技術要約：離散層による選好集計の局所化

問題提起
本論文は、代替案に対する可視性が部分的である複数のソースから得られる順序選好データを集計する際の課題に取り組んでいる。これは、投票者の正当な意見の相違を解決することを目的とする従来の社会選択問題とは異なり、本研究はデータ融合（data fusion）、すなわち、重複するソースからの部分的なランキングを単一の整合性のあるグローバルなランキングへと結合できるかどうかを判断することに焦点を当てている。紛争は、単なる意見の相違としてではなく、ソースが共有する代替案に関して不一致が生じるという**不整合（inconsistencies）**として発生する。中心となる問題は、これらの不整合が相互作用構造内の「どこ」で発生しているかを診断すること、および、ペアごとの合意がより深い構造的な不可能性を覆い隠している可能性がある場合でも、グローバルな解が存在するかどうかを判断することである。

手法
著者らは、線形化（HodgeRankとは異なる）を行わずに、順序データに直接作用する**離散層論的フレームワーク（discrete sheaf-theoretic framework）**を提案している。

1. 離散順序層（Discrete Order Sheaf）:

   • システムはグラフ $G=(V, E)$ としてモデル化される。ここで頂点は投票者（ソース）を表し、エッジは重なり（共有される代替案）を表す。
   • **離散順序前層（Discrete Order Presheaf）**は以下のように定義される：
     • 頂点茎（Vertex stalks, $F_v$）: 投票者 $v$ に見えるすべての代替案に対する全順序の集合。
     • エッジ茎（Edge stalks, $F_e$）: 両端の頂点が可視とする代替案の共通部分に対する全順序の集合。
     • 制限写像（Restriction maps）: 隣接する投票者と共有する代替案のサブセットへと、局所的な全順序を制限する写像。
   • 選好プロファイルは、0-コチェイン（各頂点への局所的な順序の割り当て）として扱われる。

2. 障害ロカス（Obstruction Locus, $\Omega_1$）および不適合指数（Incompatibility Index）:

   • 障害ロカス（Obstruction Locus） $\Omega_1(\sigma)$ は、隣接する投票者の制限された局所的な順序が一致しないエッジの集合（$\sigma_u|_{A_{uv}} \neq \sigma_v|_{A_{uv}}$）として定義される。
   • 不適合指数 $|\Omega_1|$ は、この集合の濃度である。
   • 決定的なのは、この指標が**局所化（localization）**を提供する点である。すなわち、単一のグローバルなスカラー値としての不整合ではなく、どの投票者ペアが整合性を欠いているかを特定する。

3. 押し出し（Pushforward）とグローバルな解の存在可能性:

   • グローバルなランキングが存在するかどうかに対処するため、著者らはグラフの商写像（例：投票者の統合）の下での**押し出し操作（pushforward operation, $\pi_*$）**を利用する。
   • マージされた頂点 $v'$ 上の押し出し層 $\pi_*F$ は、その逆像に含まれるすべての元の投票者と互換性のある、代替案の和集合上の全順序の集合を含む。
   • 空の茎（Empty Stalks）: マージされた投票者からの制約が矛盾する場合、マージされた頂点における茎は空集合（$\emptyset$）となる。これは、元のグラフにおいてペアごとのエッジに障害がなかったとしても、**局所的な不可能（local impossibility）**が生じていることを意味する。
   • アルゴリズムの実装: 押し出しは、**制約有向グラフ（constraint digraph）**を用いて効率的に計算される。局所的な順序からの制約は、有向グラフへと集約される。このグラフに有向サイクルが含まれている場合、制約は矛盾しており、茎は空となる。このサイクル検出は多項式時間（$O(|A|^2 \cdot |P|)$）で実行され、置換の列挙に伴う階乗的な複雑さを回避する。

主な貢献

1. 離散順序層の定式化: 順序データをセル層として扱うことで、線形化手法に見られる組合せ論的構造の喪失を避ける選好プロファイルのフレームワーク。
2. 障害ロカスの定義: ペアごとの紛争を定量化し、局所化するための $\Omega_1$ と不適合指数の導入。著者らは、$|\Omega_1|$ はコホモロジー不変量ではないものの、HodgeRankにおける調和空間の次元のようなグローバルな位相的不変量とは異なる、精密な「局所化器（localizer）」として機能することを明確にしている。
3. マージのための押し出しメカニズム: 投票者の統合をモデル化する層論的な押し出しの開発。これにより、紛果が（粗視化に伴い）ペアベースの不一致から**空の茎（局所的な不可能）**へと変容する現象を捉えることができる。これは、単純なペアチェックでは検出できないものである。
4. 多項式時間のアルゴリズム: 空の茎を検出するための制約有向グラフアプローチの実装。これは、グローバルな解の存在可能性を判定する上で、素朴な列挙法に対して劇的な高速化を実現する。

実験結果
著者らは、計算実験を通じてフレームワークを検証している：

• 基本例: 本フレームワークは、既知のパラドックス（例：コンドルセ・サイクル）を正しく特定し、様々なグラフトポロジー（例：$K_4, C_3$）に対して $|\Omega_1|$ を算出する。
• 確率的補間（マローズ・モデル）: 分散パラメータの変化に応じて、選好プロファイルがどのように変化するかをマローズ・モデルを用いて生成し、平均不適合指数 $|\Omega_1|$ が滑らかかつ予測通りに反応することを示す。
• 整合率: ランダムなプロファイルを用いた実験により、グローバルな整合性（グローバルな切断の存在）は、連結成分内の投票者数によって支配されること（完全な可視性の場合は $(1/|A|!)^{|V|-1}$）を示す一方、平均不適合指数はエッジ数に応じてスケールすることを示す。
• スケーリング: 制約有向グラフのアルゴリズムは効率的にスケールする。12個の代替案の場合、ダイグラフ・アプローチは素朴な列挙法よりも約149,000倍高速である。
• 「不可視の」障害: 特定の例（付録D）は、$|\Omega_1| = 0$（すべてのペアの重なりは整合している）であるにもかかわらず、すべてのソースをマージすると空の茎が生じるプロファイルを示している。これは、ペアチェックがグローバルな融合の不可能性を検出するには不十分であることを裏付けている。

意義と主張
著者らは、層論的アプローチがHodgeRankのような既存の手法に対して、2つの明確な利点を持つと主張している：

1. 局所化（Localization）: 単にグローバルな障害の存在を報告するのではなく、どの特定の相互作用（エッジ）が不整合の原因となっているかを特定する。
2. 関手性（Functoriality）: 押し出し操作により、システムが粗視化される際（例：投票者の統合）の紛争を整合的に追跡できる。これは、分散したエッジの紛争が局所的な不可能性（空の茎）へと移行する様子を捉え、ペアチェックでは提供できないグローバルな整合性の証明を与える。

著者らは、本フレームワークはコホモロジー不変量の代替ではなく、選好集計における特定の構造的失敗を局所化し、診断するためのツールであると明言している。彼らは、高次の障害（$\mathcal{C}ech$構成の性質上、グラフ上の $\Omega_k (k \ge 2)$ は自明に消滅する）は、押し出しメカニズムがペアの整合性がグローバルな順序へと貼り付くことに失敗することから生じる非自明なグローバルな障害を捉えることを強調している。本研究は、紛争の「場所」がその存在と同様に重要である選好集計を分析するための基礎的なステップとして提示されている。