Selfish AI Agents Can Now Cooperate Strategically on Graphs, Researchers Show

A new paper from researchers Itay Shedlezki and Noa Agmon tackles a fundamental challenge in multi-agent systems: how can two selfish agents cooperate when each only cares about minimizing its own travel time? The authors formalize this as the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem. In this shortest-path game on a graph, agents can optionally cooperate at certain nodes to reduce their individual travel times, but any agent can deviate at any point. This makes cooperation strategically fragile—a classic prisoner's dilemma on a graph.

The key theoretical result is that despite the tension, every IC2PP instance has at least one Pure Nash Equilibrium (PNE), meaning a joint strategy where neither agent can benefit by unilaterally changing its path. Moreover, the authors provide a polynomial-time algorithm to list all relevant PNEs. When multiple equilibria exist, they propose coordination mechanisms based on bargaining theory (e.g., selecting the equilibrium that maximizes social welfare or balances individual travel times). The work is cross-listed in multiagent systems, game theory, and robotics, and has direct implications for autonomous drones, warehouse robots, and any domain where independent AI agents must coordinate without a central planner.