两博弈者在图上间歇合作找最短路径，确保双方都受益且稳定。
Intermittent Strategic Cooperation of Two Selfish Agents on Graphs
- 设计间歇合作机制，允许节点处临时协作降低行程时间。
- 证明每个实例至少存在一个纯纳什均衡，且可多项式时间枚举。
- 通过讨价还价模型选择最优均衡，提升个人与整体效率。
我们研究两个自利代理人在图上的战略空间与时间约束下进行间歇性合作的路径规划问题（IC2PP），这是一个最短路径博弈：代理人在前往各自目标的过程中，可在特定节点选择合作以减少自身行程时间。尽管合作能严格使双方受益，但其战略稳定性脆弱，代理可能在任意路径点偏离。将问题建模为双人博弈，我们刻画了纯纳什均衡（PNE）联合策略的结构，表明稳定合作必须遵循高度受限的形式。进一步证明，每个IC2PP实例至少存在一个PNE，并提出一个多项式时间算法用于枚举所有相关PNE。当存在多个均衡时，基于讨价还价理论的协调机制被研究，并在个体行程时间和社会福利方面进行实证比较。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。