{"id":"1b507cbe-fddd-4b41-b00c-ce34d2d3cdf0","arxiv_id":"2607.07415","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Prefix-independent objectives over finite colors are positionally determined on vertex-colored one- and two-player games iff they are generalized parity objectives on ordered pairs of colors.","lead":"For finite color sets, a prefix-independent objective is positionally determined on vertex-colored games exactly when it is a parity condition on ordered pairs of consecutive colors. This closes the vertex-colored case left open by the 2006 edge-colored characterization and links the two settings.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates finiteness of Γ as the only essential hypothesis and notes that the paper itself supplies the matching counter-example for infinite alphabets. That hypothesis is used only after the anchored-word stage (which is already solid) and is therefore not a soft spot inside the claimed finite-color theorem. The remaining technical steps—mixing of cyclic words, total preorder of finite index, construction of the priority tree for pairs—are standard adaptations of the Colcombet–Niwiński / Zielonka arguments and contain no visible gap. Consequently the strongest claim stands, the reader’s verdict of ACCEPT is appropriate, and no adjustment is warranted.","tokens_in":21490,"tokens_out":447,"duration_ms":4760,"concrete_test":"Independently re-derive the quantifier-exchange statement of Lemma 20 (and the subsequent mixing lemmas 19–25) from the hub-cycle positional assumption alone, without invoking the later tree construction of Lemma 35; if the exchange fails for any concrete finite Γ and prefix-independent W that is known to be positionally determined on hub-cycles, the intermediate characterization collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence (positional determinacy on vertex-colored hub-cycle arenas ⇔ on all two-player arenas ⇔ generalized parity on ordered pairs) is supported by a complete chain of lemmas that the paper itself carefully delimits. Theorem 15 (anchored-word parity from hub-cycle positional determinacy) holds even for infinite Γ; the subsequent reduction to Muller-on-pairs (Lemma 34) and then to parity-on-pairs (Lemma 35) uses finiteness exactly where the authors prove it is necessary (Lemma 38). The 1-to-2 lift itself is obtained by a standard edge-colored parity game on the product alphabet Γ^{2} (Theorem 36). No hidden circularity, missing case, or unjustified quantifier exchange appears in the load-bearing steps.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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).","tokens_in":21681,"tokens_out":655,"duration_ms":6338,"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.","major_comments":[],"minor_comments":[{"comment":"Abstract and title page: “ordrerd” should be “ordered”.","section":null},{"comment":"Definition 2 / page 3: the inclusion Av ⊊ Ae is written with a strict-subset symbol; a non-strict symbol would be more accurate.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"References: a few arXiv identifiers (e.g., Colcombet–Idir) could be completed with final publication data if available.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance. The only remaining issues are purely presentational; the logical chain is complete and the necessity of finiteness is correctly delimited. No hidden circularity or missing case was found."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The paper gives a clean equivalence for prefix-independent objectives over finite colors: positional determinacy on vertex-colored hub-cycle arenas is equivalent to the same on all two-player vertex-colored arenas, and both are equivalent to generalized parity on ordered pairs of colors. That is the natural open case left by Colcombet–Niwiński, and they settle it.\n\nWhat is new is the intermediate notion of parity on anchored words, the careful quantifier-exchange and mixing lemmas that get you there from hub-cycle positional determinacy (even for infinite alphabets), and then the reduction through Muller-on-pairs to ordinary parity-on-pairs once finiteness is assumed. The two-way bridge via pairs is useful: you can turn a vertex game with a pair objective into an edge-colored parity game on Γ^{2} and transfer positional strategies back. The necessity of finite colors is shown cleanly with the Grädel–Walukiewicz infinite-priority example. The proof chain is fully written out; no circularity or hidden free parameters.\n\nSoft spots are minor and presentational. There are a few typos (\"ordrerd\", \"symetrically\"), the hub-cycle definition is a bit terse, and some of the technical lemmas in Section 4 are dense. Nothing load-bearing is missing; the stress-test note is right that the finiteness restriction is both necessary and correctly delimited. No machine-checked proofs, but the mathematics is classical and the citations to Zielonka, Colcombet–Niwiński, Kopczyński and Gimbert–Zielonka are accurate.\n\nThis is for people who work on infinite games, positional determinacy, and the edge/vertex distinction. It organizes the landscape rather than giving a new algorithm. I would bring it to reading group and I would cite the equivalence and the pair reduction. It deserves a serious referee; the result is solid enough for CONCUR or a theory journal after ordinary polishing.","headline":"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.","tokens_in":22304,"tokens_out":485,"would_cite":true,"duration_ms":6230,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["positional determinacy","vertex-colored games","parity objectives","one-to-two-player lift","hub-cycle arenas","prefix-independent objectives","ordered pairs of colors"],"falsifier":"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.","tokens_in":22386,"feed_emoji":"♟️","tokens_out":859,"duration_ms":8937,"temperature":0.7,"pith_summary":"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.","feed_headline":"One-player tests already decide two-player memoryless play","feed_subtitle":"For finite colors, positional determinacy on simple arenas equals parity on ordered color pairs","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["One-player positional tests decide two-player vertex parity","Finite colors equate 1- and 2-player positional determ. to pair-parity","Vertex colors: 1-player determ. lifts to 2-player via ordered pairs","Prefix-independent W on finite colors is pair-parity iff 1-player positional","Finiteness needed: 1-to-2 player lift holds only for finite vertex colors"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One-player positional tests decide two-player vertex parity","Finite colors equate 1- and 2-player positional determ. to pair-parity","Vertex colors: 1-player determ. lifts to 2-player via ordered pairs","Prefix-independent W on finite colors is pair-parity iff 1-player positional","Finiteness needed: 1-to-2 player lift holds only for finite vertex colors"]},"model":"grok-4.5","effort":"low","cost_usd":0.005232,"raw_usage":{"total_tokens":1440,"prompt_tokens":756,"num_sources_used":0,"completion_tokens":111,"cost_in_usd_ticks":52320000,"prompt_tokens_details":{"text_tokens":756,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":573,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":756,"tokens_out":111,"duration_ms":5772,"temperature":1.0,"reasoning_tokens":573,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T19:06:09.105731+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":2}