Infinite lexicographic products of positional objectives
Pith reviewed 2026-05-19 09:44 UTC · model grok-4.3
The pith
Infinite lexicographic products preserve positionality for prefix-independent objectives
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We propose two different notions of infinite lexicographic products indexed by arbitrary ordinals and prove that they preserve positionality of prefix-independent objectives. In the one-player setting this extends positional determinacy results to edge-labelled games and arbitrarily many priorities for both Max-Parity and Min-Parity. The Max-Parity objectives over countable ordinals are complete for the infinite levels of the difference hierarchy over Σ⁰₂ while Min-Parity is complete for Σ⁰₃, yielding new insights on closure under unions and neutral letters.
What carries the argument
Two notions of infinite lexicographic products indexed by arbitrary ordinals, which combine objectives by deciding the winner according to the earliest differing component in the ordinal ordering.
Load-bearing premise
The component objectives must be prefix-independent.
What would settle it
A concrete counter-example consisting of prefix-independent positional objectives whose infinite lexicographic product fails to be positional on some graph with neutral transitions.
read the original abstract
This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs with neutral transitions. Recently, [Ohlmann, TheoretiCS 2023] established that positionality of prefix-independent objectives is preserved by finite lexicographic products. We propose two different notions of infinite lexicographic products indexed by arbitrary ordinals, and extend Ohlmann's result by proving that they also preserve positionality. In the context of one-player positionality, this extends positional determinacy results of [Gr\"adel and Walukiewicz, Logical Methods in Computer Science 2006] to edge-labelled games and arbitrarily many priorities for both Max-Parity and Min-Parity. Moreover, we show that the Max-Parity objectives over countable ordinals are complete for the infinite levels of the difference hierarchy over $\Sigma^0_2$ and that Min-Parity is complete for the class $\Sigma^0_3$. We obtain therefore positional languages that are complete for all those levels, as well as new insights about closure under unions and neutral letters.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines two notions of infinite lexicographic products of prefix-independent objectives, indexed by arbitrary ordinals, and proves that both preserve positionality. This extends Ohlmann's 2023 finite-product result. The authors further apply the framework to obtain positional determinacy for edge-labelled Max-Parity and Min-Parity games over countable ordinals, establish completeness of these objectives for the infinite levels of the difference hierarchy over Σ⁰₂ and for Σ⁰₃, and derive new closure properties under unions and neutral letters.
Significance. If the preservation proofs hold, the work substantially enlarges the class of positional objectives available for infinite-duration games on arbitrary graphs. It supplies the first positional complete languages for all infinite levels of the difference hierarchy over Σ⁰₂ and for Σ⁰₃, while clarifying how positionality interacts with transfinite lexicographic combinations. The explicit handling of limit ordinals and the two distinct product constructions are technically valuable contributions.
major comments (1)
- [§4.3] §4.3, Theorem 4.7 (limit-ordinal case): the inductive construction of the positional strategy for a limit ordinal λ appears to rely on a choice of cofinal sequence; it is not shown that the resulting strategy remains positional independently of this choice. A concrete verification for λ=ω would strengthen the claim.
minor comments (3)
- [§3] Definition 3.2 and Definition 3.4: the two product notions are introduced with similar but non-identical notation for the ordinal indexing; a side-by-side comparison table would improve readability.
- [§5.2] The completeness statements in §5.2 cite the difference hierarchy but do not recall the precise definition of the levels used; adding a short reminder paragraph would help readers outside descriptive set theory.
- [Figure 2] Figure 2 (example game for ω-product): the edge labels are difficult to read at the printed size; increasing font size or adding a legend would clarify the illustration.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the positive recommendation. We address the major comment below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [§4.3] §4.3, Theorem 4.7 (limit-ordinal case): the inductive construction of the positional strategy for a limit ordinal λ appears to rely on a choice of cofinal sequence; it is not shown that the resulting strategy remains positional independently of this choice. A concrete verification for λ=ω would strengthen the claim.
Authors: We agree that the independence of the constructed strategy from the particular cofinal sequence should be stated more explicitly. In the proof of Theorem 4.7 the strategy for a limit ordinal λ is obtained by taking the pointwise limit (in the sense of the lexicographic product) of the positional strategies already obtained for a strictly increasing sequence of smaller ordinals whose supremum is λ. Because the objectives are prefix-independent, any two cofinal sequences that are eventually equal yield identical strategies; when the sequences differ, the resulting strategies remain equivalent with respect to the objective and therefore induce the same winning sets. Nevertheless, to make this independence fully transparent we will insert a short additional paragraph (and a small diagram) that carries out the verification explicitly for λ=ω, showing that any two strictly increasing sequences of natural numbers produce positional strategies that coincide on every finite prefix. This clarification will appear in the revised §4.3. revision: yes
Circularity Check
Minor self-citation of co-author's 2023 finite-case result; transfinite extension and completeness claims are independently derived
full rationale
The manuscript introduces two novel definitions of infinite lexicographic products over arbitrary ordinals and supplies a direct proof that these preserve positionality for prefix-independent objectives, thereby extending the finite-case theorem of Ohlmann (TheoretiCS 2023). The argument invokes classical positional-determinacy results for parity games and carries the prefix-independence hypothesis forward without modification at limit ordinals; the new completeness statements for the difference hierarchy over Σ⁰₂ and Σ⁰₃ are established inside the paper via explicit constructions on countable ordinals. No equation or central claim reduces by construction to a fitted parameter, a renaming of a known pattern, or an unverified self-citation loop; the 2023 citation functions as an external base case rather than a load-bearing substitute for the present proofs. The derivation is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Lexicographic order on sequences indexed by ordinals is well-defined and total
- domain assumption Prefix-independence of component objectives
invented entities (1)
-
Two notions of infinite lexicographic product
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.