非同期的な環境における分散型マルチエージェント・ルーティングにおいて、エージェントが異なる方向にエッジを通過する場合に発生する衝突リスクを扱う。対象は混合グラフ上のエージェント群であり、入力として各エージェントの始点・終点ペアとエッジの重みが与えられる。従来の混雑ゲームがエッジ上の全エージェント数に基づくコストを扱うのに対し、本設定では対向するエージェント間の相互作用のみをペナルティとする非対称なコスト構造を持つ。
衝突をハードな制約ではなく、対向エージェント数の積に基づくソフトなコストとして定義する新しい混雑ゲームモデルを導入した。ゲーム理論的には、純粋ナッシュ均衡の存在、最良応答ダイナミクスの収束性、および安定性の価格が $1$ であることを理論的に示した。また、最適化問題が Steiner Orientation 問題を一般化した NP 困難な問題であることを明らかにし、複数の構造的指標に基づく FPT および XP アルゴリズムを開発した。
エッジ $e$ におけるエージェント $i$ の使用回数を $n_i(e)$ としたとき、パス集合 $\mathcal{P}$ の総コストを $\sum_{e \in E \cup A} w(e) \cdot n_i(e) \cdot n_j(e)$ の形式で定義する。ゲーム理論的解析ではポテンシャル関数を用い、ナッシュ均衡の探索には各エージェントのコストをエッジ重みとして反映した有向グラフ上の最短経路問題への帰着を用いる。最適化においては、頂点数、エージェント数、無向辺数、直径、または頂点被覆数などのパラメータを用いたパラメータ化アルゴリズムを設計している。
ナッシュ均衡の計算複雑性において、重みが入力サイズに対して多項式で抑えられる場合は多項式時間で解けるが、一般には PLS 完全であることを示した。最適化の観点では、コスト $0$ の解の存在判定が NP 困難であることを示した。パラメータ化解析では、エージェント数 $k$ による $O(2^{k^2 \cdot |V|} \cdot \text{poly}(|V|, |E|))$ のアルゴリズムや、頂点被覆数 $k$ とエージェント数 $m$ を用いた FPT アルゴリズムなどの計算量を導出した。
無政府状態の価格 (Price of Anarchy) は、3頂点の完全グラフを用いた反例により非有界となる。最適化問題は Steiner Orientation 問題を一般化しているため、一般的なインスタンスに対しては計算が極めて困難である。今後の課題として、特定のパラメータに関する計算量のさらなる解明や、実用的なインスタンスに対する効率的なヒューリスティックおよび近似スキームの探索が挙げられる。
本研究では、非同期的な環境下での分散型マルチエージェント・ルーティングを扱うため、衝突をハードな制約ではなく、対向するエージェント間のリスクとして評価する「Crossing Cost」モデルを混合グラフ上で提案している。このモデルにおける Crossing Cost は、逆方向にエッジを通過するエージェントの数の積として定義され、混雑や遅延のリスクを定量化する。ゲーム理論的側面では、この設定を非標準的なコスト関数を持つ混雑ゲームとして定式化しており、純粋 Nash equilibrium の存在を証明するとともに、特定の条件下では多項式時間で均衡を求められる一方、一般には PLS-complete であることを示している。最適化の観点からは、Crossing Cost が 0 となる解の存在判定が Steiner Orientation 問題を一般化しており NP-complete であることを明らかにした上で、エッジ数、エージェント数、または頂点被覆数などの構造的指標をパラメータとした XP または FPT アルゴリズムを設計している。
本研究では、エージェントが異なる方向にエッジを通過する場合にのみコストが発生する、Crossing Cost Multi-Agent Routing (CC-MAR) という新しい混雑ゲームモデルを提案している。従来のネットワーク混雑ゲームがエッジ上の全エージェント数に基づくコストを扱うのに対し、CC-MARは対向するエージェント間の衝突リスクのみをペナルティとして課す非対称なコスト構造を持つ。ゲーム理論的側面において、本モデルは常に純戦略ナッシュ均衡が存在し、最良応答ダイナミクスは最大エッジ重みを $w_{\max}$ としたとき $2^{O(w_{\max})}$ ステップ以内に収束すること、および安定性の価格 (Price of Stability) が $1$ であることを証明している一方で、無政府状態の価格 (Price of Anarchy) は非有界となることを示している。ナッシュ均衡の計算複雑性は、重みが入力サイズに対して多項式で抑えられる場合は多項式時間で解けるが、一般には PLS 完全である。中央集権的な最適化の観点では、コスト $0$ の解の存在判定が Steiner Orientation 問題に帰着するため、最適解の導出は NP 困難である。これに対し、パラメータ化複雑性の枠組みを用いて、ターミナルペアの数 $k$ による XP アルゴリズムや、エッジ数、あるいは弧の数と $k$ の組み合わせによる FPT アルゴリズムなどの一連のアルゴリズムを提示している。
本セクションでは、混合グラフ $G = (V, E, A)$ におけるマルチエージェント・ルーティング問題の定義と、計算量解析のためのパラメータ化複雑性の枠組みが示されている。エッジの重みを正の整数 $w(e)$ としたとき、2つのパス $P_i$ と $P_j$ が同じエッジを逆方向に使用する場合の交差コスト（crossing cost）は、逆方向に使用されたエッジの重みの総和として定義される。具体的には、エッジ $e$ におけるエージェント $i$ の使用回数を $n_i(e)$ とすると、パス集合 $\mathcal{P}$ の総コストは $\sum_{e \in E \cup A} w(e) \cdot n_i(e) \cdot n_j(e)$ の形式で表される。交差コスト・マルチエージェント・ルーティング（CC-MAR）問題は、与えられた始点・終点のペアに対して、各エージェントがパスを選択し、総コストを最小化する、あるいは実現可能なパス集合を見つける問題として定式化される。最適解の計算における困難性を克服するため、パラメータ $k$ を導入したパラメータ化複雑性の概念が用いられ、計算時間が $f(k) \cdot |I|^{O(1)}$ で抑えられる固定パラメータ計算可能（FPT）なアルゴリズムや、$|I|^{f(k)}$ で解けるスライス多項式（XP）なアルゴリズムの存在が議論の基礎となる。
Crossing Costs under Multi-Agent Routing (CC-MAR) におけるナッシュ均衡の性質を、ゲーム理論およびアルゴリズムの観点から解析している。まず、エッジの最大重みを $w_{\max}$ とすると、ナッシュ均衡は常に存在し、ナッシュ・ダイナミクスは高々 $O(w_{\max} \cdot |E|)$ ステップで収束することが、ポテンシャル関数を用いた証明により示されている。また、最小コスト解がナッシュ均衡となるため、安定性の価格（Price of Stability）は $1$ であるが、単調なエッジコストであっても、3頂点の完全グラフを用いた反例により、無政府状態の価格（Price of Anarchy）は非有界となる。ナッシュ均衡の判定および改善パスの探索は、各エージェントのコストをエッジ重みとして反映した有向グラフ上での最短経路問題に帰着させることで、$O(|E| + |V|\log |V|)$ の時間計算量で実行可能である。さらに、本研究では、二次閾値ゲーム（Quadratic Threshold Game; QTG）からの多項式時間還元を用いることで、CC-MAR においてナッシュ均衡を求める問題が PLS 完全であることを証明している。この還元では、グリッド状のグラフ構造と、エッジを複数のパスに置き換える混合パス構成、およびリソース・ガジェットを組み合わせることで、QTG の戦略選択を CC-MAR のパス選択へと一対一に写像している。
本セクションでは、交差コストを伴うマルチエージェント・ルーティング（CC-MAR）問題において、最小コスト解を求めるためのパラメータ化アルゴリズムが提案されている。まず、入力グラフを無向サイクルや次数1の頂点を持たない非巡回グラフ（DAGかつ森）に簡略化できること、および同一の端点ペアは最適解においてすべて同一のパスを使用するという構造的性質（Observation 1, 2）が示されている。
以下の4つのパラメータに基づく固定パラメータ計算可能（FPT）アルゴリズムが提示されている。
1. **頂点数 $|V|$ によるパラメータ化**: 各端点ペアが選択しうるパスの数は高々 $2^{|V|}$ であるため、各ペアのパスを列挙してコストを計算することで、計算量 $O(2^{|V| \cdot k})$ で最小コスト解を求められる。
2. **エージェント数 $k$ によるパラメータ化**: 最適解において、任意の2エージェントは高々1つの無向パス上で交差するという性質を利用する。交差の有無と交差するパスを列挙し、残りの非交差パスの決定を Steiner Orientation 問題に帰着させることで、計算量 $O(2^{k^2 \cdot |V|} \cdot \text{poly}(|V|, |E|))$ で解ける。
3. **無向辺数 $|E_{undir}|$ によるパラメータ化**: 無向辺の端点集合に基づき、到達可能性を保持した新しいグラフを構成する簡約化手法を用いることで、計算量 $O(2^{2^{|E_{undir}|}} \cdot \text{poly}(|V|, |E|))$ で解ける。
4. **無向辺数 $|E_{undir}|$ と直径 $D$ によるパラメータ化**: 無向辺の次数と直径の制約から、グラフの頂点数が $|V| \le (2|E_{undir}|)^D$ で抑えられることを利用し、頂点数によるFPTアルゴリズムを適用することで、FPT時間での計算が可能となる。
重みなしグラフにおけるCrossing Costs Multi-Agent Routing (CC-MAR) 問題について、頂点被覆数 $k$ を用いたパラメータ化解析が示されている。まず、頂点被覆数とエージェント数 $m$ の両方にパラメータ化された場合、頂点被覆 $S$ とそれに基づく独立集合 $I$ を用い、各頂点の近傍（無向エッジ、入次数、出次数）に基づいた「タイプ」を定義することで、各タイプにつき高々 $m$ 個の頂点に削減したサイズ $O(k+m)$ の等価なインスタンスを構成でき、固定パラメータ計算可能 (FPT) であることが示される。次に、ターミナル対が重複しないという制約下では、頂点被覆数 $k$ のみのパラメータ化でも FPT となる。この証明では、ターミナル対、頂点、およびパスの「タイプ」を定義し、最適解において各頂点タイプがパスの中間頂点として現れる回数は高々2回であること（Claim 3）、および中間頂点として使用される頂点やターミナル対を事前に特定の集合 $\mathcal{S}_{\text{term}}$ や $\mathcal{S}_{\text{non-term}}$ に限定できること（Claim 4, 5）が示される。さらに、同一タイプのターミナル対はすべて同じパスタイプを使用できる（Claim 6）ことを利用し、パスのタイプを推測することで、計算量をパラメータの指数関数に抑えたアルゴリズムが構築可能となる。
本研究では、エージェント間の正面衝突を硬い制約ではなくソフトなコスト関数として扱う、非同期マルチエージェントルーティングの枠組みである Crossing Cost Multi-Agent Routing (CC-MAR) モデルを提案した。ゲーム理論的観点からは、ナッシュ均衡の存在と収束的なダイナミクスによる到達可能性を証明しており、緩やかな仮定の下では多項式時間で計算可能である一方、一般には PLS 完全であることが示された。最適化の観点では、本問題が Steiner Orientation 問題を一般化していることから NP 困難であることが明らかになったが、これに対し、弧の数、辺の数、ターミナル対の数、および頂点被覆数などの構造的パラメータに基づく FPT および XP 補償を持つパラメータ化アルゴリズムを開発した。今後の課題として、特定のパラメータに関するパラメータ化計算量の解明や、実用的なインスタンスに対する効率的なヒューリスティックおよび近似スキームの探索が挙げられる。