Mean-payoff parity games in quasipolynomial time

Proof. The winning-set bound is [10, Theorem 1.1]. Its Corollary 7.1 supplies exact values and globally optimal positional strategies. Positional attainment identifies U_{\mathrm{mp}}(H) with the vertices of nonnegative value; at every other vertex Min’s strategy bounds the payoff by its strictly negative value. These assertions use the same liminf convention as (1).□

Proof. Fix the global positional strategy of Proposition 2.1, retaining its chosen edge at each Max vertex and all edges at Min vertices. Every simple directed cycle in this graph has nonnegative weight: otherwise Min could repeat a negative cycle starting on it, contradicting the global guarantee. Delete simple cycles successively from any finite walk. Their nonnegative weights leave a path of at most N-1 edges whose weight is no greater than that of the original walk. Its weight is at least -(N-1)W_H.□

Proof. For (i), use a strategy keeping play in D. At P-vertices its choices remain in R by closure. At Q-vertices every ambient successor stays in D, and the restricted opponent must choose one in R. Hence play remains in the intersection and wins. This also establishes that the intersection is total.

For (ii), Q can choose the edges of its restricted dominion strategy, and P cannot exit R. The same plays and winning condition result in H.

For (iii), D is closed at Q’s vertices and is disjoint from X. The attractor-avoidance observation above shows that it is disjoint from \Attr_Q^H(X). Its winning strategies and the opposing choices within D are therefore retained.□

Proof. Suppose first that d is odd. On entering R, \mathrm{Min} starts a winning strategy for the game on R and follows it until play leaves R. The set R is closed at \mathrm{Min}’s vertices, so such an exit can only be chosen by \mathrm{Max}. In A, \mathrm{Min} follows an attracting strategy to S. After reaching S, take one edge, with an arbitrary choice if the vertex belongs to \mathrm{Min}, and resume the same rule.

If S is visited infinitely often, its odd priority is the least priority occurring infinitely often, and \mathrm{Min} wins. Otherwise play eventually stays in R: each entry into A would force another visit to S in bounded time. The final stay in R follows one winning strategy, so prefix independence again gives a win for \mathrm{Min}. The one-edge step after reaching S ensures that successive applications of the rule advance the play.

Now let d be even. By Lemma 2.2, fix a mean-payoff strategy on H whose every finite prefix, from every start, has weight at least -B. For each x\in R, also fix one conjunction-winning strategy \sigma_x in R satisfying (2). These choices will remain fixed throughout the construction.

Starting at any vertex of H, \mathrm{Max} plays rounds j=1,2,\ldots. Round j has the following parts.

1. (i)

   Follow the mean-payoff strategy for exactly j edges.

2. (ii)

   If the current vertex is some x\in R, start \sigma_x and follow it for as long as play stays in R. If play never leaves R, this is the remainder of the infinite play.

3. (iii)

   Once play is in A, follow an attracting strategy to S. End the round upon reaching S, counting this as already accomplished if its first vertex in this part lies in S.

The next round starts at the vertex of S just reached. Since R is closed at \mathrm{Max}’s vertices, any exit in the second part is chosen by \mathrm{Min}. If S=\varnothing, then R=H and the second part of the first round simply lasts forever.

If infinitely many rounds finish, they give infinitely many visits to S at distinct times: round j contains at least j edges. The least infinitely recurring priority is then the even number d. If only finitely many rounds finish, the unfinished round has an infinite second part, since its first and third parts have bounded length. Its tail follows a conjunction-winning strategy in R. Thus the constructed strategy satisfies parity in either case.

It remains to prove the uniform prefix property; this will also establish the mean-payoff condition. Let W bound the absolute edge weights in H, and fix \delta>0. Choose a common constant C_\delta for the finitely many strategies \sigma_x; use C_\delta=0 if R is empty. Any internal prefix of the second part, of length t', has weight at least -\delta t'-C_\delta. This applies even if the ambient play subsequently exits R: the internal prefix is a consistent finite path in the total arena R. The exiting edge is counted separately and costs at most W. The attraction then uses at most |H| edges. The four contributions are displayed in Figure 1. Every prefix of a round, including a completed round, therefore has weight at least

where t is the length of that prefix.

If q rounds have completed by time T, then T\geq 1+2+\cdots+q. Including a possible unfinished round, at most 1+\sqrt{2T} rounds contribute to the T-edge prefix \rho_T. Summing (3) gives

For a given \epsilon>0, set \delta=\epsilon/2 and K=K_{\epsilon/2}. The elementary inequality

shows that (2) holds with C_\epsilon=K+K^2/\epsilon. Only the analysis, not the strategy, depends on \epsilon.□

Proof. We prove both assertions by induction on the number of vertices. They are vacuous in the empty arena. Let H be nonempty and assume the assertions for all smaller arenas.

First observe how a nonempty set of already established winners reduces the induction. Suppose Y\subseteq H is nonempty and every vertex of Y is winning for a player J, with strategies satisfying (2) if J=\Max. Every vertex of Z=\Attr_J^H(Y) is also winning for J: attract to Y, then start a winning strategy from the vertex reached. Attraction lasts at most |H| edges. If J=\Max, its bounded loss and the finite choice of target strategies preserve (2).

Apply the induction hypothesis to the smaller arena H\setminus Z. It is closed at J’s vertices. A strategy there for the opponent of J can therefore keep play in this subarena and remains winning in H. A strategy there for J is followed until any exit to Z, at which point J starts the winning strategy in H associated with the entry vertex. There is at most one such switch: the new strategy is continued on all subsequent histories, even if it later leaves Z. Prefix independence proves that this strategy wins.

When J=\Max, the switch also preserves the quantitative property. For each \epsilon>0, the internal prefix in H\setminus Z and the prefix after the switch have lower bounds of the form -\epsilon t_1-C_1 and -\epsilon t_2-C_2. The intervening edge costs at most W, where W bounds the absolute weights in H. Taking the constants in common over the finitely many possible entry vertices gives a bound with slope -\epsilon and constant C_1+C_2+W. Prefixes before a switch satisfy the first bound. If J=\Min, the winning strategies of \mathrm{Max} remain entirely in the subarena and retain their prefix bounds without switching. Thus finding such a nonempty Y proves both assertions for H.

Let d=\min_{v\in H}p(v), let P be \mathrm{Max} for even d and \mathrm{Min} for odd d, and let Q be the other player. Set

If d is even and \mathrm{Max} does not win for mean payoff alone everywhere in H, Proposition 2.1 supplies a nonempty set of vertices from which \mathrm{Min} can force failure of the mean-payoff condition. These are conjunction-losing vertices, so they provide Y with J=\Min in the preceding reduction. We may therefore assume that the mean-payoff hypothesis of Lemma 3.1 holds whenever d is even.

Since S is nonempty, R has fewer vertices than H. Apply induction to the game on R. If its Q-winning set is nonempty, these strategies remain winning in H: R is closed at P’s vertices, so Q can keep play there. Their prefix bounds also remain valid when Q=\Max. They provide the required set Y with J=Q.

In the remaining case, P wins everywhere in R, with the uniform prefix property when P=\Max. Lemma 3.1 now proves the assertions for all of H. Finally, a vertex cannot be winning for both players, since their objectives are complementary.□

Proof. Inside the induced game on D, form

Because D is a Q-dominion, it is closed at P’s vertices in H. The attractor complement R_D is closed at P’s vertices in D, hence also in H. It is disjoint from S, so the attractor-avoidance observation in Section 2 gives R_D\subseteq R.

If d is even, \mathrm{Max} wins for mean payoff alone everywhere in D as well. Indeed, the choices of \mathrm{Max} under a winning strategy in H remain available in D, because D is closed at \mathrm{Max}’s vertices; \mathrm{Min} is restricted to choosing edges in D.

Suppose that the game on R_D has no Q-winning vertex. Theorem 3.2 makes every vertex there winning for P, with the uniform prefix property if P=\Max. Apply Lemma 3.1 to the arena D, using the target D\cap S and its residual arena R_D. All its hypotheses have just been verified, so P wins everywhere in D, contrary to the fact that D is a nonempty Q-dominion. This argument includes R_D=\varnothing, when its winning-strategy hypothesis is vacuous.

Consequently the Q-winning set in R_D is nonempty. It is a Q-dominion there, and it lifts to a Q-dominion in R by Lemma 2.3, since R_D is closed at P’s vertices. It is contained in D, as required. If S=\varnothing, then R=H and R_D=D; the same argument applies.□

Proof. We induct on the number of distinct priorities in H. The empty-arena and zero-bound cases terminate immediately and have the stated guarantee: the only dominion subject to a zero size bound is empty, and the other player receives the whole arena.

Consider a call with H\ne\varnothing and both bounds positive. Its fixed value d occurs in H. Every child arena R_U excludes all vertices of priority d and is a subset of H. It therefore has strictly fewer distinct priorities than H, so the induction hypothesis applies to every child. This remains true if d has disappeared from U before the child is formed: the strict decrease is relative to the parent’s input H, even when R_U=U. Each continuation of a phase loop deletes a nonempty set. Thus its children terminate by induction, its loop can continue at most |H| times, and the enclosing call terminates.

Preservation of P-dominions. Fix a P-dominion D in H with |D|\le b_P. We show that every deletion leaves all of D in the current arena and preserves it there as a P-dominion. Suppose this holds immediately before a deletion. For a deletion in the mean-payoff step, P=\Max. A winning strategy that stays in D also wins for mean payoff alone in U, so D\cap X=\varnothing. Since D is closed at Q’s vertices, Lemma 2.3 shows that \Attr_Q^U(X) misses D and preserves its dominion property in the residual arena.

For a deletion obtained from a recursive call, the restriction R_U is closed at P’s vertices. The same lemma therefore makes D\cap R_U a P-dominion in R_U. Its size is at most b_P, and both kinds of child call retain this bound for P. By the induction hypothesis, the child labels every vertex of D\cap R_U for P. Its Q-labelled set C\subseteq R_U is consequently disjoint from D. Again \Attr_Q^U(C) misses D and preserves it as a dominion. This argument applies to deletions in either phase and in the unchanged-bounds stage. Hence D lies in the returned set \Lambda_P. In particular, this reasoning uses only the child’s guarantee on small dominions; it does not require that every vertex of C actually be winning for Q.

Removal of Q-dominions. Fix a Q-dominion D in H with |D|\le b. Every current arena is obtained from the preceding one by removing a Q-attractor. Each such restriction is closed at Q’s vertices. Applying the intersection part of Lemma 2.3 after each deletion gives

Unlike the preceding preservation argument, this assertion allows some vertices of D to have been deleted.

Suppose a phase returns a nonempty arena U. It did so because its last reduced-bound child returned no Q-labelled vertices. The induction hypothesis then implies that

Moreover, when d is even, the mean-payoff step immediately before that child certified U_{\mathrm{mp}}(U)=U. Thus, at a nonempty phase return, all hypotheses of Lemma 3.3 hold in U: every priority is at least d, and the required mean-payoff condition holds when d is even. No occurrence of priority d in the current U is required.

Let U_1 be the arena returned by the first phase. If D\cap U_1 is nonempty, it is a Q-dominion there by (6). Lemma 3.3 gives a nonempty Q-dominion E of the game on R_{U_1} such that

Here the strict lower bound follows from (7). The unchanged-bounds child has Q-bound b, so it labels all of E for Q. Its subsequent attractor deletion therefore removes at least b'+1 vertices of D, leaving at most |D|-(b'+1)\le b-b'-1\le b' vertices. If D\cap U_1 was already empty, no vertices of D remain. Thus, in either case, the arena U at the start of the final phase satisfies

Let U_2 be the arena returned by the final phase. If D\cap U_2 were nonempty, it would be a Q-dominion in U_2 of size at most b' by (6) and (8). Applying Lemma 3.3 once more would produce a nonempty Q-dominion in R_{U_2} of size at most b', contradicting (7). Therefore D\cap U_2=\varnothing, and every vertex of D receives label Q. The two arguments prove the induction step for both players.□

Proof. Consider the tree of calls to \Solve, counting its immediate base cases as nodes. Every child omits the minimum priority of its parent’s input arena. Thus a path has at most n edges, independently of the numerical values of the priorities.

Each node has at most one child with both size bounds unchanged. Every other child has one bound halved, with rounding down. In either phase, a child is followed by a nonempty deletion unless that phase returns. Each phase therefore makes at most n+1 child calls, giving at most

children with a halved bound at a node. Along a path, either one of the two size bounds can be halved at most 1+\lfloor\log_2 n\rfloor times before reaching zero, where the recursion stops. Consequently, there are at most

halving edges on any path.

The resulting path count is the same combinatorial saving that underlies reduced-precision parity recursion [11]. For a path of length \ell with j halving edges, choose their positions and, at each one, the child index among at most M halving children. At every remaining position there is at most one available unchanged-bounds child. This gives at most \binom{\ell}{j}M^j paths of that type. As each node is specified by its root-to-node path, the total number of calls N_{\rm rec} satisfies

The second inequality uses \binom{\ell}{j}\le n^j and nM\ge1; it also covers n=1.

We next count the nonrecursive work at a node. A phase iteration that continues deletes at least one vertex. The two phases together therefore make at most n+2 iterations, allowing one final return iteration for each phase. In particular, they make O(n+1) ordinary mean-payoff calls. Attractor computations, construction of induced subarenas, scans for minimum priorities, and updates of the two size bounds all take polynomially many bit operations in L+2. No step iterates through the integers between two successive priority values: minimum priorities and equality tests are computed directly from their binary encodings.

All mean-payoff instances use induced subarenas of the original graph, with the weights w(v,u)=r(v). Renumbering retained vertices uses only polynomial space and time. Even if the reward r(v) is copied explicitly onto every retained outgoing edge, the total number of weight bits is at most the number of edges times the largest original reward bit length, hence polynomial in L+2. The rest of each subroutine input is also polynomial in L+2. This proves the claimed input-length bound without a dependence on the numerical magnitude of a reward. Combining these per-node bounds with (9) proves the proposition.□

Proof of Theorem 1.1. The empty arena has an empty winning set and is handled immediately. For a nonempty arena, the output of \Solve(G,(n,n)) is exact by Theorem 4.1 and the winning-region argument at the end of Section 4.

Proposition 2.1 implements each ordinary mean-payoff call of input length L' in 2^{O((\log_2(L'+2))^2)} bit operations, uniformly and deterministically. By Proposition 5.1, there is an absolute constant a such that L'\le(L+2)^a for every call, after increasing a if necessary. Its cost is therefore 2^{O((\log_2(L+2))^2)}. The number of calls and all remaining work have the same bound, since n is polynomially bounded by the explicit input length. Their product is again

All graph operations and recursion choices admit deterministic implementations, so the complete procedure has the stated uniform deterministic bit complexity. In particular, the constants do not depend on the number of priorities or on the numerical sizes of the binary rewards and priorities.□