Pith. sign in

REVIEW 5 minor 15 references

Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift

T0 review · 0 major / 5 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For finite colors, one-player positional determinacy on vertex-colored games already forces two-player positional determinacy, and both equal parity on ordered color pairs.

desk verdict Clean 1-to-2 lift for vertex-colored games that closes the 2006 gap, with a usable pair-based dictionary between edge and vertex settings. read the letter →

arxiv 2607.07415 v1 pith:7PJUQUWX submitted 2026-07-08 cs.GT

Raphaël Berthon , Stéphane Le Roux This is my paper · ORCID
classification cs.GT
keywords positionaldeterminacyvertex-coloredgamesparityobjectivesone-to-two-playerlifthub-cyclearenasprefix-independentorderedpairsofcolors
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks which prefix-independent winning conditions make memoryless strategies enough in two-player games played on graphs whose vertices carry colors. It shows that, when the color set is finite, three statements are equivalent: the condition is positionally determined already on the simplest one-player hub-cycle arenas; it is positionally determined on every two-player vertex-colored arena; and it is exactly a generalized parity condition on consecutive pairs of colors. The same characterization fails as soon as infinitely many colors are allowed. The technical bridge that moves from single colors to ordered pairs also supplies a clean two-way translation between the classical edge-colored theory and the vertex-colored setting. A sympathetic reader therefore obtains both a precise classification of the objectives that admit memoryless play and a new dictionary relating the two natural ways of coloring a game graph.

What carries the argument

The reduction of positional determinacy on hub-cycle arenas to a generalized parity condition first on anchored words and then on ordered pairs of colors (via a Muller condition on limit 2-factor sets and a priority tree built from maximality). That chain of equivalences is what lifts one-player determinacy all the way to two-player determinacy.

What would settle it

Exhibit a single prefix-independent objective over a finite alphabet that is positionally determined on every vertex-colored hub-cycle arena yet fails to be a generalized parity condition on ordered pairs, or construct an infinite-color counter-example that nevertheless satisfies all three equivalent properties claimed for finite alphabets.

Watch

Extended reading notes

Core claim

For any prefix-independent objective W over a finite color alphabet, the following three properties are equivalent: W is positionally determined on every vertex-colored hub-cycle (one-player) arena; W is positionally determined on every vertex-colored two-player arena; and W is a generalized parity objective on ordered pairs of colors. Finiteness of the alphabet is necessary for the equivalence.

Load-bearing premise

The color set must be finite; without that restriction the step that turns a Muller condition on pairs into a genuine parity condition on pairs fails, and the whole equivalence collapses.

Editorial extensions

If this is right

  • Any objective that is not equivalent to parity on pairs can be shown non-positional already by a one-player hub-cycle arena.
  • Vertex-colored games admit strictly more positionally determined objectives than edge-colored games, because pairs of consecutive colors can encode transitions that single colors cannot.
  • The same pair-based translation converts any vertex-colored parity game into an ordinary edge-colored parity game (at the cost of a quadratic blow-up of the priority set), so existing edge-colored algorithms apply after a routine rewriting.
  • The intermediate notion of generalized parity on anchored words remains meaningful for infinite alphabets and may serve as a weaker but still useful characterization.
  • The correspondence suggests that other memory notions (finite-memory, half-positionality) can likewise be transferred between edge and vertex colorings by working with pairs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The pair-based dictionary may let existing finite-memory characterizations for edge-colored games be restated, almost verbatim, for vertex-colored games.
  • Quantitative (non-Boolean) preference relations that are monotone and selective on pairs could admit an analogous one-to-two-player lift on finite vertex-colored arenas.
  • Infinite-priority parity games sit outside the finite-color classification, so any complete theory of positional determinacy must treat the finite and infinite cases separately.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper proves that for any prefix-independent objective W over a finite color set Γ the following are equivalent: (a) W is positionally determined on all vertex-colored hub-cycle one-player arenas; (b) W is positionally determined on all vertex-colored two-player arenas; (c) W is a generalized parity objective on ordered pairs of colors. The argument proceeds by first deriving a generalized parity condition on anchored words from hub-cycle positional determinacy (Theorem 15, via mixing lemmas, quantifier exchange, and a total preorder of finite index), then showing that this yields a Muller condition on pairs (Lemma 34) and finally a generalized parity condition on pairs (Lemma 35). The converse direction reduces a vertex-colored pair-parity game to an ordinary edge-colored parity game on the product alphabet Γ^{2} (Theorem 36). Finiteness of Γ is shown to be necessary (Lemma 38).

Significance. The result supplies the first 1-to-2-player lift for positional determinacy of vertex-colored arenas, closing a natural gap left open by Colcombet–Niwiński (edge-colored case) and by the classical positional determinacy of parity games. The intermediate notions of hub-cycle arenas and of parity on anchored words / ordered pairs give a clean two-way correspondence between the edge-colored and vertex-colored settings. The proofs are fully written out with intermediate lemmas, and the necessity of finiteness is established by an explicit counter-example using Grädel–Walukiewicz infinite-priority games. These contributions are of clear interest to the infinite-game and automata communities.

minor comments (5)
  1. Abstract and title page: “ordrerd” should be “ordered”.
  2. Definition 2 / page 3: the inclusion Av ⊊ Ae is written with a strict-subset symbol; a non-strict symbol would be more accurate.
  3. Lemma 27, item 1: the claim “B2i ≠ ∅ for all i < n” is slightly mis-indexed; the non-emptiness statement should cover the classes that actually appear.
  4. Section 6.1: the comparison with Gimbert–Zielonka would benefit from an explicit statement that the running example is monotone but not selective, so that the reader sees immediately why the edge-colored characterisation does not transfer.
  5. References: a few arXiv identifiers (e.g., Colcombet–Idir) could be completed with final publication data if available.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: self-contained mathematical equivalence via explicit lemmas, with external black-box citations only for classical edge-colored parity results.

full rationale

The paper derives a clean 1-to-2-player lift for prefix-independent objectives on finite vertex-colored arenas: positional determinacy on hub-cycle one-player arenas is equivalent to the same on all two-player arenas and to being a generalized parity objective on ordered pairs of colors. The chain is Theorem 15 (hub-cycle positional o anchored-word parity, valid even for infinite Γ) o Lemma 34 (anchored-word o Muller-on-pairs, using finiteness) o Lemma 35 (Muller-on-pairs + hub-cycle positional o parity-on-pairs via an explicit tree of maximal sets) o Theorem 36 (parity-on-pairs o full two-player positional via a standard product-alphabet reduction to edge-colored parity). All intermediate lemmas are proved from first principles inside the paper (quantifier exchanges, mixing lemmas, preorders of finite index, etc.). Classical results (Zielonka, Emerson–Jutla, Colcombet–Niwiński, Grädel–Walukiewicz) are invoked only as black boxes for the already-settled edge-colored case and are externally established; they do not encode the vertex-colored claim. No parameters are fitted, no uniqueness theorem is imported from the authors’ own prior work, and the necessity of finiteness is proved separately (Lemma 38). The derivation is therefore independent of its inputs by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 3 invented entities

Pure theoretical paper. No fitted parameters. Relies on standard infinite-game notions (arenas, positional strategies, prefix-independence, parity) and on previously published positional-determinacy theorems for ordinary parity games. The only paper-specific constructs are definitional (hub-cycle arenas, anchored-word parity, pair priorities).

assumptions (4)
  • domain assumption Prefix-independence of the objective W (ΓW = W)
    Stated as standing hypothesis for the whole equivalence; used in every mixing and quantifier-exchange lemma.
  • domain assumption Classical positional determinacy of (generalized) parity games on edge-colored arenas (Zielonka, Emerson–Jutla, Mostowski)
    Invoked to obtain the 1c ⇒ 1b direction via the edge-colored reduction of Theorem 36.
  • domain assumption Positional determinacy of min-parity games with infinitely many priorities (Grädel–Walukiewicz)
    Used only in the negative result (Lemma 38) showing that finiteness of Γ cannot be dropped.
  • standard math Standard set-theoretic and word-combinatorial reasoning (limit superior, finite-index preorders, radix order)
    Background mathematics used throughout Sections 4–5.
invented entities (3)
  • Hub-cycle arena
    purpose: Minimal one-player arena class on which positional determinacy already forces the parity structure
    Definitional restriction already present in Colcombet–Niwiński; re-used here as the base of the 1-to-2 lift.
  • Generalized parity objective on anchored words
    purpose: Intermediate characterization between hub-cycle positional determinacy and pair parity
    Introduced in Definition 13; shown equivalent to the other notions when Γ is finite.
  • Generalized parity objective on ordered pairs of colors
    purpose: Target characterization of positionally determined vertex-colored objectives
    Definition 8; the main object of the equivalence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift." pith.science (2026). https://pith.science/paper/7PJUQUWX

@misc{pith2026260707415,
  author       = {Pith},
  title        = {Pith review of: Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7PJUQUWX}},
  note         = {Machine review of arXiv:2607.07415}
}
abstract

Positional determinacy of vertex-colored parity games was proved in the 1990s, which directly implies positional determinacy of edge-colored parity games. In 2006, it was shown that if a prefix-independent color-based objective ensures that every edge-colored two-player turn-based game is positionally determined, this objective is equivalent to a parity objective. We prove a similar result for vertex-colored games, namely that the following are equivalent for any prefix-independent objective $W$ over a finite set of colors: - $W$ is positionally determined on all vertex-colored one-player games. - $W$ is positionally determined on all vertex-colored two-player games. - $W$ is equivalent to a parity objective on ordrerd pairs of colors. We prove that finiteness of the color set is required for our equivalence to hold. Beyond this $1$-to-$2$-player lift, the technique that we develop to handle the pairs of colors establishes a promising 2-way correspondence between edge-colored games and vertex-colored games.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    , author =

    Half-positional Determinacy of Infinite Games. , author =

    work page

  2. [2]

    Allen Emerson and Charanjit S

    E. Allen Emerson and Charanjit S. Jutla , title =. 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1-4, 1991 , pages =. 1991 , url =. doi:10.1109/SFCS.1991.185392 , timestamp =

    work page doi:10.1109/sfcs.1991.185392 1991

  3. [3]

    Mostowski , title =

    A. Mostowski , title =. Research report 78 , year =

    work page

  4. [4]

    Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees , journal =

    Wies. Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees , journal =. 1998 , url =. doi:10.1016/S0304-3975(98)00009-7 , timestamp =

    work page doi:10.1016/s0304-3975(98)00009-7 1998

  5. [5]

    Thomas Colcombet and Damian Niwinski , title =. Theor. Comput. Sci. , volume =. 2006 , url =. doi:10.1016/J.TCS.2005.10.046 , timestamp =

    work page doi:10.1016/j.tcs.2005.10.046 2006

  6. [6]

    Games Where You Can Play Optimally Without Any Memory , booktitle =

    Hugo Gimbert and Wies. Games Where You Can Play Optimally Without Any Memory , booktitle =. 2005 , url =. doi:10.1007/11539452\_33 , timestamp =

    work page doi:10.1007/11539452 2005

  7. [7]

    Games Where You Can Play Optimally with Arena-Independent Finite Memory , journal =

    Patricia Bouyer and St. Games Where You Can Play Optimally with Arena-Independent Finite Memory , journal =. 2022 , url =. doi:10.46298/LMCS-18(1:11)2022 , timestamp =

    work page doi:10.46298/lmcs-18(1:11)2022 2022

  8. [8]

    TheoretiCS , volume =

    Patricia Bouyer and Mickael Randour and Pierre Vandenhove , title =. TheoretiCS , volume =. 2023 , url =. doi:10.46298/THEORETICS.23.1 , timestamp =

    work page doi:10.46298/theoretics.23.1 2023

Show all 15 references
  1. [9]

    Half-Positional Determinacy of Infinite Games , booktitle =

    Eryk Kopczy\'. Half-Positional Determinacy of Infinite Games , booktitle =. 2006 , url =. doi:10.1007/11787006\_29 , timestamp =

    2006 doi

  2. [10]

    TheoretiCS , volume =

    Pierre Ohlmann , title =. TheoretiCS , volume =. 2023 , url =. doi:10.46298/THEORETICS.23.3 , timestamp =

    2023 doi

  3. [11]

    TheoretiCS , volume =

    Antonio Casares and Pierre Ohlmann , title =. TheoretiCS , volume =. 2026 , url =. doi:10.46298/THEORETICS.26.5 , timestamp =

    2026 doi

  4. [12]

    Positional Determinacy of Games with Infinitely Many Priorities , journal =

    Erich Gr. Positional Determinacy of Games with Infinitely Many Priorities , journal =. 2006 , url =. doi:10.2168/LMCS-2(4:6)2006 , timestamp =

    2006 doi

  5. [13]

    2002 , url =

    Automata, Logics, and Infinite Games:. 2002 , url =. doi:10.1007/3-540-36387-4 , isbn =

    2002 doi

  6. [14]

    Formal Reasoning About the Security of

    Byron Cook , editor =. Formal Reasoning About the Security of. Computer Aided Verification - 30th International Conference,. 2018 , url =. doi:10.1007/978-3-319-96145-3\_3 , timestamp =

    2018 doi

  7. [15]

    An algebraic characterisation of

    Thomas Colcombet and Olivier Idir , year=. An algebraic characterisation of. 2604.22648 , archivePrefix=

    arXiv

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.