Paper deep dive
Multiagent Stochastic Shortest Path Problem
Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/8/2026, 10:45:51 AM
Summary
The paper introduces the Multiagent Stochastic Shortest Path (MSSP) problem, where k agents aim to minimize the expected time for at least one agent to reach a target state in a Markov Decision Process. It analyzes computational complexity, showing Coordinated MSSP is PSPACE-hard and Autonomous MSSP is NP-hard. The authors propose the AutoHit algorithm for autonomous strategy synthesis using differentiable programming and introduce the 'price of autonomy' metric to quantify coordination benefits.
Entities (10)
Relation Signals (10)
Martin Jonáš → authored → Multiagent Stochastic Shortest Path Problem
confidence 99% · Multiagent Stochastic Shortest Path Problem Martin Jonáš Antonín Kučera Vojtěch Kůr Jan Mačák Vojtěch Řehák Faculty of Informatics, Masaryk University...
Multiagent Stochastic Shortest Path Problem → models → Markov Decision Process
confidence 97% · The task is to navigate an agent to a target state in a given explicitly represented Markov decision process (MDP)...
Autonomous MSSP → iscomplexity → NP-hard
confidence 96% · Then, we show that the problem of deciding the existence of an autonomous strategy profile... is 𝖭𝖯-hard even for k=2...
Coordinated MSSP → iscomplexity → PSPACE-hard
confidence 96% · We also show that the problem is 𝖯𝖲𝖯𝖠𝖢𝖤-hard, and hence the exponential blowup in kk is unavoidable.
Multiagent Stochastic Shortest Path Problem → extends → Stochastic Shortest Path
confidence 95% · We initiate the study of Multiagent Stochastic Shortest Path (MSSP) problem... As in the classical SSP...
AutoHit → solves → Autonomous MSSP
confidence 94% · This is the crucial step enabling the application of state-of-the-art techniques of differentiable programming, which is the core of our AutoHit algorithm.
Multiagent Stochastic Shortest Path Problem → hasvariant → Coordinated MSSP
confidence 93% · We analyze the computational and strategy-complexity of the problem in both autonomous and coordinated settings...
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We introduce and study the multi-agent stochastic shortest path (MSSP) problem, in which $k$ agents strive to reach a target state, aiming to minimize the expected time to reach the target by any agent. We analyze the computational and strategy-complexity of the problem in both autonomous and coordinated settings, and we design efficient strategy-synthesis algorithms. The algorithms are experimentally evaluated on instances of increasing size against natural baselines.
Tags
Links
- Source: https://arxiv.org/abs/2605.06056v1
- Canonical: https://arxiv.org/abs/2605.06056v1
Trouble viewing inline? Open PDF directly →
Full Text
142,497 characters extracted from source content.
Expand or collapse full text
Multiagent Stochastic Shortest Path Problem Martin Jonáš Antonín Kučera Vojtěch Kůr Jan Mačák Vojtěch Řehák Faculty of Informatics, Masaryk University, Czechia martin.jonas@mail.muni.cz, tony@fi.muni.cz, vojtech.kur@mail.muni.cz, macak.jan@mail.muni.cz, rehak@fi.muni.cz Abstract We introduce and study the multiagent stochastic shortest path (MSSP) problem where k agents strive to reach a target state and the task is to minimize the expected time of reaching the target by some agent. We analyze the computational and strategy complexity of the problem in both autonomous and coordinated settings, and we design efficient strategy synthesis algorithms. The algorithms are experimentally evaluated on instances of increasing size against natural baselines. 1 Introduction Stochastic Shortest Path (SSP) is a fundamental optimization problem deeply studied in planning and control. The task is to navigate an agent to a target state in a given explicitly represented Markov decision process (MDP) at minimum expected path length (the expected path length can also be interpreted as the expected time to reach a target). The SSP problem captures a variety of realistic scenarios, including car navigation, drone flying, game playing, etc. In this work, we initiate the study of Multiagent Stochastic Shortest Path (MSSP) problem, where k agents strive to reach a target so that the expected time of reaching the target by some agent is minimized. As in the classical SSP, we consider application scenarios where the MDP is known and represented explicitly (hence, there is no need to learn the MDP structure). As a simple example, consider the problem of urgent blood transport from a blood bank to a distant hospital by a car driving through a city. The current traffic density determines the probability distribution of the time required to cross individual sections of the road and can be modeled by an MDP whose size is proportional to the number of road sections. Hence, planning an optimal route for a single car is an instance of the SSP problem, and an optimal moving strategy σ can be quickly computed by existing algorithms. In order to increase the chance of timely delivery, multiple cars (from the same or different blood banks) can be dispatched simultaneously. Clearly, the aim is to minimize the expected time of the first arrival (the blood doses delivered by the cars arriving later can be stored for later use). A natural approach to solving this optimization problem is to compute the above strategy σ for each car, i.e., to solve the SSP problem independently for each car. However, this is not optimal in general, and in some cases it is even the worst possible solution. A simple demonstrative example is given in Fig. 1. More generally, MSSP models a class of time-critical delivery problems where the item can be replicated and sent across multiple paths to improve time performance and reliability. The primary research question considered in this work is “How to compute an optimal solution for a given MSSP instance?” Apart from inventing efficient algorithms, we analyze the computational complexity of MSSP and determine the type of strategies required for optimal solutions. In the above application scenario, the cars can be autonomous or coordinated by a central control room. When the agents are UAVs operating in a hostile environment, the coordination may be unachievable. Therefore, we consider the MSSP problem for both autonomous and coordinated agents. Even if agents’ coordination is achievable, it can be expensive. Therefore, we also analyze the benefits of coordination for solving MSSP, i.e., the ratio between the best solutions achievable in the autonomous/coordinated setting. sτ 110.50.50.50.51111111111bbaa Figure 1: The initial state is s, the target is τ, and the numbers denote transition probabilities. If a single agent chooses the action a (or b), the expected time to reach τ is 22 (or 2.52.5, resp.). Hence, a single agent should choose a. Now consider two agents. If both of them choose a, the expected time of reaching τ by some agent is 22. However, if one of them chooses a and the other b, the expectation decreases to 1.51.5. (The b action selects between the paths of length 11 and 44 uniformly at random. In the first case, the “blue” agent arrives to τ after one step. In the second case, the “red” agent arrives to τ already after two steps. Hence, the expectation is 0.5⋅1+0.5⋅2=1.50.5· 1+0.5· 2=1.5.) Also note that if both agents choose b, the expectation is 1.751.75. Our Contribution. We start by analyzing the computational complexity of the MSSP problem and identifying the type of strategies required for optimal solutions. For the Coordinated MSSP problem, we show that an optimal coordinated strategy for k agents in a given MPD M is computable in time polynomial in the size of M and exponential in k. For every fixed k, the problem is solvable in polynomial time, but the degree of the bounding polynomial grows linearly in k. Furthermore, an optimal strategy can be constructed so that it is memoryless (the decision depends only on the current positions of the agents) and deterministic (the choice of actions is uniquely determined in every step). We also show that the problem is PSPACE-hard, and hence the exponential blowup in k is unavoidable. More precisely, we prove it is PSPACE-hard to decide the existence of a coordinated strategy such that the expected time to reach a target by some agent is bounded by a given constant. For the Autonomous MSSP problem, we show that an optimal autonomous strategy profile for k agents (i.e., a k-tuple of independent single-agent strategies) exists, but each agent may require memory to “remember” some information about the history of previous moves. We also prove that finite-memory randomized strategy profiles are sufficient for achieving ε -optimal solutions for an arbitrarily small ε>0 >0. Hence, for practical purposes, it suffices to consider only finite-memory randomized strategy profiles. Then, we show that the problem of deciding the existence of an autonomous strategy profile for k agents such that the expected time to reach a target by some agent is bounded by a given constant is NP-hard even for k=2k=2 and even if the class of admissible profiles is restricted to memoryless profiles. Hence, the Autonomous MSSP problem is not fixed-parameter tractable in k, and it is also conceptually harder (in particular, there is no apparent way of computing an ε -optimal profile for a given ε≥0 ≥ 0). Our algorithmic solution is based on the following: (1) We show that for every memory size m, the problem of synthesizing the best randomized profile where every strategy in the profile uses at most m memory states is reducible to the problem of computing the best randomized memoryless profile. Hence, the algorithmic core of the problem is the synthesis of the best memoryless randomized profile (this problem is still NP-hard even for two agents, see above). (2) In the next step, we show how to express the expected time to reach a target by some agent as a differentiable function in the parameters representing memoryless randomized profiles. This is the crucial step enabling the application of state-of-the-art techniques of differentiable programming, which is the core of our AutoHit algorithm. The efficiency of AutoHit is bought by the loss of optimality guarantees (this is unavoidable due to the NP-hardness of the problem). In the experimental part of our paper, we evaluate our synthesis algorithms on instances of increasing size against natural baselines, and we compare the efficiency of solutions obtained in the coordinated and autonomous setting. The instances resemble city maps with a grid-like structure with random delays at certain locations. To avoid bias towards specific MDP classes, the instances are generated randomly. Related Work. The SSP problem was introduced in Eaton and Zadeh (1962) in the framework of pursuit-evasion games. The SSP problem is solvable efficiently by the standard MDP strategy synthesis techniques (i.e., value iteration, policy iteration, and linear programming) under some structural conditions Puterman (1994); Bertsekas and Tsitsiklis (1991); de Alfaro (1999). The solution algorithms and their complexity depend also on the properties of the reward function (see, e.g., Baier et al. (2018)). More recent works study SSP under some additional conditions on the probability distribution of the accumulated reward Piribauer et al. (2022); Haase and Kiefer (2015); Křetínský and Meggendorfer (2018); Ahmadi et al. (2021); Mannor and Tsitsiklis (2011). See also Randour et al. (2015) for an overview. The SSP problem in an unknown environment has been studied in various variants, and the solution is mostly constructed by appropriate reinforcement learning techniques. A recent overview of these works is given in Rosenberg (2022). Multi-agent problems related to SSP have been studied only recently. In Nawaz and Ornik (2023), an algorithm for minimizing the expected time of visiting all targets in a given set by a swarm of autonomous agents is proposed. A multi-agent extension of pursuit-evasion games is introduced in Zhang et al. (2021). The problem of minimizing the total time of reaching all targets by autonomous agents in an unknown environment is studied in Trivedi and Hemachandra (2023); Chavan et al. (2025). Recent works also study multi-agent variants of infinite-horizon objectives (such as mean-payoff or steady-state objectives) in explictly presented MDPs Jonáš et al. (2025); Díaz-García et al. (2023); Klaška et al. (2023). Related objectives such as expected average reward have also been studied for decentralized POMDPs (see, e.g., Jiang et al. (2017)). To the best of our knowledge, there are no previous works on MSSP. 2 Preliminaries We assume familiarity with basic notions of probability theory and Markov chain theory. We use ℕN to denote the sets of all non-negative integers and ℕ∞N_∞ to denote the set ℕ∪∞N∪\∞\. For a given finite or countably infinite set A, the set of all probability distributions over A is denoted by (A)Dist(A). We say that μ∈(A)μ (A) is Dirac if μ(a)=1μ(a)=1 for some a∈Aa∈ A. Markov Chains. A Markov chain is a pair C=(S,A)C=(S,A) where S is a finite or countably infinite set of states and A:S×S→[0,1]A:S× S→[0,1] is a stochastic matrix such that ∑t∈SA(s,t)=1 _t∈ SA(s,t)=1 for every s∈Ss∈ S. A path in C is a finite or infinite sequence of states. Infinite paths are called runs, where a run is also understood as a mapping ω:ℕ→Sω:N→ S. For each finite path w, we use wRun_w to denote the set of all runs starting with w. To every s∈Ss∈ S we associate the probability space (s,ℱs,Probs)(Run_s,F_s,Prob_s) such that ℱsF_s is the σ-algebra generated by all wRun_w where w is a finite path initiated in s, and ProbsProb_s is the unique probability measure satisfying Probs(w)=∏i=0n−1A(si,si+1)Prob_s(Run_w)= _i=0^n-1A(s_i,s_i+1) for all finite paths w=s0,…,snw=s_0,…,s_n such that s0=s_0=s. Markov Decision Processes (MDPs). A Markov decision process (MDP) is a triple M=(S,Act,P)M=(S,Act,P) where S and Act are non-empty finite sets of states and actions, and P:S×Act×S→[0,1]P:S×Act× S→[0,1] is a transition function. We require that, for all s∈Ss∈ S and a∈Acta , the sum ∑t∈SP(s,a,t) _t∈ SP(s,a,t) is equal either to 0 or 11. In the latter case, we say that a is enabled in s. The set of all actions enabled in s is denoted by En(s)En(s). We require that En(s)≠∅En(s)≠ for all s∈Ss∈ S. We say that t∈St∈ S is reachable from s∈Ss∈ S if there is a finite sequence s0,…,sns_0,…,s_n such that s0=s_0=s, sn=ts_n=t, and for every i<ni<n there is ai∈Acta_i such that P(si,ai,si+1)>0P(s_i,a_i,s_i+1)>0. Strategies and Strategy Profiles. Let M=(S,Act,P)M=(S,Act,P) be an MDP. Consider k≥1k≥ 1 agents moving among the vertices of M by performing the actions of M. The agents are either autonomous or coordinated, i.e., each agent acts either independently or coordinates its decisions with the other agents, respectively (the coordination is usually implemented by a central control instructing the agents). We start by defining a coordinated strategy for k≥1k≥ 1 agents. Let Mem be a non-empty set of memory states where some information about the history of previous agents’ moves is stored. A configuration is a tuple (s1,…,sk,m)(s_1,…,s_k,m) where s1,…,sk∈Ss_1,…,s_k∈ S are the states currently visited by the agents and m∈m is the current memory state. We use Conf to denote the set of all configurations. A coordinated strategy for k≥1k≥ 1 agents is a triple σ=(μ,,)σ=(μ,next,update) where μ∈μ is an initial memory state and : : →(Actk), (Act^k), : : ×Actk→() ×Act^k (Mem) are functions defining the next actions taken by the agents and the associated memory update. We require that for all γ∈γ and α∈Actkα ^k such that (γ)(α)>0next(γ)(α)>0, we have that the action αi _i is enabled in the underlying state sis_i of the configuration γ for all i∈1,…,ki∈\1,…,k\. Note that the choice of the next tuple of actions is randomized. The current memory state is updated according to the current configuration and the chosen tuple of actions. We say that σ is deterministic if next and update use only Dirac distributions. Furthermore, we say that σ is finite-memory if the underlying set Mem is finite, and memoryless if Mem is a singleton. Note that if σ is memoryless, then update is trivial and next can be seen as a function Sk→(Actk)S^k (Act^k). Slightly abusing our notation, we formally define memoryless strategies as functions σ:Sk→(Actk)σ:S^k (Act^k), i.e., we avoid using the next and update functions completely. An autonomous strategy profile for k agents is defined as a k-tuple π=(σ1,…,σk)π=( _1,…, _k) where every σi _i is a coordinated strategy for one agent (see above). Since each σi _i controls only the agent i, the behaviour of each agent is completely autonomous. We use i=S×iConf_i=S×Mem_i to denote the set of all configurations of agent i, where iMem_i is the set of memory states of σi _i. We say that π is finite-memory or memoryless if every iMem_i is finite or a singleton, respectively. Random Variable MHit. Let M=(S,Act,P)M=(S,Act,P) be an MDP, k≥1k≥ 1 the number of agents, and let ιi∈S _i∈ S, Ti⊆ST_i S be the initial/target states of agent i for every i∈1,…,ki∈\1,…,k\. Let σ=(μ,,)σ=(μ,next,update) be a strategy for k agents, and let =(ι1,…,ιk,μ)init=( _1,…, _k,μ) be the initial configuration. We define a Markov chain Mσ=(,Aσ)M_σ=(Conf,A_σ) where the stochastic matrix AσA_σ is defined as follows: for all γ,δ∈γ,δ such that γ=(s1,…,sk,n)γ=(s_1,…,s_k,n) and δ=(t1,…,tk,m)δ=(t_1,…,t_k,m), we put Aσ(γ,δ)=∑α∈Actk(γ)(α)⋅(γ,α)(m)⋅∏i=1kP(si,αi,ti).A_σ(γ,δ)= _α ^knext(γ)(α)·update(γ,α)(m)· _i=1^kP(s_i, _i,t_i)\,. Let MHit:→ℕ∞MHit:Run_init _∞ be a random variable over the runs in MσM_σ initiated in init such that MHit(ω)MHit(ω) is either the least j∈ℕj such that ω(j)i∈Tiω(j)_i∈ T_i for some i∈1,…,ki∈\1,…,k\, or ∞ if there is no such j. We use σ[MHit]E_σ[MHit] to denote the expected value of MHit. Hence, if the agents are controlled by σ, the expected number of actions executed before some agent visits a target state is equal to σ[MHit]E_σ[MHit]. Now consider an autonomous strategy profile π=(σ1,…,σk)π=( _1,…, _k) for k agents. For every i∈1,…,ki∈\1,…,k\, let μi _i be the initial memory state of σi _i and i=(ιi,μi)init_i=( _i, _i) the initial configuration of agent i. Each σi _i determines a Markov chain MσiM_ _i and the probability space over iRun_init_i in the way described above. Let ProbπProb_π be the probability measure in the product probability space over the set 1×⋯×kRun_init_1×·s×Run_init_k of all multiruns. Slightly overloading our notation, we define a random variable MHit over the multiruns such that MHit(ω1,…,ωk)MHit( _1,…, _k) is either the least j∈ℕj such that ωi(j)∈Ti×i _i(j)∈ T_i×Mem_i for some i∈1,…,ki∈\1,…,k\, or ∞ if there is no such j. We use π[MHit]E_π[MHit] to denote the expected value of MHit. Hence, if the agents move according to the profile π, then π[MHit]E_π[MHit] is the expected number of actions executed before some agent visits a target state. Multiagent Stochastic Shortest Path (MSSP) Problem. In this work, we study the Coordinated and Autonomous MSSP problems. In both cases, a problem instance consists of • an MDP M=(S,Act,P)M=(S,Act,P), • an integer k≥1k≥ 1 (the number of agents), • initial/target states ιi∈S _i∈ S, Ti⊆ST_i S such that ιi∉Ti≠∅ _i ∈ T_i≠ for every i∈1,…,ki∈\1,…,k\. The task is to construct a coordinated strategy σ (in the case of Coordinated MSSP) or an autonomous strategy profile π (in the case of Autonomous MSSP) for k agents minimizing the expected value of MHit. For a given ε≥0 ≥ 0, we say that σ∗σ^* and π∗π^* are ε -optimal if σ∗[MHit]E_σ^*[MHit] and π∗[MHit]E_π^*[MHit] are ε -close to infσ[MHit] _σE_σ[MHit] and infπ[MHit] _πE_π[MHit], where σ and π range over all coordinated strategies and autonomous strategy profiles for k agents, respectively. 0-optimal σ∗σ^* and π∗π^* are called optimal. Price of Autonomy. For every MSSP instance, the price of autonomy is defined as the ratio of infπ[MHit] _πE_π[MHit] to infσ[MHit] _σE_σ[MHit] f. Hence, the price of autonomy measures the benefits of coordination for a given MSSP instance, where higher value means higher benefits. 3 The Complexity of MSSP In this section, we analyze the computational/strategy complexity of the Coordinated and Autonomous MSSP problems. Single-Agent Case. We begin by recalling known results about the single-agent case, i.e., the SSP problem (see, e.g., Puterman (1994))). Let M=(S,Act,P)M=(S,Act,P) be an MDP, k=1k=1 the number of agents, ι∈S ∈ S an initial state and T⊆ST S a set of target states such that ι∉T≠∅ ∈ T≠ . We have the following: (a) There exists an optimal memoryless deterministic strategy for the agent computable in polynomial time by the LP of Fig. 2. (b) For a given memoryless strategy σ for one agent, we have that σ[MHit]E_σ[MHit] is computable in polynomial time by solving the system of linear equations of Fig. 3. More precisely, let SℛS_R be the maximal C⊆SC S satisfying the following conditions: • if s∈Cs∈ C, then there is t∈Tt∈ T reachable from s, • if s∈C∖Ts∈ C T, then there is a∈En(s)a (s) such that t∈Ct∈ C for all t∈St∈ S where P(s,a,t)>0P(s,a,t)>0. Furthermore, for every s∈Sℛs∈ S_R, we use Enℛ(s)En_R(s) to denote the set of all a∈En(s)a (s) such that P(s,a,t)>0P(s,a,t)>0 implies t∈Sℛt∈ S_R. If ι∉Sℛ ∈ S_R, then the expected time of visiting a target configuration from the initial configuration is infinite for every strategy σ. Otherwise, let xs∗x_s^*, s∈Sℛs∈ S_R be the solution to the LP of Fig. 2, and let σ∗σ^* be a memoryless deterministic strategy where σ∗(s)(a)=1σ^*(s)(a)=1 for an action a∈En(s)a (s) such that xs∗=1+∑t∈SℛP(s,a,t)⋅xt∗x_s^*=1+ _t∈ S_RP(s,a,t)· x_t^*. Then σ∗σ^* is optimal and σ∗[MHit]=xι∗E_σ^*[MHit]=x_ ^*. The set SσS_σ used in the system of Fig. 3 is the maximal C⊆SC S such that • if s∈Cs∈ C, then a state of T can be reached from s with positive probability in the Markov chain MσM_σ, • if s∈C∖Ts∈ C T, σ(s)(a)>0σ(s)(a)>0, and P(s,a,t)>0P(s,a,t)>0, then t∈Ct∈ C. If ι∉Sσ ∈ S_σ, then σ[MHit]=∞E_σ[MHit]=∞. Otherwise, σ[MHit]=yι∗E_σ[MHit]=y^*_ , where ys∗y^*_s, s∈Sσs∈ S_σ is the unique solution of the system of linear equations of Fig. 3. maximize∑s∈Sℛxssubject toxs=0,s∈T,xs≤1+∑t∈SℛP(s,a,t)⋅xt, ∈s∖SRT, ∈aEnR(s) array[]lmaximize& Σ _s∈ S_Rx_s&\\[11.62495pt] subject to&x_s=0,&s∈ T,\\[3.87498pt] & x_s≤ 1+ _t∈ S_RP(s,a,t)· x_t,& [t]46.2497pt$s∈ S_R T$,\\ $a _R(s)$ array Figure 2: A linear program for computing an optimal strategy for a single agent. ys=0s∈T,ys=1+∑a∈En(s)(σ(s)(a)⋅∑t∈TP(s,a,t)⋅yt)s∈Sσ∖T array[]ly_s=0&s∈ T,\\[3.87498pt] y_s=1+ _a (s) (σ(s)(a)· _t∈ TP(s,a,t)· y_t )&s∈ S_σ T array Figure 3: A system of linear equations evaluating a given memoryless strategy σ for one agent. Coordinated MSSP Problem. The problem of constructing an optimal coordinated strategy for k≥1k≥ 1 agents is easily reducible to the SSP problem discussed above. For an MSSP instance M=(S,Act,P)M=(S,Act,P), k, ιi _i, TiT_i where i∈1,…,ki∈\1,…,k\, we construct an SSP instance consisting of an MDP M′=(Sk,Actk,P′)M =(S^k,Act^k,P ) where P′((s1,…,sk),(a1,…,ak),(t1,…,tk))=∏i=1kP(si,ai,ti),P ((s_1,…,s_k),(a_1,…,a_k),(t_1,…,t_k))= _i=1^kP(s_i,a_i,t_i), the initial state is (ι1,…,ιk)( _1,…, _k), and the target states are all (t1,…,tk)∈Sk(t_1,…,t_k)∈ S^k such that ti∈Tit_i∈ T_i for some i∈1,…,ki∈\1,…,k\. There is a natural one-to-one correspondence between memoryless coordinated strategies for k agents in M and memoryless strategies for one agent in M′M , and this correspondence preserves the expected value of MHit. Hence, an optimal coordinated strategy for k agents in M corresponds to an optimal strategy for one agent in M′M computable by the LP of Fig. 2. Observe that the size of this LP is polynomial in the size of M and exponential in k. We obtain the following: Theorem 1. For every MSSP instance, there exists an optimal memoryless deterministic coordinated strategy computable in time polynomial in the size of the MDP M and exponential in the number of agents k. For every fixed k the strategy is computable in polynomial time. In the following, the above described algorithm for computing an optimal memoryless deterministic strategy for a given MSSP instance is referred to as CoorHit. Now we show that the exponential blowup in k is unavoidable (assuming ≠ P≠ PSPACE), because the Coordinated MSSP problem is PSPACE-hard. More precisely, we have the following: Theorem 2. Let M, k, ιi _i, TiT_i where 1≤i≤k1≤ i≤ k be an MSSP instance and B a rational bound. The problem of whether there is a coordinated strategy σ for k agents s.t. σ[MHit]≤BE_σ[MHit]≤ B is PSPACE-hard. A proof of Theorem 2 is non-trivial and can be found in the Supplementary material. Autonomous MSSP Problem. We start by observing that optimal autonomous profiles exist and may require strategies with memory of arbitrarily large size. The class of all autonomous strategy profiles is denoted by Π . Furthermore, for every n≥1n≥ 1, we use Πn _n to denote the class of all profiles π=(σ1,…,σk)π=( _1,…, _k) such that the underlying iMem_i of every σi _i contains at most n memory states. In particular, Π1 _1 is the class of all memoryless profiles. Recall that π∗π^* is optimal if π∗[MHit]=infπ∈Ππ[MHit]E_π^*[MHit]= _π∈ E_π[MHit]. Furthermore, we say that π∗π^* is Πn _n-optimal if π∗∈Πnπ^*∈ _n and π∗[MHit]=infπ∈Πnπ[MHit]E_π^*[MHit]= _π∈ _nE_π[MHit]. Note that the existence of an optimal and a Πn _n-optimal profile is not immediately clear. It is established in the next theorem. Theorem 3. For every MSSP instance, there exist an optimal profile and a Πn _n-optimal profile for every n≥1n≥ 1. The existence of an optimal profile is proven by repeatedly selecting converging subsequences of distributions occurring in an infinite sequence of profiles π1,π2,… _1, _2,… such that limi→∞πi[MHit]=infπ′∈Ππ′[MHit] _i→∞E_ _i[MHit]= _π ∈ E_π [MHit]. A similar technique is used to prove the existence of a Πn _n-optimal profile. The details are in the Supplementary material. Now we show that optimal autonomous profiles may require strategies with memory of arbitrarily large size. However, for every ε>0 >0, there exists an ε -optimal profile with finite memory. Theorem 4. For every n≥1n≥ 1, there exist an instance of the Automonous MSSP problem with two agents and a profile π∈Πn+1π∈ _n+1 such that π[MHit]<infπ′∈Πnπ′[MHit]E_π[MHit]< _π ∈ _nE_π [MHit]. Furthermore, for every instance of the Automonous MSSP problem with k agents and every ε>0 >0 there exists an ε -optimal finite-memory profile. Furthermore, in the Supplementary material we show that randomized profiles are strictly more powerful than deterministic profiles when the agents use memory of a given size. Now we analyze the computational complexity of Autonomous MSSP. The next theorem says that the problem of computing a profile π∈Πnπ∈ _n for an MDP M minimizing π[MHit]E_π[MHit] can be efficiently reduced to the problem of computing a memoryless profile π¯ π minimizing π¯[MHit]E_ π[MHit] in an effectively constructible MDP M¯ M. Theorem 5. Let M=(S,Act,P)M=(S,Act,P) be an MDP, k≥1k≥ 1, and Mem a set of memory states of size n≥1n≥ 1. Then there is an MDP M¯=(S×,Act×,P¯) M=(S×Mem,Act×Mem, P) such that • for every profile π=(σ1,…,σk)π=( _1,…, _k) for M where every σi _i is a strategy with memory Mem, there exists a memoryless profile π¯=(σ¯1,…,σ¯k) π=( σ_1,…, σ_k) for M¯ M such that the Markov chains MσiM_ _i and M¯σ¯i M_ σ_i are identical for every i∈1,…,ki∈\1,…,k\, • for every memoryless profile π¯=(σ¯1,…,σ¯k) π=( σ_1,…, σ_k) for M¯ M, there exists a profile π=(σ1,…,σk)π=( _1,…, _k) for M where every σi _i is a strategy with memory Mem such that the Markov chains M¯σ¯i M_ σ_i and MσiM_ _i are identical for every i∈1,…,ki∈\1,…,k\. Intuitively, the MDP M¯ M is obtained from M by encoding the elements of Mem into the states of M¯ M. Hence, instead of synthesizing a finite-memory profile for M, we may synthesize a memoryless profile π¯ π for M¯ M and then “translate” π¯ π into a finite-memory profile for M so that π¯[MHit]E_ π[MHit] in M¯ M is equal to π[MHit]E_π[MHit] in M. In other words, the algorithmic core of the MSSP problem is the synthesis of memoryless profiles. Unfortunately, the synthesis problem is NP-hard even for two agents and memoryless profiles. Theorem 6. Let M be an MDP and ιi _i, TiT_i where i∈1,2i∈\1,2\ initial/target states for two agents. Let B be a rational bound. The problem of whether there exists an autonomous strategy profile π for two agents such that π[MHit]≤BE_π[MHit]≤ B is NP-hard. The problem is NP-hard even if the class of admissible profiles is restricted to memoryless profiles. A proof is obtained by a tricky reduction from a variant of the Boolean satisfiability problem, see the Supplementary material. Finally, we show that the price of autonomy can be arbitrarily large, even for two agents. Theorem 7. For every B∈ℕB , there exists an MSSP instance with two agents such that the price of autonomy is at least B. 4 Minimizing π[MHit]E_π[MHit] The results of the previous section show that the problem of computing an optimal coordinated strategy for a given MSSP instance is fixed-parameter tractable in the number of agents k. However, there is no straightforward algorithmic solution for the Autonomous MSSP. In this section, we address this challenge by designing AutoHit, an efficient profile synthesis algorithm for the Autonomous MSSP. We begin by summarizing the principle limitations. Due to Theorems 4 and 5, we can safely restrict our attention to the synthesis of memoryless profiles. Since synthesizing optimal memoryless profiles is NP-hard even for two agents (see Theorem 6), it cannot be done efficiently unless = P= NP. Hence, efficiency inevitably leads to losing optimality guarantees. Furthermore, the synthesis should not be limited to deterministic profiles because randomized profiles are strictly more powerful (see the remarks after Theorem 4). On the other hand, the synthesis may take advantage of the explicit MDP representation by analyzing and utilizing relevant structural properties of M. The design of AutoHit reflects these observations. We start by designing an efficient evaluation procedure computing π[MHit]E_π[MHit] for a given memoryless profile π. Note that a naive evaluation based on constructing a product Markov chain and solving the linear system of Fig. 3 is exponential in k. A more efficient procedure is given below. For the rest of this section, we fix an MSSP instance consisting of an MDP M=(S,Act,P)M=(S,Act,P), k≥1k≥ 1, and ιi∈S _i∈ S, Ti⊆ST_i S for every i∈1,…,ki∈\1,…,k\. Evaluating Memoryless Profiles. Let π=(σ1,…,σk)π=( _1,…, _k) be a memoryless profile. Recall that each σi _i is formally a function S→(Act)S (Act) and determines a Markov chain Mσi=(S,Ai)M_ _i=(S,A_i). For the sake of clarity, we use HitiHit_i to denote a random variable over the runs of MσiM_ _i such that Hiti(ω)Hit_i(ω) is either the least j∈ℕj such that ω(j)∈Tiω(j)∈ T_i, or ∞ if there is no such j. Since the agents are independent, we have that π[MHit]=∑ℓ=1∞Probπ[MHit≥ℓ]=∑ℓ=1∞∏i=1kProbιi[Hiti≥ℓ]E_π[MHit]\ =\ _ =1^∞Prob_π[MHit≥ ]\ =\ _ =1^∞ _i=1^kProb_ _i[Hit_i≥ ] (1) For every i∈1,…,ki∈\1,…,k\, we fix a target state τi∈Ti _i∈ T_i and define a transition matrix A¯i A_i obtained from AiA_i by changing τi _i into a sink and modifying transitions ending in a state of TiT_i so that they end in τi _i. More precisely, we put • A¯i(s,t)=Ai(s,t) A_i(s,t)=A_i(s,t) for all s,t∉Tis,t ∈ T_i, • A¯i(s,τi)=∑t∈TiAi(s,t) A_i(s, _i)= _t∈ T_iA_i(s,t) for all s∉Tis ∈ T_i, • A¯i(s,t)=0 A_i(s,t)=0 for all s∉Tis ∈ T_i and t∈Ti∖τit∈ T_i \ _i\, • A¯i(t,t)=1 A_i(t,t)=1, and A¯i(t,s)=0 A_i(t,s)=0 for all t∈Tit∈ T_i and s≠ts≠ t. Then, for every ℓ≥0 ≥ 0, we have that Probιi[Hiti≤ℓ]=A¯iℓ(ιi,τi)Prob_ _i[Hit_i≤ ]= A_i ( _i, _i) where A¯i0 A_i^0 is the identity matrix. Hence, Probιi[Hiti≥ℓ]=1−A¯iℓ−1(ιi,τi)Prob_ _i[Hit_i≥ ]=1- A_i -1( _i, _i) (2) for all ℓ≥1 ≥ 1, and thus we obtain π[MHit]=∑ℓ=1∞∏i=1k(1−A¯iℓ−1(ιi,τi))E_π[MHit]\ =\ _ =1^∞ _i=1^k (1- A_i -1( _i, _i) ) (3) Since (3) is an infinite sum, it is not algorithmically workable. Therefore, we also consider a truncated version of (3) where the range of ℓ is restricted to 1,…,γ\1,…,γ\ for a suitable constant γ∈ℕγ . Formally, we define ⟨γ⟩π[MHit]=∑ℓ=1γ∏i=1k(1−A¯iℓ−1(ιi,τi))E γ _π[MHit]\ =\ _ =1^γ _i=1^k (1- A_i -1( _i, _i) ) (4) Note that ⟨γ⟩π[MHit]E γ _π[MHit] is computable in time polynomial in k, γ, and the size of M. Furthermore, we show that for every ε>0 >0, there is efficiently computable γε _ such that π[MHit]−⟨γε⟩π[MHit]≤εE_π[MHit]-E _ _π[MHit]≤ . Thus, the value of π[MHit]E_π[MHit] can be efficiently ε -approximated by evaluating the right-hand side of (4). The constant γε _ is computed as follows. Recall that for every i∈1,…,ki∈\1,…,k\, the value of σi[Hiti]E_ _i[Hit_i] is computable in polynomial time by solving the system of linear equations of Fig. 3. For a given ϱ∈ℕ , we put δ⟨ϱ⟩i=σi[Hiti]−∑ℓ=1ϱ(1−A¯iℓ−1(ιi,τi)).δ _i=E_ _i[Hit_i]- _ =1 (1- A -1_i( _i, _i))\,. Furthermore, let Xi=1,…,k∖iX_i=\1,…,k\ \i\. Then π[MHit]−⟨ϱ⟩π[MHit]≤δ⟨ϱ⟩i⋅∏j∈Xi(1−A¯jϱ(ιj,τj))E_π[MHit]-E _π[MHit]\ ≤\ δ _i· _j∈ X_i(1- A _j( _j, _j)) (5) Note that (5) follows immediately from definitions and the fact that A¯jℓ(ιj,τj)≥A¯jϱ(ιj,τj) A _j( _j, _j)≥ A _j( _j, _j) for all ℓ≥ϱ ≥ . Hence, γε _ can be set to the least ϱ such that the right-hand side of (5) is bounded by ε for some i∈1,…,ki∈\1,…,k\. Since the right-hand side of (5) decreases exponentially in ϱ , the value of γε _ is small for most instances. Representing Memoryless Profiles. Now we show how to represent memoryless strategies by vectors of real-valued parameters so that ⟨γ⟩π[MHit]E γ _π[MHit] becomes a differentiable function of these parameters. Let i∈1,…,ki∈\1,…,k\ be an agent index. For all s∈Ss∈ S and a∈En(s)a (s), we fix a fresh parameter (variable) Xi,s,aX_i,s,a ranging over ℝR. We use PariPar_i to denote the vector of all Xi,s,aX_i,s,a. Furthermore, for every s∈Ss∈ S, we use Pari,sPar_i,s to denote the vector of all Xi,s,aX_i,s,a where a∈En(s)a (s). Let SoftMax be the standard softmax function transforming a vector of real values into a probability distribution, i.e., a vector of the same dimension over (0,1](0,1] whose sum is equal to one. The values of PariPar_i represent a memoryless strategy i σ_i such that i(s)(a)=SoftMax(Pari,s)(a) σ_i(s)(a)= SoftMax(Par_i,s)(a) for every a∈En(s)a (s). In other words, for every s∈Ss∈ S, the values of Pari,sPar_i,s are transformed into a probability distribution over En(s)En(s) using SoftMax. Note that i σ_i can be seen as a function of PariPar_i. We also use ¯i A_i and ¯iℓ A_i to denote the matrices A¯i A_i and A¯iℓ A_i determined by i σ_i (see the previous paragraphs). Again, ¯i A_i and ¯iℓ A_i are seen as functions of PariPar_i. More concretely, for all s,t∈Ss,t∈ S, the element ¯iℓ(s,t) A_i (s,t) is a function of PariPar_i involving SoftMax, multiplication, addition, and some constants. Note that ¯iℓ(s,t) A_i (s,t) is differentiable. Let Par1,…,ParkPar_1,…,Par_k be parameters whose values represent a memoryless profile =(1,…,k) π=( σ_1,…, σ_k) in the way described above. We use ⟨⟩[MHit] E γ _π[MHit] to denote the value of ⟨γ⟩π[MHit]E γ _π[MHit] for the profile π. Note that ⟨⟩[MHit] E γ _π[MHit] is a differentiable function of Par1,…,ParkPar_1,…,Par_k. Algorithm 1 The AutoHit Synthesis Algorithm 1:Inputs: 2: MDP M=(S,Act,P)M=(S,Act,P), the number of agents k≥1k≥ 1, ιi∈S _i∈ S, Ti⊆ST_i S for all i∈1,…,ki∈\1,…,k\ 3:Outputs: 4: A memoryless profile π for M and k agents Val such that π[MHit]−ε≤Val≤π[MHit]E_π[MHit]- _π[MHit] 5:Numerical hyperparameters: 6: Steps,ε,γSteps, ,γ 7:Par1,…,Park←InitParams(M,k)Par_1,…,Par_k← InitParams(M,k) 8:for all ∈1,…,Stepsindex∈\1,…,Steps\ do 9: grad←∇⟨⟩[MHit](Par1,…,Park)grad←∇\, E γ _π[MHit](Par_1,…,Par_k) 10: Par1,…,Park←Optimize(grad,Par1,…,Park)Par_1,…,Par_k← Optimize(grad,Par_1,…,Par_k) 11:Val←Evaluate(,ε)Val← Evaluate( π, ) 12:return π, Val AutoHit Algorithm. The AutoHit algorithm (Algorithm 1) is based on minimizing ⟨⟩[MHit] E γ _π[MHit] by gradient descent from a suitable initial profile. More precisely, AutoHit starts by invoking an abstract function InitParams(M,k) InitParams(M,k) initializing the parameters Par1,…,ParkPar_1,…,Par_k to values representing an initial profile π0 _0 (line 7). In our experiments, π0 _0 is either a random profile or a precomputed profile (in the latter case, π0 _0 is computed by some efficient method based on analyzing the structure of M, see Section 5). For the random profile π0 _0, the value of each parameter Xi,s,aX_i,s,a is sampled from the normal distribution with expected value 0 and variance 11. The main optimization loop at lines 8–10 is terminated after Steps iterations, where Steps is a hyperparameter. In each step, the gradient of ⟨⟩[MHit] E γ _π[MHit] at Par1,…,ParkPar_1,…,Par_k is computed (line 9) and then passed to a gradient-based optimizer that computes modified parameter values (line 10). Our implementation uses PyTorch library Paszke et al. (2019) to compute the gradient, and Optimize(grad,Par1,…,Park) Optimize(grad,Par_1,…,Par_k) is implemented by Adam optimizer Kingma and Ba (2015). At line 11, the value of π[MHit]E_π[MHit] for the resulting profile π is computed up to the precision ε by the function Evaluate(,ε) Evaluate( π, ) whose implementation is described in the paragraph “Evaluating Memoryless Profiles” above. 5 Experiments Our experimental evaluation aims to answer the following fundamental research questions: What is the quality of strategies and strategy profiles synthesized by our CoorHit and AutoHit algorithms? What is the efficiency/scalability of these algorithms? We also aim to compare the quality of solutions obtained in the coordinated/autonomous setting (i.e., estimate the price of autonomy). Benchmarks. We designed a scalable family of benchmarks resembling cities with congestion at some crossroads. The benchmarks, parameterized by their length l and a “congestion factor” pcp_c, consist of states sx,ys_x,y for all 1≤x≤l1≤x≤l, 1≤y≤51≤y≤5 and actions left, ℎright, up, down. Each state is congested with probability pcp_c (to avoid bias towards specific instances, the subset of congested states is determined randomly). In non-congested states, the actions work as expected, moving the agent left, right, up, and down, respectively. In congested states, the actions work as expected only with probability p∈[18,12]p∈ [ 18, 12 ] and with probability 1−p1-p do not move the agent (i.e., they lead back to the same state). Thus, congested states model random delays at road segments. The goal is to reach the target state sl,3s_l,3 from s1,3s_1,3. Setup. We used a Linux machine with AMD Ryzen 7 PRO 5750G CPU and 32 GB of RAM. All experiments were executed without using GPUs. Each execution has wall clock time limit of 55 minutes. In all experiments, the hyperparameters are set to =1000Steps=1000 and ε=10−9 =10^-9. The hyperparameter γ is set to the number of states of the MDP. This ensures that each simple path from the initial state to the target state is reflected in the objective function111We also experimented with other values of γ, the results are available in the Supplementary material. ⟨⟩[MHit] E γ _π[MHit]. Results for AutoHit. For each l∈10,20,30,40,50l∈\10,20,30,40,50\, we generated 1010 random benchmarks with pc=0.2p_c=0.2. Thus, we considered 5050 benchmarks in total. As a baseline, we use the profile πLP _LP consisting of the optimal single-agent strategies obtained by solving the LP of Fig. 2. We ran AutoHit for every k∈1,5,10,15,20k∈\1,5,10,15,20\. All AutoHit executions took less than 8585 seconds of wall time, even for 2020 agents and grids with l=50l=50 containing 250250 states and 890890 actions. We executed AutoHit with two initial parameter settings representing a random profile πRND _ RND and a precomputed profile πRLP _ RLP which is a “randomized version” of πLP _ LP. Note that since πLP _ LP is deterministic, it cannot be precisely translated into the parameter values due to the use of SoftMax. Instead, each parameter Xi,s,aX_i,s,a representing πRLP _ RLP is sampled from the normal distribution with the expected value equal to 1010 or 0, depending on whether the strategy σi _i in the profile πLP _ LP selects the action a in s or not, respectively (the variance is 11). For each MSSP instance, we generate 55 randomly sampled versions of πRND _ RND and πRLP _ RLP, and we use ValRNDVal_ RND and ValRLPVal_ RLP to denote the average Val returned by AutoHit for these 55 versions of πRND _ RND and πRLP _ RLP, respectively. We compare ValRNDVal_ RND and ValRLPVal_ RLP against the baseline Base=Evaluate(πLP,ε)Base= Evaluate( _LP, ). Figure 4: We report the ValRND/BaseVal_ RND/Base (blue) and ValRLP/BaseVal_ RLP/Base (brown) ratios. The points below the line y=1y=1 correspond to benchmarks where the ratio is smaller than 11, i.e., the profiles computed by AutoHit outperform the baseline. The results are presented in Fig. 4. The value ValRNDVal_ RND is on average 97.5 % of Base and is even 81.9 % in some cases. For ValRLPVal_ RLP, this improves to 96.0 % on average and 81.8 % in the best case. Hence, AutoHit computes strategy profiles that outperform the baseline, decreasing the expected value of MHit by almost 20 % in some cases. When initialized with πRLP _ RLP, the profile computed by AutoHit outperforms the baseline in the vast majority of the benchmarks. We executed similar experiments also for another precomputed initial profile πSP _ SP consisting of strategies following a graph-theoretic shortest path in the MDP. However, the quality of the resulting profiles computed by AutoHit tends to be worse than for πRND _ RND and πRLP _ RLP. We refer to the Supplementary material for details. Figure 5: Average execution times of CoorHit (solid line) and AutoHit (dashed line). Results for CoorHit. Our CoorHit implementation is based on Gurobi Gurobi Optimization, LLC (2024) LP solver. Since CoorHit does not scale so well in the number of agents, we use smaller grids.We generated 1010 random benchmarks for each l between 33 and 1010. To ensure that there are some congested crossroads on the shortest path, we used pc=1p_c=1. We ran the algorithms with 22, 33, and 44 agents. The average runtimes of CoorHit and AutoHit (initialized with πRLP _ RLP profile) are shown in Fig. 5. Note that AutoHit scales significantly better than CoorHit, consistently with our theoretical results. For 44 agents, CoorHit did not terminate for any grid with l>3l>3 within 55 minutes. Hence, AutoHit is significantly more efficient than CoorHit. In the cases where both algorithms terminated, the expected values of MHit for the resulting strategies and strategy profiles differ by 0.010.01 on average and at most by 0.080.08. This shows that the price of autonomy is rather low in the considered benchmarks. 6 Conclusions Our initial study of the MSSP problem reveals the fundamental complexity barriers for designing efficient algorithmic solutions in both coordinated and autonomous setting. Our AutoHit algorithm successfully overcomes the barriers in the (more challenging) autonomous setting and produces high-quality solutions. For our randomly generated benchmarks, AutoHit consistently improves the expected value of MHit over the baseline πLP[MHit]E_ _ LP[MHit] where πLP _ LP is the profile consisting of optimal single-agent strategies. In some cases, this improvement is significant. This shows that despite the high computational complexity of the MSSP problem, there are efficient synthesis algorithms producing solutions outperforming the natural baseline πLP[MHit]E_ _ LP[MHit]. The questions whether a similarly efficient synthesis algorithm exists also for the coordinated setting and whether alternative approaches can lead to even better synthesis algorithms certainly deserve an adequate research effort left for future work. References [1] (2025) Advances in neural information processing systems (neurips 2025). Vol. 38, Curran Associates, Inc.. Cited by: U. Chavan, P. Trivedi, and H. Hemachandra (2025). M. Ahmadi, A. Dixit, J.W. Burdick, and A.D. Ames (2021) Risk-averse stochastic shortest path planning. See 20, p. 5199–5204. Cited by: §1. C. Baier, N. Bertrand, C. Dubslaff, D. Gburek, and O. Sankur (2018) Stochastic shortest paths and weight-bounded properties in Markov decision processes. See 24, p. 86–94. Cited by: §1. D.P. Bertsekas and J.N. Tsitsiklis (1991) An analysis of stochastic shortest path problems. Mathematics of Operations Research 16 (3), p. 580–595. Cited by: §1. U. Chavan, P. Trivedi, and H. Hemachandra (2025) Regret lower bounds for decentralized multi-agent stochastic shortest path problems. See 1, p. 173948–173992. Cited by: §1. L. de Alfaro (1999) Computing minimum and maximum reachability times in probabilistic systems. See 21, p. 66–81. Cited by: §1. G. Díaz-García, F. Bullo, and J.R. Marden (2023) Distributed Markov chain-based strategies for multi-agent robotic surveillance. IEEE Control Systems Letters 7, p. 2527–2532. Cited by: §1. J.H. Eaton and L.A. Zadeh (1962) Optimal pursuit strategies in discrete-state probabilistic systems. Journal of Basic Engineering 84 (1), p. 23–29. Cited by: §1. Gurobi Optimization, LLC (2024) Gurobi Optimizer Reference Manual. External Links: Link Cited by: §5. Ch. Haase and S. Kiefer (2015) The odds of staying on budget. See 22, p. 234–246. Cited by: §1. X. Jiang, X. Wang, H. Xi, and F. Liu (2017) Centralized optimization for Dec-POMDPs under the expected average reward criterion. IEEE Transactions on Automatic Control 62 (11), p. 6032–6038. Cited by: §1. M. Jonáš, A. Kučera, V. Kůr, and J. Mačák (2025) Steady-state strategy synthesis for swarms of autonomous agents. See 28, p. 135–142. Cited by: §1. D. P. Kingma and J. Ba (2015) Adam: a method for stochastic optimization. In Proceedings of ICLR 2015, Cited by: §4. D. Klaška, A. Kučera, M. Kurečka, P. Novotný, V. Musil, and V. Řehák (2023) Synthesizing resilient strategies for infinite-horizon objectives in multi-agent systems. See 27, p. 171–179. Cited by: §1. J. Křetínský and T. Meggendorfer (2018) Conditional value-at-risk for reachability and mean payoff in Markov decision processes. See 24, p. 609–618. Cited by: §1. S. Mannor and J.N. Tsitsiklis (2011) Mean-variance optimization in Markov decision processes. See 26, p. 177–184. Cited by: §1. F. Nawaz and M. Ornik (2023) Multiagent, multitarget path planning in Markov decision processes. IEEE Transactions on Automatic Control 68 (12), p. 7560–7574. Cited by: §1. A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala (2019) PyTorch: an imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, p. 8024–8035. External Links: Link Cited by: §4. J. Piribauer, O. Sankur, and C. Baier (2022) The variance-penalized stochastic shortest path problem. See 23, p. 129:1–129:19. Cited by: §1. [20] (2021) Proceedings of 60th ieee conference on decision and control (cdc 2021). IEEE Computer Society Press. Cited by: M. Ahmadi, A. Dixit, J.W. Burdick, and A.D. Ames (2021). [21] (1999) Proceedings of concur’99. Lecture Notes in Computer Science, Vol. 1664, Springer. Cited by: L. de Alfaro (1999). [22] (2015) Proceedings of icalp 2015. Lecture Notes in Computer Science, Vol. 9135, Springer. Cited by: Ch. Haase and S. Kiefer (2015). [23] (2022) Proceedings of icalp 2022. Leibniz International Proceedings in Informatics, Vol. 229, Schloss Dagstuhl–Leibniz-Zentrum für Informatik. Cited by: J. Piribauer, O. Sankur, and C. Baier (2022). [24] (2018) Proceedings of lics 2018. ACM Press. Cited by: C. Baier, N. Bertrand, C. Dubslaff, D. Gburek, and O. Sankur (2018), J. Křetínský and T. Meggendorfer (2018). [25] (2023) Proceedings of the 26th international conference on artificial intelligence and statistics (aistats) 2023. Cited by: P. Trivedi and N. Hemachandra (2023). [26] (2011) Proceedings of the 28th international conference on machine learning, icml 2011. Omnipress. Cited by: S. Mannor and J.N. Tsitsiklis (2011). [27] (2023) Proceedings of the international joint conference on artificial intelligence (ijcai 2023). Cited by: D. Klaška, A. Kučera, M. Kurečka, P. Novotný, V. Musil, and V. Řehák (2023). [28] (2025) Proceedings of the international joint conference on artificial intelligence (ijcai 2025). Cited by: M. Jonáš, A. Kučera, V. Kůr, and J. Mačák (2025). [29] (2015) Proceedings of vmcai 2015. Lecture Notes in Computer Science, Vol. 8931, Springer. Cited by: M. Randour, J.-F. Raskin, and O. Sankur (2015). M.L. Puterman (1994) Markov decision processes. Wiley. Cited by: §1, §3. M. Randour, J.-F. Raskin, and O. Sankur (2015) Variations on the stochastic shortest path problem. See 29, p. 1–18. Cited by: §1. A. Rosenberg (2022) Regret minimization in reinforcement learning. Ph.D. Thesis, Tel Aviv University, Israel. Cited by: §1. P. Trivedi and N. Hemachandra (2023) Multi-agent congestion cost minimization with linear function approximations. See 25, p. 7611–7643. Cited by: §1. L. Zhang, A. Prorok, and S. Bhattacharya (2021) Pursuer assignment and control strategies in multi-agent pursuit-evasion under uncertainties. Frontiers in Robotics and AI 8, p. 691637. Cited by: §1. Supplementary Material Appendix A Proof of Theorem 2 In this proof, we first show that a certain variant of the quantified Boolean formula problem (QBF) is PSPACE-hard. We then prove PSPACE-hardess of the Coordinated MSSP problem by reduction from that QBF variant. A truth assignment is a mapping from the set of all propositional variables Var=x0,x1,x2,…Var=\x_0,x_1,x_2,…\ to the set of truth values 0,1\0,1\. Every truth assignment is associated with a unique extended truth assignment, which is a mapping from the set of all (quantified) Boolean formulae to the set of truth values 0,1\0,1\. In this proof, we do not distinguish between a truth assignment and its corresponding extended truth assignment (we use the same symbol for both). Let ⊙ denote the ternary logical connective whose semantics is the indication of whether exactly one of the three parameters is true (e.g., ⊙(x1,x2,x3) (x_1,x_2,x_3) evaluates to 11 under a truth assignment ν′ν such that ν′(x1)=ν′(x2)=0ν (x_1)=ν (x_2)=0 and ν′(x3)=1ν (x_3)=1, but evaluates to 0 under a truth assignment ν′ν such that ν′(x1)=ν′(x2)=ν′(x3)=1ν (x_1)=ν (x_2)=ν (x_3)=1). The aforementioned QBF variant used in this proof restricts the input formulae to be of the form Q1x1Q2x2…QkxkφQ_1x_1Q_2x_2… Q_kx_k\ where each QiQ_i stands either for ∃ or ∀ and φ is a conjunction of subformulae of the form ⊙(xi1,xi2,xi3) (x_i_1,x_i_2,x_i_3) (all propositional variables occurring in φ are quantified). In the next two paragraphs, we prove PSPACE-hardness of this QBF variant by showing a simple polynomial-time reduction from another QBF variant where the input formulae are restricted to be of the form Q1x1Q2x2…QℓxℓψQ_1x_1Q_2x_2… Q_ x_ \ ψ for some Boolean formula ψ in 3-CNF (i.e., each clause of ψ has exactly three distinct literals). This QBF variant is known to be PSPACE-complete.222See Oijid, N. (2025). Bounded Degree QBF and Positional Games. In: Finocchi, I., Georgiadis, L. (eds) Algorithms and Complexity. CIAC 2025. Lecture Notes in Computer Science, vol 15680. Springer, Cham. https://doi.org/10.1007/978-3-031-92935-9_8 Let Ψ≡Q1x1Q2x2…Qℓxℓψ ≡ Q_1x_1Q_2x_2… Q_ x_ \ ψ be an arbitrary input formula of the latter QBF variant. Without restrictions, we assume that ψ contains no tautological clauses. We show how to efficiently transform Ψ to an equivalent formula Φ of the desired form. For each clause of ψ of the form (xi1∨xi2∨xi3)(x_i_1 x_i_2 x_i_3) (i.e., without negations), replace this clause by ⊙(x,y,w)∧⊙(y,z,w)∧⊙(z,x,w)∧⊙(xi1,x,ti1) (x,y,w) (y,z,w) (z,x,w) (x_i_1,x,t_i_1) ∧ ⊙(xi2,x,ti2)∧⊙(xi3,x,ti3)∧⊙(ti1,r,d) (x_i_2,x,t_i_2) (x_i_3,x,t_i_3) (t_i_1,r,d) ∧ ⊙(ti2,u,e)∧⊙(ti3,v,f)∧⊙(d,e,f) (t_i_2,u,e) (t_i_3,v,f) (d,e,f) where ti1t_i_1, ti2t_i_2, ti3t_i_3, w, x, y, z, r, u, v, d, e, f are fresh propositional variables, and append ∃ti1∃ti2∃ti3∃w∃x∃y∃z∃r∃u∃v∃d∃e∃f∃ t_i_1\ ∃ t_i_2\ ∃ t_i_3\ ∃ w\ ∃ x\ ∃ y\ ∃ z\ ∃ r\ ∃ u\ ∃ v\ ∃ d\ ∃ e\ ∃ f to the quantifier prefix of the formula. Proceed analogously also for clauses containing negative literals ¬xi x_i (for one or more i∈i1,i2,i3i∈\i_1,i_2,i_3\), but use xix_i instead of the last occurrence of tit_i in the subformula replacing the original clause: for example, the clause (x4∨¬x5∨¬x6)(x_4 x_5 x_6) is replaced by ⊙(x,y,w)∧⊙(y,z,w)∧⊙(z,x,w)∧⊙(x4,x,t4) (x,y,w) (y,z,w) (z,x,w) (x_4,x,t_4) ∧ ⊙(x5,x,t5)∧⊙(x6,x,t6)∧⊙(t4,r,d)∧⊙(x5,u,e) (x_5,x,t_5) (x_6,x,t_6) (t_4,r,d) (x_5,u,e) ∧ ⊙(x6,v,f)∧⊙(d,e,f) (x_6,v,f) (d,e,f) Obviously, the transformation described in the previous paragraph can be implemented by a polynomial-time algorithm (the length of the formula increases by at most a constant multiplicative factor) and the resulting formula Φ is of the desired form. Let ν:Var→0,1ν:Var→\0,1\ be an arbitrary truth assignment, let ξ denote the formula ⊙(x,y,w)∧⊙(y,z,w)∧⊙(z,x,w)∧⊙(xi1,x,ti1) (x,y,w) (y,z,w) (z,x,w) (x_i_1,x,t_i_1) ∧ ⊙(xi2,x,ti2)∧⊙(xi3,x,ti3)∧⊙(ti1,r,d) (x_i_2,x,t_i_2) (x_i_3,x,t_i_3) (t_i_1,r,d) ∧ ⊙(ti2,u,e)∧⊙(ti3,v,f)∧⊙(d,e,f) (t_i_2,u,e) (t_i_3,v,f) (d,e,f) and let ξ′ξ denote the formula ∃ti1∃ti2∃ti3∃w∃x∃y∃z∃r∃u∃v∃d∃e∃fξ.∃ t_i_1\ ∃ t_i_2\ ∃ t_i_3\ ∃ w\ ∃ x\ ∃ y\ ∃ z\ ∃ r\ ∃ u\ ∃ v\ ∃ d\ ∃ e\ ∃ f\ ξ\,. In order to show that the described transformation is equivalence-preserving, we are to prove that ν(xi1∨xi2∨xi3)=ν(ξ′)ν(x_i_1 x_i_2 x_i_3)=ν(ξ ) (the proof for the cases with negative literals is analogous). Let us first consider the case when ν(xi1∨xi2∨xi3)=0ν(x_i_1 x_i_2 x_i_3)=0, which implies that ν(xi1)=ν(xi2)=ν(xi3)=0ν(x_i_1)=ν(x_i_2)=ν(x_i_3)=0. Assume for the sake of contradiction that ν(ξ′)=1ν(ξ )=1. It follows that there exists a truth assignment μ such that μ(xi1)=ν(xi1)μ(x_i_1)=ν(x_i_1), μ(xi2)=ν(xi2)μ(x_i_2)=ν(x_i_2), μ(xi3)=ν(xi3)μ(x_i_3)=ν(x_i_3) and μ(ξ)=1μ(ξ)=1: let us fix any such μ. It is easy to observe that necessarily μ(w)=1μ(w)=1, μ(x)=μ(y)=μ(z)=0μ(x)=μ(y)=μ(z)=0 and thus μ(ti1)=μ(ti2)=μ(ti3)=1μ(t_i_1)=μ(t_i_2)=μ(t_i_3)=1, implying μ(d)=μ(e)=μ(f)=0μ(d)=μ(e)=μ(f)=0, which is in contradiction with μ(⊙(d,e,f))=1μ( (d,e,f))=1. Let us now consider the case when ν(xi1∨xi2∨xi3)=1ν(x_i_1 x_i_2 x_i_3)=1. Without loss of generality, we assume that ν(xi1)=1ν(x_i_1)=1 (the proof in the remaining two cases is analogous). We are to prove ν(ξ′)=1ν(ξ )=1. Let μ′μ be the variable assignment such that • μ′(w)=1μ (w)=1, • μ′(x)=μ′(y)=μ′(z)=0μ (x)=μ (y)=μ (z)=0, • μ′(ti1)=1−ν(xi1)=0μ (t_i_1)=1-ν(x_i_1)=0, • μ′(ti2)=1−ν(xi2)μ (t_i_2)=1-ν(x_i_2), • μ′(ti3)=1−ν(xi3)μ (t_i_3)=1-ν(x_i_3), • μ′(r)=0μ (r)=0, • μ′(d)=1μ (d)=1, • μ′(e)=μ′(f)=0μ (e)=μ (f)=0, • μ′(u)=ν(xi2)μ (u)=ν(x_i_2), • μ′(v)=ν(xi3)μ (v)=ν(x_i_3), • μ′(x′)=ν(x′)μ (x )=ν(x ) for all remaining variables x′x . It is easy to verify that μ′(ξ)=1μ (ξ)=1 and thus ν(ξ′)=1ν(ξ )=1, which was to be proved. For the rest of this proof, let us fix an input formula Φ≡Q1x1Q2x2…Qkxkφ ≡ Q_1x_1Q_2x_2… Q_kx_k\ , where φ≡(C1∧C2∧…∧Cn) ≡(C_1 C_2 … C_n) and each CjC_j is a subformula of the form ⊙(xi1,xi2,xi3) (x_i_1,x_i_2,x_i_3) (these subformulae are often understood as sets of three propositional variables in this proof). We describe a construction (implementable by a polynomial-time algorithm) of an instance of the MSSP problem for k agents and a rational bound B such that a coordinated strategy σ achieving σ[MHit]≤BE_σ[MHit]≤ B exists if and only if the formula Φ is true. Since there always exists an optimal coordinated strategy which is deterministic and memoryless (see the main body of the paper), we consider only memoryless strategies in this proof and we understand the term configuration simply as a k-tuple of states throughout the rest of this proof (completely omitting the memory state from the tuple). Our construction is based on an observation of a simple MSSP instance where three agents can choose between two actions enabled in their (shared) initial state. One choice causes the agent to reach the target state after exactly 22 steps (with probability 11). The other choice causes the agent to reach the target state after 11 step or after 44 steps with probability 0.50.5 for both eventualities. Optimal strategies are precisely those where (with probability 11) exactly one of the agents makes the first choice, whereas the remaining two agents make the second choice. Technical description of the whole construction follows. Let M=(S,Act,P)M=(S,Act,P) be an MDP where S S = = τ∪si,ℓ′∣1≤i≤k,1≤ℓ≤i \τ\∪\s _i, 1≤ i≤ k,1≤ ≤ i\ ∪ ∪ si,⊤,ℓ′∣1≤i≤k,i+1≤ℓ≤k+1 \s _i, , 1≤ i≤ k,i+1≤ ≤ k+1\ ∪ ∪ si,⊥,ℓ′∣1≤i≤k,i+1≤ℓ≤k+1 \s _i, , 1≤ i≤ k,i+1≤ ≤ k+1\ ∪ ∪ si,⊤,j′∣1≤i≤k,1≤j≤4n \s _i, ,j 1≤ i≤ k,1≤ j≤ 4n\ ∪ ∪ si,⊥,j′∣1≤i≤k,1≤j≤4n, \s _i, ,j 1≤ i≤ k,1≤ j≤ 4n\, Act = = ⊤,⊥ \ , \ and the transition function P is defined as follows: • P(τ,⊥,τ)=1P(τ, ,τ)=1; • P(si,ℓ′,⊥,si,ℓ+1′)=1P(s _i, , ,s _i, +1)=1 for all 1≤i≤k1≤ i≤ k and 1≤ℓ≤i−11≤ ≤ i-1; • P(si,i′,⊥,si,⊤,i+1′)=P(si,i′,⊥,si,⊥,i+1′)=12P(s _i,i, ,s _i, ,i+1)=P(s _i,i, ,s _i, ,i+1)= 12 for all 1≤i≤k1≤ i≤ k such that Qi≡∀Q_i≡∀; • P(si,i′,⊤,si,⊤,i+1′)=P(si,i′,⊥,si,⊥,i+1′)=1P(s _i,i, ,s _i, ,i+1)=P(s _i,i, ,s _i, ,i+1)=1 for all 1≤i≤k1≤ i≤ k such that Qi≡∃Q_i≡∃; • P(si,⊤,ℓ′,⊥,si,⊤,ℓ+1′)=P(si,⊥,ℓ′,⊥,si,⊥,ℓ+1′)=1P(s _i, , , ,s _i, , +1)=P(s _i, , , ,s _i, , +1)=1 for all 1≤i≤k1≤ i≤ k and i+1≤ℓ≤ki+1≤ ≤ k; • P(si,⊤,k+1′,⊥,si,⊤,1′)=P(si,⊥,k+1′,⊥,si,⊥,1′)=1P(s _i, ,k+1, ,s _i, ,1)=P(s _i, ,k+1, ,s _i, ,1)=1 for all 1≤i≤k1≤ i≤ k; • P(si,⊤,4n′,⊥,τ)=P(si,⊥,4n′,⊥,τ)=1P(s _i, ,4n, ,τ)=P(s _i, ,4n, ,τ)=1 for all 1≤i≤k1≤ i≤ k; • P(si,⊤,4j−3′,⊥,si,⊤,4j−2′)=P(si,⊤,4j−2′,⊥,si,⊤,4j−1′)=P(si,⊤,4j−1′,⊥,si,⊤,4j′)=P(si,⊥,4j−3′,⊥,si,⊥,4j−2′)=P(si,⊥,4j−2′,⊥,si,⊥,4j−1′)=P(si,⊥,4j−1′,⊥,si,⊥,4j′)=1P(s _i, ,4j-3, ,s _i, ,4j-2)=P(s _i, ,4j-2, ,s _i, ,4j-1)=P(s _i, ,4j-1, ,s _i, ,4j)=P(s _i, ,4j-3, ,s _i, ,4j-2)=P(s _i, ,4j-2, ,s _i, ,4j-1)=P(s _i, ,4j-1, ,s _i, ,4j)=1 for all 1≤i≤k1≤ i≤ k and 1≤j≤n1≤ j≤ n such that xi∉Cjx_i∉ C_j; • P(si,⊤,4j′,⊥,τ)=P(si,⊥,4j′,⊥,τ)=99100P(s _i, ,4j, ,τ)=P(s _i, ,4j, ,τ)= 99100, • P(si,⊤,4j′,⊥,si,⊤,4j+1′)=P(si,⊥,4j′,⊥,si,⊥,4j+1′)=1100P(s _i, ,4j, ,s _i, ,4j+1)=P(s _i, ,4j, ,s _i, ,4j+1)= 1100 for all 1≤i≤k1≤ i≤ k and 1≤j≤n−11≤ j≤ n-1 such that xi∉Cjx_i∉ C_j; • P(si,⊤,4j−3′,⊥,si,⊤,4j−2′)=P(si,⊤,4j−1′,⊥,si,⊤,4j′)=P(si,⊥,4j−2′,⊥,si,⊥,4j−1′)=P(si,⊥,4j−1′,⊥,si,⊥,4j′)=1P(s _i, ,4j-3, ,s _i, ,4j-2)=P(s _i, ,4j-1, ,s _i, ,4j)=P(s _i, ,4j-2, ,s _i, ,4j-1)=P(s _i, ,4j-1, ,s _i, ,4j)=1, • P(si,⊤,4j−2′,⊥,si,⊤,4j−1′)=1100P(s _i, ,4j-2, ,s _i, ,4j-1)= 1100, • P(si,⊤,4j−2′,⊥,τ)=99100P(s _i, ,4j-2, ,τ)= 99100, • P(si,⊥,4j−3′,⊥,τ)=99200P(s _i, ,4j-3, ,τ)= 99200, • P(si,⊥,4j−3′,⊥,si,⊥,4j−2′)=101200P(s _i, ,4j-3, ,s _i, ,4j-2)= 101200 for all 1≤i≤k1≤ i≤ k and 1≤j≤n1≤ j≤ n such that xi∈Cjx_i∈ C_j; • P(si,⊤,4j′,⊥,si,⊤,4j+1′)=1P(s _i, ,4j, ,s _i, ,4j+1)=1, • P(si,⊥,4j′,⊥,si,⊥,4j+1′)=2101P(s _i, ,4j, ,s _i, ,4j+1)= 2101, • P(si,⊥,4j′,⊥,τ)=99101P(s _i, ,4j, ,τ)= 99101 for all 1≤i≤k1≤ i≤ k and 1≤j≤n−11≤ j≤ n-1 such that xi∈Cjx_i∈ C_j; • the function P maps all the remaining triples to 0. For each i∈1,…,ki∈\1,…,k\, let Ti=τT_i=\τ\ be the set of target states and let si,1′s _i,1 be the initial state of agent i. Furthermore, let B=k+1+1.2601255⋅102nk−1102nk−102(n−1)k.B=k+1+1.2601255· 10^2nk-110^2nk-10^2(n-1)k\,. Observe that in the constructed MSSP instance, there is only the ⊥ action enabled in every state of the MDP M except for states si,i′s _i,i such that QiQ_i is an existential quantifier, where both actions ⊤ and ⊥ are enabled. After k steps from the beginning, agent i can be either in state si,⊤,k+1′s _i, ,k+1 or in state si,⊥,k+1′s _i, ,k+1. Which of these two possibilities will occur is decided in the i-th step, when the state of agent i changes from si,i′s _i,i to either si,⊤,i+1′s _i, ,i+1 or si,⊥,i+1′s _i, ,i+1. If QiQ_i is an existential quantifier, then the strategy can decide (by choosing either the action ⊤ or ⊥ for agent i) in the i-th step whether agent i will be in state si,⊤,k+1′s _i, ,k+1 or si,⊥,k+1′s _i, ,k+1 after k steps from the beginning. If QiQ_i is a universal quantifier, then such decision in the i-th step is made randomly (with probability 12 12 for both possibilities). Once every agent has made k steps from the beginning, the ⊤ action will not be enabled anymore. It follows that after k steps, the strategy starts to be completely irrelevant to the behaviour of the system and each agent starts to be fully independent (as in the Autonomous MSSP). After k steps from the beginning, the sequence of states visited by agent i must be either of the form si,⊤,k+1′,si,⊤,1′,si,⊤,2′,…,si,⊤,d′,τ,τ,…s _i, ,k+1,s _i, ,1,s _i, ,2,…,s _i, ,d,τ,τ,… or of the form si,⊥,k+1′,si,⊥,1′,si,⊥,2′,…,si,⊥,d′,τ,τ,…s _i, ,k+1,s _i, ,1,s _i, ,2,…,s _i, ,d,τ,τ,… for some d∈1,2,…,4nd∈\1,2,…,4n\. Let j∈1,…,nj∈\1,…,n\. Let us first assume j≠nj≠ n. The MDP M is designed in a way that whenever an agent visits the state si,⊤,4j−3′s _i, ,4j-3 (or si,⊥,4j−3′s _i, ,4j-3), then with probability 0.010.01 the agent reaches the state si,⊤,4j+1′=si,⊤,4(j+1)−3′s _i, ,4j+1=s _i, ,4(j+1)-3 (or si,⊥,4j+1′=si,⊥,4(j+1)−3′s _i, ,4j+1=s _i, ,4(j+1)-3, respectively) after exactly four next steps and with probability 0.990.99 the agent instead reaches the target state τ in at most four next steps: more specifically, if xi∉Cjx_i∉ C_j, then the agent visiting the state si,⊤,4j−3′s _i, ,4j-3 (or si,⊥,4j−3′s _i, ,4j-3) reaches the target state τ after exactly four next steps with probability 0.990.99, whereas if xi∈Cjx_i∈ C_j, then the agent visiting the state si,⊤,4j−3′s _i, ,4j-3 (or si,⊥,4j−3′s _i, ,4j-3) reaches the target τ after exactly two steps with probability 0.990.99 (or after exactly one step with probability 0.4950.495 and after exactly four steps with probability 0.4950.495, respectively). Let us now assume j=nj=n. The situation in the case j=nj=n is similar, but instead of reaching si,⊤,4(j+1)−3′s _i, ,4(j+1)-3 or si,⊥,4(j+1)−3′s _i, ,4(j+1)-3 (which are not states of the MDP M) from si,⊤,4j−3′s _i, ,4j-3 or si,⊥,4j−3′s _i, ,4j-3 in exactly four steps, the agent reaches the target state τ in exactly four steps (the probability of the latter event is thus increased by 0.010.01). Let μ:Var→0,1μ:Var→\0,1\ be an arbitrary truth assignment. Let μ¯ μ denote the configuration in which the state visited by each agent i is equal to si,⊤,k+1′s _i, ,k+1 if μ(xi)=1μ(x_i)=1 or equal to si,⊥,k+1′s _i, ,k+1 if μ(xi)=0μ(x_i)=0 (this configuration can occur after exactly k steps from the beginning in the constructed MSSP instance). Let random variable MHitμMHit_μ be the number of steps taken until the target τ is first reached by some agent from the configuration μ¯ μ. Similarly, let random variable HitμiHit_μ^i be the number of steps taken until the target τ is first reached by agent i from the configuration μ¯ μ (for all i∈1,…,ki∈\1,…,k\). Let us inspect the expected value of MHitμMHit_μ, denoted by [MHitμ]E[MHit_μ]. [MHitμ] [MHit_μ] = = ∑ℓ=0∞ℓ⋅Prob[MHitμ=ℓ]=∑ℓ=0∞Prob[MHitμ>ℓ] _ =0^∞ ·Prob[MHit_μ= ]= _ =0^∞Prob[MHit_μ> ] = = Prob[MHitμ>0]+∑ℓ=14nProb[MHitμ>ℓ] [MHit_μ>0]+ _ =1^4nProb[MHit_μ> ] = = 1+∑j=1nProb[MHitμ>4j−3] 1+ _j=1^nProb[MHit_μ>4j-3] +∑j=1nProb[MHitμ>4j−2] + _j=1^nProb[MHit_μ>4j-2] +∑j=1nProb[MHitμ>4j−1] + _j=1^nProb[MHit_μ>4j-1] +∑j=1nProb[MHitμ>4j]. + _j=1^nProb[MHit_μ>4j]. Using independence, we get that Prob[MHitμ>ℓ]=∏i=1kProb[Hitμi>ℓ]Prob[MHit_μ> ]= _i=1^kProb[Hit_μ^i> ] for all ℓ∈ℕ . The previously described properties allow us to derive the following: Prob[Hitμi>4j−3] [Hit_μ^i>4j-3] = = Prob[Hitμi>4j−2] [Hit_μ^i>4j-2] = = Prob[Hitμi>4j−1] [Hit_μ^i>4j-1] = = Prob[Hitμi>4j] [Hit_μ^i>4j] = = 0.01j−1 0.01^j-1 for all 1≤i≤k1≤ i≤ k and 1≤j≤n1≤ j≤ n such that xi∉Cjx_i∉ C_j. Furthermore, Prob[Hitμi>4j−3] [Hit_μ^i>4j-3] = = Prob[Hitμi>4j−2] [Hit_μ^i>4j-2] = = 0.01j−1, 0.01^j-1, Prob[Hitμi>4j−1] [Hit_μ^i>4j-1] = = Prob[Hitμi>4j] [Hit_μ^i>4j] = = 0.01j=0.01j−1⋅0.01 0.01^j=0.01^j-1· 0.01 for all 1≤i≤k1≤ i≤ k and 1≤j≤n1≤ j≤ n such that xi∈Cjx_i∈ C_j and μ(xi)=1μ(x_i)=1. Finally, Prob[Hitμi>4j−3] [Hit_μ^i>4j-3] = = 0.01j−1, 0.01^j-1, Prob[Hitμi>4j−2] [Hit_μ^i>4j-2] = = Prob[Hitμi>4j−1] [Hit_μ^i>4j-1] = = Prob[Hitμi>4j] [Hit_μ^i>4j] = = 0.01j−1⋅0.505 0.01^j-1· 0.505 for all 1≤i≤k1≤ i≤ k and 1≤j≤n1≤ j≤ n such that xi∈Cjx_i∈ C_j and μ(xi)=0μ(x_i)=0. In the following part of this proof, we show that [MHitμ]≥B−kE[MHit_μ]≥ B-k, where [MHitμ]=B−kE[MHit_μ]=B-k if and only if μ(φ)=1μ( )=1. Let us first assume that μ(φ)=1μ( )=1. Recall that for every j∈1,2,…,nj∈\1,2,…,n\ there are exactly three values of i such that xi∈Cjx_i∈ C_j, where for exactly one such i we have that μ(xi)=1μ(x_i)=1. Hence, we obtain Prob[MHitμ>4j−3] [MHit_μ>4j-3] = = ∏i=1kProb[Hitμi>4j−3] _i=1^kProb[Hit_μ^i>4j-3] = = 0.01(j−1)k, 0.01^(j-1)k, Prob[MHitμ>4j−2] [MHit_μ>4j-2] = = ∏i=1kProb[Hitμi>4j−2] _i=1^kProb[Hit_μ^i>4j-2] = = 0.01(j−1)k⋅0.5052, 0.01^(j-1)k· 0.505^2, Prob[MHitμ>4j−1] [MHit_μ>4j-1] = = Prob[MHitμ>4j] [MHit_μ>4j] = = ∏i=1kProb[Hitμi>4j−1] _i=1^kProb[Hit_μ^i>4j-1] = = 0.01(j−1)k⋅0.01⋅0.5052 0.01^(j-1)k· 0.01· 0.505^2\, for every j∈1,2,…,nj∈\1,2,…,n\. We can now infer the following: [MHitμ] [MHit_μ] = = 1+∑j=1nProb[MHitμ>4j−3] 1+ _j=1^nProb[MHit_μ>4j-3] +∑j=1nProb[MHitμ>4j−2] + _j=1^nProb[MHit_μ>4j-2] +∑j=1nProb[MHitμ>4j−1] + _j=1^nProb[MHit_μ>4j-1] +∑j=1nProb[MHitμ>4j] + _j=1^nProb[MHit_μ>4j] = = 1+∑j=1n0.01(j−1)k(1+0.5052+ 1+ _j=1^n0.01^(j-1)k(1+0.505^2+ 0.01⋅0.5052+0.01⋅0.5052) 0.01· 0.505^2+0.01· 0.505^2) = = 1+1.2601255∑j=1n0.01(j−1)k 1+1.2601255 _j=1^n0.01^(j-1)k = = 1+1.2601255⋅102nk−1102nk−102(n−1)k 1+1.2601255· 10^2nk-110^2nk-10^2(n-1)k = = B−k. B-k\,. Let us now assume that μ(φ)=0μ( )=0. Our aim is to show that [MHitμ]>B−kE[MHit_μ]>B-k. We first show that [MHitμ] [MHit_μ] = = 1+∑j=1nProb[MHitμ>4j−3] 1+ _j=1^nProb[MHit_μ>4j-3] +∑j=1nProb[MHitμ>4j−2] + _j=1^nProb[MHit_μ>4j-2] +∑j=1nProb[MHitμ>4j−1] + _j=1^nProb[MHit_μ>4j-1] +∑j=1nProb[MHitμ>4j] + _j=1^nProb[MHit_μ>4j] ≥ ≥ 1+∑j=1n1.2601255⋅0.01(j−1)k=B−k 1+ _j=1^n1.2601255· 0.01^(j-1)k=B-k by comparison of the respective summands. Let j∈1,2,…,nj∈\1,2,…,n\ be an arbitrary index of summation. The sum Prob[MHitμ>4j−3]+Prob[MHitμ>4j−2] [MHit_μ>4j-3]+Prob[MHit_μ>4j-2] + + Prob[MHitμ>4j−1]+Prob[MHitμ>4j] [MHit_μ>4j-1]+Prob[MHit_μ>4j] is equal to ∏i=1kProb[Hitμi>4j−3]+∏i=1kProb[Hitμi>4j−2] _i=1^kProb[Hit_μ^i>4j-3]+ _i=1^kProb[Hit_μ^i>4j-2] + + ∏i=1kProb[Hitμi>4j−1]+∏i=1kProb[Hitμi>4j]. _i=1^kProb[Hit_μ^i>4j-1]+ _i=1^kProb[Hit_μ^i>4j]\,. Let the set i∣xi∈Cj\i x_i∈ C_j\ be denoted by C^j C_j. It follows from the construction of the MDP M and from the previously described properties that for all i∈1,2,…,k∖C^ji∈\1,2,…,k\ C_j we have that Prob[Hitμi>4j−3] [Hit_μ^i>4j-3] = = Prob[Hitμi>4j−2] [Hit_μ^i>4j-2] = = Prob[Hitμi>4j−1] [Hit_μ^i>4j-1] = = Prob[Hitμi>4j] [Hit_μ^i>4j] = = 0.01j−1. 0.01^j-1\,. We distinguish four cases depending on the value of βj=∑i∈C^jμ(xi) _j= _i∈ C_jμ(x_i). If βj=0 _j=0, we get ∏i∈C^jProb[Hitμi>4j−3] _i∈ C_jProb[Hit_μ^i>4j-3] = = ∏i∈C^j0.01j−1 _i∈ C_j0.01^j-1 = = 0.01(j−1)3 0.01^(j-1)3 and ∏i∈C^jProb[Hitμi>4j−2] _i∈ C_jProb[Hit_μ^i>4j-2] = = ∏i∈C^jProb[Hitμi>4j−1] _i∈ C_jProb[Hit_μ^i>4j-1] = = ∏i∈C^jProb[Hitμi>4j] _i∈ C_jProb[Hit_μ^i>4j] = = ∏i∈C^j(0.01j−1⋅0.505) _i∈ C_j(0.01^j-1· 0.505) = = 0.01(j−1)3⋅0.5053, 0.01^(j-1)3· 0.505^3\,, implying that the sum ∏i=1kProb[Hitμi>4j−3]+∏i=1kProb[Hitμi>4j−2] _i=1^kProb[Hit_μ^i>4j-3]+ _i=1^kProb[Hit_μ^i>4j-2] + + ∏i=1kProb[Hitμi>4j−1]+∏i=1kProb[Hitμi>4j] _i=1^kProb[Hit_μ^i>4j-1]+ _i=1^kProb[Hit_μ^i>4j]\, is equal to (1+3⋅0.5053)⋅0.01(j−1)k (1+3· 0.505^3)· 0.01^(j-1)k = = 1.386362875⋅0.01(j−1)k 1.386362875· 0.01^(j-1)k > > 1.2601255⋅0.01(j−1)k. 1.2601255· 0.01^(j-1)k\,. If βj=1 _j=1 (βj=2 _j=2, βj=3 _j=3, respectively) we obtain that the sum ∏i=1kProb[Hitμi>4j−3]+∏i=1kProb[Hitμi>4j−2] _i=1^kProb[Hit_μ^i>4j-3]+ _i=1^kProb[Hit_μ^i>4j-2] + + ∏i=1kProb[Hitμi>4j−1]+∏i=1kProb[Hitμi>4j] _i=1^kProb[Hit_μ^i>4j-1]+ _i=1^kProb[Hit_μ^i>4j]\, is equal to 1.2601255⋅0.01(j−1)k1.2601255· 0.01^(j-1)k (1.505101⋅0.01(j−1)k1.505101· 0.01^(j-1)k, 2.000002⋅0.01(j−1)k2.000002· 0.01^(j-1)k, respectively). We thus get even the strict inequality for the cases βj=0 _j=0, βj=2 _j=2, βj=3 _j=3. Since the inequality holds in all four cases (for every j), it follows that [MHitμ]≥B−kE[MHit_μ]≥ B-k. Recall the current assumption μ(φ)=0μ( )=0, which implies that there is at least one j∈1,2,…,nj∈\1,2,…,n\ such that βj=∑i∈C^jμ(xi)≠1 _j= _i∈ C_jμ(x_i)≠ 1. Hence, the inequality is strict for at least one j, therefore [MHitμ]>B−kE[MHit_μ]>B-k. The constructed MSSP instance has the property that the target state τ is never reached within the first k steps from the beginning and that after exactly k steps, the configuration is μ¯ μ for some truth assignment μ. We have proved that the expected number of steps to reach the target τ from such a configuration is always greater than or equal to B−kB-k, with equality occurring if and only if φ is true under the truth assignment μ. With these observations we are finally ready to prove the claim that a coordinated strategy σ achieving σ[MHit]≤BE_σ[MHit]≤ B exists if and only if the input formula Φ is true. For the rest of this paragraph, let us assume that Φ≡Q1x1Q2x2…Qkxkφ ≡ Q_1x_1Q_2x_2… Q_kx_k\ is true. Determining the truth value of a quantified Boolean formula can be seen as a 2-player game, where the two players, called Prover and Disprover, sequentially assign truth values to the propositional variables x1,x2,…xkx_1,x_2,… x_k: if the variable is existentially quantified, then the assigned value is chosen by Prover, if the variable is universally quantified, the assigned value is chosen by Disprover. If the chosen truth values make the formula φ true, then Prover wins, otherwise Disprover wins. The quantified Boolean formula Φ is true if and only if Prover has a winning strategy in such a game. Any such Prover’s strategy can be transformed into a coordinated strategy for the constructed MSSP instance using the following correspondence: for every i∈1,…,ki∈\1,…,k\, the presence of agent i in one of the states si,ℓ′s _i, corresponds to xix_i not being assigned to a truth value yet, the presence of agent i in one of the states si,⊤,ℓ′s _i, , (or si,⊥,ℓ′s _i, , ) corresponds to xix_i being assigned to 11 (or 0, respectively), for agent i such that Qi≡∃Q_i≡∃ the choice of action ⊤ (or ⊥ ) in the i-th step corresponds to the Prover’s choice of assigning truth value 11 to xix_i (or 0 to xix_i, respectively), similarly, for agent i such that Qi≡∀Q_i≡∀ the outcome of action ⊥ in the i-th step corresponds to the Disprover’s choice for xix_i. Let σ be a coordinated strategy corresponding to a winning strategy for Prover. It is now an easy observation that applying such a coordinated strategy σ ensures that after k steps from the beginning the agents will always be in a configuration μ¯ μ corresponding to some truth assignment μ satisfying μ(φ)=1μ( )=1 (and thus [MHitμ]=B−kE[MHit_μ]=B-k), implying that σ[MHit]=k+(B−k)≤BE_σ[MHit]=k+(B-k)≤ B. To prove the converse, let σ be a (memoryless deterministic) coordinated strategy for the constructed MSSP instance such that σ[MHit]≤BE_σ[MHit]≤ B. As implied by the previous statements, the configuration μ¯ μ reached after exactly k steps from the beginning must correspond (with probability 11) to some truth assignment μ such that [MHitμ]=B−kE[MHit_μ]=B-k (and therefore μ(φ)=1μ( )=1). Using the correspondence described in the previous paragraph, σ can be used to construct a winning strategy for Prover, witnessing that the input formula Φ is true. Appendix B Proof of Theorem 3 Let k≥1k≥ 1 be the number of agents. Let us fix a set of memory states Mem (finite or countably infinite), and let Π _Mem be the set of all strategy profiles for k agents such that every strategy in the profile uses memory Mem. We show that there exists π∗∈Ππ^*∈ _Mem such that π∗[MHit]=infπ′∈Ππ′[MHit].E_π^*[MHit]\ =\ _π ∈ _MemE_π [MHit]\,. Clearly, there exists a sequence of profiles π1,π2,… _1, _2,… such that limn→∞πn[MHit]=infπ′∈Ππ′[MHit]. _n→∞E_ _n[MHit]\ =\ _π ∈ _MemE_π [MHit]\,. For all n≥1n≥ 1 and i∈1,…,ki∈\1,…,k\, we use σni=(mni,ni,ni) _n^i=(m_n^i,next_n^i,update_n^i) to denote the strategy for agent i in the profile πn _n. Without restrictions, we assume there exists m∗∈m^* such that mni=m∗m_n^i=m^* for all strategies (note that the memory elements can be permuted). Let Ψ=Ψ1,Ψ2,… = _1, _2,… be an infinite sequence containing all elements of the set U U = = 1,…,k×S×Act \1,…,k\× S×Mem×Act ∪ ∪ 1,…,k×S×Act× \1,…,k\× S×Mem×Act×Mem Note that U is either finite or countably infinite, and hence the sequence Ψ exists (if Mem is finite, then some elements of U occur infinitely often in Ψ ). For every n≥0n≥ 0, we define an infinite sequence of profiles Υn _n inductively as follows: • Υ0 _0 is the sequence π1,π2,… _1, _2,… fixed above. • Let Υi=π^1,π^2,… _i= π_1, π_2,… Then Υi+1=π^j1,π^j2,… _i+1= π_j_1, π_j_2,… is an infinite subsequence of Υi _i where the indexes j1,j2,…j_1,j_2,… are obtained in the following way. Consider the element Ψi+1 _i+1 of the sequence Ψ . There are two possibilities. – Ψi+1≡(i,s,m,a) _i+1≡(i,s,m,a). Then, j1,j2,…j_1,j_2,… are selected so that the sequence j1i(s,m)(a),j2i(s,m)(a),…next^i_j_1(s,m)(a),next^i_j_2(s,m)(a),… is convergent. This is possible because every infinite sequence of real numbers in the interval [0,1][0,1] contains an infinite convergent subsequence. We use ℒi+1L_i+1 to denote the corresponding limit. – Ψi+1≡(i,s,m,a,m′) _i+1≡(i,s,m,a,m ). In this case, the indexes j1,j2,…j_1,j_2,… are selected so that the sequence j1i((s,m),a)(m′),j2i((s,m),a)(m′),update^i_j_1((s,m),a)(m ),update^i_j_2((s,m),a)(m ), … is convergent. Again, we use ℒi+1L_i+1 to denote the corresponding limit. Observe that if Ψn=Ψn′ _n= _n , then ℒn=ℒn′L_n=L_n . Furthermore, for every Υn=π1n,π2n,… _n= _1^n, _2^n,…, we have that limj→∞πjn[MHit]=infπ′∈Ππ′[MHit]. _j→∞E_ _j^n[MHit]\ =\ _π ∈ _MemE_π [MHit]\,. Consider the profile π∗=(σ1∗,…,σk∗)π^*=( _1^*,…, _k^*) where the strategy σi∗=(m∗,i∗,i∗) _i^*=(m^*,next_i^*,update_i^*) is defined as follows: • i∗(s,m)(a)=ℒnnext_i^*(s,m)(a)=L_n where Ψn=(i,s,m,a) _n=(i,s,m,a) (if there are multiple eligible n’s, any of them can be chosen because all of them determine the same ℒnL_n). • i∗((s,m),a)(m′)=ℒnupdate_i^*((s,m),a)(m )=L_n where Ψn=(i,s,m,a,m′) _n=(i,s,m,a,m ). We show that the assumption π∗[MHit]=ε+infπ′∈Ππ′[MHit]E_π^*[MHit]\ =\ + _π ∈ _MemE_π [MHit] (6) leads to a contradiction for an arbitrarily small fixed ε>0 >0. This implies π∗[MHit]=infπ′∈Ππ′[MHit]E_π^*[MHit]\ =\ _π ∈ _MemE_π [MHit] and the proof is finished. To derive the contradiction, suppose that (6) hold for some ε>0 >0. Consider the original sequence of profiles π1,π2,… _1, _2,… satisfying limn→∞πn[MHit]=infπ′∈Ππ′[MHit]. _n→∞E_ _n[MHit]\ =\ _π ∈ _MemE_π [MHit]\,. Clearly, for an arbitrarily small δ>0δ>0, there exists nδ∈ℕn_δ such that πn[MHit]E_ _n[MHit] is δ-close to infπ′∈Ππ′[MHit] _π ∈ _MemE_π [MHit] for all n≥nδn≥ n_δ. Furthermore, from the definition π∗π^*, we obtain that for an arbitrarily small δ>0δ>0 there exists mδ∈ℕm_δ such that πm[MHit]E_ _m[MHit] is δ-close to π∗[MHit]E_π^*[MHit] for infinitely many m≥m0m≥ m_0. However, for δ=ε/4δ= /4, the nδn_δ and mδm_δ cannot exist simultaneously. Appendix C Proof of Theorem 4 For the rest of this proof, let us fix an integer n≥1n≥ 1. We start by describing an instance of the Autonomous MSSP problem with k=2k=2 agents. Let M=(S,Act,P)M=(S,Act,P) be an MDP where the set of states is S=s,q,r0,r1,…,r2n+2S=\s,q,r_0,r_1,…,r_2n+2\, the set of actions is Act=⊤,⊥Act=\ , \ and the transition function P is defined as follows: • P(s,⊤,q)=P(r0,⊤,r0)=1P(s, ,q)=P(r_0, ,r_0)=1, P(r2n+2,⊤,r2n+1)=P(r2n+1,⊤,r2n)=P(r2n,⊤,r2n−1)=…=P(r2,⊤,r1)=P(r1,⊤,r0)=1P(r_2n+2, ,r_2n+1)=P(r_2n+1, ,r_2n)=P(r_2n, ,r_2n-1)=…=P(r_2, ,r_1)=P(r_1, ,r_0)=1, • P(q,⊤,s)=P(q,⊤,r0)=12P(q, ,s)=P(q, ,r_0)= 12, • P(s,⊥,r2n+2)=34P(s, ,r_2n+2)= 34, • P(s,⊥,r0)=14P(s, ,r_0)= 14, • the function P maps all the remaining triples to 0. Let s, r2n+2r_2n+2 be the initial states and let T1=T2=r0T_1=T_2=\r_0\ be the set of target states. Let =1,…,n+1Mem=\1,…,n+1\ be the set of memory states, let σ=(n+1,,)σ=(n+1,next,update) be a coordinated strategy for one agent such that: • (s,j)(⊤)=1next(s,j)( )=1 and (s,j)(⊥)=0next(s,j)( )=0 for all j∈∖1j \1\, • (s,1)(⊤)=0next(s,1)( )=0, (s,1)(⊥)=1next(s,1)( )=1, • next returns the Dirac distribution on the set ⊤\ \ for the remaining cases, • ((s,1),⊤)(1)=((s,1),⊥)(1)=1update((s,1), )(1)=update((s,1), )(1)=1, • ((s,j),⊤)(j−1)=((s,j),⊥)(j−1)=1update((s,j), )(j-1)=update((s,j), )(j-1)=1 for all j∈∖1j \1\, • ((x,j),⊤)(j)=((x,j),⊥)(j)=1update((x,j), )(j)=update((x,j), )(j)=1 for all j∈j and x∈S∖sx∈ S \s\. Let π=(σ,σ)π=(σ,σ). Note that π is a strategy profile of Πn+1 _n+1. With the application of Theorem 3, let us fix a Πn _n-optimal profile π′π such that π′[MHit]=infπ′∈Πnπ′[MHit]E_π [MHit]= _π ∈ _nE_π [MHit]. In order to finish the proof of the first part of Theorem 4, it remains to show that π[MHit]<π′[MHit]E_π[MHit]<E_π [MHit]. In the constructed MSSP instance, it holds that whenever the first agent is in the state s, then the second agent is in state r2jr_2j for some j∈0,1,…,n+1j∈\0,1,…,n+1\. The strategy profile π defined above has the property that if the first agent is in state s, it chooses the action ⊥ whenever the second agent is in the state r2r_2 and chooses the action ⊤ whenever the second agent is in state r2jr_2j for some j∈2,3,…,n+1j∈\2,3,…,n+1\. It is easy to verify that all profiles with this property achieve the same expected value of MHit and that none of the profiles of Πn _n (including π′π ) have this property (since with at most n memory states there will always be a nonzero probability of not choosing ⊥ when the second agent is in state r2r_2 or choosing ⊥ before the second agent has reached r2r_2). In the following paragraphs, we show that π′π achieves strictly higher expected value of MHit compared to π, using the fact that π′π does not have the described property of π. Let us first assume that π′π admits a nonzero probability that the first agent (being in the state s) chooses the action ⊤ while the second agent is in the state r2r_2. The target state r0r_0 is then first reached by some agent after exactly 22 following steps (with probability 11), however, choosing the action ⊥ would lead to a strictly smaller expected number (14⋅1+34⋅2=1.75 14· 1+ 34· 2=1.75) of steps to reach the target. Let us now assume that π′π admits a positive probability that the first agent (being in the state s) chooses the action ⊥ while the second agent is in the state r2jr_2j for some j∈2,3,…,n+1j∈\2,3,…,n+1\. The target state r0r_0 is then first reached by some agent after exactly 11 step with probability 14 14 and after exactly 2j2j steps with probability 34 34, resulting in the expected number of 14⋅1+34⋅2j=32j+14 14· 1+ 34· 2j= 32j+ 14 steps. However, choosing the action ⊤ would lead to a strictly smaller expected number of steps to reach the target (at most 12⋅2+12⋅2j=j+1 12· 2+ 12· 2j=j+1, which is strictly less than 32j+14 32j+ 14 for all j≥2j≥ 2). Since the strategy profile π′π does not have the described property of π, it follows that performing a sequence of successive improvements of π′π in compliance with the previous paragraph (adding new memory states may be required to implement such improvements) yields a strategy profile having the property of π and achieving strictly smaller expected value of MHit (namely π[MHit]E_π[MHit]). We thus get π[MHit]<π′[MHit]E_π[MHit]<E_π [MHit], which was to be proved. It remains to show that for every ε>0 >0 there exists an ε -optimal finite-memory strategy profile. Let π=(σ1,…,σk)π=( _1,…, _k) an optimal strategy profile which is guaranteed to exist by Theorem 3. If π is finite-memory, we are done immediately. Otherwise, let π^=(σ^1,…,σ^k) π=( σ_1,…, σ_k) be a memoryless profile where every σ^i σ_i is an optimal strategy for agent i computable by the LP of Fig. 2 in the main body of the paper. For every ℓ∈ℕ , consider a profile π[ℓ]=(σ[ℓ]1,…,σ[ℓ]k)π[ ]=(σ[ ]_1,…,σ[ ]_k) such that every σ[ℓ]iσ[ ]_i behaves exactly like σi _i for the first ℓ steps, and then it “switches” to σ^i σ_i forever. Since σi _i uses only finitely many memory states during the first ℓ steps, the strategy σ[ℓ]iσ[ ]_i requires only finitely many memory states (some new memory states may be needed to implement a bounded counter that counts the steps until reaching ℓ ). It is easy to see that limℓ→∞π[ℓ][MHit]=π[MHit] _ →∞E_π[ ][MHit]=E_π[MHit]. Hence, for every ε>0 >0, there exists a sufficiently large ℓ such that π[ℓ][MHit]−π[MHit]≤εE_π[ ][MHit]-E_π[MHit]≤ . Appendix D Randomized Profiles For single-agent SSP, there always exists an optimal memoryless deterministic strategy (see Fig. 2 in the main body of the paper). For the Autonomous MSSP, the role of randomization is essential. More precisely, randomized profiles may achieve strictly better performance than deterministic profiles with the same amount of memory. This is demonstrated by the following example: s1s_1τ 2s_2926 9261726 172678 7818 18aabb There are two agents with the initial states s1s_1 and s2s_2, and the common target state τ. The first agent (starting in s1s_1) has only one strategy, leading to τ in 44 steps with probability one. In the best memoryless deterministic profile π, agent 2 selects the action b. This yields π[MHit]≐3.30769231E_π[MHit] 3.30769231. However, there is a randomized memoryless profile π π where agent 2 selects the action a with probability 0.26260.2626 and action b with the remaining probability 0.73740.7374. This yields a strictly better outcome π^[MHit]≐3.29972213E_ π[MHit] 3.29972213. Appendix E Proof of Theorem 5 Let M=(S,Act,P)M=(S,Act,P) be an MDP, k≥1k≥ 1, and Mem a set of memory states of size n≥1n≥ 1. We define an MDP M¯=(S×,Act×,P¯) M=(S×Mem,Act×Mem, P) such that, for all s∈Ss∈ S, a∈Acta , and m,m′∈m,m , we have that P(s,a,t)=pP(s,a,t)=p in M iff P((s,m),(a,m′),(t,m′))=pP((s,m),(a,m ),(t,m ))=p in M¯ M. Let σ be a strategy for one agent in M with memory Mem. We show that there is a memoryless strategy σ¯ σ for one agent in M¯ M such that the Markov chains MσM_σ and M¯σ¯ M_ σ are identical. The strategy σ¯:(S×)→(Act×) σ:(S×Mem) (Act×Mem) is defined as follows: σ¯(s,m)(a,m′)=(s,m)(a)⋅((s,m),a)(m′). σ(s,m)(a,m )=next(s,m)(a)·update((s,m),a)(m )\,. The Markov chains MσM_σ and M¯σ¯ M_ σ have the same set of states S×S×Mem. Let (s,m),(t,m′)∈S×(s,m),(t,m )∈ S×Mem. The stochastic matrix of MσM_σ assigns to the pair of states ((s,m),(t,m′))((s,m),(t,m )) the probability ∑a∈En(s)(s,m)(a)⋅P(s,a,t)⋅((s,m),a)(m′). _a (s)next(s,m)(a)· P(s,a,t)·update((s,m),a)(m )\,. The stochastic matrix of M¯σ¯ M_ σ assigns to the pair of states ((s,m),(t,m′))((s,m),(t,m )) the probability ∑(a,m′)∈En(s,m)σ¯(s,m)(a,m′)⋅P((s,m),(a,m′),(t,m′)) _(a,m ) (s,m) σ(s,m)(a,m )· P((s,m),(a,m ),(t,m )) By definition of σ¯ σ, we immediately obtain that the above sums are equal. This proves the first part of Theorem 5. The second part of Theorem 5 is proven similarly. Let σ¯ σ be a memoryless strategy for M¯ M. We define a strategy σ for M with memory Mem as follows: • (s,m)(a)=∑m′∈σ¯(s,m)(a,m′)next(s,m)(a)= _m σ(s,m)(a,m ) • ((s,m),a)(m′)=σ¯(s,m)(a,m′)∑m′∈σ¯(s,m)(a,m′)update((s,m),a)(m )= σ(s,m)(a,m ) _m σ(s,m)(a,m ) Now, it is easy to verify that the stochastic matrices of MσM_σ and M¯σ¯ M_ σ assign to every pair of states the same probability. This proves the second part of Theorem 5. Appendix F Proof of Theorem 6 We prove this NP-hardness result by polynomial-time reduction from a variant of the positive 1-in-3-SAT problem where every clause contains exactly three literals and every variable occurs in exactly three clauses. An input instance of this problem is a negation-free propositional formula in conjunctive normal form (with exactly three distinct variables appearing in each clause and every variable occurring in exactly three clauses) and the task is to decide whether there exists a truth assignment such that exactly one literal is assigned the value 11 in each clause. If such an assignment exists, we say that the formula is 1-in-3-satisfiable and we call the corresponding truth assignment 1-in-3-satisfying. To see that this restricted variant of the positive 1-in-3-SAT problem is still NP-hard, notice that the NP-complete RXC3 problem333See Teofilo F. Gonzales: Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, Volume 38, 1985, Pages 293–306. is essentially the same problem, where the elements play the role of clauses, the 3-element subsets play the role of literals (propositional variables) and the presence of a 3-element subset in the subcollection (i.e., in the candidate for an exact cover) plays the role of assigning value 11 to the corresponding propositional variable. Let Φ≡C0∧C1∧…∧Cn−1 ≡ C_0 C_1 … C_n-1 be an instance of the restricted variant of the positive 1-in-3-SAT problem, where each CjC_j is a clause. In this proof, the clauses are understood as sets of three propositional variables. Without restrictions, we assume that ⋃j=0n−1Cj=x0,x1,…,xn−1⊆Var _j=0^n-1C_j=\x_0,x_1,…,x_n-1\ , where each xi∈Varx_i denotes a fresh propositional variable (the number of variables occurring in Φ must be equal to n≥3n≥ 3). In the following paragraphs, we describe a polynomial-time construction of an MSSP instance with two agents and a rational bound B such that a (memoryless) strategy profile π achieving π[MHit]≤BE_π[MHit]≤ B exists if and only if Φ is 1-in-3-satisfiable. A key ingredient used in this construction is a gadget, which is an MDP with two entry states g0g_0, g1g_1 and with the property that • whenever an agent visits a state g0g_0, then it reaches the target state τ in exactly 11 step with probability 0.50.5 and in exactly 44 steps with probability 0.50.5, • whenever an agent visits a state g1g_1, then it reaches the target state τ in exactly 22 steps with probability 0.90.9 and in exactly 77 steps with probability 0.10.1. For a single agent, the expected number of steps to reach τ is equal to 2.52.5, regardless of whether the current state is g0g_0 or g1g_1. However, • when two agents simultaneously visit g0g_0, then the achieved expected number of steps to reach τ (by some agent) is equal to 1.751.75, • when the two agents simultaneously visit g1g_1, then the achieved expected number of steps to reach τ is equal to 2.052.05, • when one agent visits g0g_0 and the other visits g1g_1, then the expected number of steps to reach τ is equal to 1.61.6. We construct an MSSP instance for two agents so that there always exists an optimal strategy profile which is memoryless and deterministic. The two memoryless deterministic strategies will then correspond to two truth assignments. Using the gadget described in the previous paragraph, we enforce that an optimal memoryless deterministic strategy profile necessarily consists of two strategies that both correspond to the same truth assignment. Such pairs of strategies are called consistent. To complete our proof, we use the same gadget to ensure the following: • If a 1-in-3-satisfying truth assignment (corresponding to the input formula Φ ) exists, then the pair of two consistent memoryless deterministic strategies corresponding to such an assignment forms a strategy profile π achieving π[MHit]=BE_π[MHit]=B. • If a 1-in-3-satisfying truth assignment does not exist, then every pair of consistent memoryless deterministic strategies achieves a strictly higher expected value of MHit. Let M=(S,Act,P)M=(S,Act,P) be an MDP where S S = = τ,s′,s′,g0,g1,g1′,g2′,g3′,g4′,g5′,g6′ \τ,s ,s ,g_0,g_1,g _1,g _2,g _3,g _4,g _5,g _6\ ∪ ∪ si′∣0≤i≤n−1 \s _i 0≤ i≤ n-1\ ∪ ∪ si′∣0≤i≤n−1 \s _i 0≤ i≤ n-1\ ∪ ∪ si,0,ℓ′∣0≤i≤n−1,0≤ℓ≤8n−1 \s _i,0, 0≤ i≤ n-1,0≤ ≤ 8n-1\ ∪ ∪ si,1,ℓ′∣0≤i≤n−1,0≤ℓ≤8n−1 \s _i,1, 0≤ i≤ n-1,0≤ ≤ 8n-1\ ∪ ∪ si,0,ℓ′∣0≤i≤n−1,0≤ℓ≤8n−1 \s _i,0, 0≤ i≤ n-1,0≤ ≤ 8n-1\ ∪ ∪ si,1,ℓ′∣0≤i≤n−1,0≤ℓ≤8n−1 \s _i,1, 0≤ i≤ n-1,0≤ ≤ 8n-1\ ∪ ∪ si,0∣0≤i≤n−1 \s_i,0 0≤ i≤ n-1\ ∪ ∪ si,1∣0≤i≤n−1 \s_i,1 0≤ i≤ n-1\ ∪ ∪ sj,0,ℓ∣0≤j≤n−1,0≤ℓ≤8j \s_j,0, 0≤ j≤ n-1,0≤ ≤ 8j\ ∪ ∪ sj,1,ℓ∣0≤j≤n−1,0≤ℓ≤8j, \s_j,1, 0≤ j≤ n-1,0≤ ≤ 8j\, Act = = a,a0,a1 \a,a_0,a_1\ and the transition function P is defined as follows: • P(τ,a,τ)=P(g1′,a,τ)=1P(τ,a,τ)=P(g _1,a,τ)=1, • P(gℓ′,a,gℓ−1′)=1P(g _ ,a,g _ -1)=1 for all 2≤ℓ≤62≤ ≤ 6, • P(g0,a,τ)=P(g0,a,g3′)=0.5P(g_0,a,τ)=P(g_0,a,g _3)=0.5, • P(g1,a,g1′)=0.9P(g_1,a,g _1)=0.9, • P(g1,a,g6′)=0.1P(g_1,a,g _6)=0.1, • P(s′,a,si′)=1nP(s ,a,s _i)= 1n for all 0≤i≤n−10≤ i≤ n-1, • P(si′,a0,si,0,0′)=P(si′,a1,si,1,0′)=1P(s _i,a_0,s _i,0,0)=P(s _i,a_1,s _i,1,0)=1 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,8i′,a,g0)=P(si,1,8i′,a,g1)=1−18n2P(s _i,0,8i,a,g_0)=P(s _i,1,8i,a,g_1)=1- 18n^2 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,8i′,a,si,0,8i+1′)=P(si,1,8i′,a,si,1,8i+1′)=18n2P(s _i,0,8i,a,s _i,0,8i+1)=P(s _i,1,8i,a,s _i,1,8i+1)= 18n^2 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,ℓ′,a,si,0,ℓ+1′)=P(si,1,ℓ′,a,si,1,ℓ+1′)=1P(s _i,0, ,a,s _i,0, +1)=P(s _i,1, ,a,s _i,1, +1)=1 for all 0≤i≤n−10≤ i≤ n-1 and 0≤ℓ≤8n−20≤ ≤ 8n-2 such that ℓ≠8i ≠ 8i, • P(si,0,8n−1′,a,si,0)=P(si,1,8n−1′,a,si,1)=1P(s _i,0,8n-1,a,s_i,0)=P(s _i,1,8n-1,a,s_i,1)=1 for all 0≤i≤n−10≤ i≤ n-1, • P(s′,a,si′)=1nP(s ,a,s _i)= 1n for all 0≤i≤n−10≤ i≤ n-1, • P(si′,a0,si,0,0′)=P(si′,a1,si,1,0′)=1P(s _i,a_0,s _i,0,0)=P(s _i,a_1,s _i,1,0)=1 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,8i′,a,g1)=P(si,1,8i′,a,g0)=1−18n2P(s _i,0,8i,a,g_1)=P(s _i,1,8i,a,g_0)=1- 18n^2 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,8i′,a,si,0,8i+1′)=P(si,1,8i′,a,si,1,8i+1′)=18n2P(s _i,0,8i,a,s _i,0,8i+1)=P(s _i,1,8i,a,s _i,1,8i+1)= 18n^2 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,ℓ′,a,si,0,ℓ+1′)=P(si,1,ℓ′,a,si,1,ℓ+1′)=1P(s _i,0, ,a,s _i,0, +1)=P(s _i,1, ,a,s _i,1, +1)=1 for all 0≤i≤n−10≤ i≤ n-1 and 0≤ℓ≤8n−20≤ ≤ 8n-2 such that ℓ≠8i ≠ 8i, • P(si,0,8n−1′,a,si,0)=P(si,1,8n−1′,a,si,1)=1P(s _i,0,8n-1,a,s_i,0)=P(s _i,1,8n-1,a,s_i,1)=1 for all 0≤i≤n−10≤ i≤ n-1, • P(si,0,a,sj,0,0)=P(si,1,a,sj,1,0)=13P(s_i,0,a,s_j,0,0)=P(s_i,1,a,s_j,1,0)= 13 for all 0≤i≤n−10≤ i≤ n-1 and 0≤j≤n−10≤ j≤ n-1 such that xi∈Cjx_i∈ C_j, • P(sj,0,ℓ,a,sj,0,ℓ+1)=P(sj,1,ℓ,a,sj,1,ℓ+1)=1P(s_j,0, ,a,s_j,0, +1)=P(s_j,1, ,a,s_j,1, +1)=1 for all 0≤j≤n−10≤ j≤ n-1 and 0≤ℓ≤8j−10≤ ≤ 8j-1, • P(sj,0,8j,a,g0)=P(sj,1,8j,a,g1)=1P(s_j,0,8j,a,g_0)=P(s_j,1,8j,a,g_1)=1 for all 0≤j≤n−10≤ j≤ n-1, • the function P maps all the remaining triples to 0. Let T1=T2=τT_1=T_2=\τ\ be the (shared) set of target states, and let ι1=s′ _1=s , ι2=s′ _2=s be the initial states of agent 11 and agent 22. Furthermore, let B=10240n6+5760n5+2944n4−96n2+60n+593840n5.B= 10240n^6+5760n^5+2944n^4-96n^2+60n+593840n^5\,. In this instance of the MSSP problem for two agents, there is always only the action a enabled in every state of the MDP M except for the states si′s _i, si′s _i which are visited after exactly one step from the beginning. This implies that, for this particular MSSP instance, memoryless profiles are sufficient to achieve all values of π[MHit]E_π[MHit] that are achievable by general strategy profiles, because storing information about the history obviously gives the agents no advantage with respect to the achieved value of π[MHit]E_π[MHit]. Moreover, there is no advantage in using randomized strategy profiles in this instance, as the value of π[MHit]E_π[MHit] achieved by a randomized strategy profile is always equal to some weighted arithmetic mean of the values of π[MHit]E_π[MHit] achievable by deterministic strategy profiles (i.e., it is possible to successfully derandomize the strategies). Therefore, there always exists an optimal strategy profile which is memoryless and deterministic. The MDP M is designed so that each agent is forced to take action a in its initial state, changing the agent’s state randomly (with uniform distribution) to some of the states si′s _i (si′s _i, respectively), where the agent has to choose between the two available actions a0a_0 and a1a_1. The choice of a0a_0 (a1a_1, respectively) corresponds to the assignment of Boolean value 0 (11, respectively) to the propositional variable xix_i. If agent 11 chooses a0a_0 (a1a_1, respectively), then with probability 1−18n21- 18n^2 this agent reaches the gadget’s entry state g0g_0 (g1g_1, respectively) after exactly 8i+38i+3 steps from the beginning. With the remaining probability 18n2 18n^2, this agent reaches the state si,0s_i,0 (si,1s_i,1, respectively) after exactly 8n+28n+2 steps from the beginning. If agent 22 chooses a0a_0 (a1a_1, respectively), then with probability 1−18n21- 18n^2 this agent reaches the gadget’s entry state g1g_1 (g0g_0, respectively) after exactly 8i+38i+3 steps from the beginning, and with the remaining probability 18n2 18n^2 this agent reaches the state si,0s_i,0 (si,1s_i,1, respectively) after exactly 8n+28n+2 steps from the beginning. Notice the swapped gadget’s entry states for agent 22; the purpose of this swap is to ensure the consistency of the optimal deterministic strategies (where consistency means that agent 11 chooses a1a_1 in si′s _i if and only if agent 22 chooses a1a_1 in si′s _i). The construction has the property that each of the two agents can reach the target state τ only through the gadget. Whenever one of the agents (let us denote this agent α) reaches one of the states g0g_0, g1g_1, then the other agent β either reaches one of the states g0g_0, g1g_1 in the same step as agent α, or it does not reach g0g_0, g1g_1 before agent α reaches the target state τ. Furthermore, observe that if some agent does not reach the target τ within the first 8n+28n+2 steps (this happens with probability 18n2 18n^2, when the agent first reaches one of the states si,0s_i,0 or si,1s_i,1), then it enters the gadget’s state g0g_0 or g1g_1 from some of the states sj,0,8js_j,0,8j or sj,1,8js_j,1,8j (depending on whether the action taken in the second step is a0a_0 or a1a_1): for every j∈0,…,n−1j∈\0,…,n-1\, the probability that the agent reaches one of the two states sj,0,8js_j,0,8j, sj,1,8js_j,1,8j is equal to 18n2⋅1n 18n^2· 1n. If the agent reaches one of the two states sj,0,8js_j,0,8j, sj,1,8js_j,1,8j for some j∈0,…,n−1j∈\0,…,n-1\, then the conditional probability that the agent has previously reached one of the two states si,0s_i,0, si,1s_i,1 is equal to 13 13 for all i such that xi∈Cjx_i∈ C_j (and is equal to 0 for the rest). Let π=(σ1,σ2)π=( _1, _2) be a memoryless deterministic strategy profile. Let ζ1 _1 be the expected value of MHit under the condition that agent 11 (or 22, respectively) reaches the target τ in at most 8n+28n+2 steps and agent 22 (11, respectively) reaches the target τ in more than 8n+28n+2 steps. In this case, the value of MHit is equal to the number of steps taken by agent 11 (22, respectively) and the (conditional) expected value of MHit may thus be expressed easily as ζ1=∑i=0n−11n(8i+3+2.5) _1= _i=0^n-1 1n(8i+3+2.5) Notice that the value of ζ1 _1 is independent of π. Let ζ2(π) _2(π) be the expected value of MHit under the condition that both agents reach the target τ in at most 8n+28n+2 steps. In this case, we further distinguish the cases when one agent reaches the gadget strictly earlier than the other one, and when both agents enter the gadget simultaneously, obtaining ζ2(π) _2(π) = = ζ2′+ζ2′(π) _2 + _2 (π) = = ∑i=0n−121nn−i−1n(8i+3+2.5) _i=0^n-12 1n n-i-1n(8i+3+2.5) +∑i=0n−1(1n)2(8i+3+χi(π)) + _i=0^n-1 ( 1n )^2(8i+3+ _i(π)) where χi(π) _i(π) expresses the conditional expected number of steps taken to reach the target τ by some agent from the point when both agents first enter the gadget (simultaneously) after exactly 8i+38i+3 steps from the beginning. We have that χi(π)=1.6if σ1(si′)(a1)=σ2(si′)(a1),1.75if σ1(si′)(a1)=0 and σ2(si′)(a1)=1,2.05if σ1(si′)(a1)=1 and σ2(si′)(a1)=0. _i(π)= cases1.6& if _1(s _i)(a_1)= _2(s _i)(a_1),\\ 1.75& if _1(s _i)(a_1)=0 and _2(s _i)(a_1)=1,\\ 2.05& if _1(s _i)(a_1)=1 and _2(s _i)(a_1)=0\,. cases Notice that the value of ζ2′ _2 is independent of π. Similarly, let ζ3(π) _3(π) be the expected value of MHit under the condition that both agents reach the target τ in more than 8n+28n+2 steps. Again, we further distinguish the cases when one agent reaches the gadget strictly earlier than the other one and when both agents enter the gadget simultaneously, obtaining ζ3(π) _3(π) = = ζ3′+ζ3′(π) _3 + _3 (π) = = ∑j=0n−121nn−j−1n(8n+4+8j+2.5) _j=0^n-12 1n n-j-1n(8n+4+8j+2.5) +∑j=0n−1(1n)2(8n+4+8j+χj′(π)) + _j=0^n-1 ( 1n )^2(8n+4+8j+χ _j(π)) where χj′(π)χ _j(π) expresses the conditional expected number of steps taken to reach the target τ by some agent from the point when both agents first enter the gadget (simultaneously) after exactly 8n+4+8j8n+4+8j steps from the beginning. Let j∈0,…,n−1j∈\0,…,n-1\ be an index of a clause Cj=xi1,xi2,xi3C_j=\x_i_1,x_i_2,x_i_3\ (where i1,i2,i3∈0,…,n−1i_1,i_2,i_3∈\0,…,n-1\), and let kj′(π)k _j(π) (kj′(π)k _j(π), respectively) be the number of indices i∈i1,i2,i3i∈\i_1,i_2,i_3\ satisfying σ1(si′)(a1)=1 _1(s _i)(a_1)=1 (σ2(si′)(a1)=1 _2(s _i)(a_1)=1, respectively). The value of χj′(π)χ _j(π) may be expressed as χj′(π) χ _j(π) = = 3−kj′(π)33−kj′(π)3⋅1.75 3-k _j(π)3 3-k _j(π)3· 1.75 +kj′(π)3kj′(π)3⋅2.05 +\ k _j(π)3 k _j(π)3· 2.05 +(kj′(π)33−kj′(π)3+3−kj′(π)3kj′(π)3)⋅1.6 + ( k _j(π)3 3-k _j(π)3+ 3-k _j(π)3 k _j(π)3 )· 1.6 It always holds that 1.6≤χj′(π)≤2.051.6≤χ _j(π)≤ 2.05. Using the law of total expectation, we can now express the expected value of MHit as π[MHit] _π[MHit] = = 2(1−18n2)18n2ζ1+(1−18n2)2ζ2(π) 2 (1- 18n^2 ) 18n^2 _1+ (1- 18n^2 )^2 _2(π) +(18n2)2ζ3(π) + ( 18n^2 )^2 _3(π) = = 2(1−18n2)18n2ζ1+(1−18n2)2ζ2′ 2 (1- 18n^2 ) 18n^2 _1+ (1- 18n^2 )^2 _2 +(1−18n2)2ζ2′(π)+(18n2)2ζ3′ + (1- 18n^2 )^2 _2 (π)+ ( 18n^2 )^2 _3 +(18n2)2ζ3′(π) + ( 18n^2 )^2 _3 (π) For the rest of this paragraph, assume that the memoryless deterministic strategy profile π=(σ1,σ2)π=( _1, _2) is not consistent, i.e., there exists i∈0,…,n−1i∈\0,…,n-1\ such that σ1(si′)(a1)≠σ2(si′)(a1) _1(s _i)(a_1)≠ _2(s _i)(a_1). Let π′=(σ1′,σ2′)π =( _1 , _2 ) be the strategy profile where both agents always choose the action a1a_1 in the second step (i.e., σ1(si′)(a1)=σ2(si′)(a1)=1 _1(s _i)(a_1)= _2(s _i)(a_1)=1 for all i∈0,…,n−1i∈\0,…,n-1\). Let us compare the achieved expected values of MHit. We have that π[MHit]−π′[MHit]E_π[MHit]-E_π [MHit] is equal to 2(1−18n2)18n2ζ1+(1−18n2)2ζ2′ 2 (1- 18n^2 ) 18n^2 _1+ (1- 18n^2 )^2 _2 +(1−18n2)2ζ2′(π)+(18n2)2ζ3′ + (1- 18n^2 )^2 _2 (π)+ ( 18n^2 )^2 _3 +(18n2)2ζ3′(π)−2(1−18n2)18n2ζ1 + ( 18n^2 )^2 _3 (π)-2 (1- 18n^2 ) 18n^2 _1 −(1−18n2)2ζ2′−(1−18n2)2ζ2′(π′) - (1- 18n^2 )^2 _2 - (1- 18n^2 )^2 _2 (π ) −(18n2)2ζ3′−(18n2)2ζ3′(π′) - ( 18n^2 )^2 _3 - ( 18n^2 )^2 _3 (π ) = = (1−18n2)2(ζ2′(π)−ζ2′(π′))+(18n2)2(ζ3′(π)−ζ3′(π′)) (1- 18n^2 )^2 ( _2 (π)- _2 (π ) )+ ( 18n^2 )^2 ( _3 (π)- _3 (π ) ) = = (1−18n2)2(∑i=0n−1(1n)2(8i+3+χi(π))) (1- 18n^2 )^2 ( _i=0^n-1 ( 1n )^2(8i+3+ _i(π)) ) −(1−18n2)2(∑i=0n−1(1n)2(8i+3+1.6)) - (1- 18n^2 )^2 ( _i=0^n-1 ( 1n )^2(8i+3+1.6) ) +(18n2)2(∑j=0n−1(1n)2(8n+4+8j+χj′(π))) + ( 18n^2 )^2 ( _j=0^n-1 ( 1n )^2(8n+4+8j+χ _j(π)) ) −(18n2)2(∑j=0n−1(1n)2(8n+4+8j+2.05)) - ( 18n^2 )^2 ( _j=0^n-1 ( 1n )^2(8n+4+8j+2.05) ) ≥ ≥ (1−18n2)2(1n)2(1.75−1.6) (1- 18n^2 )^2 ( 1n )^2(1.75-1.6) +(18n2)2n(1n)2(1.6−2.05) + ( 18n^2 )^2n ( 1n )^2(1.6-2.05) ≥ ≥ (1−18)21n2⋅0.15−164n5⋅0.45 (1- 18 )^2 1n^2· 0.15- 164n^5· 0.45 ≥ ≥ 1n2(4964⋅0.15−164n3⋅0.45) 1n^2 ( 4964· 0.15- 164n^3· 0.45 ) ≥ ≥ 1n2(4964⋅0.15−164⋅0.45)>0 1n^2 ( 4964· 0.15- 164· 0.45 )>0 We thus get that π[MHit]>π′[MHit]E_π[MHit]>E_π [MHit], which implies that π is not optimal. It follows that every optimal strategy profile for the constructed instance of the MSSP problem must be consistent. Recall that we aim to prove that a strategy profile π achieving π[MHit]≤BE_π[MHit]≤ B exists if and only if Φ is 1-in-3-satisfiable. For the rest of this paragraph, assume that Φ is 1-in-3-satisfiable. Let ν:Var→0,1ν:Var→\0,1\ be a corresponding 1-in-3-satisfying truth assignment and let π=(σ1,σ2)π=( _1, _2) be the memoryless deterministic strategy profile such that σ1(si′)(a1)=σ2(si′)(a1)=ν(xi) _1(s _i)(a_1)= _2(s _i)(a_1)=ν(x_i) (implying that σ1(si′)(a0)=σ2(si′)(a0)=1−ν(xi) _1(s _i)(a_0)= _2(s _i)(a_0)=1-ν(x_i)). The achieved expected value of MHit may be expressed as π[MHit] _π[MHit] = = 2(1−18n2)18n2ζ1 2 (1- 18n^2 ) 18n^2 _1 +(1−18n2)2ζ2′+(1−18n2)2ζ2′(π) + (1- 18n^2 )^2 _2 + (1- 18n^2 )^2 _2 (π) +(18n2)2ζ3′+(18n2)2ζ3′(π) + ( 18n^2 )^2 _3 + ( 18n^2 )^2 _3 (π) = = 2(1−18n2)18n2∑i=0n−11n(8i+3+2.5) 2 (1- 18n^2 ) 18n^2 _i=0^n-1 1n(8i+3+2.5) +(1−18n2)2∑i=0n−121nn−i−1n(8i+3+2.5) + (1- 18n^2 )^2 _i=0^n-12 1n n-i-1n(8i+3+2.5) +(1−18n2)2∑i=0n−1(1n)2(8i+3+χi(π)) + (1- 18n^2 )^2 _i=0^n-1 ( 1n )^2(8i+3+ _i(π)) +(18n2)2∑j=0n−121nn−j−1n(8n+4+8j+2.5) + ( 18n^2 )^2 _j=0^n-12 1n n-j-1n(8n+4+8j+2.5) +(18n2)2∑j=0n−1(1n)2(8n+4+8j+χj′(π)) + ( 18n^2 )^2 _j=0^n-1 ( 1n )^2(8n+4+8j+χ _j(π)) where all χi(π)=1.6 _i(π)=1.6 and all χj′(π) χ _j(π) = = 3−133−13⋅1.75+1313⋅2.05 3-13 3-13· 1.75+ 13 13· 2.05 +(133−13+3−1313)⋅1.6 + ( 13 3-13+ 3-13 13 )· 1.6 = = 10360 10360 The simplified form π[MHit] _π[MHit] = = 10240n6+5760n5+2944n4−96n2+60n+593840n5 10240n^6+5760n^5+2944n^4-96n^2+60n+593840n^5 = = B B can be obtained using standard techniques. To prove the converse, let π=(σ1,σ2)π=( _1, _2) be an arbitrary strategy profile achieving π[MHit]≤BE_π[MHit]≤ B. Applying the aforementioned observations, we assume without loss of generality that the strategies σ1 _1, σ2 _2 are memoryless, deterministic and consistent. Let ν:Var→0,1ν:Var→\0,1\ be the truth assignment such that ν(xi)=σ1(si′)(a1)ν(x_i)= _1(s _i)(a_1) for all i∈0,…,n−1i∈\0,…,n-1\ (and ν(y)=0ν(y)=0 for all remaining variables y∈Vary∈ Var). Let j∈0,…,n−1j∈\0,…,n-1\ be an arbitrary index of a clause Cj=xi1,xi2,xi3C_j=\x_i_1,x_i_2,x_i_3\ of the input formula Φ and let k be the number of indices i∈i1,i2,i3i∈\i_1,i_2,i_3\ satisfying ν(xi)=1ν(x_i)=1. It follows that χi′(π)=1.75=10560if k=0,10360if k=1,10960if k=2,2.05=12360if k=3.χ _i(π)= cases1.75= 10560& if k=0,\\[4.30554pt] 10360& if k=1,\\[4.30554pt] 10960& if k=2,\\[4.30554pt] 2.05= 12360& if k=3. cases Using the expressions of the previous paragraphs, it is clear that this number k must be equal to 11 (for all j), otherwise π[MHit]E_π[MHit] would exceed the given bound B. Hence, ν assigns the value 11 to exactly one variable in each clause of the input formula Φ , which means that Φ is 1-in-3-satisfiable. Appendix G Proof of Theorem 7 Consider the MDP of Fig. 6 parameterized by ϱ>1 >1, where ι1,ι2 _1, _2 are the initial states of agent 11 and agent 22 and T1=T2=τT_1=T_2=\τ\. Note that agent 11 can reach only the states ι1,L,R,τ _1,L,R,τ with only one enabled action. Agent 2 can make decisions only in the state Y. Consider a memoryless coordinated strategy σ such that agent 22 in the state Y performs either the action ℓ or r depending on whether agent 11 is in the state R or L, respectively. By evaluating σ[MHit]E_σ[MHit], we obtain that σ[MHit]≤c⋅ϱE_σ[MHit]≤ c· for a suitable constant c, i.e., σ[MHit]E_σ[MHit] is asymptotically linear in ϱ . Now consider an autonomous strategy profile π for two agents. Agent 22 may choose between the actions ℓ or r at the state Y, but now independently of the current position of agent 11. Note that as ϱ increases, agent 11 enters the state L with probability close to 11. If agent 22 select the action ℓ , then π[MHit]≥d⋅ϱ2E_π[MHit]≥ d· ^2 for a suitable constant d. A carefull analysis reveals that the same holds if agent 22 selects the action r. Hence, π[MHit]E_π[MHit] is asymptotically quadratic in ϱ for every strategy of agent 22. This implies that the price of autonomy can be arbitrarily large by choosing a suitably large ϱ . Let us note that the argument can be adapted so that it avoids using arbitrarily small probabilities in the underlying MPD. A small value of ϱ−1 ^-1 can be “emulated” by inserting O(log(ϱ))O( ( )) auxiliary states and actions, and using only transition probabilities equal to 1/21/2. τ ι2 _2ι1 _1ℓ ϱ−4 ^-41−ϱ−41- ^-4ϱ−2 ^-21−ϱ−21- ^-2ϱ−1 ^-11−ϱ−11- ^-1ϱ−1 ^-11−ϱ−11- ^-1 Figure 6: The price of autonomy can be arbitrarily large even for two agents. Appendix H Additional Experimental Results Figure 7 shows the comparison of the values of strategy profiles synthesized by AutoHit compared to the baseline strategy profile πSP _ SP that for each agent uses the graph-theoretic shortest path. We executed AutoHit with two initial parameter settings representing a random profile πRND _ RND and a precomputed profile πRSP _ RSP which is a “randomized version” of πSP _ SP. Figure 7: We report the ValRND/BaseSPVal_ RND/Base_ SP (blue) and ValRSP/BaseSPVal_ RSP/Base_ SP (brown) ratios. The points below the line y=1y=1 correspond to benchmarks where the ratio is smaller than 11, i.e., the profiles computed by AutoHit outperform the baseline. Figure 8 shows the execution times of AutoHit and the execution times of the two baselines: LP and SP. All the times are wall-clock times. Figure 8: Average execution times of AutoHit and of the compared baselines. Table 1 shows all the individual values of strategy profiles for 20 agents of all compared algorithms for synthesis of autonomous strategy profiles. Columns Seed ValLPVal_ LP ValSPVal_ SP ValRNDVal_ RND ValRLPVal_ RLP ValRSPVal_ RSP 10 1 11.00 9.07 9.10 9.07 9.07 10 2 11.00 10.01 10.19 10.13 9.93 10 3 11.00 9.00 9.01 9.00 9.00 10 4 11.00 9.05 9.07 9.11 9.05 10 5 11.00 9.12 9.14 9.12 9.12 10 6 9.00 9.00 9.00 9.00 9.00 10 7 11.00 10.02 10.00 10.10 9.93 10 8 11.00 9.07 9.09 9.07 9.07 10 9 13.01 11.35 11.19 11.24 11.23 10 10 13.00 11.57 10.95 11.01 10.86 20 1 23.00 22.31 21.18 21.05 21.03 20 2 23.00 19.52 19.80 20.49 19.52 20 3 21.00 25.07 21.02 21.00 21.00 20 4 25.00 23.86 22.09 22.79 21.50 20 5 23.00 27.26 22.81 23.00 22.21 20 6 21.00 19.08 19.16 19.08 19.08 20 7 23.00 21.52 21.00 21.00 20.83 20 8 21.15 20.76 21.17 21.13 20.76 20 9 19.14 19.14 19.24 19.14 19.14 20 10 23.00 21.92 21.18 21.02 20.98 30 1 35.00 34.69 33.02 32.38 32.46 30 2 33.39 43.04 33.10 32.27 32.27 30 3 37.00 31.21 32.52 31.71 31.21 30 4 35.00 35.46 33.25 32.68 32.42 30 5 31.00 33.84 31.12 31.00 30.98 30 6 31.04 32.76 31.29 31.04 31.04 30 7 37.00 43.91 33.40 33.23 33.23 30 8 33.00 32.98 31.96 31.13 31.07 30 9 35.00 61.17 34.63 35.00 34.49 30 10 31.02 36.15 31.19 31.02 31.02 40 1 45.54 48.29 45.36 44.65 44.61 40 2 45.00 47.72 43.75 43.14 43.19 40 3 43.00 53.38 43.15 43.00 42.62 40 4 45.02 47.20 44.88 43.57 44.11 40 5 43.00 44.24 41.14 41.00 40.99 40 6 43.09 57.98 43.39 42.40 42.40 40 7 49.00 57.01 46.04 45.05 44.90 40 8 43.00 40.33 41.83 40.81 40.33 40 9 50.12 61.13 49.06 47.92 48.54 40 10 41.00 42.17 41.08 41.00 40.87 50 1 57.26 59.45 57.01 55.74 55.76 50 2 55.00 60.35 54.14 53.15 52.94 50 3 59.05 66.45 57.51 56.86 57.89 50 4 58.81 74.90 60.30 58.81 59.17 50 5 57.00 61.27 55.35 55.08 55.19 50 6 57.00 68.82 55.59 54.77 53.87 50 7 57.00 67.35 56.83 55.65 55.95 50 8 55.00 51.33 53.18 52.34 51.31 50 9 64.81 68.01 66.29 64.06 63.66 50 10 53.06 54.58 53.33 52.88 52.57 Table 1: Values of strategy profiles for 20 agents of all compared algorithms for synthesis of autonomous strategy profiles. Appendix I The Influence of the Choice of γ In this section, we discuss the influence of the choice of the hyperparameter γ. Benchmarks. For evaluation, we use the same family of grid-like city benchmarks as in the main experiments. The only difference is that we use only benchmarks of size l=30l=30. Hence, we use 10 benchmarks instead of the 50 in the main experiments. Setup. For this experiment, we used a Linux machine with an 11th Gen Intel Core i7–1165G7 2.8 GHz CPU, 15 GiB of RAM. GPUs were not used in our experiments. For each benchmark, we ran AutoHit 55 times. We ran the algorithm AutoHit for each number of agents k∈5,10,15,20k∈\5,10,15,20\. All hyperparameters except γ are set to the same values as in the main experiments. For a fixed MDP M and r≥0r≥ 0, let γr _r denote the r multiple of the number of states in M. Recall that in the main experiments γ was set to γ1 _1. Here, we use values γr _r for r∈0.2,0.5,0.8,1.0,2.0r∈\0.2,0.5,0.8,1.0,2.0\. Note that since the number of states in our benchmarks is always divisible by 55, all values γr _r considered here are integers. As in the main text, we use two initial parameter settings. One representing a random profile πRND _ RND, and the other a precomputed profile πRLP _ RLP which is a “randomized version” of πLP _ LP. Agents 0.2 0.5 0.8 1.0 2.0 5 4.72(0.35)4.72(0.35) 12.02(1.21)12.02(1.21) 19.99(1.53)19.99(1.53) 26.13(1.15)26.13(1.15) 65.56(2.96)65.56(2.96) 10 5.91(0.11)5.91(0.11) 22.18(4.63)22.18(4.63) 37.82(0.92)37.82(0.92) 42.96(1.05)42.96(1.05) 68.04(1.09)68.04(1.09) 15 9.15(0.95)9.15(0.95) 41.49(5.03)41.49(5.03) 56.66(4.15)56.66(4.15) 63.08(2.88)63.08(2.88) 99.46(4.82)99.46(4.82) 20 10.07(2.06)10.07(2.06) 46.50(5.49)46.50(5.49) 57.06(6.07)57.06(6.07) 63.55(5.41)63.55(5.41) 103.71(12.46)103.71(12.46) Table 2: Mean and standard deviation of reported times (in seconds) of the AutoHit algorithm with RandomRandom parameter initialization on the benchmarks for each combination of number of agents (rows) and r (columns). The time complexity increases with both the number of agents and the number of evaluation steps. Agents 0.2 0.5 0.8 1.0 2.0 5 5.42(0.38)5.42(0.38) 14.28(2.02)14.28(2.02) 27.43(3.31)27.43(3.31) 34.82(4.05)34.82(4.05) 63.34(7.57)63.34(7.57) 10 7.31(0.22)7.31(0.22) 24.81(3.00)24.81(3.00) 33.96(2.71)33.96(2.71) 38.50(2.93)38.50(2.93) 61.88(2.69)61.88(2.69) 15 11.37(1.24)11.37(1.24) 40.72(4.61)40.72(4.61) 50.16(5.88)50.16(5.88) 56.65(5.66)56.65(5.66) 89.84(5.54)89.84(5.54) 20 12.61(1.53)12.61(1.53) 41.86(5.74)41.86(5.74) 51.15(6.26)51.15(6.26) 56.97(6.39)56.97(6.39) 93.65(9.08)93.65(9.08) Table 3: Mean and standard deviation of reported times (in seconds) of the AutoHit algorithm with LPLP parameter initialization on the benchmarks for each combination of number of agents (rows) and r (columns). The time complexity increases with both the number of agents and the number of evaluation steps. Agents 0.2 0.5 0.8 1.0 2.0 5 25.22(3.05)25.22(3.05) 0.99(0.04)0.99(0.04) 0.99(0.04)0.99(0.04) 0.99(0.04)0.99(0.04) 1.00(0.04)1.00(0.04) 10 22.82(2.70)22.82(2.70) 0.98(0.04)0.98(0.04) 0.97(0.04)0.97(0.04) 0.98(0.04)0.98(0.04) 0.99(0.04)0.99(0.04) 15 19.87(2.91)19.87(2.91) 0.97(0.04)0.97(0.04) 0.97(0.04)0.97(0.04) 0.97(0.04)0.97(0.04) 0.98(0.04)0.98(0.04) 20 18.74(2.81)18.74(2.81) 0.96(0.05)0.96(0.05) 0.96(0.04)0.96(0.04) 0.96(0.04)0.96(0.04) 0.97(0.04)0.97(0.04) Table 4: Mean and standard deviation of normalized values (value/base) of the AutoHit algorithm with RandomRandom parameter initialization on the benchmarks for each combination of number of agents (rows) and r (columns). Lower values indicate better performance relative to the baseline. Agents 0.2 0.5 0.8 1.0 2.0 5 1.00(0.00)1.00(0.00) 0.97(0.03)0.97(0.03) 0.97(0.03)0.97(0.03) 0.97(0.03)0.97(0.03) 0.97(0.03)0.97(0.03) 10 1.00(0.00)1.00(0.00) 0.96(0.04)0.96(0.04) 0.96(0.04)0.96(0.04) 0.96(0.04)0.96(0.04) 0.96(0.04)0.96(0.04) 15 1.00(0.00)1.00(0.00) 0.96(0.05)0.96(0.05) 0.96(0.05)0.96(0.05) 0.96(0.05)0.96(0.05) 0.96(0.05)0.96(0.05) 20 1.00(0.00)1.00(0.00) 0.95(0.05)0.95(0.05) 0.95(0.05)0.95(0.05) 0.95(0.05)0.95(0.05) 0.95(0.05)0.95(0.05) Table 5: Mean and standard deviation of normalized values (value/base) of the AutoHit algorithm with LPLP parameter initialization on the benchmarks for each combination of number of agents (rows) and r (columns). Lower values indicate better performance relative to the baseline. Results. In Table 2 we report the mean and standard deviation of the total optimization time of the AutoHit algorithm with RandomRandom parameter initialization. The statistics are computed separately for each number of agents and each value of r, aggregated over all benchmarks and all runs. In Table 3 we report the same statistics for LPLP initialization. In Table 4 we report the same statistics, but of the values of the strategy profiles found, normalized by the value of the baseline, i.e., the values are ValRND/BaseVal_ RND/Base. In Table 5 we report the same statistics for LPLP initialization. Discussion. We can clearly see that the runtime increases with the number of agents and with r. This is expected, as the number of terms in the sum of ⟨⟩[MHit] E γ _π^I[MHit] is precisely γr _r, and the number of factors in each product equals the number of agents. Observe that for each r, the paths taken into account when computing ⟨⟩[MHit] E γ _π^I[MHit] have length at most γr _r. From the tables on value, we see that for γ0.2 _0.2 the values obtained with random initialization are poor, while for LP initialization the values for γ0.2 _0.2 coincide with the LP baseline. For our benchmarks, the value γ0.2 _0.2 coincides with the length of the shortest paths from the initial state to the goal. Hence, only a small number of paths are taken into account when computing ⟨⟩[MHit] E γ _π^I[MHit], and the algorithm AutoHit cannot substantially improve the strategy value. For larger values of r that cover a larger set of paths, Table 4 and Table 5 show that the influence of the actual choice of r is negligible. All values γr _r with r≥0.5r≥ 0.5 yield identical strategy values for LP initialization. For random initialization, the values are close to each other but appear to slightly decrease as r increases. A possible explanation is that larger values of r incorporate longer paths into the objective, which increases the complexity of the optimization loop and may slow down convergence for a fixed optimization budget. Thus, we conclude that γ should be chosen large enough to cover a sufficiently rich set of paths. As stated in the main text, we use γ1.0 _1.0, as it guarantees coverage of all simple paths. Beyond this point, increasing γ does not lead to a noticeable improvement in the performance of AutoHit.