Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem, where two self-interested agents navigate graphs toward individual targets while having the option to cooperate at certain nodes to minimize their travel times. The authors characterize the structure of Pure Nash Equilibrium (PNE) strategies within this framework, revealing that stable cooperation is highly constrained and that at least one PNE exists in every instance of IC2PP. They also present a polynomial-time algorithm to enumerate relevant PNEs and analyze coordination mechanisms to improve individual travel times and social welfare when multiple equilibria are present.
Stable cooperation between selfish agents in path planning is possible but comes with strict constraints that challenge traditional game theory assumptions.
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.