Limit-sure Winning in Team Games without Shared Randomness

1 Introduction

• Coalition logics such as ATL, RATL, and PATL model a coalition as one player, implicitly assuming shared randomness that may not reflect real systems.Agents such as separated sensors or independently deployed components may be unable to coordinate random choices [9].Source: §1 · p. 1
• Limit-sure winning asks whether a plan can meet every reliability requirement 1−λ, supporting planning with decentralized execution.A positive instance permits a plan with as much accuracy as needed.Source: §1 · p. 1
• For every 1 > λ > 0, choosing 0 < ε < λ ensures that the team can succeed with probability greater than 1−λ.The stated reach probability is 1−ε.Source: §1 · p. 2
• Limit-sure reachability for teams without shared randomness is NP-complete, while limit-sure safety winning coincides with almost-sure winning and is in P.The qualitative fragment of IRATL model checking is P^NP-complete.Source: §1 · p. 2
• Qualitative IRATL model checking is P^NP-complete, settling the complexity of this fragment.IRATL was introduced to express what coalitions can achieve with individual or shared random sources [9].Source: §1 · p. 2
• The reachability upper bound uses polynomial certificates for parameterized strategies, reducing verification to ranks and minimum-rank spanning forests.Action probabilities are represented as algebraic Puiseux series in ε; an encoded MDP helps certify an opponent response in polynomial time.Source: §1 · p. 2

Related work

• With shared randomness, a team reduces to a two-player game, where sure, almost-sure, and limit-sure reachability are computable in polynomial time.For two-player reachability, the quantitative threshold problem is in ∃R, with SQRTSUM-hardness as the best known lower bound [13].Source: Related work · p. 2
• Earlier work established NP-completeness for almost-sure reachability without shared randomness and left limit-sure reachability and safety open [9, Problem 3; 9, Problem 4].The threshold problem was shown to be in ∃R, with memoryless team strategies sufficient [9].Source: Related work · p. 2
• Unlike team-equilibrium studies of one-shot games or finite trees, this paper studies qualitative limit-sure winning on graphs.The related literature considers differing communication and correlation models, including teams that cannot correlate strategies [11] [5] [30].Source: Related work · pp. 2–3
• The reachability proof builds on Puiseux strategies for decentralized planning, adding polynomial-time verification against all opponent responses by checking one response.In contrast, infinite-horizon limit-sure reachability under partial observation can be undecidable even for blind POMDPs; fixed-memory policies have an NP-complete problem [3].Source: Related work · p. 3
• ATL extensions such as PATL and RATL treat coalitions as meta-players with shared randomness, whereas IRATL models individual randomization [9].The paper's results give a tight complexity bound for qualitative IRATL model checking; Probabilistic Strategy Logic is undecidable in general.Source: Related work · p. 3

2 Preliminaries

• A finite game starts at an initial state; players choose actions simultaneously and independently, and the transition distribution depends on the state and complete action profile.The team seeks to satisfy the objective while opponents try to prevent it.Source: §2 · p. 3
• A team strategy is a tuple of individual strategies that induces a product distribution over team action profiles, unlike shared randomness, which permits any joint distribution.Fixing the team strategy and an opponent response induces an MDP and a Markov chain, respectively.Source: §2 · p. 3
• Reachability requires eventually visiting a target state, whereas safety requires remaining in the safe-state set forever.The paper denotes the objectives as reachability and safety conditions.Source: §2 · p. 3
• Almost-sure winning requires probability 1 against every opponent response; limit-sure winning requires winning probability greater than 1−λ for every λ > 0.The team selects its strategy to maximize the objective probability against all opponent responses.Source: §2 · p. 4
• The complexity analysis assumes explicitly represented games with binary-encoded rational transition probabilities and objectives given by target or safe states.Opponent responses can be taken as deterministic memoryless strategies.Source: §2 · p. 4

3.1 Puiseux Strategies

• A limit-sure winning strategy exists exactly when a Puiseux team strategy has success probabilities with standard part 1 against every opponent response.Puiseux strategies symbolically capture families whose success probabilities approach 1 as the error tends to zero.Source: §3.1 · p. 4

3.1.1 Ranks.

• Winning depends only on action ranks: spanning-forest formulas reduce absorption-probability comparisons to minimum ranks of forest terms.For each opponent response, failure is infinitesimal when its forest numerator has larger minimum rank than the denominator.Source: §3.1.2 · p. 5, §3.1.1 · p. 5

3.1.2 Small ranks.

• Every limit-sure winning strategy has a Puiseux-winning realization whose finite action ranks are integers from 0 to N^(N/2), where N counts team state-action choices.These ranks need O(N log(N + 1)) bits.Source: §3.1.2 · p. 5

3.2 Puiseux Markov Decision Processes

• Making a failure region containing every opponent-response bottom SCC outside the target absorbing gives all forest comparisons the same roots.Source: §3.2 · p. 6

3.2.1 The induced Puiseux MDP.

• In the induced Puiseux MDP, each state-action pair has a successor transition of rank zero because its transition probabilities sum to 1.Source: §3.2.1 · p. 6

3.3 The NP Upper Bound

• The NP upper bound guesses team ranks and one opponent response, then uses local inequalities in an encoded MDP to certify that response is optimal.This avoids checking exponentially many opponent responses directly.Source: §3.3 · p. 6
• A response is stable when its local Bellman inequalities hold, and a stable response exists, is optimal from every state, and can be checked in polynomial time in the encoded MDP.The encoding gives distinct ranks to spanning trees, allowing the minimum tree to determine each residual’s sign.Source: §3.3 · pp. 6–7
• Residual signs are checked by weighted matroid intersection, which finds a minimum encoded-rank tree or reports that none exists.The prescribed edge groups form a partition matroid, while cycle-free edge sets form a graphic matroid; common independent sets of the required size are spanning trees.Source: §3.3 · p. 7
• Limit-sure reachability is NP-complete.Hardness follows from [9], and the upper bound uses Algorithm 1 with B = N^N/2.Source: §3.3 · pp. 7–8
• The upper-bound algorithm runs in polynomial time because it checks at most |U| |A_O| residuals, each verified in polynomial time.Ranks have O(N log(N + 1)) bits, and encoded ranks and the guessed response have polynomial size.Source: §3.3 · pp. 7–8
• The algorithm is sound and complete: acceptance yields a Puiseux-winning strategy, and limit-sure winning provides bounded ranks that the algorithm can guess.The guessed ranks have a normalized-power realization that is winning because only ranks matter.Source: §3.3 · p. 8

• For safety objectives, limit-sure winning is equivalent to almost-sure winning.Source: §4 · p. 8
• Compactness turns strategies meeting every safety threshold 1−1/m into one strategy that guarantees safety with probability 1 against every opponent.Source: §4 · p. 8
• Because almost-sure and sure safety coincide, limit-sure safety is decidable in polynomial time.Source: §4 · p. 8

• IRATL specifies coalitions’ objectives with individual or shared randomisation and sure, almost-sure, or limit-sure winning conditions.Source: §5 · p. 8
• Qualitative IRATL model checking on explicitly represented finite stochastic game structures is P^NP-complete.Source: §5 · p. 8
• Model checking recursively computes true-state sets, checking next and globally modalities in polynomial time and reducing until formulas to reachability.Source: §5 · p. 8

6 Conclusions

• Limit-sure reachability without shared randomness is NP-complete, while safety limit-sure, almost-sure, and sure winning coincide and are decidable in polynomial time.Source: §6 · p. 8
• The reachability proof relies on memoryless team strategies being sufficient; whether this holds for other objectives remains open.Source: §6 · p. 8
• Intermediate randomness-sharing models include subteams sharing randomness, pre-play correlation devices, and limited shared random bits.Source: §6 · p. 8
• The certificate replaces checks over exponentially many opponent strategies with a polynomial-time test using perturbed ranks, a stable response, and residual signs.Source: §6 · p. 9
• The authors propose extending PRISM-games and MCMAS to support individually randomised coalitions, using SAT or ILP solvers to obtain ranks.Source: §6 · p. 9

A Preliminaries

• The preliminaries show that a single opponent can represent independently randomized opponent tuples while preserving finite state-sequence probabilities.Source: A Preliminaries · p. 11

B Reachability

• Absorbing target states can be assumed without loss of generality because a play satisfies reachability as soon as it visits a target.The objective is W = ^T.Source: B Reachability · p. 11
• The reachability problem is NP-hard by the same k-clique reduction used for almost-sure winning, and the section establishes membership in NP.The upper-bound proof represents limit-sure strategies symbolically, reduces winning to ranks and spanning forests, and checks a polynomial-size certificate.Source: B Reachability · p. 11
• Memoryless team strategies suffice, and after fixing one, an optimal opponent response can be chosen deterministic and memoryless.The section therefore restricts its analysis to these strategies.Source: B Reachability · p. 11

B.1 Puiseux Strategies

• A team can represent strategies whose winning probability approaches 1 as ε tends to zero with one symbolic strategy whose probabilities are Puiseux series.The positive parameter ε stands for an arbitrarily small real number.Source: §B.1 · pp. 11–12
• The algebraic Puiseux field supports transfer between real and symbolic first-order statements, and its bounded elements can be evaluated for sufficiently small positive ε.Standard parts connect bounded symbolic probabilities to their real limiting values.Source: §B.1 · p. 12
• Limit-sure winning holds exactly when some Puiseux team strategy is Puiseux-winning against every real-valued memoryless opponent strategy.The proof transfers the limit-sure condition to the Puiseux field and evaluates a winning symbolic strategy at sufficiently small real parameters.Source: §B.1 · p. 12
• A Puiseux-winning strategy can be chosen with nonnegative integer exponents by substituting a common-denominator power of ε for the parameter.The substitution preserves order and the winning property.Source: §B.1 · pp. 12–13

B.1.1 Ranks.

• A strategy is Puiseux-winning exactly when, against every opponent strategy, the minimum rank of forests leading to failure exceeds the minimum rank among all spanning forests.The forest formula expresses absorption probabilities through forest weights, so their ranks yield this criterion; the action ranks determine the transition ranks and the relevant minima.Source: §B.1.1 · pp. 14–15
• For fixed absorbing states, the minimum rank of a spanning forest in which a state leads to a specified root subset can be computed in polynomial time.The computation reduces to minimum-weight spanning arborescence; consequently, both minima in the winning criterion are polynomial-time computable for a fixed opponent strategy.Source: §B.1.1 · pp. 15–16
• A limit-sure-winning team strategy has a Puiseux-winning witness whose finite nonnegative integer action ranks are bounded by N^N/2, enabling polynomial-bit rank encodings.The ranks can be guessed and checked against all opponent strategies in NP^NP; later sections improve the bound to NP.Source: §B.1.2 · pp. 16–17

B.2 Puiseux Markov Decision Processes

• The induced Puiseux MDP packages the team's ranked strategy so that one object can support analysis across all opponent strategies, despite their potentially exponential number.Its transition ranks are computable in polynomial time, and every state-action pair has at least one successor transition of rank zero.Source: §B.2 · p. 17, §B.2.1 · p. 17

B.2.2 Traps and the merged MDP

• The induced MDP's maximal end components can be computed in polynomial time, and its trap construction makes every trap state absorbing.Within a maximal end component, the opponent can choose actions that keep play inside; a state can therefore be in a trap even if another action leads to the target.Source: §B.2.2 · p. 18

B.2.2 Traps and the merged MDP.

• Contracting the target and Trap into absorbing states t* and f* yields a Puiseux MDP whose ranked edges do not depend on the opponent strategy.The contracted states are t* and f*, and each edge retains its transition rank.Source: §B.2.2 · p. 18
• A spanning root-forest selects one outgoing edge per non-root vertex and leads every vertex to t* or f*; its rank is the sum of its edge ranks.A forest is targeted if the initial state leads to t*, trapped if it leads to f*, and consistent with an opponent strategy when its edges use that strategy’s actions.Source: §B.2.2 · p. 18

B.3 The NP Upper Bound

• The limit-sure reachability problem belongs to NP: team action ranks give a polynomial-size description, and a stable opponent strategy avoids checking exponentially many opponent strategies individually.For fixed team ranks, checking one opponent strategy takes polynomial time, but enumerating all opponent strategies may take exponential time.Source: §B.3 · p. 19
• A certificate combines the team’s action ranks with one opponent strategy in an encoded Puiseux MDP, whose stability can be checked in polynomial time and implies optimality.Stability means the opponent cannot improve its value by choosing a different action for the next move and then following the original strategy; stable strategies exist.Source: §B.3 · p. 19

B.3.1 The encoded MDP

• Power-of-two tie-breaking encodes forest ranks so strict rank comparisons are preserved and distinct edge sets receive distinct encoded ranks.The encoded MDP provides the structure in which the opponent's values and response can be compared.Source: §B.3.1 · p. 19
• For a fixed opponent strategy, the encoded failure value is determined by forest weights, and a stable strategy exists and is optimal.Stability means no one-step action change improves the opponent's value; the minimum principle establishes optimality.Source: §B.3.1 · p. 20
• One stable opponent response suffices to certify the forest criterion for every deterministic memoryless response in the original game.The certificate equates universal satisfaction of the original criterion with a suitable stable strategy in the encoded MDP.Source: §B.3.1 · p. 21
• Stability can be checked in polynomial time by determining the signs of Bellman residuals rather than enumerating exponentially many forests.For each alternative action, the residual sign is determined by a minimum-rank tree; weighted matroid intersection finds the required tree in polynomial time.Source: §B.3.3 · pp. 22–24

B.3.4 The nondeterministic algorithm.

• The reachability algorithm is sound and complete, and its polynomial-size guesses and checks establish membership in NP.It guesses a strategy and response; the proof shows accepting guesses yield limit-sure winning, and winning strategies yield an accepting guess.Source: §B.3.4 · pp. 24–25

C Safety

• For safety, limit-sure winning implies almost-sure winning, using compactness of team strategies rather than the two-player fixed-point proof.The section states the converse direction is the one requiring proof.Source: C Safety · p. 25

C.1 Topological Preliminaries

• The safety proof uses compactness of the team-strategy space and closed threshold sets for fixed opponent strategies, then applies a nested-closed-set argument.The strategy space is a product of compact action-probability simplices.Source: C Safety · p. 25, §C.1 · p. 25

C.2 From Limit-Sure to Almost-Sure Winning

• Limit-sure and almost-sure winning coincide for safety objectives.The proof establishes the implication from limit-sure to almost-sure winning; the reverse follows directly from the definitions.Source: §C.2 · p. 26
• For safety, limit-sure, almost-sure, and sure winning are all equivalent, and the winning question is decidable in polynomial time.Sure safety is decided by computing the largest set of safe states that some team profile keeps closed against every opponent action profile.Source: §C.2 · p. 26

D IRATL

• Sure, almost-sure, and limit-sure safety coincide, and their winning set is computable in polynomial time by iterating to a fixpoint.The iteration decreases at most |S| times.Source: D IRATL · p. 27
• Sure reachability reduces to the two-player case, while almost-sure and limit-sure reachability are in NP.The cited results give polynomial algorithms for sure reachability and establish NP membership for the almost-sure and limit-sure cases.Source: D IRATL · p. 27
• The hardness reduction encodes sequentially nested SAT by having teammates independently select clause literals while the opponent challenges whether their choices are consistent.A satisfying assignment lets the team choose a true literal for each clause; almost-sure winning implies consistent choices from which an assignment can be extracted.Source: D IRATL · p. 27
• For each nested SAT layer, an almost-sure winning until objective holds exactly when that layer's formula is satisfiable under the earlier answers.The reduction's formula correspondence yields s_i |= Φ_k iff v_i = 1 for every k ≥ 2i.Source: D IRATL · pp. 29–30
• Qualitative IRATL model checking on explicitly represented finite stochastic game structures is P^NP-complete.The proof establishes membership in P^NP and P^NP-hardness.Source: D IRATL · p. 31
• Membership follows by evaluating state subformulas inside out and making polynomially many NP-oracle queries, at most one per state for each strategic subformula.There are at most |φ| state subformulas, and the winning problems queried are all in NP.Source: D IRATL · p. 31
• Hardness follows from Lemma D.2 with at most three players and deterministic transitions using only sure and almost-sure modalities.Source: D IRATL · p. 31