グラフ上の利己的エージェント2体による間欠的戦略的協力
Intermittent Strategic Cooperation of Two Selfish Agents on Graphs
自己利益を追求する2エージェントが、個々の目標へ向かう途中で特定ノードで協力し移動時間を短縮する経路計画問題(IC2PP)をゲーム理論的に解析し、純粋ナッシュ均衡の構造と存在性を証明し、多項式時間での列挙アルゴリズムを提案した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Itay Shedlezki, Noa Agmon
分類: cs.MA, cs.GT, cs.RO
原文アブストラクト
We study strategic space- and time-constrained cooperation between two self-interested agents through the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem, a shortest-path game on graphs in which agents navigate toward individual targets while optionally cooperating at specific nodes to reduce their own travel times. Although such cooperation can strictly benefit both agents, it is strategically fragile: agents may deviate at any point along their paths. Modeled as a 2-player game, we characterize the structure of Pure Nash Equilibrium (PNE) joint strategies in IC2PP, and show that stable cooperation must follow a highly constrained form. We further prove that at least one PNE exists in every instance of IC2PP, and present a polynomial-time algorithm for enumerating all relevant PNEs. When multiple equilibria arise, we study coordination mechanisms based on bargaining-theoretic selection concepts and empirically compare equilibrium outcomes in terms of individual travel times and social welfare.
