Paper deep dive
Intermittent Strategic Cooperation of Two Selfish Agents on Graphs
Itay Shedlezki, Noa Agmon
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 6/20/2026, 4:52:09 AM
Summary
The paper introduces the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem, a 2-player game on graphs where two self-interested agents navigate from start to target nodes. Agents can optionally cooperate at specific 'cooperation nodes' to reduce travel delays, but this cooperation is strategically fragile. The authors characterize the structure of Pure Nash Equilibrium (PNE) joint strategies, proving that any cooperative PNE must consist of a single contiguous cooperation segment between two independent path segments. They provide a polynomial-time algorithm to enumerate all non-dominated PNEs and discuss coordination via bargaining-theoretic selection concepts.
Entities (6)
Relation Signals (4)
Itay Shedlezki → affiliatedwith → Bar-Ilan University
confidence 100% · Itay Shedlezki Bar-Ilan University
IC2PP → hasequilibrium → Pure Nash Equilibrium
confidence 100% · We fully characterize the Pure Nash Equilibrium (PNE) of this game
IC2PP → isa → Shortest-path game on graphs
confidence 100% · a shortest-path game on graphs in which agents navigate toward individual targets while optionally cooperating at specific nodes
Cooperation Node → reduces → Travel Delay
confidence 100% · cooperation at specific nodes to reduce their own travel times
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2606.17216v1
- Canonical: https://arxiv.org/abs/2606.17216v1
Trouble viewing inline? Open PDF directly →
Full Text
220,821 characters extracted from source content.
Expand or collapse full text
Intermittent Strategic Cooperation of Two Selfish Agents on Graphs Itay Shedlezki Bar-Ilan University Ramat Gan Israel itay.shedlezki@biu.ac.il Noa Agmon Bar-Ilan University Ramat Gan Israel noa.agmon@biu.ac.il Abstract We study strategic space- and time-constrained cooperation between two self-interested agents through the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2P) 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 IC2P, and show that stable cooperation must follow a highly constrained form. We further prove that at least one PNE exists in every instance of IC2P, 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. 1 Introduction Consider the following real-world scenario: two individuals commute from their homes to separate workplaces. Each can independently follow a shortest path, yet under certain circumstances they may benefit from coordinating their routes. For instance, driving together through certain intersections may grant them precedence, enabling faster or safer travel and incentivizing deviation from individually optimal paths in favor of cooperation. Such coordination, however, is inherently precarious. It is feasible and beneficial only if both agents arrive in time relevant for forming cooperation, and neither agent may gain by deviating (e.g. by initiating cooperation earlier or later, or by leaving prematurely once its individual benefit diminishes). As a result, cooperation that appears advantageous in principle may fail in practice. This creates a fundamental tension: cooperation can strictly improve individual outcomes, but only if it is precisely timed and strategically stable. From a game-theoretic perspective, this raises a nontrivial challenge: although cooperation opportunities are local and time-dependent, agents commit to complete paths in advance, and deviations at any point can undermine cooperation. In this work, we show that despite this apparent fragility, cooperation at equilibrium is possible, and precisely because of it, such cooperation must follow a highly structured form. This structure provides a foundation for studying richer multi-agent interactions through pairwise cooperation. We study this phenomenon through the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2P) problem, a two-player game on a graph in which self-interested agents navigate from individual start nodes to individual targets, seeking to minimize their arrival times while cooperation opportunities in the graph can be leveraged to improve their outcomes. These cooperation opportunities may undermine system stability, as they allow agents to improve their path times, and consequently agents following their shortest independent paths do not necessarily form a Nash equilibrium, nor is this outcome necessarily advantageous. We fully characterize the Pure Nash Equilibria (PNE) of this game and show that any cooperative equilibrium must follow a rigid structure: a single contiguous cooperation segment, preceded and followed by independent paths, with cooperation beginning and ending only at nodes jointly stable against unilateral deviation. This structural characterization has two key implications. First, a PNE always exists. Second, equilibrium computation becomes tractable: for each cooperation node, there exists at most one non-dominated PNE ending cooperation at that node, meaning that no other PNE yields strictly lower travel times for both agents. Leveraging these insights, we present a polynomial-time algorithm that enumerates all non-dominated equilibrium joint strategies. Finally, when multiple equilibria arise, they reflect different trade-offs between the agents’ individual benefits. We examine how agents may select among such equilibria using standard bargaining-based solution concepts, and empirically evaluate how cooperation opportunities and path alignment influence equilibrium efficiency. This work lays the foundation for a novel class of path-planning problems with broad real-world applicability. By focusing on two-agent interactions, we expose fundamental strategic challenges that arise when self-interested agents may benefit from temporary cooperation while still optimizing their own paths. Since many multi-agent interactions can be decomposed into, or approximated by, sequences of pairwise encounters, the two-agent setting provides a principled starting point for studying more sophisticated coalition structures. 2 Related Work IC2P is related to a diverse set of two-player games, as well as multi-robot and multi-agent problems that arise across markedly different domains, each with distinct assumptions, objectives and interaction models. Among those are Multi-Agent Path Finding (MAPF), Autonomous Intersection Management (AIM), congestion games, games on graphs, Dynamic Coalition Formation (DCF), Task allocation, Timed Network Games (TNG), and shared transportation. Path planning is a fundamental problem in robotics, underlying nearly all tasks in mobile robot systems, and concerns determining efficient trajectories for the robot from a start to a target location. Multi-Robot Path Planning (MRPP) [2, 50] extends this to the concurrent navigation of multiple robots in a shared environment, where the presence of other robots greatly increases complexity. Various models of MRPP have been proposed, differing, for example, in system structure (centralized or decentralized), robot characteristics (homogeneous or heterogeneous), and world representation. Various approaches used game-theoretic formulations, accounting for other entities’ intent and plans in both cooperative and competitive settings [47, 17, 48, 59]. However, all typically share a core assumption: close encounters by robots should be avoided, and in most non-strictly-competitive settings, robots act cooperatively to optimize a common global objective, such as minimizing total cost or makespan. Multi-Agent Path Finding (MAPF), Autonomous Intersection Management (AIM), and congestion games typically model shared locations as detrimental phenomena to be avoided. MAPF focuses on collision-free path planning, usually under centralized or fully cooperative assumptions [55, 11, 36]. [14] study a MAPF variant that incorporates a limited form of robot cooperation, where certain hazardous target locations can be accessed only when another robot occupies a supporting location from which it can monitor the area. [63] consider another cooperation-involving variant, in which some tasks require teams of multiple agents. Both settings, however, remain fully cooperative: they do not address self-interested robots, nor the possibility of intermittent, time-limited cooperation that agents may strategically initiate or terminate along their paths. Congestion games capture competition over shared resources whose costs increase with usage [58, 28, 27, 32]. These games are commonly used to model scenarios such as traffic routing, where shared resources impact strategic decisions. Specifically, in [37] the authors study temporal network congestion games with time-dependent costs and coordination mechanisms, analyzing agents’ behavior from a game-theoretic perspective. However, this line of work, like the broader congestion game literature, treats interactions between agents as detrimental, and does not account for their potential beneficial effects. AIM plans vehicle trajectories to avoid conflicts at intersections [24, 18, 31], including distributed methods [18], multi-intersection settings [31], and vehicle platooning [9, 43, 41], where coordinated arrivals improve efficiency. However, these typically assume fully cooperative behavior. In contrast, our work models nodes as opportunities for strategic coordination among self-interested agents, introducing a fundamentally different game-theoretic structure. Several games on graphs study strategic interactions in spatial settings, including Stackelberg security games [21, 15, 61] and assignment-based models such as the dinner party problem [10, 13, 19, 7], and topological distance games [16, 23]. However, they typically focus on static assignments or partitions and do not address path-based strategies, where decisions consist of sequences of nodes subject to spatial constraints and hence may involve intermittent dynamics. Coalition formation research [6, 8, 26] studies how agents form cooperative groups to pursue mutual benefits, typically focusing on stable partitions or maximizing global utility. Dynamic coalition formation [60, 3, 45, 38] extends this line of work to settings in which collaboration can evolve over time, but it overlooks the trajectory coordination or the planning of sequences of short-term, intermittent cooperation. Probabilistic physical search problems [33, 35] address the challenge of locating items in uncertain environments with unknown acquisition costs. Collaborative variants [34] study teams searching together, but do not consider agents dynamically rearranging into different teams or influencing each other’s costs. In [54], efficiency and fairness are explored in collaborative search involving self-interested agents. Their research examined various types of fairness and cost-sharing mechanisms among self-interested agents cooperating toward a shared goal. However, the work did not consider spatial factors that may influence agents’ willingness to cooperate, nor did it address the possibility of agents resigning from the team and re-engaging in other teams. Task allocation problems [40] address efficient execution of tasks by agents focusing on optimizing a global utility. For example, in Coalition Formation with Spatial and Temporal Constraints (CFSTP) [52] agents are assigned to time-critical tasks across locations, yet this framework assumes fully cooperative agents maximizing collective utility, rather than self-interested agents forming temporary coalitions for individual objectives. Ad-Hoc Teamwork [56] refers to the problem of enabling agents to collaborate without prior coordination, focusing on adaptive behaviors and adjustment skills developed through training and experience. However, this line of work also focuses on fully cooperative settings. Cost-sharing games study how agents split the cost of jointly used network resources, focusing on equilibrium existence and efficiency under fixed cost-allocation mechanisms [30, 1]. While this line of work captures strategic incentives in network design, it assumes static participation in shared resources and does not consider path-based strategies in which agents endogenously decide when to cooperate and when to act independently along their trajectories, as in our setting. Timed Network Games (TNG) [5] provide a broad game-theoretic framework for studying timed interactions among agents moving through a network, including cases in which encounters between agents may be beneficial. Our work takes a path-planning perspective on such interactions, focusing on time-weighted graphs in which self-interested agents explicitly construct routes and cooperation is induced by the structure of the selected paths. This viewpoint shifts the analysis from general timed resource usage to cooperation-oriented path construction, allowing us to characterize when cooperation can emerge, remain stable, and terminate without creating profitable deviations. Research on urban mobility and shared transportation [44, 12, 29, 22, 62, 20, 53] primarily focuses on coordination mechanisms for ride-sharing and fleet management, often aiming to balance operational efficiency with social welfare. These models typically abstract away from agent-level strategic path choices and do not consider cooperation as a decision made by self-interested agents. While existing work, such as [25, 39], consider cooperation switching with one or multiple hops, they focus on matching drivers and riders under centralized or algorithmic coordination, rather than modeling the strategic decision-making process of self-interested agents from a game-theoretic perspective. 3 IC2P: Problem Definition We formalize the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2P) problem as follows: Given two self-interested agents simultaneously navigating a shared graph-based environment from their respective source to target nodes, where cooperation at specific interaction points may reduce the delays they incur. Each agent seeks to find a path minimizing its individual travel time, given the strategy of the other agent. Their strategic interaction is modeled as a two-player game, and the goal is to identify, characterize, and compare resulting Pure Nash Equilibrium (PNE) outcomes. Consider an environment with two self-interested agents, a1a_1 and a2a_2, simultaneously navigating an undirected graph G=(V,E)G=(V,E) representing a shared physical environment. Each agent aia_i starts at its initial node si∈Vs_i∈ V, aiming to reach its target node gi∈Vg_i∈ V as early as possible. Each edge (v,u)∈E(v,u)∈ E has an associated travel time τvu>0 _vu>0. Each node v∈Vv∈ V may impose a travel delay on an agent visiting it, representing, for example, the time required to perform a local task (e.g., opening a gate) before proceeding. The travel delay incurred by a single agent passing alone at node v is denoted τv1 _v^1, whereas cooperation may reduce it to τv2 _v^2 (τv1≥τv2≥0 _v^1≥ _v^2≥ 0). The set VC=v∈V∣τv2<τv1V_C=\v∈ V _v^2< _v^1\ includes nodes in which cooperation strictly reduces delay (referred to as cooperation nodes). If agent a1a_1 (w.l.o.g.) arrives at a cooperation node c∈VCc∈ V_C at time t1t_1 before agent a2a_2 arrives at time t2t_2, cooperation requires the earlier agent to wait until the other arrives. As a result, if a1a_1 waits for a2a_2, its total delay at c is (t2−t1)+τc2(t_2-t_1)+ _c^2. In this case, agent a2a_2 incurs a total delay of τc2 _c^2 at node c. Otherwise, both agents incur the non-cooperative delay τc1 _c^1. We note that while cooperating at c only improves a1a_1’s local travel delay at c when t2−(τc1−τc2)≤tc1t^2-(τ^1_c-τ^2_c)≤ t^1_c, considering the potential for ongoing cooperation, a1a_1 may choose to wait upon early arrival (before t2−(τc1−τc2)t^2-(τ^1_c-τ^2_c)) to cooperate with a2a_2, thereby aiding a2a_2 in improving its departure time, which could also benefit a1a_1 at subsequent nodes (see example in Figure 1). Consequently, an agent’s decision to wait at a node depends on its own arrival time, the arrival time of the other agent, and the agents’ planned future path. Figure 1: Agent a1a_1 reaches node c1c_1 in time for cooperation. While it could depart earlier without cooperating (t=7t=7 vs. t=8t=8), cooperation reduces the total path time (18 vs. 19). Formally, when agent aia_i arrives at node v at time tvit^i_v, its waiting time for the other agent a−ia_-i, denoted wviw^i_v, and its incurred travel delay δviδ^i_v, both at node v, depend on the arrival time tv−it^-i_v of a−ia_-i. Specifically wvi(tvi,tv−i)=tv−i−tviif tvi∈[tv−i−(τv1−τv2),tv−i] or if ai explicitly waits at v for a−i,0otherwise.w^i_v(t^i_v,t^-i_v)= casest^-i_v-t^i_v&if t^i_v∈ [\,t^-i_v-(τ^1_v-τ^2_v),\;t^-i_v\, ] or if a_i explicitly waits at v for a_-i,\\ 0&otherwise. cases δvi(tvi,tv−i)=τv2if tvi∈[tv−i−(τv1−τv2),tv−i+(τv1−τv2)]or if either agent deliberately waits at v to synchronize,τv1otherwise.δ^i_v(t^i_v,t^-i_v)= casesτ^2_v&if t^i_v∈ [\,t^-i_v-(τ^1_v-τ^2_v),\;t^-i_v+(τ^1_v-τ^2_v)\, ]\\ & if either agent deliberately waits at v to synchronize,\\ τ^1_v&otherwise. cases The total delay incurred at node v, combining waiting time and the node’s travel delay, is denoted by λvi(tvi,tv−i)=wvi(tvi,tv−i)+δvi(tvi,tv−i)λ^i_v(t^i_v,t^-i_v)=w^i_v(t^i_v,t^-i_v)+δ^i_v(t^i_v,t^-i_v) A path π in the graph is a sequence of nodes π(1),π(2),…,π(p) _(1), _(2),…, _(p) such that (π(i),π(i+1))∈E( _(i), _(i+1))∈ E for every i. We model deliberate waiting of an agent at a node v∈Vv∈ V, for the purpose of synchronizing with another agent, by augmenting the node with the notation v˙ v. For example, an agent following the path s1,v1,v2˙,g1s_1,v_1, v_2,g_1 waits at v2v_2 until the other agent arrives before proceeding to g1g_1. The partial path between nodes v and u is denoted by πv,u _v,u. We denote with Πp1…pl _p_1… p_l the set of all paths starting at vp1v_p_1, ending at vplv_p_l, and visiting vp2,…,vpl−1v_p_2,…,v_p_l-1 in order, possibly including additional nodes (for example, the path v1,v7,v2,v3,v4v_1,v_7,v_2,v_3,v_4 is in Π1,2,4 _1,2,4). The path time between nodes v and u for agent aia_i, when following path πiπ^i while the other agent a−ia_-i follows path π−iπ^-i, is defined as the sum of all edge traversal times, travel delays at nodes, and waiting times along πiπ^i, excluding the travel delays at the first and last nodes. We denote this time as Tv,u(πi∣π−i)T_v,u(π^i π^-i). We use Dv,u(πi∣π−i)D_v,u(π^i π^-i) to denote the departure time of agent aia_i from node u, defined as the path time from v to u plus the waiting and travel dealys incurred at u. The total path time of the full path π, from its starting node to its ending node, is denoted by T(πi∣π−i)T(π^i π^-i). Similarly, the departure time is represented by D(πi∣π−i)D(π^i π^-i). Formally, Tv,u(πi∣π−i)=0if v=u,∑(x,y)∈πv,uiτxy+∑x∈πv,ui∖v,uλxi(Tv,x(πi∣π−i),Tv,x(π−i∣πi))otherwise.T_v,u(π^i π^-i)= cases0&if v=u,\\[4.0pt] _(x,y)∈π^i_v,u _xy+ _x∈π^i_v,u \v,u\λ^i_x\! (T_v,x(π^i π^-i),\;T_v,x(π^-i π^i) )&otherwise. cases Dv,u(πi∣π−i)=Tv,u(πi∣π−i)+λui(Tv,u(πi∣π−i),Tv,u(π−i∣πi))D_v,u(π^i π^-i)=T_v,u(π^i π^-i)+λ^i_u\! (T_v,u(π^i π^-i),\;T_v,u(π^-i π^i) ) For agent aia_i, the individual path time along πv,uiπ^i_v,u, disregarding any interactions or cooperative dynamics with the other agent, is denoted by Tv,u(πi)T_v,u(π^i). The departure time from node u in this independent context is denoted by Dv,u(πi)D_v,u(π^i). The shortest independent path (SIPv,uSIP_v,u) denotes the shortest path between nodes v and u, assuming the traversing agent does not cooperate with the other agent at any node along the path. The shortest cooperation path (SCPv,uSCP_v,u) denotes the shortest path assuming the traversing agent cooperates at all cooperation nodes without waiting for the other agent, incurring delay τw2τ^2_w at each node w∈SCPv,uw∈ SCP_v,u. A path π for agent a is considered rational if, for any two nodes v and u along the path, the condition Tv,u(π|π)≤Tv,u(SIPv,u)T_v,u(π|π)≤ T_v,u(SIP_v,u) holds. This implies that if the agent cooperates in all nodes along the path, the route between any two nodes is the shortest possible. A strategy for an agent is defined as a full path from its start node to its target, including any waiting decisions. We consider a strategic setting in which each agent selects such a full-path strategy ex ante, while accounting for the other agent’s start and target nodes, as well as its possible paths, with the goal of minimizing its individual path time. A joint strategy is a pair of paths (π1,π2)(π^1,π^2) specifying the strategies chosen by agents a1a_1 and a2a_2, respectively. A joint strategy is a Pure Nash Equilibrium (PNE) if neither agent can unilaterally deviate so as to strictly improve its individual travel time. 4 PNE Properties in IC2P We seek to identify all joint strategies constituting a PNE: joint strategies where no agent has an incentive to unilaterally deviate. When considering a joint strategy in which neither agent’s path includes any cooperation nodes, verifying whether the strategy constitutes a PNE is straightforward: it suffices to check that each agent follows its shortest independent path, which can be done using a standard shortest-path algorithm. However, when cooperation nodes are part of the path, the situation becomes more complex, as these cooperation opportunities may incentivize the agents to deviate from their paths in order to improve their arrival times. If there are m>0m>0 cooperation nodes, there may exist up to 2m2^m distinct cooperation patterns. Consequently, determining whether a joint strategy that involves cooperation opportunities forms a PNE is nontrivial. This raises several structural questions: when should cooperation begin, what form should it take, and when should it end? We show that cooperation-involving equilibrium strategies exhibit strong structural properties that sharply restrict these possibilities. We divide our analysis into two classes of joint strategies: those that involve cooperation and those that do not. For each class, we characterize the structural conditions required for a joint strategy to constitute a PNE. We begin with joint strategies that involve cooperation. These can be partitioned into three distinct segments (see Figure 2): 1. Joining Segment: Each agent independently approaches the first cooperation node at which the agents cooperate, referred to as the cooperation starting node csc_s. 2. Cooperation Segment: The agents intermittently cooperate at a subset of cooperation nodes from csc_s to a later node cdc_d, referred to as the cooperation departure node. 3. Departure Segment: From cdc_d onward, each agent follows an independent path to its target node. Figure 2: Structure of a cooperative joint strategy In the following sections, we analyze each of these segments and formulate a set of structural conditions that must hold to prevent unilateral deviations111Although described in dynamic terms for clarity, deviations in our model correspond to ex ante selection of an alternative full-path. and ensure the joint strategy constitutes a PNE. 4.1 Joining segment In this segment, each agent follows an independent path, involving no cooperation, toward the cooperation starting node csc_s. To analyze this segment, we first show that, when the path of one agent is fixed, the optimal cooperative path of the other agent is achieved by joining and initiating cooperation at the earliest cooperation node along the fixed path that is reachable at a cooperation-relevant time. Definition 1. Let π2π^2 denote the path of agent a2a_2, and let c∈π2c∈π^2 be a cooperation node. We say that c is reachable by a1a_1 at a cooperation-relevant time if a1a_1 can arrive at c within a time interval that still allows cooperation with a2a_2 at c 222In our model, although the strategy of a2a_2 is fixed, if cooperation is locally beneficial, a2a_2 will trivially wait for a1a_1. In particular, even if a2a_2 has already started executing the task at c, if cooperation upon the arrival of a1a_1 still enables an earlier departure from the node, a2a_2 will cooperate., namely: T(SIPs1,c)≤T(πs2,c2)+τc1−τc2T(SIP_s_1,c)≤ T(π^2_s_2,c)+τ^1_c-τ^2_c Lemma 1 (Early Cooperation). Each agent prefers to initiate cooperation at the earliest possible cooperation node along the other agent’s path. That is, given an agent aia_i’s path, the best response for the other agent, a−ia_-i, is to join aia_i as early as possible along its path. Proof. Consider a two-agent system in which agent a2a_2 follows a fixed path π2π^2. Let VC∗V_C^* be the set of all cooperation nodes in π2π^2 that a1a_1 can reach within a cooperation-relevant time frame: VC∗=v∈VC∣T(SIPs1,v)≤Ts2,v(π2)+τv1−τv2V_C^*=\v∈ V_C T(SIP_s_1,v)≤ T_s_2,v(π^2)+τ^1_v-τ^2_v\ The path π2π^2 dictates a chronological order for the cooperation nodes. Let ci∗c^*_i denote the i-th cooperation node in VC∗V_C^* that a2a_2 visits according to the path π2π^2. Then, to prove the lemma we show that the optimal cooperation node to start cooperation at is c1∗∈VC∗c^*_1∈ V_C^*. Formally we prove that for any node ci∗∈VC∗c^*_i∈ V_C^* with i>1i>1, it holds that: ∀πci∗,g1∈Πci∗,g1,Ts1,g1(SIPs1,c1∗∘πc1∗,ci∗2∘πci∗,g1|π2)≤Ts1,g1(SIPs1,ci∗∘πci∗,g1|π2)∀ _c^*_i,g_1∈ _c^*_i,g_1, T_s_1,g_1(SIP_s_1,c^*_1 π^2_c^*_1,c^*_i _c^*_i,g_1|π^2)≤ T_s_1,g_1(SIP_s_1,c^*_i _c^*_i,g_1|π^2) Given the path πci∗,g1 _c^*_i,g_1, we construct the path πc1∗,g1′=πc1∗,ci∗2∘πci∗,g1π _c^*_1,g_1=π^2_c^*_1,c^*_i _c^*_i,g_1 and examine the full paths π^=SIPs1,ci∗∘πci∗,g1 π=SIP_s_1,c^*_i _c^*_i,g_1 and π^′=SIPs1,c1∗∘πc1∗,g1′ π =SIP_s_1,c^*_1 π _c^*_1,g_1. We need to show that: Ts1,g1(π^′|π2)≤Ts1,g1(π^|π2)T_s_1,g_1( π |π^2)≤ T_s_1,g_1( π|π^2) Since the path from ci∗c^*_i to g1g_1, denoted πci∗,g1 _c^*_i,g_1, is the same in both cases, it suffices to show that the departure time from ci∗c^*_i using the path SIPs1,c1∗∘πc1∗,g1′SIP_s_1,c^*_1 π _c^*_1,g_1 is earlier than the departure time using the path SIPs1,ci∗∘πci∗,g1SIP_s_1,c^*_i _c^*_i,g_1. When using SIPs1,ci∗SIP_s_1,c^*_i, agent a1a_1 arrives at ci∗c^*_i in a cooperation-relevant time, and its departure time from this node is given by: Ds1,ci∗(SIPs1,ci∗|π2)=max(Ts1,ci∗(SIPs1,ci∗|π2),Ts2,ci∗(π2|SIPs1,ci∗))+τci∗2D_s_1,c^*_i(SIP_s_1,c^*_i|π^2)= (T_s_1,c^*_i(SIP_s_1,c^*_i|π^2),T_s_2,c^*_i(π^2|SIP_s_1,c^*_i) )+τ^2_c^*_i However, using π^′ π , a1a_1 arrives at c1∗c^*_1 at time to cooperate and therefore the delay of a2a_2 at c1∗c^*_1 is reduced and the arrival time of a1a_1 at ci∗c^*_i (which is the same as the arrival time of a2a_2) is Ts1,ci∗(π^′|π2)=Ts2,ci∗(π2|π^′)≤Ts2,ci∗(π2|SIPs1,ci∗)T_s_1,c^*_i( π |π^2)=T_s_2,c^*_i(π^2| π )≤ T_s_2,c^*_i(π^2|SIP_s_1,c^*_i). The departure time of a1a_1 from ci∗c^*_i is then: Ds1,ci∗(π^′|π2)=Ts2,ci∗(π2|π^′)+τci∗2D_s_1,c^*_i( π |π^2)=T_s_2,c^*_i(π^2| π )+τ^2_c^*_i and it holds that: Ts1,ci∗(π^′|π2)+τci∗2=Ts2,ci∗(π2|π^′)+τci∗2≤T_s_1,c^*_i( π |π^2)+τ^2_c^*_i=T_s_2,c^*_i(π^2| π )+τ^2_c^*_i\ ≤ max(Ts1,ci∗(SIPs1,ci∗|π2),Ts2,ci∗(π2|π^′))+τci∗2≤ (T_s_1,c^*_i(SIP_s_1,c^*_i|π^2),T_s_2,c^*_i(π^2| π ))+τ^2_c^*_i≤ max(Ts1,ci∗(SIPs1,ci∗|π2),Ts2,ci∗(π2|SIPs1,ci∗))+τci∗2 (T_s_1,c^*_i(SIP_s_1,c^*_i|π^2),T_s_2,c^*_i(π^2|SIP_s_1,c^*_i))+τ^2_c^*_i Ds1,ci∗(π^′|π2)≤Ds1,ci∗(SIPs1,ci∗|π2)D_s_1,c^*_i( π |π^2)≤ D_s_1,c^*_i(SIP_s_1,c_i^*|π^2) ∎ Following Lemma 1, one might expect both agents to prefer initiating cooperation at the earliest cooperation node that is mutually reachable. However, doing so may enable one agent to exploit the other by leaving the cooperation prematurely, thereby imposing an inferior path time on the remaining agent. Anticipating such behavior, the other agent may instead prefer to avoid cooperation nodes that admit exploitative deviations, even if this delays the onset of cooperation. Figure 3 illustrates such a scenario. Figure 3: Although c1c_1 is the earliest cooperation node reachable by both agents, cooperation there allows agent a1a_1 to deviate and leave agent a2a_2 with an inferior outcome, leading a2a_2 to avoid c1c_1. To ensure that neither agent has an incentive to deviate from its intended path during the joining segment, we explicitly consider two types of potential deviations: 1. Cooperation deviation: If agent a1a_1’s (w.l.o.g.) path includes a cooperation node reachable by agent a2a_2 at a cooperation-relevant time, then by the Early Cooperation Lemma, agent a2a_2 would prefer to deviate from its intended in order to initiate cooperation at that earlier node (see Figure 4(a)). 2. Arrival time deviation: If the last-arriving agent at csc_s can adjust its path to arrive earlier (thereby enabling cooperation to begin sooner) this adjustment benefits both agents (see Figure 4(b)). (a) Starting cooperation at an earlier node. (b) Arriving earlier at vcsv_c_s to initiate cooperation sooner. Figure 4: Possible deviations in the joining segment. Definition 2 (Non-Cooperative Partial Path). A partial path πsi,v _s_i,v from agent aia_i’s starting node sis_i to a node v∈Vv∈ V is defined as a Non-Cooperative (NC) Partial Path if the first cooperation node along the path that the other agent, a−ia_-i, can reach from its starting node s−is_-i within a cooperation-relevant time is v. Formally, for every cooperation node c∈πsi,v∖vc∈ _s_i,v \v\, T(SIPs−i,c)>T(πsi,c)+τc1−τc2T(SIP_s_-i,c)>T( _s_i,c)+τ^1_c-τ^2_c. We denote the set of all Non-Cooperative Partial Paths from the starting node sis_i to node v as Πsi,vNC ^NC_s_i,v, and the shortest Non-Cooperative Partial Path from sis_i to node v as SIPsi,vNCSIP^NC_s_i,v. Algorithm 1 finds the shortest Non-Cooperative partial path from a given starting node sis_i to all nodes in the graph. The algorithm is identical to Dijkstra’s algorithm, except for one modification: if a cooperation node c∈VCc∈ V_C is reachable by the other agent at a time suitable for cooperation, it is removed from the graph once its shortest non-cooperative partial path is identified, preventing further expansions. This ensures that c is not considered as part of the non-cooperative path to any other node in the graph. The algorithm initializes by setting the paths from sis_i to all nodes in the graph to infinity (except sis_i, which is set to 0 with a trivial path) and defining Q←VQ← V as the set of unvisited nodes [lines 1–3]. The algorithm then evaluates all unvisited nodes v that are reachable from sis_i in ascending order of their path time from sis_i [lines 4-11]. For each node v, ignoring nodes that can be leveraged by the other agent to initiate an earlier cooperation [line 7], the algorithm iterates over its neighbors. For each neighbor, if the shortest Non-Cooperative path from sis_i to it via v is shorter than its current path, the algorithm updates the path and its associated time [lines 8-11]. Once all reachable nodes have been evaluated, the algorithm returns a mapping of each node in the graph to its corresponding shortest Non-Cooperative partial path from sis_i [line 12]. If a cooperation node c∈VCc∈ V_C is reachable by the other agent at a time suitable for cooperation, it is removed from the graph once its shortest non-cooperative partial path is identified, preventing further expansions. Algorithm 1 Shortest Non-Cooperative Partial Paths(G,VC,si,SIPs−iG,V_C,s_i,SIP_s_-i) 1:Tsi,v←∞,πsi,v←∅T_s_i,v←∞, _s_i,v← for all v∈Vv∈ V 2:Tsi,si←0,πsi,si←siT_s_i,s_i← 0, _s_i,s_i←s_i 3:Q←VQ← V 4:while Q has a node v s.t. Tsi,v<∞T_s_i,v<∞ do 5: v←v← node in Q with smallest Tsi,vT_s_i,v 6: Remove v from Q 7: if v∉VCv∉ V_C or SIPs−i,v>Tsi,v+τv1−τv2SIP_s_-i,v>T_s_i,v+τ^1_v-τ^2_v then 8: for each neighbor u of v do 9: if Tsi,v+τv1+τv,u<Tsi,uTs_i,v+τ^1_v+ _v,u<Ts_i,u then 10: Tsi,u←Tsi,v+τv1+τv,uTs_i,u← Ts_i,v+τ^1_v+ _v,u 11: πsi,u←πsi,v∘u _s_i,u← _s_i,v u 12:Return a dictionary from each v∈Vv∈ V to πsi,v _s_i,v Lemma 2. Algorithm 1 computes the shortest Non-Cooperative Partial Paths from a given starting node to all nodes in the graph in polynomial time. The correctness of Lemma 2 follows from the optimality of Dijkstra’s algorithm. Since the removal of nodes from the graph is done only when the shortest non-cooperative partial path to them is found, and the removed nodes are not part of any shortest non-cooperative path to any other node when this removal is performed, the path time and non-cooperation conditions are preserved. Similar to Dijkstra’s algorithm, the complexity of Algorithm 1 is (|E|+|V|log|V|)O(|E|+|V| |V|). Definition 3 (Mutually-Robust Non-Cooperative Partial Paths). Two non-cooperative partial paths, πs1,v1π^1_s_1,v and πs2,v2π^2_s_2,v, are defined as Mutually-Robust Non-Cooperative Partial Paths if neither agent can improve the cooperation starting time at v by unilaterally changing its path toward it. Formally, one of the following conditions holds: (1) Both agents arrive at node v simultaneously: T(πs1,v1)=T(πs2,v2)T(π^1_s_1,v)=T(π^2_s_2,v). (2) If agent a1a_1 (w.l.o.g.) reaches v first, then a2a_2 arrives at v via its shortest independent path, i.e., T(πs2,v2)=T(SIPs2,v)T(π^2_s_2,v)=T(SIP_s_2,v). Following Definitions 2 and 3, to eliminate unilateral deviations within the joining segment, the agents’ joining segments must form Mutually-Robust NC Partial Paths. Figure 5 illustrates the necessity of both requirements. Figure 5: The shortest independent path from s2s_2 to c passes through a. However, since this path allows a1a_1 to enforce cooperation and then deviate early, it is not considered non-cooperative. The two non-cooperative paths to c, namely (s1,c)(s_1,c) and (s2,b,c)(s_2,b,c), are nevertheless not mutually robust: agent a2a_2, which arrives later at c, would prefer to deviate to its shortest independent path (s2,a,c)(s_2,a,c). 4.2 Cooperation segment In this segment, an agent may deviate by seeking additional cooperation opportunities or by avoiding cooperation at certain nodes. To analyze this segment, we first show that when two agents cooperate along a partial path, neither agent has an incentive to leave the cooperation and rejoin it later, implying that the cooperation is continuous. Lemma 3 (Cooperation Continuity). Consider two cooperation nodes. If both agents cooperate between them along a rational path, then neither agent can strictly improve its path time by unilaterally deviating to an individual path and rejoining later. Proof. Without loss of generality, assume that agent a2a_2 follows a rational path π, and that the agents initiate cooperation at a cooperation node ci∈πc_i∈π. We show that the best response of the other agent, a1a_1, yielding the fastest path from cic_i to any subsequent cooperation node cj∈πc_j∈π, is to follow the subpath πci,cj _c_i,c_j. Formally, we prove that for any path π′∈Πs1,ci,cjsatisfyingDs1,ci(π′∣π)=Ds2,ci(π∣π′)π ∈ _s_1,c_i,c_j D_s_1,c_i(π π)=D_s_2,c_i(π π ) namely, that the agents cooperate at cic_i, the following holds: Tci,cj(πs1,ci′∘πci,cj∣π)≤Tci,cj(π′∣π)T_c_i,c_j\! (π _s_1,c_i _c_i,c_j π )\;≤\;T_c_i,c_j(π π) Since a1a_1 and a2a_2 depart from node cic_i at the same time, traveling together on the same path from cic_i to any subsequent node v ensures they arrive at v simultaneously. If v is a cooperation node, this synchronization allows them to cooperate immediately upon arrival, minimizing the latency at that node. Assume, by contradiction, that there exists a path π′∈Πs1,ci,cjπ ∈ _s_1,c_i,c_j such that Ds1,ci(π′|π)=Ds2,ci(π|π′)D_s_1,c_i(π |π)=D_s_2,c_i(π|π ) and Tci,cj(πs1,ci′∘πci,cj|π)>Tci,cj(π′|π)T_c_i,c_j(π _s_1,c_i _c_i,c_j|π)>T_c_i,c_j(π |π). Since the partial path to cic_i is the same in both paths π′π and πs1,ci′∘πci,cjπ _s_1,c_i _c_i,c_j, the deviation between the two paths must occur along the partial path starting at cic_i, that is, πci,cj′≠πci,cjπ _c_i,c_j≠ _c_i,c_j. For any deviation between the paths, let d denote the last node preceding the deviation and let r denote the first node at which the paths rejoin. Because a2a_2 is rational, it holds that Td,r(π|π)≤Td,r(SIPd,r)T_d,r(π|π)≤ T_d,r(SIP_d,r). Since there are only two agents, and their partial path from d to r doesn’t intersect, no cooperation can occur along the path πd,r′π _d,r. Therefore, Td,r(π|π)≤Td,r(SIPd,r)≤Td,r(π′|π)T_d,r(π|π)≤ T_d,r(SIP_d,r)≤ T_d,r(π |π) This implies that Tci,r(π|π)≤Tci,r(π′|π)T_c_i,r(π|π)≤ T_c_i,r(π |π) for any deviation of πci,cj′π _c_i,c_j from πci,cj _c_i,c_j. Thus, Tci,cj(πs1,ci′∘πci,cj|π)≤Tci,cj(π′|π)T_c_i,c_j(π _s_1,c_i _c_i,c_j|π)≤ T_c_i,c_j(π |π) which contradicts our initial assumption. Therefore, for any node cj∈πc_j∈π visited after cic_i, the fastest path for a1a_1 from cic_i to cjc_j is achieved by following the path πci,cj _c_i,c_j. ∎ We next show, in 4.2.1, how Lemmas 1 and 3 can be used to efficiently compute the best response of an agent to a fixed strategy of the other agent. This characterization will later be used to verify whether the fully independent joint strategy is a PNE in Section 4.5. We then return, in 4.2.2, to the cooperation segment and introduce the stability condition required for it to constitute part of a cooperative PNE. 4.2.1 Best Response Leveraging Lemmas 1 and 3, we show that the best cooperation-involving response of an agent to a fixed strategy of the other agent has a simple structure. Rather than considering all possible subsets of cooperation opportunities along the path, it suffices to consider responses that start cooperation as early as possible and maintain it continuously until an optimal departure node. This reduces the relevant strategy space for agent a1a_1 from exponentially many cooperation patterns to a number linear in m. The following theorem formalizes this structure for the best cooperation-involving response of agent a1a_1 to a fixed path π of agent a2a_2, and follows directly from Lemmas 1 and 3. Theorem 1. The best cooperation-involving response of agent a1a_1 to a fixed path π of agent a2a_2 is the path that initiates cooperation at the earliest cooperation node along π that a1a_1 can reach at a cooperation-relevant time, denoted c1∗c^*_1, and then follows π until the optimal departure node d, defined by d=argminv∈πT(πc1∗,v∘SIPv,g1∣π)d= _v∈πT( _c^*_1,v SIP_v,g_1 π) (1) That is, π∗=SIPs1,c1∗∘πc1∗,d∘SIPd,g1π^*=SIP_s_1,c^*_1 _c^*_1,d SIP_d,g_1 Intuitively, a1a_1 first follows the shortest path to the earliest node at which cooperation with a2a_2 is feasible, then continues jointly with a2a_2 along π, leveraging additional cooperation opportunities along the way. Finally, a1a_1 departs from a2a_2 only once, at node d, and follows its shortest independent path to g1g_1. Thus, given that a2a_2’s strategy π is fixed and known in advance, the best response of a1a_1 is one of the following: (a) an Independent Shortest Path: The path SIPs1,g1SIP_s_1,g_1 from s1s_1 to g1g_1 without cooperation, computed by a shortest-path algorithm with node weights τv1τ^1_v; or (b) a Cooperation-Assisted Path: The path SIPs1,c1∗∘πc1∗,d∘SIPd,g1SIP_s_1,c^*_1 _c^*_1,d SIP_d,g_1, where c1∗c^*_1 and d denote the earliest cooperation node and the optimal departure node, respectively, as defined in Theorem 1. The cooperation-assisted path can be constructed efficiently as follows: 1. Calculate all shortest paths from s1s_1 to all v∈VCv∈ V_C. 2. Identify the first cooperation node in π that a1a_1 can reach at a cooperation-relevant time, denoted as c1∗c^*_1. 3. Compute the shortest paths from every node along π to g1g_1. 4. Determine the optimal node d along π for a1a_1 to leave the cooperation, minimizing the path time Tc1∗,g1(πc1∗,d∘SIPd,g1,π)T_c^*_1,g_1( _c^*_1,d SIP_d,g_1,π): d=argmind∈πc1∗,g2Tc1∗,g1(πc1∗,d∘SIPd,g1|π)d= _d∈ _c^*_1,g_2T_c^*_1,g_1( _c^*_1,d SIP_d,g_1|π) It is straightforward to verify that this procedure operates in polynomial time. Algorithm 5 (Best Response Path), provided in Appendix A, formalizes the procedure for computing the best response of one agent to a fixed strategy of the other. 4.2.2 Cooperation Stability From Lemma 3 it follows that the cooperation segment consists of a single continuous cooperation path from the cooperation starting node to the cooperation departure node. However, this does not imply that the segment should simply coincide with the shortest cooperative path SCPcs,cdSCP_c_s,c_d. Since the agents have different individual objectives, their preferred departure nodes may differ. Consequently, an agent may benefit from leaving the cooperation earlier and continuing independently toward its target. If an agent benefits from leaving cooperation before cdc_d, such a deviation violates the Nash equilibrium conditions. Moreover, anticipating this, the other agent, may decide to depart even earlier to optimize its own departure node. This process could repeat multiple times, potentially resulting in suboptimal outcomes for both agents (see example in Figure 6). Figure 6: The optimal departure node for a2a_2 along the path x1,x2,x3,x4x_1,x_2,x_3,x_4 is x4x_4, while for a1a_1, it is x3x_3. Along the path x1,x2,x3x_1,x_2,x_3, the optimal departure node for a2a_2 is x2x_2, and for the path x1,x2x_1,x_2, the optimal departure node for a1a_1 is x1x_1. Thus, the only PNE in this scenario is the path containing only x1x_1. Alternatively, an agent may enforce a detour within the cooperation segment to avoid nodes at which the other agent could deviate prematurely, thereby preventing outcomes that would result in an inferior path time. Figure 7 illustrates such a scenario. Figure 7: A PNE exists from c1c_1 to c3c_3, but not when both agents follow SCPc1,c3SCP_c_1,c_3, since a1a_1 prefers to deviate at c2c_2. Equilibrium is obtained when both instead follow c1,a,c3c_1,a,c_3. Therefore we make the following vital definition: Definition 4 (Stable Cooperation Partial Path). A cooperation partial path πcs,cd _c_s,c_d between cooperation nodes cs,cd∈VCc_s,c_d∈ V_C is a stable cooperation partial path if the departure node cdc_d is the optimal departure node for both agents along the path. Formally, let vd∗i(πcs,cd)v_d^*^i( _c_s,c_d) denote the optimal departure node for agent aia_i along πcs,cd∈Πcs,cd _c_s,c_d∈ _c_s,c_d, defined as vd∗i(πcs,cd)=argminc∈πcs,cdT(πcs,c∘SIPc,gi|πcs,cd∘SIPcd,g−i)v_d^*^i( _c_s,c_d)= _c∈ _c_s,c_dT\! ( _c_s,c SIP_c,g_i\; |\; _c_s,c_d SIP_c_d,g_-i ) then, cd=vd∗1(πcs,cd)=vd∗2(πcs,cd)c_d=v_d^*^1( _c_s,c_d)=v_d^*^2( _c_s,c_d). This definition implies that once cooperation begins at node csc_s, both agents would prefer to continue cooperating along πcs,cd _c_s,c_d rather than deviating earlier towards their respective target nodes. The set of all stable cooperation partial paths between two nodes vv and uu is denoted by Πv,uS ^S_v,u, and the shortest stable cooperation partial path between these nodes is denoted by SCPv,uSSCP^S_v,u. The stability of a partial path between two cooperation nodes c1c_1 and c2c_2 depends solely on the path times from c1c_1 onward and is independent of the path segment leading to c1c_1. Leveraging this property, the shortest stable cooperation partial paths ending at a cooperation node c∈VCc∈ V_C can be computed efficiently via a backward variant of Dijkstra’s algorithm (Algorithm 2) which explores the graph backward from c while excluding nodes that violate stability. Algorithm 2 initializes all paths to cdc_d as empty with infinite time, except cdc_d itself, which is set to time 0 with a trivial path, and defines Q←VQ← V as the set of unvisited nodes [lines 1–3]. The algorithm then evaluates all unvisited nodes v that can reach cdc_d in ascending order of their distance to cdc_d [lines 4-10]. For each node v, only its neighbors that preserve path stability are considered as its neighbors [lines 7-8]. If the shortest stable cooperation path from a neighbor u of v via v to cdc_d is shorter than its current path, the algorithm updates the path and its associated time [lines 9-11]. Once all reachable nodes have been evaluated, the algorithm returns a mapping of each node in the graph to its corresponding shortest stable cooperation partial path to cdc_d [line 12]. Algorithm 2 Shortest Stable Paths(G,VC,cd,SIPg1,SIPg2G,V_C,c_d,SIP_g_1,SIP_g_2) 1:Tv,cd←∞,πv,cd←∅T_v,c_d←∞, _v,c_d← for all v∈Vv∈ V 2:Tcd,cd←0,πcd,cd←cdT_c_d,c_d← 0, _c_d,c_d← c_d 3:Q←VQ← V 4:while Q has a node v s.t. Tv,cd<∞T_v,c_d<∞ do 5: v←v← node in Q with smallest Tv,cdT_v,c_d 6: Remove v from Q 7: for each neighbor u of v s.t. u∈Qu∈ Q and τu,v+τv2+Tv,cd+SIPcd,g1≤SIPu,g1 _u,v+τ^2_v+T_v,c_d+SIP_c_d,g_1≤ SIP_u,g_1 8: and τu,v+τv2+Tv,cd+SIPcd,g2≤SIPu,g2 _u,v+τ^2_v+T_v,c_d+SIP_c_d,g_2≤ SIP_u,g_2 do 9: if Tv,cd+τv2+τu,v<Tu,cdTv,c_d+τ^2_v+ _u,v<Tu,c_d then 10: Tu,cd←Tv,cd+τv2+τu,vTu,c_d← Tv,c_d+τ^2_v+ _u,v 11: πu,cd←u∘πv,cd _u,c_d← u _v,c_d 12:Return a dictionary from each v∈Vv∈ V to πv,cd _v,c_d Lemma 4. Given a cooperation ending node cdc_d, Algorithm 2 computes the shortest Stable Cooperation Partial Path concluding cooperation at cdc_d from every node in the graph in polynomial time. Similar to Lemma 2, the correctness of Lemma 4 follows from the optimality of Dijkstra’s algorithm, with one adjustment. Since the neighbors of a node are filtered to maintain stability (line 7), we must also ensure that when a node v is pulled from Q, its set of stable neighbors, as filtered in line 7, is final and reflects all and only the stable neighbors of v. Specifically, we need to ensure that once node v is removed from Q, for all its neighbors u∈Vu∈ V such that (v,u)∈E(v,u)∈ E, the value τu,v+τv2+Tv,cd _u,v+τ^2_v+T_v,c_d is fixed and will not change from that point on. The only element in this value that can change during the algorithm’s execution is Tv,cdT_v,c_d, but once v is pulled from Q, its value remains fixed. Thus, the path times and stability conditions are correctly computed and finalized for each node upon removal from Q, ensuring the overall optimality of the algorithm. Similar to Dijkstra’s algorithm, the complexity of Algorithm 2 is (|E|+|V|log|V|)O(|E|+|V| |V|). Following Definition 4, to eliminate unilateral deviations within the cooperation segment, this segment must form Stable Cooperation Partial Path. 4.3 Departure segment In this segment, since cooperation ceases and both agents aim to reach their respective targets as quickly as possible, each agent will necessarily follow its shortest independent path towards its respective target: SIPcd,g1SIP_c_d,g_1 and SIPcd,g2SIP_c_d,g_2. However, if the shortest independent path of one agent, (w.l.o.g) a1a_1, includes a cooperation node cd′c_d that serves as a better departure point for a2a_2 than cdc_d, then a2a_2 would prefer to continue cooperating along SIPcd,cd′SIP_c_d,c_d instead of taking its independent shortest path directly to its target. This violates the Nash equilibrium property. Thus, the cooperation departure node cdc_d must also be the optimal exit node for both agents along the departure segment (SIPcd,g1,SIPcd,g2)(SIP_c_d,g_1,SIP_c_d,g_2). 4.4 Full Path Equilibrium Cooperation To integrate the above findings into a full-path structural characterization of cooperative joint strategies, we identify five conditions that a cooperative joint strategy must satisfy, proven to be both necessary and sufficient for it to constitute a Nash equilibrium. This characterization applies only to joint strategies that involve cooperation. The independent joint strategy (SIPs1,g1,SIPs2,g2)(SIP_s_1,g_1,SIP_s_2,g_2), which is the optimal joint strategy involving no cooperation, may also constitute a PNE and is treated separately in Section 4.5. Definition 5 (Equilibrium Cooperation Joint Strategy). A cooperation joint strategy (π1,π2)(π^1,π^2) is called an Equilibrium Cooperation Joint Strategy (ECJS) if it satisfies the following conditions: 1. The agents cooperate along exactly one cooperation segment, πcs,cdS∈Πcs,cdSπ^S_c_s,c_d∈ ^S_c_s,c_d, which is stable. 2. Both agents reach the cooperation start node csc_s via Mutually-Robust non-cooperative partial paths πs1,cs1(NC)∈Πs1,csNCπ^1(NC)_s_1,c_s∈ ^NC_s_1,c_s and πs2,cs2(NC)∈Πs2,csNCπ^2(NC)_s_2,c_s∈ ^NC_s_2,c_s. 3. The cooperation end node cdc_d is jointly optimal for departure: cd=vd∗1(πcs,g22)=vd∗2(πcs,g11)c_d=v^1_d^*(π^2_c_s,g_2)=v^2_d^*(π^1_c_s,g_1). 4. From cdc_d onward, both agents follow their shortest independent paths to their targets, SIPcd,g1SIP_c_d,g_1 and SIPcd,g2SIP_c_d,g_2. 5. Cooperation weakly dominates the shortest independent path for both agents: T(π1∣π2)≤T(SIPs1,g1),T(π^1 π^2)≤ T(SIP_s_1,g_1), T(π2∣π1)≤T(SIPs2,g2)T(π^2 π^1)≤ T(SIP_s_2,g_2). Consequently, (π1,π2)(π^1,π^2) can be formally expressed as follows: π1=πs1,cs1(NC)∘πcs,cdS∘SIPcd,g1,π2=πs2,cs2(NC)∘πcs,cdS∘SIPcd,g2π^1=π^1(NC)_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1, π^2=π^2(NC)_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2 Condition 1 ensures the validity of the Cooperation segment, while Condition 2 guarantees the validity of the Joining segment. Conditions 3 and 4 verify the correctness of the Departure segment. Finally, Condition 5 ensures that the entire path is advantageous for both agents, confirming the overall benefit of the cooperation. We denote the set of all ECJS by ℂECJS. Let ℂcdECJS^c_d denote the set of ECJS that terminate cooperation at cd∈VCc_d∈ V_C, and let ℂcs,cdECJS^c_s,c_d denote the set of ECJS that initiate cooperation at cs∈VCc_s∈ V_C and terminate it at cdc_d. Theorem 2. A cooperation joint strategy constitutes a PNE333We assume that when faced with two strategies yielding the same path time, an agent will prefer the one that starts cooperation earlier and involves a single continuous cooperation segment. if and only if it is an ECJS. The equivalence is proved formally in Appendix B. We outline the main argument below. Proof Sketch. (⇐ ) Assume that (π1,π2)(π^1,π^2) is an ECJS. By definition, the joint strategy satisfies the structural conditions ensuring that each agent minimizes its path time given the other agent’s strategy. Hence, no agent can strictly improve by unilaterally deviating, and (π1,π2)(π^1,π^2) constitutes a PNE. (⇒ ) Assume that (π1,π2)≠(SIPs1,g1,SIPs2,g2)(π^1,π^2)≠(SIP_s_1,g_1,SIP_s_2,g_2) is a cooperation PNE. We show that any violation of the ECJS conditions induces a profitable unilateral deviation for at least one agent, contradicting the PNE property. Therefore, all ECJS conditions must hold, and (π1,π2)(π^1,π^2) is an ECJS. Further analysis of the ECJS structure yields the insight: 4.4.1 Pareto Sub-optimality The optimal ECJS in ℂcs,cdECJS^c_s,c_d is not necessarily Pareto optimal. Specifically, since T(SIPsi,csNC)≥T(SIPsi,cs)T(SIP^NC_s_i,c_s)≥ T(SIP_s_i,c_s) and T(SCPcs,cdS∣SCPcs,cdS)≥T(SCPcs,cd∣SCPcs,cd)T(SCP^S_c_s,c_d SCP^S_c_s,c_d)≥ T(SCP_c_s,c_d SCP_c_s,c_d), the full-path joint strategy (SIPs1,csNC∘SCPcs,cdS∘SIPcd,g1,SIPs2,csNC∘SCPcs,cdS∘SIPcd,g2) (SIP^NC_s_1,c_s SCP^S_c_s,c_d SIP_c_d,g_1,SIP^NC_s_2,c_s SCP^S_c_s,c_d SIP_c_d,g_2 ) may be suboptimal compared to (SIPs1,cs∘SCPcs,cd∘SIPcd,g1,SIPs2,cs∘SCPcs,cd∘SIPcd,g2),(SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1,\ SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2), indicating that the optimal joint strategy in ℂcdECJS^c_d is not necessarily Pareto optimal. Figure 7 illustrates such a scenario. In this example, the game presents three PNE: ((s1,g1),(s2,g2))((s_1,g_1),(s_2,g_2)), ((s1,c1,c2,g1)((s_1,c_1,c_2,g_1), (s2,c1,c2,g2))(s_2,c_1,c_2,g_2)), and ((s1,c1,a,c3,g1),(s2,c1,a,c3,g2))((s_1,c_1,a,c_3,g_1),(s_2,c_1,a,c_3,g_2)). Among the three PNE, the joint strategy ((s1,c1,a,c3,g1),(s2,c1,a,c3,g2))((s_1,c_1,a,c_3,g_1),(s_2,c_1,a,c_3,g_2)) minimizes the path time of a2a_2, though it remains suboptimal compared to the joint strategy where both agents follow the shortest path between vc1v_c_1 and vc3v_c_3: ((s1,c1,c2,c3,g1),(s2,c1,c2,c3,g2))((s_1,c_1,c_2,c_3,g_1),(s_2,c_1,c_2,c_3,g_2)). 4.5 Equilibrium in Independent Joint Strategies A joint strategy with no cooperation can constitute a PNE only if both agents follow their shortest independent paths and neither agent has a profitable cooperation-involving deviation. As shown in Section 4.2.1, an agent’s best response to a fixed strategy of the other agent can be computed in polynomial time. Comparing this response with the agent’s shortest independent path allows us to determine whether a profitable cooperation-involving deviation exists, or whether the shortest independent path is itself the agent’s best response. Applying this test to both agents therefore enables us to efficiently verify whether (SIPs1,g1,SIPs2,g2)(SIP_s_1,g_1,SIP_s_2,g_2) constitutes a PNE. 4.6 PNE Joint Strategy Set We show that the number of ECJS that must be considered is at most linear in m=|VC|m=|V_C|, and that this set is guaranteed to be non-empty. 4.6.1 Linear Upper Bound Since all joint strategies in ℂcdECJS^c_d involve the simultaneous departure of the agents from cdc_d, and their path times from cdc_d to their respective target nodes remain constant, there exists one (or a few equivalent) joint strategy in ℂcdECJS^c_d that arrives earliest at cdc_d and dominates all others. Accordingly, our approach seeks to identify this optimal joint strategy for each cooperation node cd∈VCc_d∈ V_C, thereby reducing the number of relevant cooperation paths to be linear in m. This task reduces to identifying the optimal cooperation starting node cs∗c_s^* and the joint strategy in ℂcs∗,cdECJS^c_s^*,c_d that minimizes the arrival time at cdc_d. For a given cooperation starting node csc_s, the optimal joint strategy in ℂcs,cdECJS^c_s,c_d is obtained when both agents follow their shortest non-cooperative partial paths to csc_s (SIPs1,csNCSIP^NC_s_1,c_s, SIPs2,csNCSIP^NC_s_2,c_s), with arrival times synchronized to ensure mutual robustness, and then jointly follow the shortest stable cooperation partial path SCPcs,cdSSCP^S_c_s,c_d. Consequently, if ℂcs,cd≠∅ECJS^c_s,c_d≠ , its optimal element is (SIPs1,csNC∘SCPcs,cdS∘SIPcd,g1,SIPs2,csNC∘SCPcs,cdS∘SIPcd,g2)(SIP^NC_s_1,c_s SCP^S_c_s,c_d SIP_c_d,g_1,SIP^NC_s_2,c_s SCP^S_c_s,c_d SIP_c_d,g_2).Finding the optimal joint strategy in ECJScdECJS_c_d therefore reduces to finding the optimal cooperation starting node cs∗c_s^* minimizing the arrival time at cdc_d: cs∗=argmincs∈VCmax(T(SIPs1,csNC),T(SIPs2,csNC))+τcs2+T(SCPcs,cdS∣SCPcs,cdS) splitc_s^*= _c_s∈ V_C \& (T(SIP^NC_s_1,c_s),T(SIP^NC_s_2,c_s) )\\ &+τ^2_c_s+T(SCP^S_c_s,c_d SCP^S_c_s,c_d) \ split (2) In Section 5, we use this characterization to introduce an efficient algorithm to map all ECJS an agent must consider when determining its strategy by examining all cooperation nodes c∈VCc∈ V_C, treating each as a potential cooperation ending node and identifying the optimal ECJS concluding cooperation at that node. However, not all cooperation nodes need to be considered in this process. The following lemma, proved in Appendix C, shows that the concatenation of two stable cooperation paths remains stable, and that the resulting longer stable path necessarily dominates its shorter prefix. Consequently, partial cooperation paths can be ignored. Lemma 5. Let cd1,cd2∈VCc_d_1,c_d_2∈ V_C be two distinct cooperation nodes. Suppose there exists a stable cooperation partial path from cd1c_d_1 to cd2c_d_2, denoted πcd1,cd2Sπ^S_c_d_1,c_d_2. Then, for any stable cooperation partial path πcs,cd1 _c_s,c_d_1 from csc_s to cd1c_d_1, the concatenated path πcs,cd2′=πcs,cd1∘πcd1,cd2Sπ _c_s,c_d_2= _c_s,c_d_1 π^S_c_d_1,c_d_2 is also stable. Moreover, the optimal ECJS whose cooperation segment is πcs,cd2′π _c_s,c_d_2 dominates the optimal ECJS whose cooperation segment is πcs,cd1 _c_s,c_d_1. That is, ∀i∈1,2, ∀ i∈\1,2\, T(πcs,cd1∘SIPcd1,gi∣πcs,cd1∘SIPcd1,g−i) T\! ( _c_s,c_d_1 SIP_c_d_1,g_i _c_s,c_d_1 SIP_c_d_1,g_-i ) ≥T(πcs,cd2′∘SIPcd2,gi∣πcs,cd2′∘SIPcd2,g−i). ≥ T\! (π _c_s,c_d_2 SIP_c_d_2,g_i π _c_s,c_d_2 SIP_c_d_2,g_-i ). The following corollary follows directly from Lemma 5. Since the segment SIPcd,cd′SIP_c_d,c_d is stable, appending it to the original cooperation segment preserves stability. Moreover, this extension does not violate Conditions 1, 2, 4, or 5 in Definition 5. Corollary 1. Given a cooperation joint strategy (πs1,cs1∘πcs,cdS∘SIPcd,g1,πs2,cs2∘πcs,cdS∘SIPcd,g2)(π^1_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1,π^2_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2) that satisfies all conditions of Definition 5 except Condition 3, i.e., for some agent aia_i, the optimal departure node along πcs,cdS∘SIPcd,g−iπ^S_c_s,c_d SIP_c_d,g_-i is: cd′=vd∗i(πcs,cdS∘SIPcd,g−i)≠cdc_d =v_d^*^i(π^S_c_s,c_d SIP_c_d,g_-i)≠c_d then the joint strategy (πs1,cs1∘πcs,cdS∘SIPcd,cd′∘SIPcd′,g1,πs2,cs2∘πcs,cdS∘SIPcd,cd′∘SIPcd′,g2)(π^1_s_1,c_s π^S_c_s,c_d SIP_c_d,c_d SIP_c_d ,g_1,π^2_s_2,c_s π^S_c_s,c_d SIP_c_d,c_d SIP_c_d ,g_2) satisfies the same conditions of Definition 5 and dominates the original joint strategy. 4.6.2 Existence Guarantee To conclude the insights on the size of the ECJS set we show that in any scenario, there always exists a joint strategy that constitutes a PNE. If the independent joint strategy (SIPs1,g1,SIPs2,g2)(SIP_s_1,g_1,SIP_s_2,g_2) is already a PNE, the claim holds. Otherwise, one of the agents necessarily has an incentive to deviate from its independent shortest path in favor of cooperation with the other agent. In this case, we show that the resulting cooperative path is stable and can serve as the basis for constructing a Pure Nash Equilibrium. In Appendix D, we prove the following Lemma, showing that if there exists a cooperative joint strategy with a stable cooperation segment that both agents prefer over the independent strategy, then a PNE exists. Lemma 6. Consider a cooperative joint strategy of the form: (SIPs1,cs∘πcs,cdS∘SIPcd,g1,SIPs2,cs∘πcs,cdS∘SIPcd,g2), (SIP_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1,\ SIP_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2 ), where csc_s is the first cooperation node and cdc_d is the last cooperation node in which the agents cooperate, and πcs,cdS∈Πcs,cdπ^S_c_s,c_d∈ _c_s,c_d is a stable partial path. If the following condition holds: ∀i∈1,2,T(SIPsi,cs∘πcs,cdS∘SIPcd,gi|SIPs−i,cs∘πcs,cdS∘SIPcd,g−i)≤T(SIPsi,gi)∀ i∈\1,2\, T (SIP_s_i,c_s π^S_c_s,c_d SIP_c_d,g_i|\ SIP_s_-i,c_s π^S_c_s,c_d SIP_c_d,g_-i )≤ T (SIP_s_i,g_i ) then a Pure Nash Equilibrium (PNE) exists. Leveraging Lemma 6, we establish the existence of a PNE in any scenario. Theorem 3. IC2P always admits a Pure Nash Equilibrium Proof. Consider the Independent Joint Strategy (SIPs1,g1,SIPs2,g2)(SIP_s_1,g_1,SIP_s_2,g_2). If this strategy is already a PNE, the claim follows directly. Otherwise, at least one agent, without loss of generality, a1a_1, has an incentive to deviate and leverage cooperation with a2a_2. By Theorem 1, given that a2a_2 follows its independent shortest path SIPs2,g2SIP_s_2,g_2, the optimal path for a1a_1 adheres the structure SIPs1,cs∘SIPcs,cd∘SIPcd,g1SIP_s_1,c_s SIP_c_s,c_d SIP_c_d,g_1, where csc_s is the first cooperation node along a2a_2’s path that a1a_1 can reach in time for cooperation, and cdc_d is its optimal departure node. Since cdc_d lies on the shortest independent path from csc_s to g2g_2, it is also a2a_2’s optimal departure node along SIPcs,cdSIP_c_s,c_d. Thus, SIPcs,cdSIP_c_s,c_d forms a Stable Cooperation Partial Path. Since this strategy is a1a_1’s best response to a2a_2 shortest independent path, we have: T(SIPs1,cs∘SIPcs,cd∘SIPcd,g1∣SIPs2,cs∘SIPcs,cd∘SIPcd,g2)≤T(SIPs1,g1)T(SIP_s_1,c_s SIP_c_s,c_d SIP_c_d,g_1 SIP_s_2,c_s SIP_c_s,c_d SIP_c_d,g_2)≤ T(SIP_s_1,g_1) Additionally, since it involves cooperation along a2a_2’s shortest independent path, it also improves a2a_2’s arrival time at its target node: T(SIPs2,cs∘SIPcs,cd∘SIPcd,g2∣SIPs1,cs∘SIPcs,cd∘SIPcd,g1)≤T(SIPs2,g2)T(SIP_s_2,c_s SIP_c_s,c_d SIP_c_d,g_2 SIP_s_1,c_s SIP_c_s,c_d SIP_c_d,g_1)≤ T(SIP_s_2,g_2) By Lemma 6, this implies the existence of a PNE. ∎ 5 Mapping The Set of Relevant ECJS The structural results presented above restrict the equilibrium search to at most one candidate per cooperation departure node. Based on this observation, Algorithm 3 computes the optimal stable joint strategy ending cooperation at a given node, while Algorithm 4 enumerates all non-dominated cooperative PNEs by iterating over all possible departure nodes. The restriction to non-dominated strategies is important. By Corollary 1, if cooperation can be beneficially extended along the departure segment, then the extended cooperation joint strategy dominates the shorter one. In such cases, the shorter strategy fails to constitute a PNE, since an agent would prefer to continue cooperating rather than depart. Algorithm 4 therefore removes these dominated candidates and retains the extended strategies that dominate them, returning only the non-dominated cooperative PNEs. 5.1 Joint Paths To Cooperation Departure Node Given a cooperation departure node cdc_d, Algorithm 3 computes the dominating stable cooperation joint strategy ending cooperation at that node. The algorithm first computes the shortest independent paths from each agent’s starting node to all nodes in the graph, as well as from all nodes to each agent’s respective target node [lines 1-4], It then computes the shortest stable partial paths that end cooperation at cdc_d from all nodes in the graph using Algorithm 2 [lines 5], and the shortest non-cooperative partial paths from each agent’s starting node to all nodes in the graph using Algorithm 1 [lines 6-7]. Next, for each cooperation node cs∈VCc_s∈ V_C, the algorithm evaluates the agents’ arrival times at cdc_d under the joint strategy (SIPs1,csNC∘SCPcs,cdS∘SIPcd,g1,SIPs2,csNC∘SCPcs,cdS∘SIPcd,g2), (SIP^NC_s_1,c_s SCP^S_c_s,c_d SIP_c_d,g_1,\;SIP^NC_s_2,c_s SCP^S_c_s,c_d SIP_c_d,g_2 ), and records the cooperation-starting node that minimizes this arrival time [lines 8-12]. Finally, if the resulting stable cooperative joint strategy ending cooperation at cdc_d improves both agents’ performance relative to following their shortest independent paths to their respective target nodes, it is returned as the optimal stable joint strategy ending cooperation at cdc_d [lines 13-14]. Otherwise, the algorithm returns None [line 15]. Algorithm 3 Optimal Stable Joint Strategy Ending Cooperation At A Given Node(G,VC,cd,s1,s2,g1,g2G,V_C,c_d,s_1,s_2,g_1,g_2) 1:SIPs1←shortest paths from(G,τ1,s1)SIP_s_1\!←\! shortest paths from(G,τ^1,s_1) 2:SIPs2←shortest paths from(G,τ1,s2)SIP_s_2\!←\! shortest paths from(G,τ^1,s_2) 3:SIPg1←shortest paths to(G,τ1,g1)SIP_g_1\!←\! shortest paths to(G,τ^1,g_1) 4:SIPg2←shortest paths to(G,τ1,g2)SIP_g_2\!←\! shortest paths to(G,τ^1,g_2) 5:SCPcdS←shortest stable paths(G,VC,cd,SIPg1,SIPg2)SCP^S_c_d\!←\! shortest stable paths(G,\!V_C,\!c_d,\!SIP_g_1,\!SIP_g_2) 6:SIPs1NC←shortest nc paths(G,VC,s1,SIPs2)SIP^NC_s_1\!←\! shortest nc paths(G,V_C,s_1,SIP_s_2) 7:SIPs2NC←shortest nc paths(G,VC,s2,SIPs1)SIP^NC_s_2\!←\! shortest nc paths(G,V_C,s_2,SIP_s_1) 8:optNE←∞,cs∗←NoneoptNE\!←\!∞, c_s^*← None 9:for all cs∈VCc_s∈ V_C do 10: if max(SIPs1,csNC,SIPs2,csNC)+τcs2+SCPcs,cdS≤optNE (SIP^NC_s_1,c_s,SIP^NC_s_2,c_s)+τ^2_c_s+SCP^S_c_s,c_d≤ optNE then 11: optNE←max(SIPs1,csNC,SIPs2,csNC)+τcs2+SCPcs,cdSoptNE\!←\! (SIP^NC_s_1,c_s,SIP^NC_s_2,c_s)+τ^2_c_s+SCP^S_c_s,c_d 12: cs∗←csc_s^*←c_s 13:if optNE+τcd2+SIPcd,g1≤SIPs1,g1optNE+τ^2_c_d+SIP_c_d,g_1≤ SIP_s_1,g_1 and optNE+τcd2+SIPcd,g2≤SIPs2,g2optNE+τ^2_c_d+SIP_c_d,g_2≤ SIP_s_2,g_2 then 14: return (SIPs1,cs∗NC∘SCPcs∗,cdS∘SIPcd,g1,SIPs2,cs∗NC∘SCPcs∗,cdS∘SIPcd,g2)(SIP^NC_s_1,c_s^* SCP^S_c_s^*,c_d SIP_c_d,g_1,SIP^NC_s_2,c_s^* SCP^S_c_s^*,c_d SIP_c_d,g_2) 15:return NoneNone Lemma 7. Algorithm 3 computes, in polynomial time, the optimal stable joint strategy ending cooperation at cdc_d. The correctness of Lemma 7 follows from the observation that, if there exists a stable joint strategy that ends cooperation at cdc_d, then the joint strategy (π1,π2)=(SIPs1,csNC∘SCPcs,cdS∘SIPcd,g1,SIPs2,csNC∘SCPcs,cdS∘SIPcd,g2),(π^1,π^2)= (SIP^NC_s_1,c_s SCP^S_c_s,c_d SIP_c_d,g_1,\;SIP^NC_s_2,c_s SCP^S_c_s,c_d SIP_c_d,g_2 ), where cs=argminc∈VCmax(T(SIPs1,cNC),T(SIPs2,cNC))+τc2+T(SCPc,cdS∣SCPc,cdS),c_s= _c∈ V_C \ \! (T(SIP^NC_s_1,c),T(SIP^NC_s_2,c) )+τ^2_c+T\! (SCP^S_c,c_d SCP^S_c,c_d ) \, dominates all other stable joint strategies that end cooperation at cdc_d. The algorithm iterates over all cooperation nodes, evaluating each as a potential starting node and selecting the one that minimizes the arrival time at cdc_d. Complexity Analysis The algorithm begins with four executions of Dijkstra’s algorithm to determine the shortest paths from s1s_1, s2s_2, g1g_1, and g2g_2. Each execution of Dijkstra’s algorithm has a time complexity of (|E|+|V|log|V|)O(|E|+|V| |V|). Consequently, the total complexity for these four runs is: (4⋅(|E|+|V|log|V|))=(|E|+|V|log|V|)O(4·(|E|+|V| |V|))=O(|E|+|V| |V|) Next, the algorithm runs Algorithm 2, which operates similarly to Dijkstra’s algorithm, with a complexity of: (|E|+|V|log|V|)O(|E|+|V| |V|) Subsequently, the algorithm executes Algorithm 1 twice, each with the same complexity: 2⋅(|E|+|V|log|V|)=(|E|+|V|log|V|)2·O(|E|+|V| |V|)=O(|E|+|V| |V|) Finally, the algorithm iterates over all cooperation nodes in the graph to find the one that optimizes the Nash equilibrium overall path time. This iteration has a complexity of: (|V|)O(|V|) Combining all these components, the total complexity of the algorithm can be expressed as: (|E|+|V|log|V|+|V|)O(|E|+|V| |V|+|V|) Which concludes to: (|E|+|V|log|V|)O(|E|+|V| |V|) 5.2 Optimal ECJS Computation To map all non-dominated joint strategies in ℂECJS, we evaluate each cooperation node as a potential cooperation departure node, retaining only the dominating ECJS and discarding dominated concatenations of stable paths. Algorithm 4 Optimal ECJS(G,VC,s1,s2,g1,g2G,V_C,s_1,s_2,g_1,g_2) 1:ECJSmap←(SIPs1,g1,SIPs2,g2),dominated←∅ECJSmap←\(SIP_s_1,g_1,SIP_s_2,g_2)\, dominated← 2:for all cd∈VCc_d∈ V_C do 3: if cd∉dominatedc_d∉ dominated then 4: ECJSmap[cd]←algorithm 3(G,VC,cd,…)ECJSmap[c_d]← algorithm algorithm:optimal-equilibrium-joint-strategy(G,V_C,c_d,…) 5: dominated←dominated∪shortest stable paths(G,VC,cd,SIPg1,SIPg2)dominated← dominated∪ shortest stable paths(G,V_C,c_d,SIP_g_1,SIP_g_2) 6:S1←Best Response Path)(G,VC,s1,g1,s2,g2,SIPs2,g2)S_1← Best Response Path)(G,V_C,s_1,g_1,s_2,g_2,SIP_s_2,g_2) 7:S2←Best Response Path)(G,VC,s2,g2,s1,g1,SIPs1,g1)S_2← Best Response Path)(G,V_C,s_2,g_2,s_1,g_1,SIP_s_1,g_1) 8:if S1≠SIPs1,g1S_1≠ SIP_s_1,g_1 or S2≠SIPs2,g2S_2≠ SIP_s_2,g_2 then 9: ECJSmap←ECJSmap∖(SIPs1,g1,SIPs2,g2)ECJSmap← ECJSmap \(SIP_s_1,g_1,SIP_s_2,g_2)\ 10:return ECJSmap∖dominatedECJSmap dominated Algorithm 4 begins by initializing a dictionary that maps each cooperation node in the graph to its optimal stable joint strategy ending cooperation at that node, using Algorithm 3. The dictionary is initialized with the independent shortest-paths joint strategy, and an empty set is initialized to track cooperation nodes that admit a stable cooperation partial path to another cooperation node [line 1]. The algorithm then iterates over all cooperation nodes cd∈VCc_d∈ V_C, excluding nodes that already have a stable cooperation path to another cooperation node. For each node, it determines the optimal stable joint strategy ending cooperation at that node using Algorithm 3, and updates the list of dominated nodes with those that admit a stable cooperation partial path to cdc_d [lines 2-5]. Next, the algorithm verifies whether the independent shortest paths joint strategy constitutes a pure Nash equilibrium (PNE). If it does not, the strategy is removed [lines 6-9]. Finally, the algorithm removes all joint strategies that terminate cooperation at nodes dominated by others (i.e., nodes with stable cooperation partial paths to another node) and returns the set of all non-dominated ECJS [line 10]. Theorem 4. Algorithm 4 returns a set of joint strategies satisfying the following properties: 1. Nash Equilibrium Guarantee: Every joint strategy (π1,π2)(π^1,π^2) returned by the algorithm is a PNE. 2. Dominance: For every joint strategy (π1,π2)∈ℂ(π^1,π^2) , the algorithm returns either (π1,π2)(π^1,π^2) itself or a joint strategy (π′1,π′2)(π 1,π 2) that dominates it. Thus, the algorithm returns all non-dominated joint strategies in ℂECJS. Proof. Nash Equilibrium Guarantee: Every joint strategy (π1,π2)(π^1,π^2) that Algorithm 4 returns is either the shortest independent joint strategy or a cooperation joint strategy returned by Algorithm 3. If (π1,π2)=(SIPs1,g1,SIPs2,g2)(π^1,π^2)=(SIP_s_1,g_1,SIP_s_2,g_2), the algorithm explicitly verifies that it is a PNE in lines 7-10. Otherwise, if (π1,π2)≠(SIPs1,g1,SIPs2,g2)(π^1,π^2)≠(SIP_s_1,g_1,SIP_s_2,g_2) and is returned by Algorithm 3, it may fail to be a PNE only if the shortest independent path from its cooperation ending node cdc_d to one of the agents’ target nodes gig_i contains a stable cooperation partial path, violating Condition 3 for all cooperation joint strategies that end cooperation at cdc_d. However, since the algorithm returns only joint strategies that end cooperation at nodes without stable cooperation partial paths to other nodes in the graph, this scenario cannot occur. Consequently, all conditions of Definition 5 are satisfied, implying that (π1,π2)∈ECJS=PNE(π^1,π^2)∈ ECJS=PNE. Dominance: If (π1,π2)=(SIPs1,g1,SIPs2,g2)(π^1,π^2)=(SIP_s_1,g_1,SIP_s_2,g_2), then the algorithm implicitly adds this joint strategy to its result set. Otherwise, if (π1,π2)≠(SIPs1,g1,SIPs2,g2)(π^1,π^2)≠(SIP_s_1,g_1,SIP_s_2,g_2), then by Theorem 2, (π1,π2)∈ℂ(π^1,π^2) and can be represented as: π1=πs1,cs1(NC)∘πcs,cdS∘SIPcd,g1,π2=πs2,cs2(NC)∘πcs,cdS∘SIPcd,g2π^1=π^1(NC)_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1, π^2=π^2(NC)_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2 where csc_s is the cooperation starting node and cdc_d is the cooperation ending node. This joint strategy is dominated by the optimal joint strategy in ℂcdECJS^c_d: (π′1,π′2)=(SIPs1,csNC∘SCPcs,cdS∘SIPcd,g1,SIPs2,csNC∘SCPcs,cdS∘SIPcd,g2)(π 1,π 2)= (SIP^NC_s_1,c_s SCP^S_c_s,c_d SIP_c_d,g_1,\ SIP^NC_s_2,c_s SCP^S_c_s,c_d SIP_c_d,g_2 ) If there is no stable cooperation partial path from cdc_d to any other cooperation node in the graph, the algorithm uses Algorithm 3 to identify (π′1,π′2)(π 1,π 2), ensuring that (π′1,π′2)(π 1,π 2) is returned. If, however, there exists a cooperation node cd′c_d such that a stable cooperation partial path πcd,cd′Sπ^S_c_d,c_d exists (among multiple such nodes, we select cd′c_d as one that has no stable cooperation partial path leading to any other cooperation node in the graph), then by Lemma 5, the following joint strategy: (π′1,π′2)=(SIPs1,csNC∘SCPcs,cdS∘πcd,cd′S∘SIPcd′,g1,SIPs2,csNC∘SCPcs,cdS∘πcd,cd′S∘SIPcd′,g2)(π 1,π 2)= (SIP^NC_s_1,c_s SCP^S_c_s,c_d π^S_c_d,c_d SIP_c_d ,g_1,\ SIP^NC_s_2,c_s SCP^S_c_s,c_d π^S_c_d,c_d SIP_c_d ,g_2 ) dominates (π′1,π′2)(π 1,π 2). Since (π′1,π′2)∈ℂcd′(π 1,π 2) ^c_d and the algorithm returns the optimal joint strategy in ℂcd′ECJS^c_d , which dominates all other joint strategies in ℂcd′ECJS^c_d , it follows that the returned strategy also dominates (π′1,π′2)(π 1,π 2), which in turn dominates (π1,π2)(π^1,π^2). Consequently, for any given joint strategy (π1,π2)∈PNE(π^1,π^2)∈ PNE, Algorithm 4 either returns (π1,π2)(π^1,π^2) or an equilibrium cooperation joint strategy (π′1,π′2)(π 1,π 2) that dominates it. ∎ Complexity Analysis. Algorithm 4 iterates over all m cooperation nodes, invoking shortest stable paths and Algorithm 3 for each, yielding complexity of (m⋅(|E|+|V|log|V|))O(m·(|E|+|V| |V|)). 6 ECJS Selection When multiple non-dominated ECJSs exist, trade-offs arise: one agent’s travel time improves only if the other’s worsens (see example in Figure 8). However, since every ECJS improves upon independent shortest paths, agents share an interest in agreeing on a strategy. Figure 8: Two non-dominated ECJSs: cooperation at c1c_1 benefits a1a_1, while cooperation at c2c_2 benefits a2a_2; both outperform no cooperation. This coordination problem can be modeled as a correlation game [4], where agreement on a joint strategy is essential to avoid suboptimal outcomes. Coordination can be achieved either through conventions [49, 57] (e.g., minimizing the maximum path time, maximizing minimum utility relative to the SIPSIP, or maximizing social welfare) or through the concept of a correlated equilibrium [4]. In this setting, the agents agree on a shared probability distribution over the set of non-dominated ECJSs and use it to jointly select a strategy (e.g. via an external correlation device). This mechanism ensures consistent execution and prevents mismatched decisions, enabling the agents to maximize the expected value of a shared objective function, such as fairness or social welfare. Since the joint strategies in ℂECJS inherently reflect conflicting preferences, reaching a mutually acceptable agreement can be challenging. To address this, we model the problem as a bargaining game [51], aiming to identify a correlated equilibrium guided by standard bargaining solution concepts. Specifically, we seek a solution that satisfies the following properties: 1. Pareto Optimality: No agent’s outcome can be improved without worsening the outcome of the other. 2. Symmetry: Identical agents with symmetric options should receive identical outcomes. 3. Fairness: The outcome should be impartial and just, avoiding favoritism or discrimination between agents. While Pareto optimality and symmetry are well defined, fairness is more nuanced and context dependent. We therefore operationalize fairness by comparing four common bargaining solutions: Nash solution [51], Kalai-Smorodinsky solution [42], and the egalitarian and utilitarian solutions. Formally, we denote the set of non-dominated joint strategies in ℂECJS by ℂNDECJS^ND, and represent the selection of a probability distribution over the joint strategies in ℂNDECJS^ND as a bargaining game (S,d)(S,d). The utility of each agent is defined by the time saved compared to its SIPSIP. That is, for a given joint strategy (π1,π2)(π^1,π^2) the utility of agent aia_i is defined as ui(π1,π2)=T(SIPsi,gi)−T(πi|π−i)u_i(π^1,π^2)=T(SIP_s_i,g_i)-T(π^i|π^-i). We define the disagreement point d as: d=(u1(SIPs1,g1,SIPs2,g2),u2(SIPs2,g2,SIPs1,g1))d= (u_1(SIP_s_1,g_1,SIP_s_2,g_2),\;u_2(SIP_s_2,g_2,SIP_s_1,g_1) ) The set S of all possible outcomes in the bargaining game is defined as the set of expected utility pairs achievable by randomizing over joint strategies in ℂNDECJS^ND. Let ℂND=(π11,π12),…,(πn1,πn2)ECJS^ND=\( _1^1, _1^2),…,( _n^1, _n^2)\. Then S=∑i=1nαi⋅(u1(πi1,πi2),u2(πi2,πi1))|αi≥0,∑i=1nαi=1S= \ _i=1^n _i· (u_1( _i^1, _i^2),\,u_2( _i^2, _i^1) )\; |\; _i≥ 0,\ _i=1^n _i=1 \ where each αi _i denotes the probability assigned to the i-th joint strategy in ℂNDECJS^ND, and the resulting pair represents the expected utilities of the two agents. We determine the parameters α1,…,αn _1,…, _n for each solution concept as follows. 1. Nash Solution, maximizes the product of the agents’ utilities relative to the disagreement point, capturing mutual benefit under rational cooperation. 2. Kalai-Smorodinsky Solution, ensures proportional fairness by preserving each agent’s utility ratio relative to its maximum attainable utility. 3. Egalitarian Solution, seeks to equalize outcomes by maximizing the minimum utility across agents. 4. Utilitarian Solution, maximizes the overall social welfare. Since we seek a Pareto-optimal solution, we restrict our attention to the Pareto frontier of the set S, where no agent’s expected utility can be improved without worsening the other’s. As a result, the solution corresponds to a probability distribution supported on at most two joint strategies. The specific strategies involved, however, may vary depending on the chosen bargaining solution concept. 7 Implementation and Results To provide a comprehensive perspective of IC2P and understand how different selection methods affect individual and social outcomes, we developed a simulation tool and fully implemented all algorithms444The repositories for the simulation tool, algorithm implementation, experimental data, and results are publicly available at https://iscmpp.info/.. We then evaluated IC2P algorithms on randomly generated graphs with diverse topologies, travel times, and node delays, examining the factors that influence cooperation incentives across these varied settings. To broaden the experimental evaluation, we also utilize the MAPF Benchmark Set [55], which provides a variety of grid-based maps. To adapt these maps to IC2P, each grid cell is modeled as a node with two delay values, τ1τ^1 for single-agent and τ2τ^2 for cooperative execution, while edges between adjacent cells have a travel time of 11 time unit. To capture the factors that influence cooperation, we varied the following attributes of an IC2P instance: • Cooperation Magnitude — The average ratio between the task execution time of a single agent and that of two agents cooperating at a cooperation node. • Cooperation Density — The ratio of cooperation nodes to all nodes in the graph. • Path Lengths — The minimum, over the two agents, of the shortest independent path time from the agent’s start node to its target node. • Shortest Paths Divergence (SPD) — A path-alignment measure inspired by the Fréchet-distance view of comparing paths according to their ordered progression. SPD measures the minimum shortest independent path time between the two agents while they traverse their respective shortest independent paths. Lower SPD values indicate stronger alignment between the agents’ independent paths, while higher values indicate that the paths remain more separated. We compare methods for joint strategy selection as follows. First, we compute the optimal social welfare for each scenario using a polynomial time algorithm (explained in details in Appendix E). Then, using Algorithm 4, we identify all non-dominated ECJS and evaluate the Price of Anarchy (PoA) [46] and Price of Stability (PoS) [1], defined respectively as the ratios of the worst and best ECJS to the optimal social welfare. Finally, we compare individual path times and social welfare across ECJS selection methods under varying Cooperation Magnitude, Density, Path Length, and SPD. We conducted four separate sets of experiments, each evaluating the effect of a different cooperation factor (Magnitude, Density, Path Length, and SPD) across a range of values. Cooperation Density and Cooperation Magnitude are controlled directly by assigning cooperation nodes and their corresponding delay values. In contrast, Path Length and Shortest Paths Divergence (SPD) depend on the induced shortest paths between the agents’ start and target nodes, and therefore cannot be fixed directly. We control these factors indirectly using proxy measures based on the grid topology: the Manhattan distance between each agent’s start and target nodes for Path Length, and the Manhattan distance between the agents’ corresponding start and target nodes for SPD. The generated instances are then grouped according to their actual Path Length and SPD values, and the results are aggregated within each group. For each configuration of Cooperation Density and Cooperation Magnitude, the algorithms were evaluated on 100 randomly sampled scenarios from the MAPF Benchmark Set. For SPD and Path Length, we evaluated approximately 2,500 and 3,500 scenarios, respectively, using varying configurations of the relevant Manhattan-distance proxy measures. Since these factors are controlled only indirectly, the resulting number of instances differs across intervals. When evaluating the effect of a given attribute, the remaining attributes were fixed as follows: Cooperation Density was set to 0.70.7, Cooperation Magnitude to 1010, the Manhattan distance between each agent’s start and target nodes to 2020, corresponding to Path Length values of approximately 200200, and the Manhattan distance between the agents’ corresponding start and target nodes to 33, corresponding to SPD values of approximately 3030. These values were chosen because they produced a diverse set of PNEs, enabling a meaningful comparison among the different selection methods. Appendix F.2 reports the aggregated numerical values underlying all charts presented in this section. Figure 9 reports the average number of PNEs across the four cooperation factors. The number of PNEs increases with the potential for cooperation, as reflected by higher Cooperation Density, Cooperation Magnitude, and Path Length, as well as by lower SPD values. For high SPD values, which correspond to highly separated paths, the average number of PNEs converges to one. For short paths, the number of potential PNEs is limited. As Path Length increases, more scenarios admit multiple PNEs. However, for very long paths, the number of PNEs decreases slightly again, possibly because longer paths introduce more opportunities for profitable deviations, making cooperative equilibria harder to sustain. Figure 9: Effects of cooperation factors on average amount of PNEs. Figure 10: Effects of cooperation factors on individual path times. Figure 11: Effects of cooperation factors on social welfare. To enable a more meaningful comparison among the different selection methods, we focus on the subset of instances that admit more than one PNE. Appendix F.1 reports the corresponding results over all tested scenarios. Figure 10 summarizes the impact of the cooperation parameters on individual path times, measured by improvement ratios relative to the shortest independent paths. Increasing Cooperation Density and Cooperation Magnitude improves the agents’ individual path times under all selection methods, following trends similar to those of the shortest cooperation path (SCPSCP)555Recall that the shortest cooperation path (SCPSCP) is defined as the shortest path obtained under the idealized assumption that the agents cooperate at all nodes without waiting. This path is generally not attainable and applies only in specific cases, such as when both agents follow the same path.. Longer paths also lead to greater individual improvements, with the outcomes approaching the performance of the shortest cooperation path. The effect of SPD is more gradual: as paths become more separated, the improvement decreases slowly. However, this trend should be interpreted with caution, since the analysis is restricted to scenarios with more than one PNE, and such scenarios constitute only a small fraction of highly separated instances. Across all four factors, the different selection methods yield nearly identical individual path times. Moreover, these path times are close to those achieved by the optimal social-welfare joint strategy. Figure 11 summarizes the impact of the cooperation parameters on social welfare, measured by ratios relative to the optimal social welfare. Cooperation Density has little effect on the social welfare achieved by the different selection methods. However, when the density of cooperation nodes exceeds 0.5, the importance of coordination increases substantially, as reflected by the sharp increase in the PoA. As Cooperation Magnitude increases, the gap between PNE outcomes and the optimal social-welfare solution widens, highlighting the social-welfare cost of stability. SPD does not exhibit a consistent trend. Nevertheless, for highly separated paths, stable joint strategies appear to approach the optimal social-welfare solution. In contrast, Path Length exhibits a strong relation to the social welfare of PNE outcomes: as paths become longer, the outcomes approach the optimal social welfare. Across all scenarios, the Min-Sum convention and the Utilitarian solution consistently attain the lowest social-welfare ratios, as both explicitly optimize total path time. In contrast, the Min-Max convention and the Egalitarian solution yield the highest ratios, reflecting their emphasis on fairness and equality rather than purely minimizing total path time. Overall, since the different selection methods produce comparable individual outcomes, agents can adopt shared social objectives, such as makespan minimization or social-welfare maximization, without substantially compromising individual performance. 8 Conclusions In this paper, we introduced the IC2P framework for analyzing strategic cooperation among two self-interested agents whose incentives to cooperate depend on temporal and spatial context. We characterized the structure of Pure Nash Equilibria (PNE) and developed an efficient algorithm to enumerate all non-dominated PNE, proving existence in all instances. We compared coordination mechanisms for two agents and examined how different factors affect cooperation outcomes in general. These findings establish a foundation for understanding and guiding rational cooperation in autonomous multi-agent systems operating in real-world settings, where cooperation incentives are context-dependent and shaped by temporal and spatial synchronization. Therefore, this work opens the door to a broad line of future research, including extensions to k>2k>2 agents, online planning, and scenarios with limited information about other agents. References [1] E. Anshelevich, A. Dasgupta, J. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden (2008) The price of stability for network design with fair cost allocation. SIAM Journal on Computing 38 (4). Cited by: §2, §7. [2] L. Antonyshyn, J. Silveira, S. Givigi, and J. Marshall (2023) Multiple mobile robot task and motion planning: a survey. ACM Computing Surveys 55 (10), p. 1–35. Cited by: §2. [3] T. Arnold and U. Schwalbe (2002) Dynamic coalition formation and the core. Journal of Economic Behavior & Organization 49 (3). Cited by: §2. [4] R. J. Aumann (1974) Subjectivity and correlation in randomized strategies. Journal of mathematical Economics 1 (1). Cited by: §6. [5] G. Avni, S. Guha, and O. Kupferman (2023) Timed network games. Information and Computation 290, p. 104996. External Links: ISSN 0890-5401, Document, Link Cited by: §2. [6] H. Aziz, F. Brandt, and H. G. Seedig (2013) Computing desirable partitions in additively separable hedonic games. Artificial Intelligence 195. Cited by: §2. [7] H. Aziz, G. Lisowski, M. Suzuki, and J. Vollen (2024) Neighborhood stability in assignments on graphs. arXiv preprint arXiv:2407.05240. Cited by: §2. [8] H. Aziz and R. Savani (2016) Hedonic games. In Handbook of Computational Social Choice, Cited by: §2. [9] M. Bashiri and C. H. Fleming (2017) A platoon-based intersection management system for autonomous vehicles. In 2017 IEEE Intelligent Vehicles Symposium (IV), Vol. , p. 667–672. External Links: Document Cited by: §2. [10] D. Berriaud, A. Constantinescu, and R. Wattenhofer (2023) Stable dinner party seating arrangements. In Proc. of WINE, Cited by: §2. [11] A. Bertolini (2022) Decentralized algorithms for multi-agent pathfinding. Ph.D. Thesis, Politecnico di Torino. Cited by: §2. [12] F. Bistaffa, A. Farinelli, and S. Ramchurn (2015) Sharing rides with friends: a coalition formation algorithm for ridesharing. In Proc. of AAAI, Cited by: §2. [13] H. L. Bodlaender, T. Hanaka, L. Jaffke, H. Ono, Y. Otachi, and T. C. van der Zanden (2020) Hedonic seat arrangement problems. arXiv preprint arXiv:2002.10898. Cited by: §2. [14] C. Bonhomme, C. Grand, C. Lesire, J. Dufour, and C. Guettier (2024) Multi-agent path finding with task assignment and supporting constraints. In Proc. of ECAI, Cited by: §2. [15] V. Bucarey, C. Casorrán, M. Labbé, F. Ordoñez, and O. Figueroa (2021) Coordinating resources in stackelberg security games. European Journal of Operational Research 291 (3). Cited by: §2. [16] M. Bullinger and W. Suksompong (2024) Topological distance games. Theoretical Computer Science 981. Cited by: §2. [17] C. Burger, J. Fischer, F. Bieder, Ö. Ş. Taş, and C. Stiller (2022) Interaction-aware game-theoretic motion planning for automated vehicles using bi-level optimization. In Proc. of the International Conference on Intelligent Transportation Systems (ITSC), p. 3978–3985. Cited by: §2. [18] M. Cederle, M. Fabris, and G. A. Susto (2024) A distributed approach to autonomous intersection management via multi-agent reinforcement learning. External Links: Link Cited by: §2. [19] E. Ceylan, J. Chen, and S. Roy (2023) Optimal seat arrangement: what are the hard and easy cases?. arXiv preprint arXiv:2305.10381. Cited by: §2. [20] M. Chen, W. Shen, P. Tang, and S. Zuo (2019) Dispatching through pricing: modeling ride-sharing and designing dynamic prices.. In Proc. of IJCAI, Cited by: §2. [21] J. B. Clempner and A. S. Poznyak (2015) Stackelberg security games: computing the shortest-path equilibrium. Expert Systems with Applications 42 (8). Cited by: §2. [22] C. Cleophas, C. Cottrill, J. F. Ehmke, and K. Tierney (2019) Collaborative urban transportation: recent advances in theory and practice. European Journal of Operational Research 273 (3). Cited by: §2. [23] A. Deligkas, E. Eiben, D. Knop, and Š. Schierreich (2024) Individual rationality in topological distance games is surprisingly hard. arXiv preprint arXiv:2404.14128. Cited by: §2. [24] K. Dresner and P. Stone (2008) A multiagent approach to autonomous intersection management. Journal of artificial intelligence research 31. Cited by: §2. [25] F. Drews and D. Luxen (2021-08) Multi-hop ride sharing. Proceedings of the International Symposium on Combinatorial Search 4 (1), p. 71–79. External Links: Link, Document Cited by: §2. [26] J. H. Dreze and J. Greenberg (1980) Hedonic coalitions: optimality and stability. Econometrica: Journal of the Econometric Society. Cited by: §2. [27] M. Gairing, K. Kollias, and G. Kotsialou (2020) Existence and efficiency of equilibria for cost-sharing in generalized weighted congestion games. ACM Transactions on Economics and Computation (TEAC) 8 (2). Cited by: §2. [28] L. Gourves, J. Monnot, S. Moretti, and N. K. Thang (2015) Congestion games with capacitated resources. Theory of Computing Systems 57 (3). Cited by: §2. [29] M. Guajardo, M. Rönnqvist, P. Flisberg, and M. Frisk (2018) Collaborative transportation with overlapping coalitions. European Journal of Operational Research 271 (1). Cited by: §2. [30] A. Gupta, A. Srinivasan, and É. Tardos (2008) Cost-sharing mechanisms for network design. Algorithmica 50 (1), p. 98–119. Cited by: §2. [31] M. Hausknecht, T. Au, and P. Stone (2011) Autonomous intersection management: multi-intersection optimization. In Proc. of IROS, Cited by: §2. [32] A. Hayrapetyan, É. Tardos, and T. Wexler (2006) The effect of collusion in congestion games. In Proc. of ACM STOC, Cited by: §2. [33] N. Hazon, Y. Aumann, S. Kraus, and D. Sarne (2013) Physical search problems with probabilistic knowledge. Artificial Intelligence 196. Cited by: §2. [34] N. Hazon, Y. Aumann, and S. Kraus (2009) Collaborative multi agent physical search with probabilistic knowledge. In Proc. of IJCAI, Cited by: §2. [35] N. Hazon and M. Gonen (2020) Probabilistic physical search on general graphs: approximations and heuristics. Autonomous Agents and Multi-Agent Systems 34 (1). Cited by: §2. [36] F. Ho, R. Geraldes, A. Gonçalves, B. Rigault, B. Sportich, D. Kubo, M. Cavazza, and H. Prendinger (2020) Decentralized multi-agent path finding for uav traffic management. IEEE Transactions on Intelligent Transportation Systems 23 (2). Cited by: §2. [37] M. Hoefer, V. S. Mirrokni, H. Röglin, and S. Teng (2011) Competitive routing over time. Theoretical Computer Science 412 (39), p. 5420–5432. External Links: ISSN 0304-3975, Document, Link Cited by: §2. [38] M. Hoefer, D. Vaz, and L. Wagner (2018) Dynamics in matching and coalition formation games with structural constraints. Artificial Intelligence 262. Cited by: §2. [39] Y. Hou, X. Li, and C. Qiao (2012) TicTac: from transfer-incapable carpooling to transfer-allowed carpooling. In Proc. of GLOBECOM, Cited by: §2. [40] Y. Jiang (2015) A survey of task allocation and load balancing in distributed systems. IEEE Transactions on Parallel and Distributed Systems 27 (2). Cited by: §2. [41] J. Juraško, L. Lovás, R. Bencel, and P. Trúchly (2025) Toward 6g-v2x: edge-assisted platoon coordination for cooperative intersection control. In 2025 International Symposium ELMAR, Vol. , p. 21–24. External Links: Document Cited by: §2. [42] E. Kalai and M. Smorodinsky (1975) Other solutions to nash’s bargaining problem. Econometrica, p. 513–518. Cited by: §6. [43] J. Kang, Y. Choi, and K. Sohn (2025) Simultaneous optimization of traffic signal control and vehicle platooning scheme based on connected and automated vehicle (cav) technology. IEEE Access. Cited by: §2. [44] A. Kimms and I. Kozeletskyi (2017) Consideration of multiple objectives in horizontal cooperation with an application to transportation planning. IISE Transactions 49 (12). Cited by: §2. [45] M. Klusch and A. Gerber (2002) Dynamic coalition formation among rational agents. IEEE Intelligent Systems 17 (3). Cited by: §2. [46] E. Koutsoupias and C. Papadimitriou (1999) Worst-case equilibria. In Proc. of STACS, Cited by: §7. [47] F. Laine, D. Fridovich-Keil, C. Chiu, and C. Tomlin (2021) Multi-hypothesis interactions in game-theoretic motion planning. In Proc. of IEEE International Conference on Robotics and Automation (ICRA), Cited by: §2. [48] S. Le Cleac’h, M. Schwager, and Z. Manchester (2021) Lucidgames: online unscented inverse dynamic games for adaptive trajectory prediction and planning. IEEE Robotics and Automation Letters 6 (3), p. 5485–5492. Cited by: §2. [49] D. Lewis (2008) Convention: a philosophical study. John Wiley & Sons. Cited by: §6. [50] S. Lin, A. Liu, J. Wang, and X. Kong (2022) A review of path-planning approaches for multiple mobile robots. Machines 10 (9), p. 773. Cited by: §2. [51] J. F. e. al. Nash (1950) The bargaining problem. Econometrica 18 (2). Cited by: §6, §6. [52] S. D. Ramchurn, M. Polukarov, A. Farinelli, C. Truong, and N. R. Jennings (2010) Coalition formation with spatial and temporal constraints. In Proc. of AAMAS, Cited by: §2. [53] D. Rheingans-Yoo, S. D. Kominers, H. Ma, and D. C. Parkes (2019) Ridesharing with driver location preferences. arXiv preprint arXiv:1905.13191. Cited by: §2. [54] I. Rochlin, Y. Aumann, D. Sarne, and L. Golosman (2016) Efficiency and fairness in team search with self-interested agents. Autonomous Agents and Multi-Agent Systems 30. Cited by: §2. [55] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar, et al. (2019) Multi-agent pathfinding: definitions, variants, and benchmarks. In Proc. of SoCS, Cited by: §2, §7. [56] P. Stone, G. Kaminka, S. Kraus, and J. Rosenschein (2010) Ad hoc autonomous agent teams: collaboration without pre-coordination. In Proc. of AAAI, Cited by: §2. [57] P. Vanderschraaf (1995) Convention as correlated equilibrium. Erkenntnis 42 (1). Cited by: §6. [58] B. Vöcking and R. Aachen (2006) Congestion games: optimization in competition.. In ACiD, Cited by: §2. [59] M. Wang, Z. Wang, J. Talbot, J. C. Gerdes, and M. Schwager (2021) Game-theoretic planning for self-driving cars in multivehicle competitive scenarios. IEEE Transactions on Robotics 37 (4), p. 1313–1325. Cited by: §2. [60] D. Ye, M. Zhang, and D. Sutanto (2013) Self-adaptation-based dynamic coalition formation in a distributed agent network: a mechanism and a brief survey. IEEE Transactions on Parallel and Distributed Systems 24 (5). Cited by: §2. [61] Y. Zhang, P. Zhang, X. Wang, F. Song, C. Li, and J. Hao (2022) An open loop stackelberg solution to optimal strategy for uav pursuit-evasion game. Aerospace Science and Technology 129. Cited by: §2. [62] Z. Zhao, X. Chen, X. Zhang, and Y. Zhou (2022) Dynamic car dispatching and pricing: revenue and fairness for ridesharing platforms. arXiv preprint arXiv:2207.06318. Cited by: §2. [63] N. Zhou, N. W. Bode, and E. R. Hunt (2026) Multi-agent cooperative transportation: optimal and efficient task allocation and path finding. Cited by: §2. Appendix A Best Response Algorithm Algorithm 5 identifies the best response strategy for agent a1a_1, given a2a_2’s path π. The algorithm begins by computing SIPs1SIP_s_1 (the shortest independent paths from a1a_1’s starting node to all other nodes) and SIPg1SIP_g_1 (the shortest independent paths from all nodes to a1a_1’s target node) and initializes the optimal cooperation starting and departure nodes to None [lines 1-3]. It then iterates over all nodes in π to find the first cooperation node a1a_1 can reach at a cooperation-relevant time, denoted as c1∗c^*_1 [lines 4-7]. If no such node exists, since no cooperation can be established, the algorithm returns the independent shortest path as the best response to π [lines 8-9]. Otherwise, it tracks the cooperation path time along πc1∗,g2 _c^*_1,g_2 and determines the departure node d that optimizes a1a_1’s arrival at its target [lines 10-18]. Finally, the algorithm compares the cooperation-assisted path time with the independent shortest path time and returns the strategy that minimizes travel time [lines 19-22]. Algorithm 5 Best Response Path (G,VC,s1,g1,s2,g2,πG,V_C,s_1,g_1,s_2,g_2,π) 1:SIPs1←all shortest paths from(G,τ1,s1)SIP_s_1← all shortest paths from(G,τ^1,s_1) ⊳ Find shortest paths from starting nodes 2:SIPg1←all shortest paths to(G,τ1,g1)SIP_g_1← all shortest paths to(G,τ^1,g_1) ⊳ Find shortest paths to target nodes 3:c1∗,d←Nonec^*_1,d← None 4:for all ci∈πc_i∈π by its order of occurrence along π do 5: if SIPs1,ci≤πs2,ci+τc11−τci2SIP_s_1,c_i≤ _s_2,c_i+τ^1_c_1-τ^2_c_i then ⊳ Find the first cooperation node in π that a1a_1 can reach 6: c1∗←cic^*_1←c_i ⊳ At a cooperation-relevant time 7: break 8:if c1∗=Nonec^*_1=None then ⊳ If cooperation cannot be established, return the independent shortest path 9: return SIPs1,g1SIP_s_1,g_1 10:optimalPathTime←∞optimalPathTime←∞ 11:cooperationPathTime←0cooperationPathTime← 0 12:for all v∈πc1∗,g2v∈ _c^*_1,g_2 by its order of occurrence along π do ⊳ Find the optimal cooperation departure node 13: cooperationPathTime←cooperationPathTime+τv2cooperationPathTime← cooperationPathTime+τ^2_v 14: if cooperationPathTime+SIPv,g1≤optimalPathTimecooperationPathTime+SIP_v,g_1≤ optimalPathTime then 666 15: optimalPathTime←cooperationPathTime+SIPv,g1optimalPathTime← cooperationPathTime+SIP_v,g_1 16: d←vd← v 17: vnext←next node in πv_next node in π 18: cooperationPathTime←cooperationPathTime+τv,vnextcooperationPathTime← cooperationPathTime+ _v,v_next 19:if SIPs1,c1∗+optimalPathTime≤SIPs1,g1SIP_s_1,c^*_1+optimalPathTime≤ SIP_s_1,g_1 then ⊳ Return the shorter path between the independent 20: return SIPs1,c1∗∘πc1∗,d∘SIPd,g1SIP_s_1,c^*_1 _c^*_1,d SIP_d,g_1 ⊳ shortest path and the cooperation-assisted path 21:else 22: return SIPs1,g1SIP_s_1,g_1 66footnotetext: In the context of the pseudocode, SPv,uSP_v,u denotes both the shortest path between nodes v and u and the associated path time, depending on the context. Complexity Analysis The algorithm begins with two executions of Dijkstra’s algorithm to compute the shortest paths from s1s_1 and g1g_1 to all nodes in the graph. Each run of Dijkstra’s algorithm has a time complexity of (|E|+|V|log|V|)O(|E|+|V| |V|). Thus, the total complexity for these two runs is: (2⋅(|E|+|V|log|V|))=(|E|+|V|log|V|)O(2·(|E|+|V| |V|))=O(|E|+|V| |V|) The algorithm then iterates over all nodes in π twice, first to find the optimal cooperation starting node and then to determine the optimal cooperation departure node. Since |π|≤|V||π|≤|V|, these two iterations contribute: (2⋅|V|)=(|V|)O(2·|V|)=O(|V|) Combining these, the overall complexity of the algorithm remains: (|E|+|V|log|V|)O(|E|+|V| |V|) Appendix B Proof of Theorem 2 Theorem 2 A cooperation joint strategy constitutes a PNE if and only if it is an ECJS. Proof. Direction 1: (,)≠(,,,) (π^1,π^2)≠(SIP_s_1,g_1,SIP_s_2,g_2) is an ECJS ⟹(,) (π^1,π^2) is a PNE: Since (π1,π2)(π^1,π^2) is an ECJS, it can be expressed as: π1=πs1,cs1(NC)∘πcs,cdS∘SIPcd,g1,π2=πs2,cs2(NC)∘πcs,cdS∘SIPcd,g2.π^1=π^1(NC)_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1, π^2=π^2(NC)_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2. Where cs,cd∈VCc_s,c_d∈ V_C, πs1,cs1(NC)∈Πs1,csNCπ^1(NC)_s_1,c_s∈ ^NC_s_1,c_s, πs2,cs2(NC)∈Πs2,csNCπ^2(NC)_s_2,c_s∈ ^NC_s_2,c_s, and πcs,cdS∈Πcs,cdSπ^S_c_s,c_d∈ ^S_c_s,c_d. By Theorem 1, the optimal path for aia_i, assuming π−i _-i’s is fixed, known in advance, and rational, is one of the following: 1. The shortest independent path from sis_i to gig_i. 2. The path SIPsi,c1∗∘πc1∗,d−i∘SIPd,giSIP_s_i,c^*_1 π^-i_c^*_1,d SIP_d,g_i, where c1∗c^*_1 is the first cooperation node along π−iπ^-i that aia_i can reach at a cooperation-relevant time, and d is the optimal departure node for aia_i along πc1∗,gi−iπ^-i_c^*_1,g_i Since (π1,π2)(π^1,π^2) is an ECJS, following Condition 5, it holds that: T(πi∣π−i)≤T(SIPsi,gi)T(π^i π^-i)≤ T(SIP_s_i,g_i) We therefore examine the cooperation-assisted path SIPsi,c1∗∘πc1∗,d−i∘SIPd,giSIP_s_i,c^*_1 π^-i_c^*_1,d SIP_d,g_i. Since a−ia_-i’s path to csc_s is non-cooperative (Condition 2, it follows that csc_s is the first cooperation node along π−iπ^-i that aia_i can reach at a cooperation-relevant time. Furthermore, by Condition 3, cdc_d is the optimal departure node for aia_i along πcs,g−i−iπ^-i_c_s,g_-i. Therefore, aia_i’s best response to π−iπ^-i is the path πi∗=SIPsi,cs∘πcs,cd−i∘SIPcd,gi=SIPsi,cs∘πcs,cdS∘SIPcd,giπ^i^*=SIP_s_i,c_s π^-i_c_s,c_d SIP_c_d,g_i=SIP_s_i,c_s π^S_c_s,c_d SIP_c_d,g_i The arrival time of aia_i at its target node using this path can be expressed as: T(πi∗|π−i)=max(T(SIPsi,cs),T(πs−i,cs−i(NC)))+τcs2+D(πcs,cdS|πcs,cdS)+T(SIPcd,gi)T(π^i^*|π^-i)= (T(SIP_s_i,c_s),T(π^-i(NC)_s_-i,c_s))+τ^2_c_s+D(π^S_c_s,c_d|π^S_c_s,c_d)+T(SIP_c_d,g_i) We now analyze aia_i’s path πi=πsi,csi(NC)∘πcs,cdS∘SIPcd,giπ^i=π^i(NC)_s_i,c_s π^S_c_s,c_d SIP_c_d,g_i. The arrival time of aia_i using πiπ^i is: T(πi|π−i)=max(T(πsi,csi(NC)),T(πs−i,cs−i(NC)))+τcs2+D(πcs,cdS|πcs,cdS)+T(SIPcd,gi)T(π^i|π^-i)= (T(π^i(NC)_s_i,c_s),T(π^-i(NC)_s_-i,c_s))+τ^2_c_s+D(π^S_c_s,c_d|π^S_c_s,c_d)+T(SIP_c_d,g_i) Since πs1,cs1(NC)π^1(NC)_s_1,c_s and πs2,cs2(NC)π^2(NC)_s_2,c_s are Mutually-Robust Non-Cooperative Partial Paths, there are two possible cases for T(πsi,csi(NC))T(π^i(NC)_s_i,c_s): 1. If T(πsi,csi(NC))≤T(πs−i,cs−i(NC))T(π^i(NC)_s_i,c_s)≤ T(π^-i(NC)_s_-i,c_s), then T(SIPsi,cs)≤T(πsi,csi(NC))≤T(πs−i,cs−i(NC))T(SIP_s_i,c_s)≤ T(π^i(NC)_s_i,c_s)≤ T(π^-i(NC)_s_-i,c_s) Thus: max(T(πsi,csi(NC)),T(πs−i,cs−i(NC)))=max(T(SIPsi,cs),T(πs−i,cs−i(NC)))=T(πs−i,cs−i(NC)) (T(π^i(NC)_s_i,c_s),T(π^-i(NC)_s_-i,c_s))= (T(SIP_s_i,c_s),T(π^-i(NC)_s_-i,c_s))=T(π^-i(NC)_s_-i,c_s) Hence: T(πi|π−i)=T(πi∗|π−i)T(π^i|π^-i)=T(π^i^*|π^-i) 2. If T(πsi,csi(NC))>T(πs−i,cs−i(NC))T(π^i(NC)_s_i,c_s)>T(π^-i(NC)_s_-i,c_s), then, since πs1,cs1(NC)π^1(NC)_s_1,c_s and πs2,cs2(NC)π^2(NC)_s_2,c_s are Mutually-Robust Non-Cooperative Partial Paths, it follows that πsi,csi(NC)=SIPsi,csπ^i(NC)_s_i,c_s=SIP_s_i,c_s. Thus: max(T(πsi,csi(NC)),T(πs−i,cs−i(NC)))=max(T(SIPsi,cs),T(πs−i,cs−i(NC))) (T(π^i(NC)_s_i,c_s),T(π^-i(NC)_s_-i,c_s))= (T(SIP_s_i,c_s),T(π^-i(NC)_s_-i,c_s)) Hence: T(πi|π−i)=T(πi∗|π−i)T(π^i|π^-i)=T(π^i^*|π^-i) In both cases, aia_i’s path πiπ^i serves as the best response to π−iπ^-i. Therefore, the joint strategy (π1,π2)(π^1,π^2) constitutes a PNE. Direction 2: (,)≠(,,,) (π^1,π^2)≠(SIP_s_1,g_1,SIP_s_2,g_2) is a PNE ⟹(,) (π^1,π^2) is an ECJS: Given a Pure Nash Equilibrium (PNE) joint strategy (π1,π2)(π^1,π^2), we assume, by contradiction, that one or more of the five conditions for an ECJS is violated. Each condition is analyzed individually: 1. Condition 1: We consider both parts of Condition 1: (a) the agents cooperate along exactly one continuous cooperation segment, and (b) this cooperation segment is stable. (a) We assume, by contradiction, that the joint strategy (π1,π2)(π^1,π^2) contains more than one cooperation segment. In that case, it can be expressed as: π1=πs1,cs11∘πcs1,cd1C∘πcd1,cs21∘πcs2,cd2C∘πcd2,cg11π^1=π^1_s_1,c_s_1 π^C_c_s_1,c_d_1 π^1_c_d_1,c_s_2 π^C_c_s_2,c_d_2 π^1_c_d_2,c_g_1 π2=πs2,cs12∘πcs1,cd1C∘πcd1,cs22∘πcs2,cd2C∘πcd2,cg22π^2=π^2_s_2,c_s_1 π^C_c_s_1,c_d_1 π^2_c_d_1,c_s_2 π^C_c_s_2,c_d_2 π^2_c_d_2,c_g_2 However, according to Lemma 3 (Cooperation Continuity), we have: T(πs1,cd11∘πcd1,cs22|πs2,cs22)≤T(πs1,cs21|πs2,cs22)T(π^1_s_1,c_d_1 π^2_c_d_1,c_s_2|π^2_s_2,c_s_2)≤ T(π^1_s_1,c_s_2|π^2_s_2,c_s_2) Therefore, it follows that: T(πs1,cd11∘πcd1,cs22∘πcs2,g11|π2)≤T(π1|π2)T(π^1_s_1,c_d_1 π^2_c_d_1,c_s_2 π^1_c_s_2,g_1|π^2)≤ T(π^1|π^2) If equality holds, since the joint path (πs1,cd11∘πcd1,cs22∘πcs2,g11,π2)(π^1_s_1,c_d_1 π^2_c_d_1,c_s_2 π^1_c_s_2,g_1,π^2) involves a single continuous cooperation segment, a1a_1 would prefer the strategy πs1,cd11∘πcd1,cs22∘πcs2,g11π^1_s_1,c_d_1 π^2_c_d_1,c_s_2 π^1_c_s_2,g_1 over π1π^1, contradicting the assumption that (π1,π2)(π^1,π^2) is a PNE. (b) We assume, by contradiction, that the cooperation partial path πcs,cd _c_s,c_d is not stable. In that case, for one of the agents, without loss of generality a1a_1, there exists a better departure node cd′=vd∗1(πcs,cd)c_d =v_d^*^1( _c_s,c_d), where cd′≠cdc_d ≠c_d, along the cooperation path: T(πcs,cd′∘SIPcd′,g1|πcs,cd)<T(πcs,cd∘SIPcd,g1|πcs,cd)T( _c_s,c_d SIP_c_d ,g_1| _c_s,c_d)<T( _c_s,c_d SIP_c_d,g_1| _c_s,c_d) Therefore, it follows that: T(πs1,cs1∘πcs,cd′∘SIPcd′,g1|π2)<T(π1,π2)T(π^1_s_1,c_s _c_s,c_d SIP_c_d ,g_1|π^2)<T(π^1,π^2) which contradicts the assumption that (π1,π2)(π^1,π^2) is a PNE. 2. Condition 2: We assume, by contradiction, that the paths of the two agents from their starting nodes to csc_s are not Mutually-Robust Non-Cooperative Partial Paths. We consider two options: (a) The path of one of the agents, without loss of generality a2a_2, to csc_s, πs2,cs2π^2_s_2,c_s, is not non-cooperative. In this case, there exists a cooperation node along this path, c∈πs2,cs2c∈π^2_s_2,c_s, c≠csc≠c_s, that a1a_1 can reach at a cooperation-relevant time (if there is more than one such node, we take c to be the first one along πs2,cs2π^2_s_2,c_s). From Lemma 1 (Early Cooperation), it follows that: T(SIPs1,c∘πc,cs2∘πcs,g11,π2)≤T(SIPs1,cs∘πcs,g11,π2)T(SIP_s_1,c π^2_c,c_s π^1_c_s,g_1,π^2)≤ T(SIP_s_1,c_s π^1_c_s,g_1,π^2) Additionally, since SIPs1,csSIP_s_1,c_s is the shortest path from s1s_1 to csc_s without involving cooperation, it follows that: T(SIPs1,cs∘πcs,g11,π2)≤T(πs1,cs1∘πcs,g11,π2)=T(πs1,g11|πs2,g22)T(SIP_s_1,c_s π^1_c_s,g_1,π^2)≤ T(π^1_s_1,c_s π^1_c_s,g_1,π^2)=T(π^1_s_1,g_1|π^2_s_2,g_2) If equality holds, since the joint path (SIPs1,c∘πc,cs2∘πcs,g11,π2)(SIP_s_1,c π^2_c,c_s π^1_c_s,g_1,π^2) starts cooperation earlier than (π1,π2)(π^1,π^2), a1a_1 would prefer the strategy SIPs1,c∘πc,cs2∘πcs,g11SIP_s_1,c π^2_c,c_s π^1_c_s,g_1 over π1π^1, contradicting the assumption that (π1,π2)(π^1,π^2) is a PNE. (b) One of the agents, without loss of generality a1a_1, can modify its path toward csc_s to a new path πs1,cs1′π^1 _s_1,c_s, allowing cooperation to start earlier at time t′=max(T(πs1,cs1′),T(πs2,cs2))<max(T(πs1,cs1),T(πs2,cs2))t = (T(π^1 _s_1,c_s),T(π^2_s_2,c_s))< (T(π^1_s_1,c_s),T(π^2_s_2,c_s)) The agent can then use the modified full path πs1,g11′=πs1,cs1′∘πcs,g11π^1 _s_1,g_1=π^1 _s_1,c_s π^1_c_s,g_1 and reach its target node at an improved time: T(πs1,g11′|πs2,g22)=t′+τcs2+T(πcs,g11|πcs,g22)<T(π^1 _s_1,g_1|π^2_s_2,g_2)=t +τ^2_c_s+T(π^1_c_s,g_1|π^2_c_s,g_2)< max(T(πs1,cs1),T(πs2,cs2))+τcs2+T(πcs,g11|πcs,g22)=T(π1,π2) (T(π^1_s_1,c_s),T(π^2_s_2,c_s))+τ^2_c_s+T(π^1_c_s,g_1|π^2_c_s,g_2)=T(π^1,π^2) contradicting the assumption that (π1,π2)(π^1,π^2) is a PNE. 3. Condition 3: We assume, by contradiction, that the optimal departure node for one of the agents, without loss of generality a1a_1, along the other agent’s path πcs,g22π^2_c_s,g_2 is cd′≠cdc_d ≠c_d. This implies that: T(πs1,cs1∘πcs,cd′2∘SIPcd′,g1|π2)<T(SIPs1,cs∘πcs,cd2∘SIPcd,g1|π2)=T(π1,π2)T(π^1_s_1,c_s π^2_c_s,c_d SIP_c_d ,g_1|π^2)<T(SIP_s_1,c_s π^2_c_s,c_d SIP_c_d,g_1|π^2)=T(π^1,π^2) which contradicts the assumption that (π1,π2)(π^1,π^2) is a PNE. 4. Condition 4: We assume, by contradiction, that for one of the agents, without loss of generality a1a_1, the partial path πcd,g11π^1_c_d,g_1 from the departure node cdc_d to its target node g1g_1 differs from the shortest independent path SIPcd,g1SIP_c_d,g_1. Since (π1,π2)(π^1,π^2) involves a single continuous cooperation segment (Condition 1), and cdc_d is the cooperation departure node, the joint path (πcd,g11,πcd,g22)(π^1_c_d,g_1,π^2_c_d,g_2) contains no cooperation. Therefore: T(πcd,g11|πcd,g22)=T(πcd,g11)>T(SIPcd,g1),T(π^1_c_d,g_1|π^2_c_d,g_2)=T(π^1_c_d,g_1)>T(SIP_c_d,g_1), which implies: T(π1|π2)>T(πs1,cd1∘SIPcd,g1|π2),T(π^1|π^2)>T(π^1_s_1,c_d SIP_c_d,g_1|π^2), contradicting the assumption that (π1,π2)(π^1,π^2) is a PNE. 5. Condition 5: We assume, by contradiction, that one of the agents, without loss of generality a1a_1, prefers to take its independent path directly from its starting node to its target node, SIPs1,g1SIP_s_1,g_1. In this case, the independent shortest path for a1a_1 would be a better response to the π2π^2 than π1π^1: T(SIPs1,g1,π2)<T(π1,π2).T(SIP_s_1,g_1,π^2)<T(π^1,π^2). This contradicts the assumption that the joint strategy (π1,π2)(π^1,π^2) is a PNE. Therefore, it holds that a cooperation joint strategy (π1,π2)≠(SIPs1,g1,SIPs2,g2)(π^1,π^2)≠(SIP_s_1,g_1,SIP_s_2,g_2) constitutes a Pure Nash Equilibrium (PNE) if and only if (π1,π2)(π^1,π^2) is an ECJS. ∎ Appendix C Proof of Lemma 5 Lemma 5 Let cd1,cd2∈VCc_d_1,c_d_2∈ V_C be two distinct cooperation nodes. Suppose there exists a stable cooperation partial path from cd1c_d_1 to cd2c_d_2, denoted πcd1,cd2Sπ^S_c_d_1,c_d_2. Then, for any stable cooperation partial path πcs,cd1 _c_s,c_d_1 from csc_s to cd1c_d_1, the concatenated path πcs,cd2′=πcs,cd1∘πcd1,cd2Sπ _c_s,c_d_2= _c_s,c_d_1 π^S_c_d_1,c_d_2 is also stable. Moreover, the optimal ECJS whose cooperation segment is πcs,cd2′π _c_s,c_d_2 dominates the optimal ECJS whose cooperation segment is πcs,cd1 _c_s,c_d_1. That is, ∀i∈1,2, ∀ i∈\1,2\, T(πcs,cd1∘SIPcd1,gi∣πcs,cd1∘SIPcd1,g−i) T\! ( _c_s,c_d_1 SIP_c_d_1,g_i _c_s,c_d_1 SIP_c_d_1,g_-i ) ≥T(πcs,cd2′∘SIPcd2,gi∣πcs,cd2′∘SIPcd2,g−i). ≥ T\! (π _c_s,c_d_2 SIP_c_d_2,g_i π _c_s,c_d_2 SIP_c_d_2,g_-i ). Proof. Given a stable path πcs,cd1 _c_s,c_d_1, since πcd1,cd2Sπ^S_c_d_1,c_d_2 is stable, the path πcs,cd2′=πcs,cd1∘πcd1,cd2Sπ _c_s,c_d_2= _c_s,c_d_1 π^S_c_d_1,c_d_2 is also stable. For an agent aia_i, the path time to its target node via a cooperation along πcs,cd1 _c_s,c_d_1 can be described as: T(πcs,cd1∘SIPcd1,gi|πcs,cd1∘SIPcd1,g−i)=T(πcs,cd1|πcs,cd1)+τcd12+T(SIPcd1,gi|SIPcd1,g−i)T( _c_s,c_d_1 SIP_c_d_1,g_i| _c_s,c_d_1 SIP_c_d_1,g_-i)=T( _c_s,c_d_1| _c_s,c_d_1)+τ^2_c_d_1+T(SIP_c_d_1,g_i|SIP_c_d_1,g_-i) Similarly, the path time to its target node via a cooperation along πcs,cd2′π _c_s,c_d_2 is: T(πcs,cd2′∘SIPcd2,gi|πcs,cd2′∘SIPcd2,g−i)=T(πcs,cd1|πcs,cd1)+τcd12+T(πcd1,cd2S∘SIPcd2,gi|πcd1,cd2S∘SIPcd2,g−i)T(π _c_s,c_d_2\!\! SIP_c_d_2,g_i|π _c_s,c_d_2\!\! SIP_c_d_2,g_-i)=T( _c_s,c_d_1| _c_s,c_d_1)+τ^2_c_d_1\!\!+T(π^S_c_d_1,c_d_2\!\! SIP_c_d_2,g_i|π^S_c_d_1,c_d_2\!\! SIP_c_d_2,g_-i) Since πcd1,cd2Sπ^S_c_d_1,c_d_2 is stable, it holds that: T(SIPcd1,gi|πcd1,cd2S∘SIPcd2,g−i)≥T(πcd1,cd2S∘SIPcd2,gi|πcd1,cd2S∘SIPcd2,g−i)T(SIP_c_d_1,g_i|π^S_c_d_1,c_d_2 SIP_c_d_2,g_-i)≥ T(π^S_c_d_1,c_d_2 SIP_c_d_2,g_i|π^S_c_d_1,c_d_2 SIP_c_d_2,g_-i) Additionally, since cd1c_d_1 is the last cooperation node along πcs,cd1 _c_s,c_d_1, (SIPcd1,gi,SIPcd1,g−i)(SIP_c_d_1,g_i,SIP_c_d_1,g_-i) involves no cooperation, and it follows that: T(SIPcd1,gi|SIPcd1,g−i)≥T(SIPcd1,gi|πcd1,cd2S∘SIPcd2,g−i)T(SIP_c_d_1,g_i|SIP_c_d_1,g_-i)≥ T(SIP_c_d_1,g_i|π^S_c_d_1,c_d_2 SIP_c_d_2,g_-i) Hence, T(πcs,cd1|πcs,cd1)+τcd12+T(SIPcd1,gi|SIPcd1,g−i)≥T( _c_s,c_d_1| _c_s,c_d_1)+τ^2_c_d_1\!\!+T(SIP_c_d_1,g_i|SIP_c_d_1,g_-i)\!\!≥\!\! T(πcs,cd1|πcs,cd1)+τcd12+T(πcd1,cd2S∘SIPcd2,gi|πcd1,cd2S∘SIPcd2,g−i)T( _c_s,c_d_1| _c_s,c_d_1)+τ^2_c_d_1+T(π^S_c_d_1,c_d_2 SIP_c_d_2,g_i|π^S_c_d_1,c_d_2 SIP_c_d_2,g_-i) which implies that: T(πcs,cd1∘SIPcd1,gi|πcs,cd1∘SIPcd1,g−i)≥T(πcs,cd2′∘SIPcd2,gi|πcs,cd2′∘SIPcd2,g−i)T( _c_s,c_d_1 SIP_c_d_1,g_i| _c_s,c_d_1 SIP_c_d_1,g_-i)≥ T(π _c_s,c_d_2 SIP_c_d_2,g_i|π _c_s,c_d_2 SIP_c_d_2,g_-i) and the lemma holds. ∎ Appendix D Proof of Lemma 6 Lemma 6 Consider a cooperative joint strategy of the form: (SIPs1,cs∘πcs,cdS∘SIPcd,g1,SIPs2,cs∘πcs,cdS∘SIPcd,g2), (SIP_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1,\ SIP_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2 ), where csc_s is the first cooperation node and cdc_d is the last cooperation node in which the agents cooperate, and πcs,cdS∈Πcs,cdπ^S_c_s,c_d∈ _c_s,c_d is a stable partial path. If the following condition holds: ∀i∈1,2,T(SIPsi,cs∘πcs,cdS∘SIPcd,gi|SIPs−i,cs∘πcs,cdS∘SIPcd,g−i)≤T(SIPsi,gi)∀ i∈\1,2\, T (SIP_s_i,c_s π^S_c_s,c_d SIP_c_d,g_i|\ SIP_s_-i,c_s π^S_c_s,c_d SIP_c_d,g_-i )≤ T (SIP_s_i,g_i ) then a Pure Nash Equilibrium (PNE) exists. Proof. Following Theorem 2, to show that a cooperative joint strategy constitutes a PNE, it is sufficient to show that it is an ECJS (by verifying the five conditions of Definition 5). Considering the joint strategy: (SIPs1,cs∘πcs,cdS∘SIPcd,g1,SIPs2,cs∘πcs,cdS∘SIPcd,g2) (SIP_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1,\ SIP_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2 ) We show that this joint strategy is either already an ECJS or can serve as the foundation for constructing one. The cooperation segment πcs,cdSπ^S_c_s,c_d is stable by the Lemma’s assumption, satisfying Condition 1. Additionally, since both agents follow their respective shortest independent paths from cdc_d to their target nodes, Condition 4 is satisfied. Furthermore, because both agents prefer this cooperative joint strategy over their independent shortest-path strategy, Condition 5 also holds. We show that if Conditions 2 and 3 do not hold, the cooperation segment πcs,cdSπ^S_c_s,c_d can be extended to satisfy them without violating the other conditions. Condition 2: If the paths SIPs1,csSIP_s_1,c_s and SIPs2,csSIP_s_2,c_s toward the cooperation starting node are non-cooperative, then, since neither agent can shorten its path to csc_s, these paths are mutually robust, satisfying the condition. However, if one agent (without loss of generality, a1a_1) can reach a cooperation node ce∈SIPs2,csc_e∈ SIP_s_2,c_s at a cooperation-relevant time, we show that the partial path πce,cd=SIPce,cs∘πcs,cdS _c_e,c_d=SIP_c_e,c_s π^S_c_s,c_d is also stable, and the resulting joint strategy (SIPs1,ce∘πce,cd∘SIPcd,g1,SIPs2,ce∘πce,cd∘SIPcd,g2) (SIP_s_1,c_e _c_e,c_d SIP_c_d,g_1,\ SIP_s_2,c_e _c_e,c_d SIP_c_d,g_2 ) continues to satisfy Conditions 1, 4, and 5. We assume, by contradiction, that for one of the agents, without loss of generality a1a_1, vd∗1(πce,cd)≠cdv_d^*^1( _c_e,c_d)≠c_d, and denote the optimal departure node as ce′c_e . Then: T(SIPs1,ce∘πce,ce′∘SIPce′,g1∣SIPs2,ce∘πce,cd∘SIPcd,g2)<T(SIPs1,ce∘πce,cd∘SIPcd,g1∣SIPs2,ce∘πce,cd∘SIPcd,g2)T(SIP_s_1,c_e _c_e,c_e SIP_c_e ,g_1 SIP_s_2,c_e _c_e,c_d SIP_c_d,g_2)<T(SIP_s_1,c_e _c_e,c_d SIP_c_d,g_1 SIP_s_2,c_e _c_e,c_d SIP_c_d,g_2) Since both agents start cooperating at cec_e, the above inequality can be rewritten as: max(T(SIPs1,ce∣SIPs2,ce),T(SIPs2,ce∣SIPs1,ce))+τce2+D(πce,ce′∣πce,ce′)+T(SIPce′,g1∣πce′,cd∘SIPcd,g2) (T(SIP_s_1,c_e SIP_s_2,c_e),T(SIP_s_2,c_e SIP_s_1,c_e))+τ^2_c_e+D( _c_e,c_e _c_e,c_e )+T(SIP_c_e ,g_1 _c_e ,c_d SIP_c_d,g_2) <max(T(SIPs1,ce∣SIPs2,ce),T(SIPs2,ce∣SIPs1,ce))+τce2+D(πce,ce′∣πce,ce′)+T(πce′,cd∘SIPcd,g1∣πce′,cd∘SIPcd,g2)< (T(SIP_s_1,c_e SIP_s_2,c_e),T(SIP_s_2,c_e SIP_s_1,c_e))+τ^2_c_e+D( _c_e,c_e _c_e,c_e )+T( _c_e ,c_d SIP_c_d,g_1 _c_e ,c_d SIP_c_d,g_2) Simplifying: T(SIPce′,g1∣πce′,cd∘SIPcd,g2)<T(πce′,cd∘SIPcd,g1∣πce′,cd∘SIPcd,g2)T(SIP_c_e ,g_1 _c_e ,c_d SIP_c_d,g_2)<T( _c_e ,c_d SIP_c_d,g_1 _c_e ,c_d SIP_c_d,g_2) Adding the arrival time of a1a_1 at ce′c_e (without cooperation) to both sides of the in-equation: D(SIPs1,ce′)+T(SIPce′,g1∣πce′,cd∘SIPcd,g2)<D(SIPs1,ce′)+T(πce′,cd∘SIPcd,g1∣πce′,cd∘SIPcd,g2)D(SIP_s_1,c_e )+T(SIP_c_e ,g_1 _c_e ,c_d SIP_c_d,g_2)<D(SIP_s_1,c_e )+T( _c_e ,c_d SIP_c_d,g_1 _c_e ,c_d SIP_c_d,g_2) Since ce′c_e is the optimal departure node for a1a_1, (SIPce′,g1,πce′,cd∘SIPcd,g2)(SIP_c_e ,g_1, _c_e ,c_d SIP_c_d,g_2) does not involve cooperation. Moreover, as SIPs1,g1SIP_s_1,g_1 denotes the shortest path to g1g_1 without cooperation: D(SIPs1,ce′)+T(SIPce′,g1∣πce′,cd∘SIPcd,g2)=D(SIPs1,ce′)+T(SIPce′,g1)≥T(SIPs1,g1)D(SIP_s_1,c_e )+T(SIP_c_e ,g_1 _c_e ,c_d SIP_c_d,g_2)=D(SIP_s_1,c_e )+T(SIP_c_e ,g_1)≥ T(SIP_s_1,g_1) Thus: D(SIPs1,ce′)+T(πce′,cd∘SIPcd,g1∣πce′,cd∘SIPcd,g2)>T(SIPs1,g1)D(SIP_s_1,c_e )+T( _c_e ,c_d SIP_c_d,g_1 _c_e ,c_d SIP_c_d,g_2)>T(SIP_s_1,g_1) Since the path time T(πce′,cd∘SIPcd,g1∣πce′,cd∘SIPcd,g2)T( _c_e ,c_d SIP_c_d,g_1 _c_e ,c_d SIP_c_d,g_2) assumes cooperation along πce′,cs _c_e ,c_s, it follows that: T(SIPs1,cs∘πcs,cdS∘SIPcd,g1∣SIPs2,cs∘πcs,cdS∘SIPcd,g2)≥T(SIP_s_1,c_s π^S_c_s,c_d SIP_c_d,g_1 SIP_s_2,c_s π^S_c_s,c_d SIP_c_d,g_2)≥ D(SIPs1,ce′)+T(πce′,cd∘SIPcd,g1∣πce′,cd∘SIPcd,g2)>T(SIPs1,g1)D(SIP_s_1,c_e )+T( _c_e ,c_d SIP_c_d,g_1 _c_e ,c_d SIP_c_d,g_2)>T(SIP_s_1,g_1) contradicting our assumption. Thus, we conclude that πce,cd=SIPce,cs∘πcs,cdS _c_e,c_d=SIP_c_e,c_s π^S_c_s,c_d constitutes a Stable Cooperation Partial Path. Since the joint strategy (SIPs1,ce∘πce,cd∘SIPcd,g1,SIPs2,ce∘πce,cd∘SIPcd,g2) (SIP_s_1,c_e _c_e,c_d SIP_c_d,g_1,\ SIP_s_2,c_e _c_e,c_d SIP_c_d,g_2 ) initiates cooperation at node cec_e, which precedes csc_s, it dominates the original joint strategy and therefore preserves the conditions of Definition 5 that were satisfied by the original joint strategy. Since the set of cooperation nodes is finite, the cooperation segment can be repeatedly extended until reaching a cooperation starting node cs∈VCc_s∈ V_C for which the paths SIPs1,csSIP_s_1,c_s and SIPs2,csSIP_s_2,c_s are mutually robust and non-cooperative, satisfying Condition 2. Condition 3: By Corollary 1, if there exists a cooperation joint strategy that satisfies all conditions of Definition 5 except Condition 3 (i.e., one of the agents, aia_i, prefers to continue cooperating with a−ia_-i beyond cdc_d along the path to a−ia_-i’s target node), then a cooperation joint strategy extending this cooperation satisfies the same conditions of Definition 5 and dominates the original one. Since the set of cooperation nodes is finite, the cooperation segment can be repeatedly extended until reaching a cooperation ending node cd′∈VCc_d ∈ V_C that satisfies Condition 3. Thus, the joint strategy (SIPs1,cs′∘SCPcs′,cd′S∘SIPcd′,g1,SIPs2,cs′∘SCPcs′,cd′,g2S∘SCPcd′) (SIP_s_1,c_s SCP^S_c_s ,c_d SIP_c_d ,g_1, SIP_s_2,c_s SCP^S_c_s ,c_d ,g_2 SCP_c_d ) where cs′c_s is the cooperation starting node that satisfies Condition 2, found by repeatedly extending the cooperation segment from the beginning, and cd′c_d is the cooperation ending node that satisfies Condition 3, found by repeatedly extending the segment from the end, is an ECJS and, by Theorem 2, constitutes a PNE. ∎ Appendix E Social Welfare Optimization We aim to determine the joint strategy (π1∗,π2∗)(π^1^*,π^2^*) for agents a1a_1 and a2a_2 that minimizes their total path time: (π1∗,π2∗)=argminπ1,π2[Tg1(π1|π2)+Tg2(π2|π1)](π^1^*,π^2^*)= _π^1,π^2 [T_g_1(π^1|π^2)+T_g_2(π^2|π^1) ] Considering VC=c1,…,cmV_C=\c_1,…,c_m\ for some m>0m>0, a naive approach might involve evaluating all combinations of possible cooperation paths. However, Lemma 3 provides key insights into the structure of the optimal social welfare joint strategy, significantly streamlining the search process. According to Lemma 3, the most efficient cooperation path, minimizing the total path time between some initial cooperation node (denoted with csc_s) and a final cooperation node (denoted with cdc_d) for both agents, involves continuous cooperation along the same path SCPcs,cdSCP_c_s,c_d. The joint strategy that optimizes social welfare is therefore: (π1∗,π2∗)=(SIPs1,cs∘SCPcs,cd∘SIPcd,g1,SIPs2,cs∘SCPcs,cd∘SIPcd,g2)(π^1^*,π^2^*)=(SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1,SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2) Thus, our objective is to identify the cooperation starting node csc_s and the cooperation departure node cdc_d that optimize social welfare (see illustration in Figure 12): cs,cd=argmincs,cd[ c_s,c_d= _c_s,c_d [ Tg1(SIPs1,cs∘SCPcs,cd∘SIPcd,g1|SIPs2,cs∘SCPcs,cd∘SIPcd,g2)+ T_g_1(SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1|SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2)+ Tg2(SIPs2,cs∘SCPcs,cd∘SIPcd,g2|SIPs1,cs∘SCPcs,cd∘SIPcd,g1) T_g_2(SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2|SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1) ] ] Figure 12: Social welfare optimization occurs when both agents follow the shortest path from their initial nodes to a cooperation node csc_s, then continuously cooperate along a shared path to the final cooperation node cdc_d. After reaching cdc_d, the agents depart and take the shortest paths to their respective target nodes. Using a shortest path algorithm from g1g_1 and g2g_2, we can determine the shortest path time from each cooperation node ci∈VCc_i∈ V_C to g1g_1, denoted as SIPci,g1SIP_c_i,g_1, and to g2g_2, denoted as SIPci,g2SIP_c_i,g_2. The total path time of these paths, Tci,g1(SIPci,g1)+Tci,g2(SIPci,g2)T_c_i,g_1(SIP_c_i,g_1)+T_c_i,g_2(SIP_c_i,g_2), is referred to as the departure value of node cic_i and is denoted by d∗(ci)d^*(c_i): d∗(ci)=Tci,g1(SIPcig1)+Tci,g2(SIPci,g2)d^*(c_i)=T_c_i,g_1(SIP_c_ig_1)+T_c_i,g_2(SIP_c_i,g_2) To find the optimal departure node for a cooperation that starts at a given node csc_s, we identify the departure node that minimizes the combined path time of reaching it cooperatively from csc_s and subsequently reaching the target nodes from it: vd(cs)=argminc∈VC(2⋅(Tcs,c(SCPcs,c|SCPcs,c)+τc2)+d∗(c))v_d(c_s)= _c∈ V_C (2· (T_c_s,c(SCP_c_s,c|SCP_c_s,c)+τ^2_c )+d^*(c) ) However, determining the optimal node to initiate cooperation, csc_s, may still require evaluating all potential cooperation nodes. While Lemma 1 demonstrates that starting cooperation earlier along a specific path generally results in a shorter overall path time, it cannot be applied to globally compare cooperation nodes, as different nodes may result in distinct subsequent paths. Consequently, a cooperation that begins later but follows a different path may achieve a better overall path time than one that begins earlier (see example in Figure 13). Figure 13: Although a1a_1 and a2a_2 can begin cooperation at c2c_2 earlier than at c1c_1, the optimal social welfare is achieved when the cooperation starts at c1c_1. To improve the performance of finding the optimal cooperation starting node csc_s we propose a pruning approach that leverages Lemma 1 to reduce the number of evaluated cooperation nodes while ensuring all possible cooperation paths are considered. Using a shortest path algorithm from s1s_1 and s2s_2, we can determine the shortest path time to each cooperation node ci∈VCc_i∈ V_C, denoted as SIPs1,ciSIP_s_1,c_i and SIPs2,ciSIP_s_2,c_i, respectively. We denote the earliest cooperation time of node cic_i as t∗(ci)t^*(c_i), which represents the earliest shared departure time for two agents starting to cooperate at this node: t∗(ci)=max(Ts1,ci(SIPs1,ci),Ts2,ci(SIPs2,ci))+τci2t^*(c_i)= (T_s_1,c_i(SIP_s_1,c_i),T_s_2,c_i(SIP_s_2,c_i) )+τ^2_c_i We sort the cooperation nodes in ascending order based on their earliest cooperation times . For each potential cooperation starting node cic_i, we determine its associated optimal departure node vdi=vd(ci)v_d_i=v_d(c_i) and calculate the social welfare of the path dictated by the two nodes: 2⋅(t∗(ci)+Tci,di(SCPci,di|SCPci,di)+τdi2)+d∗(vdi)2· (t^*(c_i)+T_c_i,d_i(SCP_c_i,d_i|SCP_c_i,d_i)+τ^2_d_i )+d^*(v_d_i) With the goal of finding the optimal cooperation starting node csc_s that minimizes social welfare: cs=argminci∈VC(2⋅(t∗(ci)+Tci,di(SCPci,di|SCPci,di)+τvdi2)+d∗(vdi))c_s= _c_i∈ V_C (2· (t^*(c_i)+T_c_i,d_i(SCP_c_i,d_i|SCP_c_i,d_i)+τ^2_v_d_i )+d^*(v_d_i) ) Since evaluating a cooperation starting node cic_i as a starting node involves finding the shortest cooperative path to every other cooperation node cj∈VCc_j∈ V_C, we compare the arrival time at cjc_j through cic_i with t∗(cj)t^*(c_j). If t∗(cj)≥t∗(ci)+Dci,cj(SCPci,cj|SCPci,cj)t^*(c_j)≥ t^*(c_i)+D_c_i,c_j(SCP_c_i,c_j|SCP_c_i,c_j) then we can prune cjc_j and exclude it as a potential cooperation starting node, thereby reducing the number of nodes to be evaluated (see example in Figure 14). Figure 14: Although a1a_1 and a2a_2 can individually reach c2c_2 by t=6t=6, starting cooperation earlier at c1c_1 allows them to reach c2c_2 by t=5t=5, improving path efficiency. As a result, c2c_2 can be excluded from the set of potential cooperation starting nodes, as initiating cooperation earlier at c1c_1 yields a more efficient outcome. Algorithm 6 is designed to identify the optimal joint strategy (π1∗,π2∗π^*_1,π^*_2) that minimizes social welfare for two agents navigating a graph with m cooperation nodes. The algorithm starts by finding SIPs1SIP_s_1 and SIPs2SIP_s_2 (all shortest independent paths from the initial nodes to other graph nodes), and SIPg1SIP_g_1 and SIPg2SIP_g_2 (all shortest independent paths to the target nodes from other graph nodes) [lines 1-4]. These paths are then used to compute the departure value d∗(c)d^*(c) and the earliest cooperation time t∗(c)t^*(c) for each cooperation node c∈VCc∈ V_C [lines 5-8]. The algorithm iterates over all cooperation nodes cs∈VCc_s∈ V_C, in ascending order of their t∗t^* values, evaluating each as a potential cooperation starting node within a continuous cooperation joint strategy (SIPs1,cs∘SCPcs,cd∘SIPcd,g1,SIPs2,cs∘SCPcs,cd∘SIPcd,g2)(SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1,SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2). It first computes the shortest paths from the selected node to all other nodes in the graph, assuming cooperation at all nodes. Then, it evaluates the remaining cooperation nodes as potential cooperation departure nodes by calculating the total path time for both agents when these nodes are designated as the cooperation endpoints [lines 9-26]. If a cooperation node can be reached earlier through cooperation than individually, it is pruned from consideration as a cooperation starting node [lines 16-17]. Finally, the algorithm returns the social welfare optimal joint strategy [line 27]. Algorithm 6 Social Welfare Optimal Path(G,VC,s1,s2,g1,g2G,V_C,s_1,s_2,g_1,g_2) 1:SIPs1←all shortest paths from(G,τ1,s1)SIP_s_1← all shortest paths from(G,τ^1,s_1) ⊳ Find shortest paths from starting nodes 2:SIPs2←all shortest paths from(G,τ1,s2)SIP_s_2← all shortest paths from(G,τ^1,s_2) 3:SIPg1←all shortest paths to(G,τ1,g1)SIP_g_1← all shortest paths to(G,τ^1,g_1) ⊳ Find shortest paths to target nodes 4:SIPg2←all shortest paths to(G,τ1,g2)SIP_g_2← all shortest paths to(G,τ^1,g_2) 5:for all c∈VCc∈ V_C do ⊳ Determine t∗t^* and d∗d^* for all node 6: tc∗←max(SIPs1,c,SIPs2,c)+τc2t^*_c← (SIP_s_1,c,SIP_s_2,c)+τ^2_c 7: dc∗←SIPg1,c+SIPg2,cd^*_c← SIP_g_1,c+SIP_g_2,c 8:coopStartNodes←Sort(VC,by ascending t∗)coopStartNodes← Sort(V_C,by ascending t^*) ⊳ Sort cooperation nodes by t∗t^* 9:π1∗←SIPs1,g1,π2∗←SIPs2,g2π^*_1← SIP_s_1,g_1,π^*_2← SIP_s_2,g_2 10:minimalJointPathTime←SIPs1,g1+SIPs2,g2minimalJointPathTime← SIP_s_1,g_1+SIP_s_2,g_2 11:while coopStartNodes≠∅coopStartNodes≠ do 12: cs←coopStartNodes.pop()c_s← coopStartNodes. pop() ⊳ Select a starting node 13: SCPcs←all shortest paths from(G,τ2,cs)SCP_c_s← all shortest paths from(G,τ^2,c_s) ⊳ Find shortest paths from csc_s 14: for all c∈VCc∈ V_C do 15: if tcs∗+SCPcs,c+τc2≤tc∗t^*_c_s+SCP_c_s,c+τ^2_c≤ t^*_c then 16: coopStartNodes.remove(c)coopStartNodes. remove(c) ⊳ Prune non-optimal cooperation starting nodes 17: totalPathTime←2⋅(tcs∗+SCPcs,c+τc2)+dc∗totalPathTime← 2·(t^*_c_s+SCP_c_s,c+τ^2_c)+d^*_c 18: if totalPathTime<minimalJointPathTimetotalPathTime<minimalJointPathTime then ⊳ Update optimal joint path time 19: minimalJointPathTime←totalPathTimeminimalJointPathTime← totalPathTime 20: π1∗←SIPs1,cs∘SCPcs,c∘SIPc,g1π^*_1← SIP_s_1,c_s SCP_c_s,c SIP_c,g_1 21: π2∗←SIPs2,cs∘SCPcs,c∘SIPc,g2π^*_2← SIP_s_2,c_s SCP_c_s,c SIP_c,g_2 22:return (π1∗,π2∗)(π^*_1,π^*_2) ⊳ Return social welfare optimal path To establish the optimality of the algorithm, we verify two key lemmas, analogous to Lemmas 1 and 3 presented in the Fixed Strategy Assumption scenario: 1. Cooperation Continuity: The joint strategy that optimizes social welfare through cooperation is one in which a1a_1 and a2a_2 independently follow the shortest paths to a cooperation starting node csc_s (SIPs1,cs,SIPs2,csSIP_s_1,c_s,SIP_s_2,c_s), cooperate along the joint shortest path to a cooperation departure node cdc_d (SCPcs,cdSCP_c_s,c_d), and then each independently follows the shortest path to their respective target nodes (SIPcd,g1,SIPcd,g2SIP_c_d,g_1,SIP_c_d,g_2). 2. Early Cooperation: If agents a1a_1 and a2a_2 can reach a cooperation node c∈VCc∈ V_C earlier through cooperation rather than individually, then c is not the first cooperation node in the joint strategy that optimizes social welfare. Lemma 8 (Cooperation Continuity). Let π1∈Πs1,g1π^1∈ _s_1,g_1 and π2∈Πs2,g2π^2∈ _s_2,g_2 be two paths that begin cooperation at node csc_s and finish the cooperation at node cdc_d. Then, it holds that: Tg1(π′1|π′2)+Tg2(π′2|π′1)≤Tg1(π1|π2)+Tg2(π2|π1)T_g_1(π 1|π 2)+T_g_2(π 2|π 1)≤ T_g_1(π^1|π^2)+T_g_2(π^2|π^1) Where: π′1=SIPs1,cs∘SCPcs,cd∘SIPcd,g1π 1=SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1 π′2=SIPs2,cs∘SCPcs,cd∘SIPcd,g2π 2=SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2 Proof. Since a1a_1 and a2a_2 cooperate at nodes csc_s and cdc_d, the social welfare induced by π′1π 1 and π′2π 2 is given by: Tg1(π′1|π′2)+Tg2(π′2|π′1)=T_g_1(π 1|π 2)+T_g_2(π 2|π 1)= 2⋅(max(Ts1,cs(SIPs1,cs),Ts2,cs(SIPs2,cs))+τcs2+Tcs,cd(SCPcs,cd|SCPcs,cd)+τcd2)2· ( (T_s_1,c_s(SIP_s_1,c_s),T_s_2,c_s(SIP_s_2,c_s) )+τ^2_c_s+T_c_s,c_d(SCP_c_s,c_d|SCP_c_s,c_d)+τ^2_c_d ) +Tcd,g1(SIPcd,g1)+Tcd,g2(SIPcd,g2)+T_c_d,g_1(SIP_c_d,g_1)+T_c_d,g_2(SIP_c_d,g_2) The social welfare induced by π1π^1 and π2π^2 is: Tg1(π1|π2)+Tg2(π2|π1)=T_g_1(π^1|π^2)+T_g_2(π^2|π^1)= 2⋅(max(Ts1,cs(π1),Ts2,cs(π2))+τcs2+max(Tcs,cd(π1|π2),Tcs,cd(π2|π1))+τcd2)2· ( (T_s_1,c_s(π^1),T_s_2,c_s(π^2) )+τ^2_c_s+ (T_c_s,c_d(π^1|π^2),T_c_s,c_d(π^2|π^1))+τ^2_c_d ) +Tcd,g1(π1)+Tcd,g2(π2)+T_c_d,g_1(π^1)+T_c_d,g_2(π^2) Since the execution time for a1a_1 at each node v visited by π1 _1 before csc_s or after cdc_d is τi1τ^1_i, Then by the definitions of SIPs1,csSIP_s_1,c_s and SIPcd,g1SIP_c_d,g_1 we have: Ts1,cs(SIPs1,cs)≤Ts1,cs(π1)T_s_1,c_s(SIP_s_1,c_s)≤ T_s_1,c_s(π^1) Tcd,g1(SIPcd,g1)≤Tcd,g1(π1)T_c_d,g_1(SIP_c_d,g_1)≤ T_c_d,g_1(π^1) Similarly: Ts2,cs(SIPs2,cs)≤Ts2,cs(π2)T_s_2,c_s(SIP_s_2,c_s)≤ T_s_2,c_s(π^2) Tcd,g2(SIPcd,g2)≤Tcd,g2(π2)T_c_d,g_2(SIP_c_d,g_2)≤ T_c_d,g_2(π^2) Therefore: max(Ts1,cs(SIPs1,cs),Ts2,cs(SIPs2,cs))≤max(Ts1,cs(π1|π2),Ts2,cs(π2|π1)) (T_s_1,c_s(SIP_s_1,c_s),T_s_2,c_s(SIP_s_2,c_s) )≤ (T_s_1,c_s(π^1|π^2),T_s_2,c_s(π^2|π^1) ) Additionally, since a1a_1 and a2a_2 depart from node csc_s simultaneously, traveling together ensures they arrive at subsequent cooperation nodes at the same time, enabling them to cooperate at those nodes. Therefore, by the definition of SCPcs,cdSCP_c_s,c_d: Tcs,cd(SCPcs,cd|SCPcs,cd)≤Tcs,cd(π1|π2)T_c_s,c_d(SCP_c_s,c_d|SCP_c_s,c_d)≤ T_c_s,c_d(π^1|π^2) Tcs,cd(SCPcs,cd|SCPcs,cd)≤Tcs,cd(π2|π1)T_c_s,c_d(SCP_c_s,c_d|SCP_c_s,c_d)≤ T_c_s,c_d(π^2|π^1) Thus: Tcs,cd(SCPcs,cd|SCPcs,cd)≤max(Tcs,cd(π1|π2),Tcs,cd(π2|π1))T_c_s,c_d(SCP_c_s,c_d|SCP_c_s,c_d)≤ (T_c_s,c_d(π^1|π^2),T_c_s,c_d(π^2|π^1)) Combining these results: Tg1(π′1|π′2)+Tg2(π′2|π′1)≤Tg1(π1|π2)+Tg2(π2|π1)T_g_1(π 1|π 2)+T_g_2(π 2|π 1)≤ T_g_1(π^1|π^2)+T_g_2(π^2|π^1) ∎ Lemma 9 (Early Cooperation). Assume two cooperation nodes ci,cj∈VCc_i,c_j∈ V_C such that a1a_1 and a2a_2 can both reach cic_i by cooperating at cjc_j no later than they would by traveling directly, i.e., t∗(ci)≥t∗(cj)+Tcj,ci(SCPcj,ci|SCPcj,ci)+τci2.t^*(c_i)≥ t^*(c_j)+T_c_j,c_i(SCP_c_j,c_i|SCP_c_j,c_i)+τ^2_c_i. Then, the minimal joint path time possible by a path starting cooperation at cjc_j (achieved by departing from vdj=vd(cj)v_d_j=v_d(c_j)) is at least as low as the minimal joint path time possible by a path starting cooperation at cic_i (achieved by departing from vdi=vd(ci)v_d_i=v_d(c_i)), i.e., 2⋅(t∗(cj)+Tcj,vdj(SCPcj,vdj|SCPcj,vdj)+τvdj2)+d∗(vdj)≤2· (t^*(c_j)+T_c_j,v_d_j(SCP_c_j,v_d_j|SCP_c_j,v_d_j)+τ^2_v_d_j )+d^*(v_d_j)≤ 2⋅(t∗(ci)+Tci,vdi(SCPci,vdi|SCPci,vdi)+τvdi2)+d∗(vdi).2· (t^*(c_i)+T_c_i,v_d_i(SCP_c_i,v_d_i|SCP_c_i,v_d_i)+τ^2_v_d_i )+d^*(v_d_i). Theorem 5. Given an IC2P instance with two agents a1a_1 and a2a_2, Algorithm 6 finds the joint strategy (S1∗,S2∗)(S^1^*,S^2^*) that optimizes the social welfare of a1a_1 and a2a_2. Outline. This result follows directly from Lemmas 8 and 9. Lemma 8 establishes that the joint strategy that optimizes social welfare is of the following form: (π1∗,π2∗)=(SIPs1,cs∘SCPcs,cd∘SIPcd,g1,SIPs2,cs∘SCPcs,cd∘SIPcd,g2),(π^1^*,π^2^*)=(SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1,SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2), which implies that finding the joint strategy that optimizes social welfare is equivalent to finding the nodes csc_s and cdc_d that minimize the total path time. Lemma 9 demonstrates that if a cooperation node can be reached earlier through cooperation rather than individually, then this node is not the starting cooperation node in the optimal social welfare joint strategy and can be disregarded. By combining these results, we conclude that Algorithm 6, which evaluates all possible cooperation nodes c∈VCc∈ V_C as potential starting cooperation nodes (excluding those that can be pruned by Lemma 9), identifies their corresponding optimal departure nodes vd(c)v_d(c), and returns the paths π1∗,π2∗π^1^*,π^2^* (π1∗,π2∗)=(SIPs1,cs∘SCPcs,cd∘SIPcd,g1,SIPs2,cs∘SCPcs,cd∘SIPcd,g2),(π^1^*,π^2^*)=(SIP_s_1,c_s SCP_c_s,c_d SIP_c_d,g_1,SIP_s_2,c_s SCP_c_s,c_d SIP_c_d,g_2), corresponding to: cs=argminc∈VC(2⋅(t∗(c)+Tc,cd(SCPc,cd|SCPc,cd)+τcd2)+d∗(vd(c))c_s= _c∈ V_C (2· (t^*(c)+T_c,c_d(SCP_c,c_d|SCP_c,c_d)+τ^2_c_d )+d^*(v_d(c) ) cd=vd(cs)c_d=v_d(c_s) successfully finds the joint strategy (π1∗,π2∗)(π^1^*,π^2^*) that optimizes the social welfare of a1a_1 and a2a_2. Complexity Analysis Every run of the algorithm starts with four executions of Dijkstra’s algorithm to determine the shortest paths from s1,s2,g1s_1,s_2,g_1, and g2g_2. Each run of Dijkstra’s algorithm has a time complexity of (|E|+|V|log|V|)O(|E|+|V| |V|). Consequently, the total complexity for these four runs is: (4⋅(|E|+|V|log|V|))=(|E|+|V|log|V|)O(4·(|E|+|V| |V|))=O(|E|+|V| |V|) The algorithm then evaluates at most m potential starting cooperation nodes. Thus, the overall complexity for evaluating these nodes is: (m⋅(|E|+|V|log|V|))O(m·(|E|+|V| |V|)) Combining these, the total complexity of the algorithm is: (m⋅(|E|+|V|log|V|))O(m·(|E|+|V| |V|)) Appendix F Experimental Results F.1 Results Across All Scenarios Figure 15: Effects of cooperation factors on individual path times across all tested scenarios, including those with a single PNE. Figure 16: Effects of cooperation factors on social welfare across all tested scenarios, including those with a single PNE. F.2 Summary Tables for the Experimental Results All values in the table below are reported together with their corresponding standard deviations. F.2.1 Average Number of PNEs a Table 1: Effects of Cooperation Density on average amount of PNEs. Cooperation Density Average Number of PNEs 0.1 1.02±0.141.02± 0.14 0.2 1.21±0.45381.21± 0.4538 0.3 1.27±0.52641.27± 0.5264 0.4 1.4±0.61641.4± 0.6164 0.5 1.41±0.60161.41± 0.6016 0.6 1.55±0.68371.55± 0.6837 0.7 1.65±0.68371.65± 0.6837 0.8 2.15±0.80472.15± 0.8047 0.9 2.16±0.95622.16± 0.9562 1.0 2.58±1.23432.58± 1.2343 Table 2: Effects of Cooperation Magnitude on average amount of PNEs. Cooperation Magnitude Average Number of PNEs 2 1.18±0.40941.18± 0.4094 4 1.5±0.74161.5± 0.7416 6 1.62±0.74541.62± 0.7454 8 1.76±0.90691.76± 0.9069 10 1.77±0.73291.77± 0.7329 12 1.94±0.89241.94± 0.8924 14 1.78±0.84361.78± 0.8436 16 1.9±0.88881.9± 0.8888 18 1.99±0.81851.99± 0.8185 20 1.88±0.8281.88± 0.828 Table 3: Effects of Path Length on average amount of PNEs. Path Length Average Number of PNEs 0-49 1.2439±0.4571.2439± 0.457 50-99 1.3509±0.57711.3509± 0.5771 100-149 1.8759±0.79641.8759± 0.7964 150-199 1.7828±0.81541.7828± 0.8154 200-249 1.8873±0.81451.8873± 0.8145 250-299 1.9157±0.78411.9157± 0.7841 300-349 1.8977±0.76891.8977± 0.7689 350-399 1.7359±0.83481.7359± 0.8348 400-449 1.5455±0.72641.5455± 0.7264 450-499 1.4674±0.77251.4674± 0.7725 500-549 1.4667±0.78461.4667± 0.7846 550-599 1.561±0.9641.561± 0.964 600-649 1.6591±0.95211.6591± 0.9521 650-699 1.4595±0.64071.4595± 0.6407 700-749 1.4167±0.68211.4167± 0.6821 750-799 1.6±0.58311.6± 0.5831 800-849 1.3333±0.47141.3333± 0.4714 850-899 1.4±0.63251.4± 0.6325 900-949 1.68±1.22381.68± 1.2238 950-999 1.4±0.58311.4± 0.5831 Table 4: Effects of SPD on average amount of PNEs. SPD Average Number of PNEs 0-10 1.3996±0.72761.3996± 0.7276 11-20 1.4372±0.73511.4372± 0.7351 21-30 1.52±0.83641.52± 0.8364 31-40 1.4271±0.73941.4271± 0.7394 41-50 1.4167±0.74261.4167± 0.7426 51-60 1.2552±0.68651.2552± 0.6865 61-70 1.2267±0.56111.2267± 0.5611 71-80 1.1152±0.44591.1152± 0.4459 81-90 1.0471±0.21181.0471± 0.2118 91-100 1.0472±0.2121.0472± 0.212 F.2.2 Individual path times in multiple-PNE scenarios a Table 5: Effect of Cooperation Density on individual path times among scenarios with more than one PNE. Cooperation Density SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 0.1 1±01± 0 0.8072±0.05620.8072± 0.0562 0.8816±0.06740.8816± 0.0674 0.8878±0.06440.8878± 0.0644 0.8878±0.06440.8878± 0.0644 0.9024±0.03320.9024± 0.0332 0.8878±0.06440.8878± 0.0644 0.8935±0.05440.8935± 0.0544 0.9024±0.03320.9024± 0.0332 0.8878±0.06440.8878± 0.0644 0.2 1±01± 0 0.705±0.06350.705± 0.0635 0.786±0.07970.786± 0.0797 0.8007±0.08080.8007± 0.0808 0.7924±0.07610.7924± 0.0761 0.7996±0.0670.7996± 0.067 0.794±0.07240.794± 0.0724 0.7994±0.06840.7994± 0.0684 0.8074±0.06080.8074± 0.0608 0.7924±0.07610.7924± 0.0761 0.3 1±01± 0 0.6072±0.0730.6072± 0.073 0.6838±0.09830.6838± 0.0983 0.6952±0.09470.6952± 0.0947 0.692±0.09710.692± 0.0971 0.6966±0.09420.6966± 0.0942 0.692±0.09290.692± 0.0929 0.6962±0.09120.6962± 0.0912 0.6975±0.09140.6975± 0.0914 0.6914±0.09590.6914± 0.0959 0.4 1±01± 0 0.5079±0.0830.5079± 0.083 0.6038±0.11850.6038± 0.1185 0.6174±0.12210.6174± 0.1221 0.6116±0.12040.6116± 0.1204 0.6229±0.1050.6229± 0.105 0.6131±0.11280.6131± 0.1128 0.6185±0.10730.6185± 0.1073 0.6279±0.09930.6279± 0.0993 0.6115±0.12030.6115± 0.1203 0.5 1±01± 0 0.4031±0.09460.4031± 0.0946 0.4816±0.11260.4816± 0.1126 0.4911±0.11170.4911± 0.1117 0.4854±0.11370.4854± 0.1137 0.4918±0.10870.4918± 0.1087 0.4857±0.10820.4857± 0.1082 0.4902±0.10780.4902± 0.1078 0.4964±0.10810.4964± 0.1081 0.4851±0.11350.4851± 0.1135 0.6 1±01± 0 0.322±0.06510.322± 0.0651 0.4144±0.0870.4144± 0.087 0.4235±0.09080.4235± 0.0908 0.4211±0.09010.4211± 0.0901 0.4261±0.08560.4261± 0.0856 0.4212±0.08760.4212± 0.0876 0.4275±0.08520.4275± 0.0852 0.4319±0.08360.4319± 0.0836 0.4211±0.08950.4211± 0.0895 0.7 1±01± 0 0.2818±0.05930.2818± 0.0593 0.3886±0.12010.3886± 0.1201 0.3996±0.12480.3996± 0.1248 0.3938±0.12270.3938± 0.1227 0.3985±0.12470.3985± 0.1247 0.394±0.12170.394± 0.1217 0.4015±0.11810.4015± 0.1181 0.4024±0.120.4024± 0.12 0.3938±0.12280.3938± 0.1228 0.8 1±01± 0 0.2326±0.04040.2326± 0.0404 0.3286±0.08670.3286± 0.0867 0.337±0.09140.337± 0.0914 0.3341±0.09020.3341± 0.0902 0.3382±0.08940.3382± 0.0894 0.334±0.08920.334± 0.0892 0.3399±0.08710.3399± 0.0871 0.3425±0.08850.3425± 0.0885 0.3345±0.09140.3345± 0.0914 0.9 1±01± 0 0.2029±0.02090.2029± 0.0209 0.3117±0.12070.3117± 0.1207 0.3175±0.12110.3175± 0.1211 0.3158±0.12170.3158± 0.1217 0.3183±0.11920.3183± 0.1192 0.3156±0.11950.3156± 0.1195 0.3196±0.11810.3196± 0.1181 0.3219±0.1170.3219± 0.117 0.3158±0.12160.3158± 0.1216 1.0 1±01± 0 0.1873±0.00270.1873± 0.0027 0.2846±0.07620.2846± 0.0762 0.2922±0.08530.2922± 0.0853 0.2885±0.07790.2885± 0.0779 0.2914±0.07760.2914± 0.0776 0.2884±0.07710.2884± 0.0771 0.2927±0.07440.2927± 0.0744 0.2943±0.07610.2943± 0.0761 0.2885±0.07790.2885± 0.0779 Table 6: Effect of Cooperation Magnitude on individual path times among scenarios with more than one PNE. Cooperation Magnitude SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 2 1±01± 0 0.7368±0.02980.7368± 0.0298 0.8307±0.07460.8307± 0.0746 0.8375±0.05760.8375± 0.0576 0.8299±0.06390.8299± 0.0639 0.8357±0.05210.8357± 0.0521 0.8313±0.05940.8313± 0.0594 0.8344±0.05830.8344± 0.0583 0.8366±0.04970.8366± 0.0497 0.8301±0.06650.8301± 0.0665 4 1±01± 0 0.497±0.04560.497± 0.0456 0.592±0.08030.592± 0.0803 0.6044±0.08920.6044± 0.0892 0.5943±0.0860.5943± 0.086 0.5987±0.07540.5987± 0.0754 0.5941±0.07850.5941± 0.0785 0.6006±0.0780.6006± 0.078 0.6033±0.07120.6033± 0.0712 0.5942±0.08140.5942± 0.0814 6 1±01± 0 0.3774±0.05660.3774± 0.0566 0.4869±0.11550.4869± 0.1155 0.492±0.11740.492± 0.1174 0.4887±0.11690.4887± 0.1169 0.4924±0.11620.4924± 0.1162 0.489±0.1160.489± 0.116 0.494±0.1160.494± 0.116 0.4962±0.11360.4962± 0.1136 0.4888±0.11640.4888± 0.1164 8 1±01± 0 0.3197±0.06430.3197± 0.0643 0.4076±0.08260.4076± 0.0826 0.4169±0.08520.4169± 0.0852 0.412±0.08560.412± 0.0856 0.4172±0.07980.4172± 0.0798 0.4121±0.08380.4121± 0.0838 0.4186±0.07880.4186± 0.0788 0.4243±0.07930.4243± 0.0793 0.412±0.08560.412± 0.0856 10 1±01± 0 0.2776±0.0590.2776± 0.059 0.3682±0.08920.3682± 0.0892 0.3813±0.09680.3813± 0.0968 0.3728±0.09050.3728± 0.0905 0.3779±0.08720.3779± 0.0872 0.3728±0.09010.3728± 0.0901 0.3798±0.08760.3798± 0.0876 0.3819±0.08450.3819± 0.0845 0.373±0.09140.373± 0.0914 12 1±01± 0 0.2493±0.06380.2493± 0.0638 0.3608±0.11310.3608± 0.1131 0.3713±0.11470.3713± 0.1147 0.3667±0.11570.3667± 0.1157 0.3731±0.11230.3731± 0.1123 0.367±0.11340.367± 0.1134 0.3737±0.11060.3737± 0.1106 0.3767±0.110.3767± 0.11 0.3667±0.11560.3667± 0.1156 14 1±01± 0 0.2223±0.05550.2223± 0.0555 0.3156±0.09420.3156± 0.0942 0.3265±0.09520.3265± 0.0952 0.3213±0.09180.3213± 0.0918 0.3252±0.08810.3252± 0.0881 0.3214±0.0910.3214± 0.091 0.3271±0.08820.3271± 0.0882 0.3286±0.08660.3286± 0.0866 0.3213±0.09180.3213± 0.0918 16 1±01± 0 0.2094±0.06090.2094± 0.0609 0.3154±0.12530.3154± 0.1253 0.3274±0.12750.3274± 0.1275 0.3217±0.12830.3217± 0.1283 0.3279±0.12420.3279± 0.1242 0.3218±0.12640.3218± 0.1264 0.3286±0.12250.3286± 0.1225 0.3317±0.1220.3317± 0.122 0.3217±0.12830.3217± 0.1283 18 1±01± 0 0.178±0.05470.178± 0.0547 0.2625±0.06780.2625± 0.0678 0.2741±0.070.2741± 0.07 0.2704±0.07090.2704± 0.0709 0.2756±0.06780.2756± 0.0678 0.2703±0.06850.2703± 0.0685 0.277±0.06460.277± 0.0646 0.281±0.06610.281± 0.0661 0.2703±0.07060.2703± 0.0706 20 1±01± 0 0.1768±0.06280.1768± 0.0628 0.2692±0.09960.2692± 0.0996 0.2785±0.09720.2785± 0.0972 0.2767±0.09870.2767± 0.0987 0.2828±0.09750.2828± 0.0975 0.2767±0.0980.2767± 0.098 0.2819±0.0950.2819± 0.095 0.2869±0.09490.2869± 0.0949 0.2767±0.09870.2767± 0.0987 Table 7: Effect of Path Length on individual path times among scenarios with more than one PNE. Path Length SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 0-49 1±01± 0 0.2667±0.08140.2667± 0.0814 0.6116±0.15680.6116± 0.1568 0.6408±0.16060.6408± 0.1606 0.6267±0.16540.6267± 0.1654 0.642±0.13550.642± 0.1355 0.6328±0.13120.6328± 0.1312 0.6441±0.12330.6441± 0.1233 0.653±0.11740.653± 0.1174 0.6267±0.16540.6267± 0.1654 50-99 1±01± 0 0.2838±0.08340.2838± 0.0834 0.4968±0.13690.4968± 0.1369 0.5224±0.14290.5224± 0.1429 0.5086±0.13290.5086± 0.1329 0.517±0.11990.517± 0.1199 0.5091±0.1290.5091± 0.129 0.5218±0.11770.5218± 0.1177 0.5232±0.11430.5232± 0.1143 0.5106±0.13830.5106± 0.1383 100-149 1±01± 0 0.2831±0.07150.2831± 0.0715 0.4255±0.10590.4255± 0.1059 0.4439±0.1180.4439± 0.118 0.4346±0.1110.4346± 0.111 0.4419±0.10950.4419± 0.1095 0.4348±0.10780.4348± 0.1078 0.4452±0.1030.4452± 0.103 0.4478±0.10610.4478± 0.1061 0.4346±0.11050.4346± 0.1105 150-199 1±01± 0 0.2678±0.05590.2678± 0.0559 0.3709±0.08220.3709± 0.0822 0.385±0.08830.385± 0.0883 0.3786±0.08080.3786± 0.0808 0.3849±0.07850.3849± 0.0785 0.3785±0.07860.3785± 0.0786 0.386±0.07480.386± 0.0748 0.3867±0.07530.3867± 0.0753 0.3785±0.08110.3785± 0.0811 200-249 1±01± 0 0.2603±0.05590.2603± 0.0559 0.3515±0.09210.3515± 0.0921 0.3611±0.09660.3611± 0.0966 0.3568±0.09410.3568± 0.0941 0.3617±0.09090.3617± 0.0909 0.3568±0.09230.3568± 0.0923 0.3625±0.08970.3625± 0.0897 0.3658±0.08980.3658± 0.0898 0.3569±0.0940.3569± 0.094 250-299 1±01± 0 0.2635±0.05560.2635± 0.0556 0.34±0.09070.34± 0.0907 0.3488±0.09380.3488± 0.0938 0.3448±0.09220.3448± 0.0922 0.3485±0.08940.3485± 0.0894 0.3446±0.09070.3446± 0.0907 0.3494±0.08880.3494± 0.0888 0.3513±0.08840.3513± 0.0884 0.3445±0.09160.3445± 0.0916 300-349 1±01± 0 0.2594±0.05340.2594± 0.0534 0.3199±0.07060.3199± 0.0706 0.3267±0.07240.3267± 0.0724 0.3242±0.0730.3242± 0.073 0.3287±0.07160.3287± 0.0716 0.3242±0.07230.3242± 0.0723 0.3286±0.06940.3286± 0.0694 0.332±0.06970.332± 0.0697 0.3242±0.07290.3242± 0.0729 350-399 1±01± 0 0.2805±0.0570.2805± 0.057 0.3541±0.10280.3541± 0.1028 0.3616±0.10420.3616± 0.1042 0.3577±0.10330.3577± 0.1033 0.3617±0.10170.3617± 0.1017 0.3577±0.10260.3577± 0.1026 0.3617±0.10080.3617± 0.1008 0.3645±0.10.3645± 0.1 0.3577±0.10330.3577± 0.1033 400-449 1±01± 0 0.2956±0.04670.2956± 0.0467 0.398±0.13580.398± 0.1358 0.4078±0.14190.4078± 0.1419 0.4004±0.13560.4004± 0.1356 0.4035±0.13450.4035± 0.1345 0.4004±0.13540.4004± 0.1354 0.4044±0.13470.4044± 0.1347 0.4059±0.13310.4059± 0.1331 0.4004±0.13550.4004± 0.1355 450-499 1±01± 0 0.3072±0.04960.3072± 0.0496 0.3809±0.11730.3809± 0.1173 0.3893±0.11710.3893± 0.1171 0.3838±0.11660.3838± 0.1166 0.3881±0.11650.3881± 0.1165 0.3837±0.11730.3837± 0.1173 0.3876±0.11540.3876± 0.1154 0.3883±0.11610.3883± 0.1161 0.3838±0.11670.3838± 0.1167 500-549 1±01± 0 0.2991±0.04950.2991± 0.0495 0.3838±0.1260.3838± 0.126 0.3879±0.12590.3879± 0.1259 0.3863±0.12670.3863± 0.1267 0.3885±0.12540.3885± 0.1254 0.3862±0.12610.3862± 0.1261 0.3887±0.12630.3887± 0.1263 0.3916±0.12730.3916± 0.1273 0.3864±0.12680.3864± 0.1268 550-599 1±01± 0 0.2987±0.03760.2987± 0.0376 0.408±0.15170.408± 0.1517 0.4121±0.15310.4121± 0.1531 0.4093±0.14950.4093± 0.1495 0.4108±0.14970.4108± 0.1497 0.4092±0.14920.4092± 0.1492 0.4104±0.15020.4104± 0.1502 0.4106±0.15020.4106± 0.1502 0.4093±0.14940.4093± 0.1494 600-649 1±01± 0 0.2979±0.05270.2979± 0.0527 0.3748±0.12120.3748± 0.1212 0.3788±0.11960.3788± 0.1196 0.3764±0.1210.3764± 0.121 0.3778±0.12130.3778± 0.1213 0.3764±0.12060.3764± 0.1206 0.3772±0.12150.3772± 0.1215 0.3792±0.11930.3792± 0.1193 0.3764±0.12110.3764± 0.1211 650-699 1±01± 0 0.3099±0.02990.3099± 0.0299 0.4076±0.13150.4076± 0.1315 0.4126±0.13360.4126± 0.1336 0.41±0.13260.41± 0.1326 0.4114±0.13310.4114± 0.1331 0.41±0.13260.41± 0.1326 0.4119±0.13220.4119± 0.1322 0.4124±0.13270.4124± 0.1327 0.41±0.13260.41± 0.1326 700-749 1±01± 0 0.2934±0.03640.2934± 0.0364 0.3588±0.10910.3588± 0.1091 0.3622±0.10940.3622± 0.1094 0.3599±0.10930.3599± 0.1093 0.3618±0.10920.3618± 0.1092 0.3599±0.10920.3599± 0.1092 0.3617±0.10750.3617± 0.1075 0.3632±0.10760.3632± 0.1076 0.3599±0.10930.3599± 0.1093 750-799 1±01± 0 0.2987±0.03820.2987± 0.0382 0.3592±0.08250.3592± 0.0825 0.3611±0.08310.3611± 0.0831 0.3608±0.08330.3608± 0.0833 0.3646±0.08060.3646± 0.0806 0.3608±0.08330.3608± 0.0833 0.3616±0.08350.3616± 0.0835 0.3665±0.0870.3665± 0.087 0.3608±0.08330.3608± 0.0833 800-849 1±01± 0 0.2879±0.02520.2879± 0.0252 0.3076±0.02620.3076± 0.0262 0.311±0.02610.311± 0.0261 0.3105±0.02680.3105± 0.0268 0.3111±0.02740.3111± 0.0274 0.3105±0.02680.3105± 0.0268 0.3119±0.02530.3119± 0.0253 0.3123±0.02580.3123± 0.0258 0.3105±0.02680.3105± 0.0268 850-899 1±01± 0 0.3094±0.03120.3094± 0.0312 0.3392±0.03530.3392± 0.0353 0.3428±0.03570.3428± 0.0357 0.3412±0.03660.3412± 0.0366 0.3428±0.0350.3428± 0.035 0.3412±0.03660.3412± 0.0366 0.3426±0.03460.3426± 0.0346 0.3429±0.0350.3429± 0.035 0.3412±0.03660.3412± 0.0366 900-949 1±01± 0 0.2919±0.03480.2919± 0.0348 0.3665±0.14430.3665± 0.1443 0.3688±0.14330.3688± 0.1433 0.3674±0.14380.3674± 0.1438 0.3692±0.14360.3692± 0.1436 0.3675±0.14290.3675± 0.1429 0.3688±0.14290.3688± 0.1429 0.3692±0.14240.3692± 0.1424 0.3674±0.14380.3674± 0.1438 950-999 1±01± 0 0.3076±0.03790.3076± 0.0379 0.3406±0.04450.3406± 0.0445 0.3446±0.04320.3446± 0.0432 0.3418±0.04490.3418± 0.0449 0.3441±0.04330.3441± 0.0433 0.3418±0.04490.3418± 0.0449 0.343±0.04410.343± 0.0441 0.3443±0.04310.3443± 0.0431 0.3418±0.04490.3418± 0.0449 Table 8: Effect of SPD on individual path times among scenarios with more than one PNE. SPD SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 0-10 1±01± 0 0.2776±0.07180.2776± 0.0718 0.5997±0.1720.5997± 0.172 0.6421±0.19470.6421± 0.1947 0.6058±0.16860.6058± 0.1686 0.6047±0.15830.6047± 0.1583 0.6013±0.15710.6013± 0.1571 0.6094±0.15660.6094± 0.1566 0.6053±0.15530.6053± 0.1553 0.6056±0.16870.6056± 0.1687 11-20 1±01± 0 0.283±0.07340.283± 0.0734 0.6005±0.18050.6005± 0.1805 0.6304±0.190.6304± 0.19 0.6102±0.17980.6102± 0.1798 0.6157±0.16630.6157± 0.1663 0.6091±0.17190.6091± 0.1719 0.6168±0.16670.6168± 0.1667 0.6204±0.16380.6204± 0.1638 0.6088±0.17740.6088± 0.1774 21-30 1±01± 0 0.2791±0.07290.2791± 0.0729 0.6145±0.1760.6145± 0.176 0.6598±0.17550.6598± 0.1755 0.621±0.17410.621± 0.1741 0.639±0.14520.639± 0.1452 0.6215±0.15270.6215± 0.1527 0.6356±0.13960.6356± 0.1396 0.6472±0.13220.6472± 0.1322 0.621±0.17410.621± 0.1741 31-40 1±01± 0 0.2789±0.06370.2789± 0.0637 0.6402±0.21090.6402± 0.2109 0.6654±0.16510.6654± 0.1651 0.6428±0.17870.6428± 0.1787 0.6639±0.14890.6639± 0.1489 0.6463±0.15310.6463± 0.1531 0.6529±0.14980.6529± 0.1498 0.6665±0.14020.6665± 0.1402 0.6428±0.17870.6428± 0.1787 41-50 1±01± 0 0.2787±0.07720.2787± 0.0772 0.6567±0.19430.6567± 0.1943 0.6936±0.17090.6936± 0.1709 0.6673±0.20220.6673± 0.2022 0.6898±0.15890.6898± 0.1589 0.6764±0.16360.6764± 0.1636 0.6821±0.16290.6821± 0.1629 0.6919±0.15440.6919± 0.1544 0.6662±0.20170.6662± 0.2017 51-60 1±01± 0 0.2621±0.05290.2621± 0.0529 0.6726±0.17640.6726± 0.1764 0.7217±0.16410.7217± 0.1641 0.6855±0.16410.6855± 0.1641 0.7029±0.15330.7029± 0.1533 0.6892±0.14850.6892± 0.1485 0.6981±0.14660.6981± 0.1466 0.7001±0.14760.7001± 0.1476 0.6856±0.16560.6856± 0.1656 61-70 1±01± 0 0.2728±0.07280.2728± 0.0728 0.6895±0.16520.6895± 0.1652 0.7073±0.15630.7073± 0.1563 0.6894±0.15670.6894± 0.1567 0.7049±0.13640.7049± 0.1364 0.6934±0.13850.6934± 0.1385 0.6982±0.13930.6982± 0.1393 0.706±0.13570.706± 0.1357 0.6894±0.15670.6894± 0.1567 71-80 1±01± 0 0.2556±0.05120.2556± 0.0512 0.7736±0.24150.7736± 0.2415 0.7855±0.15120.7855± 0.1512 0.7623±0.16020.7623± 0.1602 0.7737±0.13530.7737± 0.1353 0.7629±0.14240.7629± 0.1424 0.7709±0.13260.7709± 0.1326 0.7729±0.13370.7729± 0.1337 0.7623±0.16020.7623± 0.1602 81-90 1±01± 0 0.2704±0.05130.2704± 0.0513 0.7823±0.29550.7823± 0.2955 0.7884±0.15930.7884± 0.1593 0.7823±0.16970.7823± 0.1697 0.7845±0.15360.7845± 0.1536 0.784±0.15280.784± 0.1528 0.7849±0.15360.7849± 0.1536 0.7845±0.15340.7845± 0.1534 0.7823±0.16970.7823± 0.1697 91-100 1±01± 0 0.3032±0.04430.3032± 0.0443 0.7772±0.25050.7772± 0.2505 0.7678±0.18760.7678± 0.1876 0.7549±0.18350.7549± 0.1835 0.7618±0.16890.7618± 0.1689 0.7602±0.17150.7602± 0.1715 0.7598±0.17410.7598± 0.1741 0.7618±0.16890.7618± 0.1689 0.7549±0.18350.7549± 0.1835 F.2.3 Social welfare in multiple-PNE scenarios a Table 9: Effects of Cooperation Density on social welfare among scenarios with more than one PNE. Cooperation Density Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 0.1 1±01± 0 1.0067±0.00671.0067± 0.0067 1.0067±0.00671.0067± 0.0067 1.0255±0.01211.0255± 0.0121 1.0067±0.00671.0067± 0.0067 1.0139±0.00111.0139± 0.0011 1.0255±0.01211.0255± 0.0121 1.0067±0.00671.0067± 0.0067 1.1384±0.04661.1384± 0.0466 1.03±0.00761.03± 0.0076 1.0067±0.00671.0067± 0.0067 0.2 1±01± 0 1.018±0.02111.018± 0.0211 1.0088±0.01361.0088± 0.0136 1.0192±0.02171.0192± 0.0217 1.0115±0.01361.0115± 0.0136 1.0181±0.01511.0181± 0.0151 1.0297±0.02441.0297± 0.0244 1.0088±0.01361.0088± 0.0136 1.2836±0.09981.2836± 0.0998 1.0489±0.03431.0489± 0.0343 1.0088±0.01361.0088± 0.0136 0.3 1±01± 0 1.0149±0.01711.0149± 0.0171 1.0118±0.0171.0118± 0.017 1.0202±0.02261.0202± 0.0226 1.0128±0.01781.0128± 0.0178 1.018±0.01721.018± 0.0172 1.021±0.02261.021± 0.0226 1.0118±0.0171.0118± 0.017 1.4857±0.17781.4857± 0.1778 1.0404±0.02581.0404± 0.0258 1.0118±0.0171.0118± 0.017 0.4 1±01± 0 1.0218±0.02571.0218± 0.0257 1.0135±0.01951.0135± 0.0195 1.037±0.04321.037± 0.0432 1.0169±0.02161.0169± 0.0216 1.0269±0.01871.0269± 0.0187 1.0466±0.0391.0466± 0.039 1.0135±0.01951.0135± 0.0195 1.7153±0.32581.7153± 0.3258 1.0706±0.04681.0706± 0.0468 1.0135±0.01951.0135± 0.0195 0.5 1±01± 0 1.0176±0.02971.0176± 0.0297 1.0079±0.01381.0079± 0.0138 1.0217±0.03041.0217± 0.0304 1.0093±0.01381.0093± 0.0138 1.0184±0.01431.0184± 0.0143 1.0316±0.03271.0316± 0.0327 1.0079±0.01381.0079± 0.0138 2.1641±0.42622.1641± 0.4262 1.0622±0.05181.0622± 0.0518 1.0079±0.01381.0079± 0.0138 0.6 1±01± 0 1.022±0.02811.022± 0.0281 1.0174±0.02221.0174± 0.0222 1.0335±0.03441.0335± 0.0344 1.0182±0.02341.0182± 0.0234 1.0332±0.02621.0332± 0.0262 1.0481±0.04771.0481± 0.0477 1.0174±0.02221.0174± 0.0222 2.5041±0.46612.5041± 0.4661 1.1249±0.10051.1249± 0.1005 1.0174±0.02221.0174± 0.0222 0.7 1±01± 0 1.027±0.0411.027± 0.041 1.016±0.01971.016± 0.0197 1.0288±0.03571.0288± 0.0357 1.0165±0.021.0165± 0.02 1.0348±0.02511.0348± 0.0251 1.0401±0.03581.0401± 0.0358 1.016±0.01971.016± 0.0197 2.7322±0.58062.7322± 0.5806 1.1124±0.08481.1124± 0.0848 1.016±0.01971.016± 0.0197 0.8 1±01± 0 1.0251±0.02761.0251± 0.0276 1.0187±0.01851.0187± 0.0185 1.034±0.03421.034± 0.0342 1.0192±0.01821.0192± 0.0182 1.035±0.02491.035± 0.0249 1.047±0.04271.047± 0.0427 1.0187±0.01851.0187± 0.0185 3.1876±0.60233.1876± 0.6023 1.1054±0.07621.1054± 0.0762 1.0187±0.01851.0187± 0.0185 0.9 1±01± 0 1.0176±0.02131.0176± 0.0213 1.0139±0.01641.0139± 0.0164 1.0259±0.02841.0259± 0.0284 1.0143±0.01621.0143± 0.0162 1.026±0.01931.026± 0.0193 1.0386±0.03711.0386± 0.0371 1.0139±0.01641.0139± 0.0164 3.4182±0.62333.4182± 0.6233 1.0997±0.08761.0997± 0.0876 1.0139±0.01641.0139± 0.0164 1.0 1±01± 0 1.0192±0.02721.0192± 0.0272 1.0138±0.01461.0138± 0.0146 1.028±0.02521.028± 0.0252 1.014±0.01451.014± 0.0145 1.0263±0.01941.0263± 0.0194 1.0388±0.03271.0388± 0.0327 1.0138±0.01461.0138± 0.0146 3.6318±0.62773.6318± 0.6277 1.0961±0.08771.0961± 0.0877 1.0138±0.01461.0138± 0.0146 Table 10: Effects of Magnitude on social welfare among scenarios with more than one PNE. Cooperation Magnitude Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 2 1±01± 0 1.0083±0.01241.0083± 0.0124 1±01± 0 1.0077±0.00951.0077± 0.0095 1.0017±0.00491.0017± 0.0049 1.0053±0.00451.0053± 0.0045 1.0087±0.00971.0087± 0.0097 1±01± 0 1.2081±0.05731.2081± 0.0573 1.0197±0.0161.0197± 0.016 1±01± 0 4 1±01± 0 1.0174±0.02811.0174± 0.0281 1.004±0.01661.004± 0.0166 1.0121±0.02581.0121± 0.0258 1.0041±0.01651.0041± 0.0165 1.0137±0.01651.0137± 0.0165 1.0202±0.02811.0202± 0.0281 1.004±0.01661.004± 0.0166 1.7107±0.18891.7107± 0.1889 1.0517±0.0381.0517± 0.038 1.004±0.01661.004± 0.0166 6 1±01± 0 1.0101±0.02491.0101± 0.0249 1.0052±0.00751.0052± 0.0075 1.0151±0.02371.0151± 0.0237 1.0061±0.00831.0061± 0.0083 1.0155±0.00751.0155± 0.0075 1.0235±0.02841.0235± 0.0284 1.0052±0.00751.0052± 0.0075 2.1341±0.38342.1341± 0.3834 1.0632±0.0561.0632± 0.056 1.0052±0.00751.0052± 0.0075 8 1±01± 0 1.0214±0.02551.0214± 0.0255 1.0116±0.01531.0116± 0.0153 1.0285±0.031.0285± 0.03 1.0127±0.01551.0127± 0.0155 1.0281±0.02031.0281± 0.0203 1.0464±0.04441.0464± 0.0444 1.0116±0.01531.0116± 0.0153 2.5248±0.38352.5248± 0.3835 1.0946±0.07341.0946± 0.0734 1.0116±0.01531.0116± 0.0153 10 1±01± 0 1.0306±0.04621.0306± 0.0462 1.016±0.021.016± 0.02 1.0316±0.04161.0316± 0.0416 1.0161±0.02011.0161± 0.0201 1.0321±0.02551.0321± 0.0255 1.0429±0.04481.0429± 0.0448 1.016±0.021.016± 0.02 2.8271±0.53812.8271± 0.5381 1.0987±0.07191.0987± 0.0719 1.016±0.021.016± 0.02 12 1±01± 0 1.0279±0.03571.0279± 0.0357 1.0186±0.02331.0186± 0.0233 1.0383±0.0391.0383± 0.039 1.0201±0.02331.0201± 0.0233 1.037±0.02781.037± 0.0278 1.0499±0.04491.0499± 0.0449 1.0186±0.02331.0186± 0.0233 2.963±0.68452.963± 0.6845 1.1007±0.07681.1007± 0.0768 1.0186±0.02331.0186± 0.0233 14 1±01± 0 1.0354±0.04871.0354± 0.0487 1.0229±0.03141.0229± 0.0314 1.0401±0.04391.0401± 0.0439 1.0233±0.03171.0233± 0.0317 1.0403±0.0341.0403± 0.034 1.0504±0.04921.0504± 0.0492 1.0229±0.03141.0229± 0.0314 3.3515±0.6883.3515± 0.688 1.1136±0.09311.1136± 0.0931 1.0229±0.03141.0229± 0.0314 16 1±01± 0 1.037±0.04681.037± 0.0468 1.0236±0.03081.0236± 0.0308 1.05±0.05691.05± 0.0569 1.0253±0.03251.0253± 0.0325 1.0466±0.03541.0466± 0.0354 1.0636±0.0611.0636± 0.061 1.0236±0.03081.0236± 0.0308 3.465±0.89143.465± 0.8914 1.1376±0.08111.1376± 0.0811 1.0236±0.03081.0236± 0.0308 18 1±01± 0 1.0448±0.05441.0448± 0.0544 1.0326±0.03911.0326± 0.0391 1.0594±0.0711.0594± 0.071 1.0337±0.03931.0337± 0.0393 1.0565±0.04441.0565± 0.0444 1.0778±0.0641.0778± 0.064 1.0326±0.03911.0326± 0.0391 3.9817±0.77693.9817± 0.7769 1.1578±0.10411.1578± 0.1041 1.0326±0.03911.0326± 0.0391 20 1±01± 0 1.0386±0.05881.0386± 0.0588 1.0314±0.051.0314± 0.05 1.058±0.0791.058± 0.079 1.032±0.05021.032± 0.0502 1.0505±0.05731.0505± 0.0573 1.0744±0.08961.0744± 0.0896 1.0314±0.051.0314± 0.05 4.0337±1.03214.0337± 1.0321 1.154±0.12271.154± 0.1227 1.0314±0.051.0314± 0.05 Table 11: Effects of Path Length on social welfare among scenarios with more than one PNE. Path Length Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 0-49 1±01± 0 1.0506±0.0841.0506± 0.084 1.0312±0.04081.0312± 0.0408 1.0847±0.0831.0847± 0.083 1.0655±0.06271.0655± 0.0627 1.0757±0.05051.0757± 0.0505 1.1043±0.07421.1043± 0.0742 1.0312±0.04081.0312± 0.0408 1.737±0.27081.737± 0.2708 1.1497±0.0821.1497± 0.082 1.0312±0.04081.0312± 0.0408 50-99 1±01± 0 1.0508±0.04271.0508± 0.0427 1.034±0.02931.034± 0.0293 1.0672±0.07821.0672± 0.0782 1.0363±0.03131.0363± 0.0313 1.063±0.04661.063± 0.0466 1.081±0.0821.081± 0.082 1.034±0.02931.034± 0.0293 2.106±0.38862.106± 0.3886 1.1827±0.12061.1827± 0.1206 1.034±0.02931.034± 0.0293 100-149 1±01± 0 1.0383±0.04981.0383± 0.0498 1.0231±0.0271.0231± 0.027 1.046±0.04261.046± 0.0426 1.025±0.02681.025± 0.0268 1.047±0.03021.047± 0.0302 1.0605±0.05221.0605± 0.0522 1.0231±0.0271.0231± 0.027 2.4494±0.44042.4494± 0.4404 1.1318±0.07791.1318± 0.0779 1.0231±0.0271.0231± 0.027 150-199 1±01± 0 1.0347±0.04131.0347± 0.0413 1.0237±0.02341.0237± 0.0234 1.0457±0.04461.0457± 0.0446 1.0245±0.0241.0245± 0.024 1.0425±0.02691.0425± 0.0269 1.0511±0.04611.0511± 0.0461 1.0237±0.02341.0237± 0.0234 2.7851±0.47832.7851± 0.4783 1.1291±0.0891.1291± 0.089 1.0237±0.02341.0237± 0.0234 200-249 1±01± 0 1.0263±0.03481.0263± 0.0348 1.0171±0.02041.0171± 0.0204 1.0347±0.04121.0347± 0.0412 1.0178±0.0211.0178± 0.021 1.0333±0.02451.0333± 0.0245 1.0466±0.04821.0466± 0.0482 1.0171±0.02041.0171± 0.0204 2.9738±0.55772.9738± 0.5577 1.1076±0.08421.1076± 0.0842 1.0171±0.02041.0171± 0.0204 250-299 1±01± 0 1.0243±0.02921.0243± 0.0292 1.0154±0.01861.0154± 0.0186 1.0296±0.03351.0296± 0.0335 1.0157±0.01881.0157± 0.0188 1.0291±0.02061.0291± 0.0206 1.0376±0.03611.0376± 0.0361 1.0154±0.01861.0154± 0.0186 3.0781±0.58583.0781± 0.5858 1.0951±0.07541.0951± 0.0754 1.0154±0.01861.0154± 0.0186 300-349 1±01± 0 1.021±0.0241.021± 0.024 1.0141±0.01571.0141± 0.0157 1.0296±0.03371.0296± 0.0337 1.0141±0.01571.0141± 0.0157 1.028±0.01831.028± 0.0183 1.0404±0.03731.0404± 0.0373 1.0141±0.01571.0141± 0.0157 3.2411±0.57213.2411± 0.5721 1.0858±0.05881.0858± 0.0588 1.0141±0.01571.0141± 0.0157 350-399 1±01± 0 1.0205±0.02561.0205± 0.0256 1.0116±0.01461.0116± 0.0146 1.0248±0.03061.0248± 0.0306 1.0119±0.01461.0119± 0.0146 1.023±0.01651.023± 0.0165 1.0331±0.03411.0331± 0.0341 1.0116±0.01461.0116± 0.0146 2.9915±0.6562.9915± 0.656 1.0716±0.05451.0716± 0.0545 1.0116±0.01461.0116± 0.0146 400-449 1±01± 0 1.0165±0.02741.0165± 0.0274 1.0064±0.00941.0064± 0.0094 1.0161±0.0221.0161± 0.022 1.0065±0.00941.0065± 0.0094 1.0154±0.0131.0154± 0.013 1.0227±0.02531.0227± 0.0253 1.0064±0.00941.0064± 0.0094 2.7004±0.66512.7004± 0.6651 1.0518±0.04121.0518± 0.0412 1.0064±0.00941.0064± 0.0094 450-499 1±01± 0 1.0205±0.0321.0205± 0.032 1.0086±0.00861.0086± 0.0086 1.0209±0.02221.0209± 0.0222 1.0087±0.00851.0087± 0.0085 1.0182±0.01391.0182± 0.0139 1.0216±0.02391.0216± 0.0239 1.0086±0.00861.0086± 0.0086 2.7869±0.59832.7869± 0.5983 1.0691±0.10131.0691± 0.1013 1.0086±0.00861.0086± 0.0086 500-549 1±01± 0 1.0116±0.01281.0116± 0.0128 1.0069±0.00751.0069± 0.0075 1.0146±0.01621.0146± 0.0162 1.007±0.00751.007± 0.0075 1.014±0.00911.014± 0.0091 1.0229±0.02441.0229± 0.0244 1.0069±0.00751.0069± 0.0075 2.802±0.68582.802± 0.6858 1.042±0.04191.042± 0.0419 1.0069±0.00751.0069± 0.0075 550-599 1±01± 0 1.0096±0.01191.0096± 0.0119 1.0048±0.00641.0048± 0.0064 1.01±0.01041.01± 0.0104 1.005±0.00631.005± 0.0063 1.0093±0.00741.0093± 0.0074 1.0101±0.00811.0101± 0.0081 1.0048±0.00641.0048± 0.0064 2.6832±0.72872.6832± 0.7287 1.0308±0.03771.0308± 0.0377 1.0048±0.00641.0048± 0.0064 600-649 1±01± 0 1.0107±0.01391.0107± 0.0139 1.0048±0.0061.0048± 0.006 1.0093±0.00741.0093± 0.0074 1.0051±0.0061.0051± 0.006 1.009±0.00781.009± 0.0078 1.0148±0.01771.0148± 0.0177 1.0048±0.0061.0048± 0.006 2.8434±0.6812.8434± 0.681 1.0272±0.0231.0272± 0.023 1.0048±0.0061.0048± 0.006 650-699 1±01± 0 1.0095±0.01011.0095± 0.0101 1.0054±0.00541.0054± 0.0054 1.0089±0.0091.0089± 0.009 1.0054±0.00541.0054± 0.0054 1.01±0.00561.01± 0.0056 1.0119±0.01011.0119± 0.0101 1.0054±0.00541.0054± 0.0054 2.6382±0.6362.6382± 0.636 1.0276±0.01871.0276± 0.0187 1.0054±0.00541.0054± 0.0054 700-749 1±01± 0 1.0076±0.01251.0076± 0.0125 1.0031±0.00371.0031± 0.0037 1.0088±0.00831.0088± 0.0083 1.0031±0.00371.0031± 0.0037 1.0076±0.00431.0076± 0.0043 1.0124±0.01231.0124± 0.0123 1.0031±0.00371.0031± 0.0037 2.9807±0.71182.9807± 0.7118 1.0295±0.0251.0295± 0.025 1.0031±0.00371.0031± 0.0037 750-799 1±01± 0 1.006±0.00561.006± 0.0056 1.0051±0.00421.0051± 0.0042 1.0194±0.0251.0194± 0.025 1.0051±0.00421.0051± 0.0042 1.008±0.00531.008± 0.0053 1.0237±0.0271.0237± 0.027 1.0051±0.00421.0051± 0.0042 2.9115±0.6022.9115± 0.602 1.0347±0.04141.0347± 0.0414 1.0051±0.00421.0051± 0.0042 800-849 1±01± 0 1.0115±0.00941.0115± 0.0094 1.0097±0.00791.0097± 0.0079 1.0118±0.00691.0118± 0.0069 1.0097±0.00791.0097± 0.0079 1.0147±0.00961.0147± 0.0096 1.0161±0.00861.0161± 0.0086 1.0097±0.00791.0097± 0.0079 3.2712±0.24833.2712± 0.2483 1.0312±0.01931.0312± 0.0193 1.0097±0.00791.0097± 0.0079 850-899 1±01± 0 1.0106±0.00711.0106± 0.0071 1.0058±0.00451.0058± 0.0045 1.0112±0.00911.0112± 0.0091 1.0058±0.00451.0058± 0.0045 1.0106±0.00581.0106± 0.0058 1.0113±0.0091.0113± 0.009 1.0058±0.00451.0058± 0.0045 2.9825±0.32662.9825± 0.3266 1.0252±0.01841.0252± 0.0184 1.0058±0.00451.0058± 0.0045 900-949 1±01± 0 1.0072±0.01021.0072± 0.0102 1.0032±0.00441.0032± 0.0044 1.0081±0.0081.0081± 0.008 1.0038±0.00441.0038± 0.0044 1.008±0.0051.008± 0.005 1.0092±0.00591.0092± 0.0059 1.0032±0.00441.0032± 0.0044 2.9892±0.72282.9892± 0.7228 1.0304±0.03181.0304± 0.0318 1.0032±0.00441.0032± 0.0044 950-999 1±01± 0 1.0112±0.00811.0112± 0.0081 1.0035±0.00381.0035± 0.0038 1.0101±0.00731.0101± 0.0073 1.0035±0.00381.0035± 0.0038 1.0072±0.00431.0072± 0.0043 1.0108±0.00811.0108± 0.0081 1.0035±0.00381.0035± 0.0038 2.9733±0.36122.9733± 0.3612 1.018±0.00651.018± 0.0065 1.0035±0.00381.0035± 0.0038 Table 12: Effects of SPD on social welfare among scenarios with more than one PNE. SPD Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 0-10 1±01± 0 1.0471±0.05991.0471± 0.0599 1.0175±0.02291.0175± 0.0229 1.0337±0.03421.0337± 0.0342 1.0245±0.02591.0245± 0.0259 1.0289±0.0271.0289± 0.027 1.035±0.03621.035± 0.0362 1.0175±0.02291.0175± 0.0229 1.8324±0.55661.8324± 0.5566 1.0825±0.07791.0825± 0.0779 1.0175±0.02291.0175± 0.0229 11-20 1±01± 0 1.0376±0.05361.0376± 0.0536 1.0177±0.031.0177± 0.03 1.0446±0.05811.0446± 0.0581 1.0233±0.03211.0233± 0.0321 1.0353±0.03491.0353± 0.0349 1.0527±0.05981.0527± 0.0598 1.0177±0.031.0177± 0.03 1.8333±0.59781.8333± 0.5978 1.0887±0.06911.0887± 0.0691 1.0177±0.031.0177± 0.03 21-30 1±01± 0 1.0578±0.06651.0578± 0.0665 1.0154±0.02491.0154± 0.0249 1.0562±0.07361.0562± 0.0736 1.0232±0.02731.0232± 0.0273 1.0421±0.03981.0421± 0.0398 1.0696±0.08231.0696± 0.0823 1.0154±0.02491.0154± 0.0249 1.7211±0.43851.7211± 0.4385 1.1253±0.09881.1253± 0.0988 1.0154±0.02491.0154± 0.0249 31-40 1±01± 0 1.0511±0.07021.0511± 0.0702 1.019±0.02631.019± 0.0263 1.0672±0.07891.0672± 0.0789 1.0337±0.03261.0337± 0.0326 1.0431±0.03521.0431± 0.0352 1.0747±0.09271.0747± 0.0927 1.019±0.02631.019± 0.0263 1.6647±0.34391.6647± 0.3439 1.1221±0.1181.1221± 0.118 1.019±0.02631.019± 0.0263 41-50 1±01± 0 1.0525±0.0671.0525± 0.067 1.0161±0.02471.0161± 0.0247 1.0626±0.07261.0626± 0.0726 1.0394±0.05081.0394± 0.0508 1.0452±0.04191.0452± 0.0419 1.0646±0.07041.0646± 0.0704 1.0161±0.02471.0161± 0.0247 1.6027±0.40421.6027± 0.4042 1.1063±0.08391.1063± 0.0839 1.0161±0.02471.0161± 0.0247 51-60 1±01± 0 1.0564±0.06831.0564± 0.0683 1.0273±0.04851.0273± 0.0485 1.0555±0.06761.0555± 0.0676 1.0365±0.04891.0365± 0.0489 1.0416±0.04881.0416± 0.0488 1.0515±0.05731.0515± 0.0573 1.0273±0.04851.0273± 0.0485 1.5379±0.29651.5379± 0.2965 1.0849±0.06721.0849± 0.0672 1.0273±0.04851.0273± 0.0485 61-70 1±01± 0 1.0222±0.0291.0222± 0.029 1.0074±0.01881.0074± 0.0188 1.0466±0.05411.0466± 0.0541 1.0189±0.02751.0189± 0.0275 1.0245±0.02391.0245± 0.0239 1.0474±0.05311.0474± 0.0531 1.0074±0.01881.0074± 0.0188 1.5202±0.28241.5202± 0.2824 1.0717±0.04781.0717± 0.0478 1.0074±0.01881.0074± 0.0188 71-80 1±01± 0 1.0392±0.061.0392± 0.06 1.015±0.02831.015± 0.0283 1.0571±0.06441.0571± 0.0644 1.0356±0.03811.0356± 0.0381 1.0426±0.03311.0426± 0.0331 1.0585±0.06311.0585± 0.0631 1.015±0.02831.015± 0.0283 1.3992±0.25841.3992± 0.2584 1.1006±0.06061.1006± 0.0606 1.015±0.02831.015± 0.0283 81-90 1±01± 0 1.0251±0.02571.0251± 0.0257 1.0221±0.02681.0221± 0.0268 1.0433±0.03831.0433± 0.0383 1.0358±0.03261.0358± 0.0326 1.0345±0.03051.0345± 0.0305 1.043±0.03781.043± 0.0378 1.0221±0.02681.0221± 0.0268 1.343±0.26031.343± 0.2603 1.0449±0.03751.0449± 0.0375 1.0221±0.02681.0221± 0.0268 91-100 1±01± 0 1.0111±0.01351.0111± 0.0135 1.0041±0.00571.0041± 0.0057 1.0189±0.00541.0189± 0.0054 1.0148±0.00911.0148± 0.0091 1.013±0.00511.013± 0.0051 1.0189±0.00541.0189± 0.0054 1.0041±0.00571.0041± 0.0057 1.431±0.34991.431± 0.3499 1.0233±0.00811.0233± 0.0081 1.0041±0.00571.0041± 0.0057 F.2.4 Individual path times in all scenarios a Table 13: Effects of Cooperation Density on individual path times across all tested scenarios, including those with a single PNE. Cooperation Density SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 0.1 1±01± 0 0.8463±0.0710.8463± 0.071 0.9044±0.07680.9044± 0.0768 0.9091±0.07660.9091± 0.0766 0.9091±0.07660.9091± 0.0766 0.9094±0.07610.9094± 0.0761 0.9091±0.07660.9091± 0.0766 0.9092±0.07640.9092± 0.0764 0.9094±0.07610.9094± 0.0761 0.9091±0.07660.9091± 0.0766 0.2 1±01± 0 0.7247±0.08420.7247± 0.0842 0.8097±0.11150.8097± 0.1115 0.817±0.11030.817± 0.1103 0.8154±0.10990.8154± 0.1099 0.8168±0.10860.8168± 0.1086 0.8157±0.10940.8157± 0.1094 0.8168±0.10870.8168± 0.1087 0.8183±0.10770.8183± 0.1077 0.8154±0.10990.8154± 0.1099 0.3 1±01± 0 0.6179±0.08740.6179± 0.0874 0.7045±0.12310.7045± 0.1231 0.711±0.1180.711± 0.118 0.7103±0.11850.7103± 0.1185 0.7114±0.11790.7114± 0.1179 0.7103±0.11780.7103± 0.1178 0.7113±0.11730.7113± 0.1173 0.7116±0.11730.7116± 0.1173 0.7102±0.11830.7102± 0.1183 0.4 1±01± 0 0.516±0.08330.516± 0.0833 0.6007±0.11430.6007± 0.1143 0.6076±0.11580.6076± 0.1158 0.6057±0.11510.6057± 0.1151 0.6094±0.11030.6094± 0.1103 0.6062±0.11250.6062± 0.1125 0.608±0.11090.608± 0.1109 0.6111±0.10880.6111± 0.1088 0.6057±0.1150.6057± 0.115 0.5 1±01± 0 0.4283±0.09550.4283± 0.0955 0.5188±0.15250.5188± 0.1525 0.5273±0.14840.5273± 0.1484 0.5253±0.14940.5253± 0.1494 0.5276±0.14750.5276± 0.1475 0.5254±0.14790.5254± 0.1479 0.527±0.14740.527± 0.1474 0.5292±0.1470.5292± 0.147 0.5252±0.14930.5252± 0.1493 0.6 1±01± 0 0.3518±0.08750.3518± 0.0875 0.459±0.14980.459± 0.1498 0.4667±0.14960.4667± 0.1496 0.4657±0.14970.4657± 0.1497 0.4678±0.14790.4678± 0.1479 0.4657±0.1490.4657± 0.149 0.4685±0.14760.4685± 0.1476 0.4704±0.14670.4704± 0.1467 0.4656±0.14960.4656± 0.1496 0.7 1±01± 0 0.303±0.06370.303± 0.0637 0.4194±0.14050.4194± 0.1405 0.4273±0.14130.4273± 0.1413 0.4242±0.1410.4242± 0.141 0.4267±0.14140.4267± 0.1414 0.4243±0.14050.4243± 0.1405 0.4283±0.13810.4283± 0.1381 0.4288±0.13890.4288± 0.1389 0.4242±0.14110.4242± 0.1411 0.8 1±01± 0 0.2372±0.04060.2372± 0.0406 0.3383±0.10890.3383± 0.1089 0.3468±0.11480.3468± 0.1148 0.3446±0.11430.3446± 0.1143 0.3477±0.11350.3477± 0.1135 0.3445±0.11360.3445± 0.1136 0.3491±0.1120.3491± 0.112 0.351±0.11270.351± 0.1127 0.3449±0.11490.3449± 0.1149 0.9 1±01± 0 0.2073±0.02430.2073± 0.0243 0.3352±0.16690.3352± 0.1669 0.3421±0.16920.3421± 0.1692 0.3408±0.16970.3408± 0.1697 0.3427±0.1680.3427± 0.168 0.3406±0.16860.3406± 0.1686 0.3436±0.16740.3436± 0.1674 0.3453±0.16650.3453± 0.1665 0.3408±0.16960.3408± 0.1696 1.0 1±01± 0 0.187±0.00270.187± 0.0027 0.3047±0.13160.3047± 0.1316 0.3128±0.14070.3128± 0.1407 0.3096±0.13750.3096± 0.1375 0.3121±0.13690.3121± 0.1369 0.3096±0.13710.3096± 0.1371 0.3132±0.13530.3132± 0.1353 0.3146±0.13580.3146± 0.1358 0.3096±0.13750.3096± 0.1375 Table 14: Effects of Cooperation Magnitude on individual path times across all tested scenarios, including those with a single PNE. Cooperation Magnitude SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 2 1±01± 0 0.724±0.03040.724± 0.0304 0.8019±0.0750.8019± 0.075 0.805±0.07480.805± 0.0748 0.8037±0.07510.8037± 0.0751 0.8047±0.07390.8047± 0.0739 0.804±0.07460.804± 0.0746 0.8045±0.07460.8045± 0.0746 0.8049±0.07370.8049± 0.0737 0.8038±0.07550.8038± 0.0755 4 1±01± 0 0.496±0.04970.496± 0.0497 0.6±0.1130.6± 0.113 0.6068±0.11860.6068± 0.1186 0.6032±0.11790.6032± 0.1179 0.6048±0.11510.6048± 0.1151 0.6031±0.1160.6031± 0.116 0.6055±0.11570.6055± 0.1157 0.6065±0.11410.6065± 0.1141 0.6032±0.11670.6032± 0.1167 6 1±01± 0 0.3897±0.05630.3897± 0.0563 0.4996±0.12180.4996± 0.1218 0.5037±0.1220.5037± 0.122 0.5021±0.1220.5021± 0.122 0.5039±0.12150.5039± 0.1215 0.5023±0.12160.5023± 0.1216 0.5046±0.12130.5046± 0.1213 0.5056±0.12010.5056± 0.1201 0.5022±0.12170.5022± 0.1217 8 1±01± 0 0.3284±0.06250.3284± 0.0625 0.4355±0.14490.4355± 0.1449 0.4418±0.13940.4418± 0.1394 0.4391±0.14010.4391± 0.1401 0.442±0.13760.442± 0.1376 0.4391±0.13950.4391± 0.1395 0.4428±0.13720.4428± 0.1372 0.446±0.13680.446± 0.1368 0.4391±0.14010.4391± 0.1401 10 1±01± 0 0.2866±0.06160.2866± 0.0616 0.4074±0.16950.4074± 0.1695 0.4193±0.17180.4193± 0.1718 0.4141±0.17090.4141± 0.1709 0.4172±0.16910.4172± 0.1691 0.4141±0.17070.4141± 0.1707 0.4184±0.16890.4184± 0.1689 0.4197±0.16770.4197± 0.1677 0.4143±0.17110.4143± 0.1711 12 1±01± 0 0.2558±0.0640.2558± 0.064 0.3695±0.12840.3695± 0.1284 0.3774±0.12950.3774± 0.1295 0.3744±0.13020.3744± 0.1302 0.3786±0.12810.3786± 0.1281 0.3746±0.12890.3746± 0.1289 0.3789±0.12710.3789± 0.1271 0.3809±0.12670.3809± 0.1267 0.3744±0.13020.3744± 0.1302 14 1±01± 0 0.2297±0.05920.2297± 0.0592 0.3357±0.12410.3357± 0.1241 0.3456±0.12850.3456± 0.1285 0.3426±0.12750.3426± 0.1275 0.3448±0.12560.3448± 0.1256 0.3426±0.12720.3426± 0.1272 0.3459±0.12550.3459± 0.1255 0.3468±0.12470.3468± 0.1247 0.3425±0.12750.3425± 0.1275 16 1±01± 0 0.2188±0.06640.2188± 0.0664 0.3377±0.15460.3377± 0.1546 0.3502±0.16350.3502± 0.1635 0.3465±0.16440.3465± 0.1644 0.3505±0.16180.3505± 0.1618 0.3466±0.16340.3466± 0.1634 0.351±0.16090.351± 0.1609 0.353±0.16030.353± 0.1603 0.3465±0.16440.3465± 0.1644 18 1±01± 0 0.1966±0.06920.1966± 0.0692 0.2979±0.13320.2979± 0.1332 0.3079±0.13290.3079± 0.1329 0.3054±0.13380.3054± 0.1338 0.3089±0.13180.3089± 0.1318 0.3053±0.1330.3053± 0.133 0.3098±0.13050.3098± 0.1305 0.3124±0.13040.3124± 0.1304 0.3053±0.13370.3053± 0.1337 20 1±01± 0 0.1986±0.0660.1986± 0.066 0.299±0.12990.299± 0.1299 0.3062±0.12790.3062± 0.1279 0.305±0.12880.305± 0.1288 0.3088±0.12750.3088± 0.1275 0.305±0.12850.305± 0.1285 0.3082±0.12640.3082± 0.1264 0.3114±0.12570.3114± 0.1257 0.305±0.12880.305± 0.1288 Table 15: Effects of Path Length on individual path times across all tested scenarios, including those with a single PNE. Path Length SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 0-49 1±01± 0 0.3391±0.17140.3391± 0.1714 1.0258±2.02331.0258± 2.0233 0.7957±0.20670.7957± 0.2067 0.7925±0.21010.7925± 0.2101 0.796±0.20230.796± 0.2023 0.7939±0.20330.7939± 0.2033 0.7965±0.20010.7965± 0.2001 0.7986±0.19770.7986± 0.1977 0.7925±0.21010.7925± 0.2101 50-99 1±01± 0 0.3133±0.09380.3133± 0.0938 0.5839±0.21850.5839± 0.2185 0.6068±0.21210.6068± 0.2121 0.6027±0.21190.6027± 0.2119 0.6052±0.20850.6052± 0.2085 0.6028±0.21110.6028± 0.2111 0.6066±0.20750.6066± 0.2075 0.6071±0.20680.6071± 0.2068 0.6033±0.21270.6033± 0.2127 100-149 1±01± 0 0.2921±0.0750.2921± 0.075 0.4545±0.15070.4545± 0.1507 0.4692±0.15650.4692± 0.1565 0.4632±0.15420.4632± 0.1542 0.4679±0.15270.4679± 0.1527 0.4633±0.15270.4633± 0.1527 0.4701±0.14940.4701± 0.1494 0.4718±0.15050.4718± 0.1505 0.4632±0.1540.4632± 0.154 150-199 1±01± 0 0.2783±0.05840.2783± 0.0584 0.3962±0.12440.3962± 0.1244 0.4061±0.12560.4061± 0.1256 0.4025±0.12340.4025± 0.1234 0.4061±0.12190.4061± 0.1219 0.4024±0.12260.4024± 0.1226 0.4067±0.12040.4067± 0.1204 0.4071±0.12050.4071± 0.1205 0.4025±0.12350.4025± 0.1235 200-249 1±01± 0 0.2698±0.06130.2698± 0.0613 0.3699±0.1320.3699± 0.132 0.3792±0.13220.3792± 0.1322 0.3764±0.13150.3764± 0.1315 0.3796±0.12960.3796± 0.1296 0.3764±0.13060.3764± 0.1306 0.3801±0.1290.3801± 0.129 0.3822±0.12880.3822± 0.1288 0.3765±0.13140.3765± 0.1314 250-299 1±01± 0 0.2717±0.05950.2717± 0.0595 0.3605±0.12560.3605± 0.1256 0.369±0.12920.369± 0.1292 0.3664±0.12890.3664± 0.1289 0.3688±0.12710.3688± 0.1271 0.3662±0.12820.3662± 0.1282 0.3695±0.12670.3695± 0.1267 0.3708±0.12630.3708± 0.1263 0.3661±0.12860.3661± 0.1286 300-349 1±01± 0 0.2676±0.05630.2676± 0.0563 0.3387±0.11460.3387± 0.1146 0.3444±0.10980.3444± 0.1098 0.3427±0.11040.3427± 0.1104 0.3458±0.10930.3458± 0.1093 0.3427±0.11010.3427± 0.1101 0.3457±0.10840.3457± 0.1084 0.348±0.10810.348± 0.1081 0.3427±0.11030.3427± 0.1103 350-399 1±01± 0 0.2919±0.05850.2919± 0.0585 0.3751±0.13230.3751± 0.1323 0.3807±0.13270.3807± 0.1327 0.3785±0.13260.3785± 0.1326 0.3808±0.13160.3808± 0.1316 0.3785±0.13230.3785± 0.1323 0.3807±0.13110.3807± 0.1311 0.3823±0.13060.3823± 0.1306 0.3785±0.13260.3785± 0.1326 400-449 1±01± 0 0.3069±0.05030.3069± 0.0503 0.4269±0.20530.4269± 0.2053 0.4304±0.18470.4304± 0.1847 0.4272±0.18310.4272± 0.1831 0.4286±0.18260.4286± 0.1826 0.4272±0.18310.4272± 0.1831 0.4289±0.18260.4289± 0.1826 0.4296±0.18210.4296± 0.1821 0.4272±0.18310.4272± 0.1831 450-499 1±01± 0 0.3159±0.05460.3159± 0.0546 0.4307±0.17960.4307± 0.1796 0.4382±0.18480.4382± 0.1848 0.4363±0.18520.4363± 0.1852 0.4378±0.18480.4378± 0.1848 0.4362±0.18540.4362± 0.1854 0.4376±0.18460.4376± 0.1846 0.4378±0.18470.4378± 0.1847 0.4363±0.18530.4363± 0.1853 500-549 1±01± 0 0.3047±0.04780.3047± 0.0478 0.412±0.22960.412± 0.2296 0.4087±0.16790.4087± 0.1679 0.4082±0.16820.4082± 0.1682 0.4089±0.16780.4089± 0.1678 0.4082±0.16810.4082± 0.1681 0.409±0.1680.409± 0.168 0.41±0.16810.41± 0.1681 0.4082±0.16820.4082± 0.1682 550-599 1±01± 0 0.3094±0.04340.3094± 0.0434 0.4242±0.16550.4242± 0.1655 0.43±0.17130.43± 0.1713 0.429±0.17020.429± 0.1702 0.4296±0.17030.4296± 0.1703 0.4289±0.17020.4289± 0.1702 0.4294±0.17040.4294± 0.1704 0.4295±0.17040.4295± 0.1704 0.429±0.17020.429± 0.1702 600-649 1±01± 0 0.3055±0.04980.3055± 0.0498 0.3959±0.14180.3959± 0.1418 0.3997±0.1430.3997± 0.143 0.3986±0.14370.3986± 0.1437 0.3993±0.14370.3993± 0.1437 0.3987±0.14350.3987± 0.1435 0.399±0.14380.399± 0.1438 0.3999±0.14280.3999± 0.1428 0.3986±0.14370.3986± 0.1437 650-699 1±01± 0 0.3115±0.04350.3115± 0.0435 0.4055±0.14360.4055± 0.1436 0.4138±0.15140.4138± 0.1514 0.4128±0.15110.4128± 0.1511 0.4133±0.15120.4133± 0.1512 0.4128±0.15110.4128± 0.1511 0.4135±0.15090.4135± 0.1509 0.4137±0.15110.4137± 0.1511 0.4128±0.15110.4128± 0.1511 700-749 1±01± 0 0.2998±0.03570.2998± 0.0357 0.372±0.11940.372± 0.1194 0.3744±0.12020.3744± 0.1202 0.3736±0.12030.3736± 0.1203 0.3743±0.12020.3743± 0.1202 0.3736±0.12030.3736± 0.1203 0.3742±0.11970.3742± 0.1197 0.3748±0.11970.3748± 0.1197 0.3736±0.12030.3736± 0.1203 750-799 1±01± 0 0.3159±0.03990.3159± 0.0399 0.383±0.09970.383± 0.0997 0.3847±0.10130.3847± 0.1013 0.3845±0.10140.3845± 0.1014 0.3866±0.09980.3866± 0.0998 0.3845±0.10140.3845± 0.1014 0.385±0.10140.385± 0.1014 0.3877±0.10240.3877± 0.1024 0.3845±0.10140.3845± 0.1014 800-849 1±01± 0 0.3194±0.0380.3194± 0.038 0.347±0.05110.347± 0.0511 0.3492±0.0510.3492± 0.051 0.349±0.05120.349± 0.0512 0.3492±0.05120.3492± 0.0512 0.349±0.05120.349± 0.0512 0.3495±0.05060.3495± 0.0506 0.3496±0.05060.3496± 0.0506 0.349±0.05120.349± 0.0512 850-899 1±01± 0 0.3194±0.02940.3194± 0.0294 0.3644±0.05940.3644± 0.0594 0.3665±0.06020.3665± 0.0602 0.366±0.06060.366± 0.0606 0.3665±0.06010.3665± 0.0601 0.366±0.06060.366± 0.0606 0.3665±0.06010.3665± 0.0601 0.3666±0.06010.3666± 0.0601 0.366±0.06060.366± 0.0606 900-949 1±01± 0 0.3051±0.03580.3051± 0.0358 0.3759±0.16050.3759± 0.1605 0.3775±0.160.3775± 0.16 0.3769±0.16030.3769± 0.1603 0.3777±0.16010.3777± 0.1601 0.377±0.15990.377± 0.1599 0.3776±0.15980.3776± 0.1598 0.3777±0.15960.3777± 0.1596 0.3769±0.16030.3769± 0.1603 950-999 1±01± 0 0.3245±0.03710.3245± 0.0371 0.3622±0.06380.3622± 0.0638 0.3644±0.0630.3644± 0.063 0.3634±0.06370.3634± 0.0637 0.3642±0.06310.3642± 0.0631 0.3634±0.06370.3634± 0.0637 0.3639±0.06340.3639± 0.0634 0.3643±0.0630.3643± 0.063 0.3634±0.06370.3634± 0.0637 Table 16: Effects of Cooperation SPD on individual path times across all tested scenarios, including those with a single PNE. SPD SIP SCP Optimal Social Welfare Min-Max Min-Sum Max-Min-Surplus Nash Kalai_Smorodinsky Egalitarian Utilitarian 0-10 1±01± 0 0.3013±0.0880.3013± 0.088 0.7662±0.33090.7662± 0.3309 0.7624±0.22650.7624± 0.2265 0.7522±0.22660.7522± 0.2266 0.7519±0.22470.7519± 0.2247 0.7509±0.22510.7509± 0.2251 0.7532±0.22350.7532± 0.2235 0.7521±0.2240.7521± 0.224 0.7521±0.22660.7521± 0.2266 11-20 1±01± 0 0.298±0.07650.298± 0.0765 0.7823±0.30230.7823± 0.3023 0.7924±0.23860.7924± 0.2386 0.786±0.24060.786± 0.2406 0.7877±0.23630.7877± 0.2363 0.7856±0.23910.7856± 0.2391 0.7881±0.23610.7881± 0.2361 0.7892±0.23470.7892± 0.2347 0.7855±0.24040.7855± 0.2404 21-30 1±01± 0 0.3039±0.090.3039± 0.09 0.7821±0.25850.7821± 0.2585 0.8026±0.20460.8026± 0.2046 0.7895±0.2140.7895± 0.214 0.7956±0.20170.7956± 0.2017 0.7896±0.20830.7896± 0.2083 0.7944±0.20130.7944± 0.2013 0.7983±0.19650.7983± 0.1965 0.7895±0.2140.7895± 0.214 31-40 1±01± 0 0.2958±0.08410.2958± 0.0841 0.8236±0.25620.8236± 0.2562 0.8437±0.19490.8437± 0.1949 0.837±0.20470.837± 0.2047 0.8433±0.19140.8433± 0.1914 0.838±0.19740.838± 0.1974 0.84±0.19470.84± 0.1947 0.844±0.18870.844± 0.1887 0.837±0.20470.837± 0.2047 41-50 1±01± 0 0.2983±0.08410.2983± 0.0841 0.8032±0.2720.8032± 0.272 0.8404±0.20190.8404± 0.2019 0.8325±0.21620.8325± 0.2162 0.8392±0.19980.8392± 0.1998 0.8352±0.2040.8352± 0.204 0.8369±0.20250.8369± 0.2025 0.8399±0.19830.8399± 0.1983 0.8321±0.21630.8321± 0.2163 51-60 1±01± 0 0.2944±0.09650.2944± 0.0965 0.8758±0.2640.8758± 0.264 0.9065±0.1670.9065± 0.167 0.901±0.17340.901± 0.1734 0.9037±0.16870.9037± 0.1687 0.9016±0.17060.9016± 0.1706 0.9029±0.16870.9029± 0.1687 0.9032±0.16840.9032± 0.1684 0.9011±0.17360.9011± 0.1736 61-70 1±01± 0 0.2971±0.08850.2971± 0.0885 0.9148±0.27040.9148± 0.2704 0.9313±0.13930.9313± 0.1393 0.9283±0.14410.9283± 0.1441 0.9309±0.13650.9309± 0.1365 0.929±0.13990.929± 0.1399 0.9298±0.13880.9298± 0.1388 0.931±0.13610.931± 0.1361 0.9283±0.14410.9283± 0.1441 71-80 1±01± 0 0.293±0.08760.293± 0.0876 0.9433±0.23550.9433± 0.2355 0.9629±0.09970.9629± 0.0997 0.9612±0.10380.9612± 0.1038 0.9621±0.09960.9621± 0.0996 0.9613±0.10180.9613± 0.1018 0.9619±0.09970.9619± 0.0997 0.962±0.09950.962± 0.0995 0.9612±0.10380.9612± 0.1038 81-90 1±01± 0 0.3013±0.09120.3013± 0.0912 0.964±0.19960.964± 0.1996 0.9747±0.08340.9747± 0.0834 0.9745±0.0850.9745± 0.085 0.9746±0.08340.9746± 0.0834 0.9745±0.08330.9745± 0.0833 0.9746±0.08330.9746± 0.0833 0.9746±0.08330.9746± 0.0833 0.9745±0.0850.9745± 0.085 91-100 1±01± 0 0.2966±0.08010.2966± 0.0801 0.9763±0.21650.9763± 0.2165 0.976±0.09270.976± 0.0927 0.9754±0.09380.9754± 0.0938 0.9757±0.09170.9757± 0.0917 0.9756±0.09210.9756± 0.0921 0.9756±0.09240.9756± 0.0924 0.9757±0.09170.9757± 0.0917 0.9754±0.09380.9754± 0.0938 F.2.5 Social welfare in all scenarios a Table 17: Effects of Cooperation Density on social welfare across all tested scenarios, including those with a single PNE. Cooperation Density Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 0.1 1±01± 0 1.0055±0.01151.0055± 0.0115 1.0055±0.01151.0055± 0.0115 1.0059±0.01191.0059± 0.0119 1.0055±0.01151.0055± 0.0115 1.0056±0.01151.0056± 0.0115 1.0059±0.01191.0059± 0.0119 1.0055±0.01151.0055± 0.0115 1.1129±0.08191.1129± 0.0819 1.006±0.0121.006± 0.012 1.0055±0.01151.0055± 0.0115 0.2 1±01± 0 1.0098±0.01971.0098± 0.0197 1.0081±0.0181.0081± 0.018 1.0101±0.01991.0101± 0.0199 1.0086±0.0181.0086± 0.018 1.0099±0.01861.0099± 0.0186 1.0121±0.02181.0121± 0.0218 1.0081±0.0181.0081± 0.018 1.2579±0.15991.2579± 0.1599 1.0157±0.02781.0157± 0.0278 1.0081±0.0181.0081± 0.018 0.3 1±01± 0 1.0109±0.01971.0109± 0.0197 1.0102±0.01961.0102± 0.0196 1.0121±0.02131.0121± 0.0213 1.0104±0.01981.0104± 0.0198 1.0116±0.01991.0116± 0.0199 1.0123±0.02141.0123± 0.0214 1.0102±0.01961.0102± 0.0196 1.4557±0.21371.4557± 0.2137 1.0167±0.02521.0167± 0.0252 1.0102±0.01961.0102± 0.0196 0.4 1±01± 0 1.0117±0.01841.0117± 0.0184 1.0089±0.01431.0089± 0.0143 1.0167±0.02981.0167± 0.0298 1.01±0.01571.01± 0.0157 1.0133±0.01661.0133± 0.0166 1.0199±0.03041.0199± 0.0304 1.0089±0.01431.0089± 0.0143 1.7142±0.30211.7142± 0.3021 1.0278±0.04121.0278± 0.0412 1.0089±0.01431.0089± 0.0143 0.5 1±01± 0 1.0182±0.03711.0182± 0.0371 1.0148±0.0341.0148± 0.034 1.0197±0.03731.0197± 0.0373 1.0153±0.0341.0153± 0.034 1.0185±0.03371.0185± 0.0337 1.0231±0.03851.0231± 0.0385 1.0148±0.0341.0148± 0.034 2.0435±0.45062.0435± 0.4506 1.0338±0.04941.0338± 0.0494 1.0148±0.0341.0148± 0.034 0.6 1±01± 0 1.0193±0.03391.0193± 0.0339 1.0172±0.03181.0172± 0.0318 1.0243±0.03721.0243± 0.0372 1.0176±0.03221.0176± 0.0322 1.0242±0.03411.0242± 0.0341 1.0308±0.04511.0308± 0.0451 1.0172±0.03181.0172± 0.0318 2.3437±0.56412.3437± 0.5641 1.0645±0.091.0645± 0.09 1.0172±0.03181.0172± 0.0318 0.7 1±01± 0 1.0207±0.03271.0207± 0.0327 1.0149±0.01841.0149± 0.0184 1.0217±0.02941.0217± 0.0294 1.0152±0.01861.0152± 0.0186 1.0248±0.0241.0248± 0.024 1.0277±0.03141.0277± 0.0314 1.0149±0.01841.0149± 0.0184 2.5726±0.61382.5726± 0.6138 1.066±0.07981.066± 0.0798 1.0149±0.01841.0149± 0.0184 0.8 1±01± 0 1.024±0.02821.024± 0.0282 1.0191±0.02181.0191± 0.0218 1.0308±0.03371.0308± 0.0337 1.0195±0.02151.0195± 0.0215 1.0315±0.02691.0315± 0.0269 1.0406±0.04151.0406± 0.0415 1.0191±0.02181.0191± 0.0218 3.1327±0.63643.1327± 0.6364 1.0851±0.07711.0851± 0.0771 1.0191±0.02181.0191± 0.0218 0.9 1±01± 0 1.0212±0.0571.0212± 0.057 1.0184±0.0561.0184± 0.056 1.0274±0.05911.0274± 0.0591 1.0187±0.0561.0187± 0.056 1.0275±0.05621.0275± 0.0562 1.0369±0.06261.0369± 0.0626 1.0184±0.0561.0184± 0.056 3.3199±0.77093.3199± 0.7709 1.0827±0.09741.0827± 0.0974 1.0184±0.0561.0184± 0.056 1.0 1±01± 0 1.02±0.03111.02± 0.0311 1.0154±0.02291.0154± 0.0229 1.0276±0.02951.0276± 0.0295 1.0156±0.02281.0156± 0.0228 1.0262±0.02541.0262± 0.0254 1.0369±0.03561.0369± 0.0356 1.0154±0.02291.0154± 0.0229 3.5319±0.77023.5319± 0.7702 1.0861±0.08681.0861± 0.0868 1.0154±0.02291.0154± 0.0229 Table 18: Effects of Cooperation Magnitude on social welfare across all tested scenarios, including those with a single PNE. Cooperation Magnitude Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 2 1±01± 0 1.004±0.01841.004± 0.0184 1.0026±0.01761.0026± 0.0176 1.0039±0.01811.0039± 0.0181 1.0029±0.01771.0029± 0.0177 1.0035±0.01771.0035± 0.0177 1.0041±0.01821.0041± 0.0182 1.0026±0.01761.0026± 0.0176 1.255±0.07661.255± 0.0766 1.006±0.01981.006± 0.0198 1.0026±0.01761.0026± 0.0176 4 1±01± 0 1.011±0.0361.011± 0.036 1.0061±0.0331.0061± 0.033 1.0091±0.03511.0091± 0.0351 1.0062±0.0331.0062± 0.033 1.0096±0.03311.0096± 0.0331 1.012±0.03621.012± 0.0362 1.0061±0.0331.0061± 0.033 1.7072±0.23261.7072± 0.2326 1.0233±0.04431.0233± 0.0443 1.0061±0.0331.0061± 0.033 6 1±01± 0 1.0089±0.02131.0089± 0.0213 1.0066±0.01371.0066± 0.0137 1.0113±0.02091.0113± 0.0209 1.007±0.01381.007± 0.0138 1.0115±0.01411.0115± 0.0141 1.0152±0.02451.0152± 0.0245 1.0066±0.01371.0066± 0.0137 2.0852±0.38492.0852± 0.3849 1.0339±0.04891.0339± 0.0489 1.0066±0.01371.0066± 0.0137 8 1±01± 0 1.0173±0.02481.0173± 0.0248 1.0118±0.0191.0118± 0.019 1.0213±0.02841.0213± 0.0284 1.0124±0.01911.0124± 0.0191 1.0211±0.02291.0211± 0.0229 1.0313±0.04031.0313± 0.0403 1.0118±0.0191.0118± 0.019 2.4446±0.49362.4446± 0.4936 1.0583±0.07021.0583± 0.0702 1.0118±0.0191.0118± 0.019 10 1±01± 0 1.0281±0.05791.0281± 0.0579 1.0192±0.0481.0192± 0.048 1.0286±0.05581.0286± 0.0558 1.0192±0.0481.0192± 0.048 1.029±0.04961.029± 0.0496 1.0355±0.05791.0355± 0.0579 1.0192±0.0481.0192± 0.048 2.699±0.67552.699± 0.6755 1.0696±0.08081.0696± 0.0808 1.0192±0.0481.0192± 0.048 12 1±01± 0 1.0214±0.03131.0214± 0.0313 1.0154±0.02111.0154± 0.0211 1.0282±0.03531.0282± 0.0353 1.0163±0.02121.0163± 0.0212 1.0273±0.02731.0273± 0.0273 1.0357±0.04191.0357± 0.0419 1.0154±0.02111.0154± 0.0211 2.9286±0.70542.9286± 0.7054 1.0687±0.07621.0687± 0.0762 1.0154±0.02111.0154± 0.0211 14 1±01± 0 1.0292±0.04261.0292± 0.0426 1.0219±0.03091.0219± 0.0309 1.0319±0.03991.0319± 0.0399 1.0222±0.03111.0222± 0.0311 1.032±0.03391.032± 0.0339 1.0379±0.04471.0379± 0.0447 1.0219±0.03091.0219± 0.0309 3.2267±0.79493.2267± 0.7949 1.0745±0.08671.0745± 0.0867 1.0219±0.03091.0219± 0.0309 16 1±01± 0 1.0358±0.05561.0358± 0.0556 1.027±0.0481.027± 0.048 1.0442±0.06191.0442± 0.0619 1.0281±0.04871.0281± 0.0487 1.042±0.05021.042± 0.0502 1.053±0.06551.053± 0.0655 1.027±0.0481.027± 0.048 3.3066±0.92853.3066± 0.9285 1.1012±0.09171.1012± 0.0917 1.027±0.0481.027± 0.048 18 1±01± 0 1.0386±0.04921.0386± 0.0492 1.0304±0.03731.0304± 0.0373 1.0484±0.06311.0484± 0.0631 1.0312±0.03751.0312± 0.0375 1.0465±0.04341.0465± 0.0434 1.0607±0.06081.0607± 0.0608 1.0304±0.03731.0304± 0.0373 3.722±1.00423.722± 1.0042 1.1143±0.10711.1143± 0.1071 1.0304±0.03731.0304± 0.0373 20 1±01± 0 1.0294±0.051.0294± 0.05 1.0249±0.04281.0249± 0.0428 1.0414±0.06741.0414± 0.0674 1.0253±0.04311.0253± 0.0431 1.0368±0.05061.0368± 0.0506 1.0516±0.07781.0516± 0.0778 1.0249±0.04281.0249± 0.0428 3.7155±1.05553.7155± 1.0555 1.1009±0.11891.1009± 0.1189 1.0249±0.04281.0249± 0.0428 Table 19: Effects of Path Length on social welfare across all tested scenarios, including those with a single PNE. Path Length Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 0-49 1±01± 0 1.0811±0.11561.0811± 0.1156 1.0766±0.11151.0766± 0.1115 1.089±0.11421.089± 0.1142 1.0846±0.11161.0846± 0.1116 1.0869±0.10981.0869± 0.1098 1.0935±0.11291.0935± 0.1129 1.0766±0.11151.0766± 0.1115 1.4459±0.33971.4459± 0.3397 1.1041±0.11671.1041± 0.1167 1.0766±0.11151.0766± 0.1115 50-99 1±01± 0 1.0522±0.0481.0522± 0.048 1.0472±0.04571.0472± 0.0457 1.0571±0.06021.0571± 0.0602 1.0478±0.04591.0478± 0.0459 1.0558±0.04931.0558± 0.0493 1.0612±0.06271.0612± 0.0627 1.0472±0.04571.0472± 0.0457 1.862±0.47491.862± 0.4749 1.0915±0.09811.0915± 0.0981 1.0472±0.04571.0472± 0.0457 100-149 1±01± 0 1.0321±0.04471.0321± 0.0447 1.0223±0.02811.0223± 0.0281 1.0372±0.04051.0372± 0.0405 1.0235±0.0281.0235± 0.028 1.0378±0.03261.0378± 0.0326 1.0466±0.04941.0466± 0.0494 1.0223±0.02811.0223± 0.0281 2.3512±0.51572.3512± 0.5157 1.0929±0.08411.0929± 0.0841 1.0223±0.02811.0223± 0.0281 150-199 1±01± 0 1.0263±0.03551.0263± 0.0355 1.02±0.02291.02± 0.0229 1.0326±0.03951.0326± 0.0395 1.0205±0.02341.0205± 0.0234 1.0308±0.02811.0308± 0.0281 1.0356±0.04151.0356± 0.0415 1.02±0.02291.02± 0.0229 2.6701±0.54522.6701± 0.5452 1.0802±0.08891.0802± 0.0889 1.02±0.02291.02± 0.0229 200-249 1±01± 0 1.0266±0.04581.0266± 0.0458 1.0207±0.04021.0207± 0.0402 1.032±0.04921.032± 0.0492 1.0211±0.04031.0211± 0.0403 1.031±0.04141.031± 0.0414 1.0396±0.05381.0396± 0.0538 1.0207±0.04021.0207± 0.0402 2.8879±0.61482.8879± 0.6148 1.0786±0.08571.0786± 0.0857 1.0207±0.04021.0207± 0.0402 250-299 1±01± 0 1.0232±0.03781.0232± 0.0378 1.0172±0.0331.0172± 0.033 1.0268±0.04031.0268± 0.0403 1.0174±0.03311.0174± 0.0331 1.0265±0.03391.0265± 0.0339 1.0323±0.04241.0323± 0.0424 1.0172±0.0331.0172± 0.033 2.9731±0.66042.9731± 0.6604 1.0714±0.07691.0714± 0.0769 1.0172±0.0331.0172± 0.033 300-349 1±01± 0 1.0188±0.02581.0188± 0.0258 1.0141±0.02081.0141± 0.0208 1.0246±0.03291.0246± 0.0329 1.0142±0.02081.0142± 0.0208 1.0235±0.02311.0235± 0.0231 1.0318±0.03681.0318± 0.0368 1.0141±0.02081.0141± 0.0208 3.1339±0.64273.1339± 0.6427 1.0623±0.06091.0623± 0.0609 1.0141±0.02081.0141± 0.0208 350-399 1±01± 0 1.0156±0.02451.0156± 0.0245 1.0106±0.01811.0106± 0.0181 1.018±0.0281.018± 0.028 1.0108±0.01811.0108± 0.0181 1.017±0.02011.017± 0.0201 1.0226±0.03151.0226± 0.0315 1.0106±0.01811.0106± 0.0181 2.8777±0.69142.8777± 0.6914 1.044±0.0531.044± 0.053 1.0106±0.01811.0106± 0.0181 400-449 1±01± 0 1.0134±0.0221.0134± 0.022 1.0091±0.01431.0091± 0.0143 1.0132±0.01921.0132± 0.0192 1.0092±0.01431.0092± 0.0143 1.0129±0.01541.0129± 0.0154 1.016±0.02151.016± 0.0215 1.0091±0.01431.0091± 0.0143 2.6248±0.7132.6248± 0.713 1.0282±0.03571.0282± 0.0357 1.0091±0.01431.0091± 0.0143 450-499 1±01± 0 1.0166±0.04951.0166± 0.0495 1.0125±0.04611.0125± 0.0461 1.0168±0.04761.0168± 0.0476 1.0125±0.04611.0125± 0.0461 1.0158±0.04651.0158± 0.0465 1.017±0.04791.017± 0.0479 1.0125±0.04611.0125± 0.0461 2.5938±0.72962.5938± 0.7296 1.0335±0.07961.0335± 0.0796 1.0125±0.04611.0125± 0.0461 500-549 1±01± 0 1.0135±0.03051.0135± 0.0305 1.0119±0.03011.0119± 0.0301 1.0145±0.0311.0145± 0.031 1.012±0.03011.012± 0.0301 1.0143±0.03011.0143± 0.0301 1.0173±0.0331.0173± 0.033 1.0119±0.03011.0119± 0.0301 2.7092±0.66052.7092± 0.6605 1.0236±0.04031.0236± 0.0403 1.0119±0.03011.0119± 0.0301 550-599 1±01± 0 1.0132±0.05261.0132± 0.0526 1.0114±0.05241.0114± 0.0524 1.0134±0.05251.0134± 0.0525 1.0115±0.05241.0115± 0.0524 1.0131±0.05231.0131± 0.0523 1.0134±0.05231.0134± 0.0523 1.0114±0.05241.0114± 0.0524 2.6095±0.72712.6095± 0.7271 1.0212±0.05741.0212± 0.0574 1.0114±0.05241.0114± 0.0524 600-649 1±01± 0 1.0107±0.01431.0107± 0.0143 1.0081±0.01191.0081± 0.0119 1.0101±0.01191.0101± 0.0119 1.0082±0.01191.0082± 0.0119 1.01±0.0121.01± 0.012 1.0126±0.01621.0126± 0.0162 1.0081±0.01191.0081± 0.0119 2.7095±0.65872.7095± 0.6587 1.0183±0.02061.0183± 0.0206 1.0081±0.01191.0081± 0.0119 650-699 1±01± 0 1.02±0.07231.02± 0.0723 1.0185±0.07241.0185± 0.0724 1.0198±0.07231.0198± 0.0723 1.0185±0.07241.0185± 0.0724 1.0202±0.07211.0202± 0.0721 1.021±0.07221.021± 0.0722 1.0185±0.07241.0185± 0.0724 2.6608±0.66192.6608± 0.6619 1.0269±0.07251.0269± 0.0725 1.0185±0.07241.0185± 0.0724 700-749 1±01± 0 1.0062±0.00881.0062± 0.0088 1.0047±0.00551.0047± 0.0055 1.0066±0.0071.0066± 0.007 1.0047±0.00551.0047± 0.0055 1.0062±0.00561.0062± 0.0056 1.0078±0.00921.0078± 0.0092 1.0047±0.00551.0047± 0.0055 2.8798±0.68442.8798± 0.6844 1.0135±0.0191.0135± 0.019 1.0047±0.00551.0047± 0.0055 750-799 1±01± 0 1.0048±0.00511.0048± 0.0051 1.0044±0.00431.0044± 0.0043 1.0122±0.02041.0122± 0.0204 1.0044±0.00431.0044± 0.0043 1.0059±0.00531.0059± 0.0053 1.0146±0.02261.0146± 0.0226 1.0044±0.00431.0044± 0.0043 2.7342±0.56882.7342± 0.5688 1.0206±0.03451.0206± 0.0345 1.0044±0.00431.0044± 0.0043 800-849 1±01± 0 1.0069±0.00741.0069± 0.0074 1.0063±0.00641.0063± 0.0064 1.007±0.00651.007± 0.0065 1.0063±0.00641.0063± 0.0064 1.0079±0.00821.0079± 0.0082 1.0084±0.00831.0084± 0.0083 1.0063±0.00641.0063± 0.0064 2.9351±0.36742.9351± 0.3674 1.0135±0.01721.0135± 0.0172 1.0063±0.00641.0063± 0.0064 850-899 1±01± 0 1.0058±0.00671.0058± 0.0067 1.0043±0.00511.0043± 0.0051 1.006±0.00761.006± 0.0076 1.0043±0.00511.0043± 0.0051 1.0058±0.00631.0058± 0.0063 1.0061±0.00761.0061± 0.0076 1.0043±0.00511.0043± 0.0051 2.8022±0.40752.8022± 0.4075 1.0105±0.01511.0105± 0.0151 1.0043±0.00511.0043± 0.0051 900-949 1±01± 0 1.005±0.00781.005± 0.0078 1.0033±0.00441.0033± 0.0044 1.0054±0.00671.0054± 0.0067 1.0035±0.00441.0035± 0.0044 1.0054±0.00521.0054± 0.0052 1.0059±0.00591.0059± 0.0059 1.0033±0.00441.0033± 0.0044 2.9136±0.65132.9136± 0.6513 1.0152±0.02521.0152± 0.0252 1.0033±0.00441.0033± 0.0044 950-999 1±01± 0 1.0064±0.00691.0064± 0.0069 1.0037±0.00411.0037± 0.0041 1.006±0.00631.006± 0.0063 1.0037±0.00411.0037± 0.0041 1.005±0.00451.005± 0.0045 1.0062±0.00681.0062± 0.0068 1.0037±0.00411.0037± 0.0041 2.8216±0.39392.8216± 0.3939 1.0087±0.00851.0087± 0.0085 1.0037±0.00411.0037± 0.0041 1000-1049 1±01± 0 1.0049±0.0051.0049± 0.005 1.0043±0.00371.0043± 0.0037 1.0074±0.00841.0074± 0.0084 1.0043±0.00371.0043± 0.0037 1.0054±0.00391.0054± 0.0039 1.0074±0.00841.0074± 0.0084 1.0043±0.00371.0043± 0.0037 2.6694±0.4362.6694± 0.436 1.0091±0.00911.0091± 0.0091 1.0043±0.00371.0043± 0.0037 Table 20: Effects of SPD on social welfare across all tested scenarios, including those with a single PNE. SPD Optimal Social Welfare Min-Max Min-Sum Max-Min Improvement Nash Kalai_Smorodinsky Egalitarian Utilitarian SIP|SIP PoA PoS 0-10 1±01± 0 1.0435±0.07781.0435± 0.0778 1.0352±0.07291.0352± 0.0729 1.0397±0.07341.0397± 0.0734 1.0371±0.07271.0371± 0.0727 1.0384±0.07271.0384± 0.0727 1.0401±0.07361.0401± 0.0736 1.0352±0.07291.0352± 0.0729 1.5433±0.60421.5433± 0.6042 1.0534±0.08411.0534± 0.0841 1.0352±0.07291.0352± 0.0729 11-20 1±01± 0 1.0371±0.06191.0371± 0.0619 1.0308±0.05731.0308± 0.0573 1.0394±0.06331.0394± 0.0633 1.0326±0.05741.0326± 0.0574 1.0364±0.05751.0364± 0.0575 1.0419±0.06411.0419± 0.0641 1.0308±0.05731.0308± 0.0573 1.492±0.65421.492± 0.6542 1.0533±0.07081.0533± 0.0708 1.0308±0.05731.0308± 0.0573 21-30 1±01± 0 1.0472±0.07311.0472± 0.0731 1.0328±0.06451.0328± 0.0645 1.0467±0.07531.0467± 0.0753 1.0355±0.06421.0355± 0.0642 1.0419±0.06581.0419± 0.0658 1.0512±0.07911.0512± 0.0791 1.0328±0.06451.0328± 0.0645 1.4069±0.43151.4069± 0.4315 1.0702±0.09311.0702± 0.0931 1.0328±0.06451.0328± 0.0645 31-40 1±01± 0 1.0486±0.07851.0486± 0.0785 1.0391±0.07121.0391± 0.0712 1.0534±0.08131.0534± 0.0813 1.0435±0.0711.0435± 0.071 1.0463±0.07111.0463± 0.0711 1.0557±0.0861.0557± 0.086 1.0391±0.07121.0391± 0.0712 1.3215±0.35581.3215± 0.3558 1.0697±0.09991.0697± 0.0999 1.0391±0.07121.0391± 0.0712 41-50 1±01± 0 1.0691±0.09831.0691± 0.0983 1.0581±0.09561.0581± 0.0956 1.0721±0.09911.0721± 0.0991 1.0651±0.09621.0651± 0.0962 1.0669±0.09451.0669± 0.0945 1.0727±0.09851.0727± 0.0985 1.0581±0.09561.0581± 0.0956 1.3495±0.39581.3495± 0.3958 1.0852±0.10241.0852± 0.1024 1.0581±0.09561.0581± 0.0956 51-60 1±01± 0 1.0575±0.08151.0575± 0.0815 1.0531±0.08011.0531± 0.0801 1.0573±0.08151.0573± 0.0815 1.0545±0.07981.0545± 0.0798 1.0552±0.07961.0552± 0.0796 1.0567±0.08031.0567± 0.0803 1.0531±0.08011.0531± 0.0801 1.2175±0.29971.2175± 0.2997 1.0618±0.0821.0618± 0.082 1.0531±0.08011.0531± 0.0801 61-70 1±01± 0 1.0474±0.07111.0474± 0.0711 1.045±0.07161.045± 0.0716 1.0514±0.07271.0514± 0.0727 1.0469±0.07121.0469± 0.0712 1.0478±0.07071.0478± 0.0707 1.0515±0.07251.0515± 0.0725 1.045±0.07161.045± 0.0716 1.1595±0.2281.1595± 0.228 1.0555±0.07231.0555± 0.0723 1.045±0.07161.045± 0.0716 71-80 1±01± 0 1.0394±0.071.0394± 0.07 1.0377±0.06881.0377± 0.0688 1.0407±0.07041.0407± 0.0704 1.0392±0.06891.0392± 0.0689 1.0397±0.06871.0397± 0.0687 1.0408±0.07031.0408± 0.0703 1.0377±0.06881.0377± 0.0688 1.0986±0.17591.0986± 0.1759 1.0439±0.07181.0439± 0.0718 1.0377±0.06881.0377± 0.0688 81-90 1±01± 0 1.0232±0.05061.0232± 0.0506 1.0231±0.05061.0231± 0.0506 1.0241±0.05111.0241± 0.0511 1.0238±0.05081.0238± 0.0508 1.0237±0.05071.0237± 0.0507 1.0241±0.05111.0241± 0.0511 1.0231±0.05061.0231± 0.0506 1.0598±0.12761.0598± 0.1276 1.0242±0.05111.0242± 0.0511 1.0231±0.05061.0231± 0.0506 91-100 1±01± 0 1.0267±0.06071.0267± 0.0607 1.0263±0.06071.0263± 0.0607 1.027±0.06051.027± 0.0605 1.0268±0.06061.0268± 0.0606 1.0267±0.06061.0267± 0.0606 1.027±0.06051.027± 0.0605 1.0263±0.06071.0263± 0.0607 1.0674±0.16971.0674± 0.1697 1.0272±0.06051.0272± 0.0605 1.0263±0.06071.0263± 0.0607 F.3 Execution Environment The experiments were conducted on a MacBook Pro with an Apple M1 Pro processor and 16 GB of RAM, running macOS 26.5. The implementation was written in Python 3.11.3 and relies primarily on the Python standard library, with NetworkX used for graph representation and graph algorithms. Matplotlib was used to generate the plots and simulation visualizations. No GPU acceleration was used. Randomness was used only for sampling experimental scenarios from the benchmark maps, using Python’s built-in random module. No fixed random seed was used. However, the actual sampled instances are publicly available as serialized pickle files representing the generated graphs, together with the experimental data and aggregated results, at https://iscmpp.info/.