💻 computer science

Intermittent Strategic Cooperation of Two Selfish Agents on Graphs

This paper introduces the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem, characterizing the structure and existence of Pure Nash Equilibria in this strategic graph game and providing polynomial-time algorithms to enumerate equilibria and analyze coordination mechanisms for selfish agents.

Original authors: Itay Shedlezki, Noa Agmon

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Itay Shedlezki, Noa Agmon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine two people, Alice and Bob, trying to get from their homes to their respective workplaces. They are both in a hurry and want to take the fastest route possible. Usually, they would just grab their phones, find the shortest path, and go their separate ways.

But sometimes, the map has special "cooperation zones"—like a narrow bridge, a busy intersection, or a gate that needs two people to open. If Alice and Bob arrive at these zones at the same time, they can help each other out. Maybe they can cross the bridge faster together, or one can hold the gate while the other passes, saving time for both.

The Problem: The "Trust" Trap
Here's the catch: Alice and Bob are selfish. They only care about their own time. They want to cooperate if it helps them, but they are also suspicious.

If Alice waits for Bob at the gate, she might get there early and waste time if Bob is late.
If they agree to meet at the bridge, Alice might think, "If I just leave a minute earlier, I'll get there faster, and Bob can figure it out."
If they start cooperating, Bob might think, "I can leave the group early to save time, and Alice will have to wait for me."

This creates a fragile situation. Even if working together is the best idea in theory, it often falls apart in practice because neither person wants to be the one who gets "screwed over" by the other's selfish move.

The Solution: Finding the "Perfect Dance"
The authors of this paper studied this exact scenario using a graph (a map of nodes and paths). They asked: Is there a way for two selfish people to cooperate without one of them cheating?

They discovered that yes, there is a way, but it has to follow a very strict, rigid structure. Think of it like a perfectly choreographed dance routine:

The Approach (The Solo): Both Alice and Bob travel alone from their homes until they reach a specific meeting point. They must arrive in a way that neither can cheat by taking a different route to get there earlier.
The Dance (The Continuous Cooperation): Once they meet, they must stick together in a single, unbroken line. They cannot split up and then come back together later. If they do, one of them will likely try to leave the group early to save time, ruining the plan. They must stay together until a specific "exit point."
The Exit (The Solo Again): At the exact same moment, they both decide to leave the group and go their separate ways to their final destinations. This exit point is chosen so that neither of them would want to stay with the other any longer, nor leave any earlier.

The Key Findings

Stability is Possible: Even though the agents are selfish, there is always at least one "Perfect Dance" (called a Pure Nash Equilibrium) where neither person has an incentive to change their plan. If they both follow this plan, they are happy.
It's Predictable: The authors figured out that you don't need to check millions of possibilities. Because the "dance" has to be so rigid (one meeting point, one continuous path, one exit point), you can calculate the best strategy very quickly, even on a large map.
Multiple Options: Sometimes, there isn't just one perfect dance; there might be two or three different ways they could cooperate. One way might help Alice a lot but help Bob a little, while another helps Bob a lot and Alice a little. The paper suggests using "bargaining" rules (like splitting the difference or maximizing the total happiness) to decide which dance they should pick.

Why It Matters
This isn't just about two people walking. It's about understanding how selfish entities (like self-driving cars, delivery drones, or even people in traffic) can briefly team up to save time without needing a boss to force them to. The paper proves that even without a boss, if the timing and the path are just right, selfish agents can naturally find a stable way to help each other out.

In short: Selfish agents can cooperate, but only if they follow a very specific, unbreakable script where they meet, stay together, and leave at the exact right moments.

Technical Summary: Intermittent Strategic Cooperation of Two Selfish Agents on Graphs

1. Problem Definition

The paper introduces the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem. This models a scenario where two self-interested agents navigate an undirected graph $G=(V, E)$ from individual start nodes ( $s_1, s_2$ ) to target nodes ( $g_1, g_2$ ).

The core mechanic involves cooperation nodes ( $V_C \subseteq V$ ) where the travel delay for an agent can be reduced from $\tau^1_v$ (non-cooperative) to $\tau^2_v$ (cooperative) if both agents are present. However, cooperation is not automatic; it requires synchronization. If one agent arrives early, it must wait for the other. The total delay at a node includes waiting time plus the reduced travel time.

The agents are modeled as players in a 2-player game. Each seeks to minimize their own total travel time. A Pure Nash Equilibrium (PNE) is a joint strategy (pair of paths) where neither agent can unilaterally deviate to strictly improve their arrival time. The central challenge is that while cooperation can strictly benefit both agents, it is "strategically fragile": agents may deviate at any point (e.g., arriving earlier, leaving earlier, or avoiding synchronization) to exploit the other or optimize their own path, potentially destabilizing the cooperative arrangement.

2. Methodology and Structural Characterization

The authors characterize the structure of PNEs in IC2PP, proving that any cooperative equilibrium must follow a highly constrained, rigid form. The analysis divides joint strategies into three segments:

Joining Segment: Agents travel independently from their start nodes to a cooperation start node ( $c_s$ ).
- Constraint: These paths must be Mutually-Robust Non-Cooperative (NC) Partial Paths. Neither agent can reach an earlier cooperation node on the other's path within a "cooperation-relevant time" (a time window allowing synchronization). If an agent could reach an earlier node, they would deviate to start cooperation sooner.
Cooperation Segment: Agents travel together (intermittently or continuously) from $c_s$ $c_{s}$ to a cooperation departure node ( $c_d$ ).
- Constraint: This segment must be a Stable Cooperation Partial Path. The departure node $c_d$ must be the optimal exit point for both agents simultaneously. If one agent prefers to leave earlier, they will deviate, breaking the equilibrium.
- Continuity: The authors prove that once cooperation begins, agents will not deviate to an independent path and rejoin later; the cooperation segment is continuous.
Departure Segment: From $c_d$ $c_{d}$ to the targets, agents follow their Shortest Independent Paths (SIP).
- Constraint: The path from $c_d$ to the target must not contain any node that would serve as a better departure point for the other agent, which would incentivize extending the cooperation.

Algorithmic Contributions

Based on these structural properties, the paper presents polynomial-time algorithms:

Algorithm 1: Computes the shortest Non-Cooperative Partial Paths, effectively pruning nodes where early cooperation is possible.
Algorithm 2: Computes the shortest Stable Cooperation Partial Paths using a backward Dijkstra-like approach, ensuring stability constraints are met.
Algorithm 3 & 4: Enumerate all non-dominated Equilibrium Cooperation Joint Strategies (ECJS). The authors prove that for any cooperation departure node $c_d$ , there is at most one non-dominated ECJS. This reduces the search space from exponential to linear in the number of cooperation nodes ( $m$ ).
Existence Proof: The paper proves that a PNE always exists in every IC2PP instance. If the independent shortest paths do not form a PNE, a cooperative PNE can be constructed.

Coordination Mechanisms

When multiple non-dominated ECJS exist, the paper models the selection as a bargaining game. It evaluates standard solution concepts:

Nash Solution: Maximizes the product of utilities relative to the disagreement point.
Kalai-Smorodinsky Solution: Preserves utility ratios relative to maximum attainable utility.
Egalitarian Solution: Maximizes the minimum utility.
Utilitarian Solution: Maximizes total social welfare.

3. Key Results

The authors implemented simulations on randomly generated graphs and MAPF benchmarks to evaluate the framework:

Equilibrium Existence and Count: A PNE always exists. The number of PNEs increases with Cooperation Density (more nodes), Cooperation Magnitude (greater time savings), and Path Length, but decreases for very long paths (likely due to increased opportunities for profitable deviations).
Individual Performance: Across all selection methods (Nash, Egalitarian, Utilitarian, etc.), individual path times are nearly identical and significantly better than non-cooperative paths. The outcomes approach the performance of the "Shortest Cooperation Path" (an idealized lower bound where agents never wait).
Social Welfare:
- Price of Anarchy (PoA): As cooperation density increases (specifically > 0.5), the gap between the worst equilibrium and the optimal social welfare widens, indicating that coordination becomes critical to avoid suboptimal stable outcomes.
- Selection Methods: Utilitarian and Min-Sum methods consistently achieve the lowest social welfare ratios (closest to optimal). Egalitarian and Min-Max methods yield higher ratios, prioritizing fairness over total efficiency.
Path Alignment: When agents' independent paths are highly separated (high Shortest Paths Divergence), the number of PNEs drops, and stable strategies tend to approach the optimal social welfare solution.

4. Significance and Claims

The paper claims to lay the foundation for a novel class of path-planning problems where cooperation is intermittent, strategic, and time-dependent, rather than a global, pre-committed objective.

Structural Insight: The primary contribution is the characterization of PNEs, showing that despite the apparent fragility of cooperation, stable equilibria exist and possess a rigid structure (Joining-Cooperation-Departure).
Computational Tractability: By proving that the equilibrium search space is linear in the number of cooperation nodes, the paper demonstrates that finding these complex strategic equilibria is computationally feasible.
Decomposition: The authors argue that since many multi-agent interactions can be approximated by sequences of pairwise encounters, this two-agent framework provides a principled starting point for understanding more complex coalition structures in autonomous systems.
Real-World Applicability: The work addresses scenarios like shared transportation or autonomous intersection management where agents are self-interested but can benefit from temporary coordination, provided the timing and strategic stability are precise.

The paper concludes that while different coordination mechanisms (bargaining solutions) yield similar individual outcomes, they offer distinct trade-offs in social welfare, allowing system designers to select mechanisms based on desired fairness or efficiency goals.