{"id":"0f350ec7-65ae-4bae-bfd0-bc49158f53b2","arxiv_id":"2509.04129","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of memory and randomness complexity for strategies in reactive synthesis, arguing that Mealy-machine-based measures of simplicity are representation-dependent.","lead":"This invited survey reviews what makes game strategies for controller synthesis simple or complex, focusing on memory and randomness, and argues that the usual measure of complexity depends on how strategies are represented. A generalist should read it as a concise map of the field and a case that how we count 'simple' may be misleading in practice.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Section 5 is a clearly framed position argument, and its informal notion of practical simplicity is disclosed rather than hidden.","rationale":"The reader's verdict of ACCEPT is appropriate because the paper is a self-described invited survey. Section 5 is explicitly suggestive rather than theorem-like, and the paper provides pointers to primary literature and discloses its own hand-waving. The reader's weakest-assumption concern—that 'practical simplicity' is not formalized—is the closest thing to a weakness, but it is not load-bearing for the survey's acceptance: the paper's central observation that Mealy-state counts are model-dependent is supported by examples, and its call for a representation-agnostic theory is framed as a research agenda, not a proven conclusion. The manuscript also earns credit for clearly flagging its own limitations and for citing independent lines of work on alternative strategy representations. No technical error or overreach was found that would require a conditional or revised verdict.","tokens_in":15328,"tokens_out":4215,"duration_ms":46423,"concrete_test":"To test the normative part, formalize 'practical simplicity' for the Fig. 8 examples as, e.g., program size, circuit size, or description length of an implementation (Kolmogorov complexity of the strategy description), and check whether the ordering predicted by the paper—counter strategy simple, Mealy state count misleading—is preserved. If under a natural formalization the counter strategy is not simpler, the Section 5 slogan would need qualification; if it is, the position survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper is an invited survey and makes no pretense of proving a formal theorem in Section 5. The central claim—that Mealy-state count can misrepresent practical simplicity—is supported by two illustrative examples showing that measured complexity can shift under representation changes (Fig. 8). This supports the accurate, weaker reading that strategy complexity is representation-relative. The stronger normative reading, that ranking by Mealy states 'misrepresents' practical ease, rests on an unformalized notion of practical simplicity that is indeed not formally defined. This is a real limitation, but it is explicitly acknowledged in the paper's own warning about informal treatment and hand-waving in Section 1, and it does not undermine the survey's reliability. The examples are not circular: the counter-based example in Fig. 8b genuinely shows a representation with logarithmic descriptive state size versus N+1 flat memory states. No internal inconsistency or unsupported technical claim was found in the survey's main results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This invited survey addresses the complexity of winning and optimal strategies in game-theoretic controller synthesis. It recalls the basic game models, objectives, and the standard Mealy-machine representation of strategies. Sections 3 and 4 summarize recent results on memory and randomized strategies, including a characterization of finite-memory determinacy via arena-independent chromatic memory structures, a one-to-two-player lift, a characterization of omega-regularity via finite-memory determinacy on infinite arenas, and a complete taxonomy of randomized finite-memory strategies. Section 5 argues that the usual measure of complexity—number of Mealy memory states—is representation-dependent: it gives a memoryless strategy whose intuitive simplicity is not reflected in its single-state encoding, and a counter-based strategy whose Mealy encoding needs N+1 states but is simple in a programmatic representation. The paper advocates studying alternative representations (decision trees, strategy machines, enriched Mealy machines, programs, neural networks) and developing a representation-agnostic complexity theory.","tokens_in":143,"tokens_out":5885,"duration_ms":111313,"significance":"If the thesis of Section 5 is adopted, it would push the community to reconsider rankings of strategies based solely on Mealy-state counting and to develop richer complexity measures that reflect implementation, explanation, and verification effort. The survey's main contribution is organizational and programmatic rather than theorem-based; it condenses a significant body of recent work, including the author's own results on memory and randomized strategies, into an accessible narrative. It cites primary sources for all formal statements and is candid about its informal treatment. The examples in Section 5 effectively demonstrate that the Mealy-state measure can be representation-relative, although the stronger normative conclusion about 'practical simplicity' rests on an informal notion that the paper itself does not formalize. This is a limitation, but an openly acknowledged one for a position-style invited survey.","major_comments":[],"minor_comments":[{"comment":"The claim that the counter-based strategy is 'easily implementable with a simple counter' would be strengthened by an explicit sentence distinguishing the mathematical fact (the number of Mealy states is representation-dependent) from the informal judgment about practical simplicity. As written, the normative reading is clear but the criteria for 'practical simplicity' are left implicit. I suggest adding one paragraph stating that no formal definition is intended and that a formal treatment is left for future work.","section":"Section 5, Fig. 8"},{"comment":"The warning about informality is useful. Since Section 5 introduces the phrase 'practical simplicity' without a definition, consider placing a similar caveat there.","section":"Section 1, Outline"},{"comment":"Minor typo: 'N + 1distinct' should be 'N + 1 distinct'.","section":"Section 5, first paragraph"},{"comment":"The taxonomy diagram is presented without mentioning that the inclusions are proved in [41]. Adding a one-line pointer adjacent to the figure would help readers who are not familiar with the source.","section":"Section 4, Fig. 5"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is an invited survey and is heavily centered on the author's own line of work. That is natural and clearly disclosed; references are accurate. The paper is a good fit for a journal or forum that publishes survey/position pieces. No concerns about novelty or citation discipline."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague, quick take: this is a self-described invited survey, not a new-result paper. What it does well: it synthesizes the author's recent line of work on memory and randomness complexity in reactive synthesis, and it makes a genuinely interesting point in Section 5 that the standard Mealy-machine measure of strategy complexity is representation-dependent. The two examples—the structurally different memoryless strategies and the energy-Büchi counter strategy—make the point concretely. The randomness taxonomy in Section 4 is also a useful digest of results scattered across several papers.\n\nThe soft spots are mostly disclosed ones. The paper leans heavily on the author's own papers; that's expected for a personal survey, but it means a reader looking for an independent map of the field should supplement it. The bigger soft spot is Section 5's central claim: the paper argues that Mealy-based complexity can 'misrepresent' practical simplicity, but 'practical simplicity' is never given a formal definition. The examples show representation-dependence, which is a solid observational claim; but the leap to 'misrepresent' depends on an intuitive notion that the paper itself admits is informal. That doesn't sink the paper, but it does mean Section 5 is a position statement and a call for future work rather than a settled argument.\n\nI think the reader's assessment is about right. There are no internal inconsistencies I could find, and the theorem statements are properly attributed. The survey is worth a serious referee: it's not a desk-reject, and an editor should send it out. If I were refereeing, I'd ask the author to be more explicit that Section 5 is a research agenda and perhaps to sketch what a formalization of 'practical simplicity' could look like, but I wouldn't require new theorems for acceptance.\n\nWho is it for? Someone working in games/reactive synthesis who wants a quick orientation on recent memory/randomness results and a conversation-piece about strategy representations. I'd probably cite it for the Section 5 point.","headline":"Solid, honest survey of memory/randomness complexity; the Section 5 representation-dependence argument is the memorable part, but it's a position statement, not a formal theory.","tokens_in":15959,"tokens_out":2030,"would_cite":true,"duration_ms":19554,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q60","91A50","03D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Strategy complexity in reactive synthesis is not an intrinsic property of a strategy: the paper argues the standard Mealy-machine measure is representation-dependent and can misorder how simple controllers really are.","keywords":["reactive synthesis","strategy complexity","Mealy machines","games on graphs","finite memory","randomized strategies","multi-objective games","controller synthesis"],"falsifier":"A computed falsifier: define a formal 'program complexity' for strategies, say the size of a while-loop-plus-counter program that computes the next action, and check whether minimal Mealy-state size and minimal program size diverge on a family of games. The paper's energy-Büchi example predicts an exponential gap; proving that for every omega-regular objective the two measures are polynomially related would refute the representation-dependence claim.","tokens_in":15284,"feed_emoji":"🎮","tokens_out":7455,"duration_ms":69853,"temperature":0.7,"pith_summary":"This paper argues that the standard way of measuring strategy complexity in reactive synthesis—counting the memory states in a Mealy machine—is representation-dependent and can misrepresent how simple a controller actually is to explain, verify, and implement. It surveys recent results showing when memory and randomness are needed for optimal play in games on graphs, including a finite-memory analogue of the classical memoryless determinacy characterization and a strict taxonomy of randomized finite-memory strategies. The core plea is for a representation-agnostic theory of strategy complexity, where a controller's true cost is assessed independently of the particular machine format used to encode it. If the claim holds, ranking strategies by Mealy-state count, a widespread practice, may send synthesis in the wrong direction.","feed_headline":"Counting Mealy states misreads strategy simplicity","feed_subtitle":"A survey argues controllers that look exponentially complex in the standard model can be simple one-counter programs.","key_machinery":"The load-bearing object is the Mealy machine model of a strategy (memory states plus a next-action function and an update function), which the paper argues is the source of the apparent complexity: by flattening data structures like counters into distinct states, it inflates complexity, while treating irregular lookup tables as equally simple. For the technical results on memory, the key tool is the arena-independent chromatic memory structure, whose monotonicity and selectivity conditions characterize when strategies based on that memory suffice for both players and yield one-to-two-player lifts.","core_discovery":"The paper's central claim is that 'simplicity' of a strategy is not an intrinsic property: it depends on the representation. Under the standard Mealy-machine model, all memoryless strategies count as equally simple, yet two single-state strategies can differ widely in how easy they are to explain or implement; conversely, a strategy that cycles in a state N times before moving looks pseudo-polynomial in Mealy states but is naturally a one-counter program. The paper supports this with a review of results: arena-independent chromatic memory structures characterize when finite-memory strategies suffice for both players, with one-to-two-player lifts; chromatic finite-memory strategies characteri","pith_inferences":["A testable extension is a formal cost model for strategies as programs (counters, loops, trees) and a systematic comparison of description length against Mealy-state count across synthesis benchmarks; the paper's examples suggest the rankings would diverge.","Existing lower bounds stated in Mealy states, such as 'exponential memory required,' may overstate practical difficulty for objectives with structured data representations; reinterpreted as program-size bounds, some may collapse.","A representation-agnostic theory would likely need to treat interpretability as a cost dimension, which cannot be settled by expressiveness alone; the paper leaves that formalization open.","The decision-tree and enriched-Mealy alternatives point to an analogy with data structures in algorithm design: complexity should be measured on the structure actually used, not on a flattened encoding."],"forward_implications":["If the standard measure is model-dependent, minimizing Mealy-state count can misorder strategies that are simple in practice; controller synthesis should compare representations, not just machines.","Finite-memory determinacy lifts from one-player to two-player games exactly when objectives are monotone and selective with respect to an arena-independent chromatic memory structure.","In stochastic games, the same arena-independent finite-memory techniques lift optimal play from MDPs to stochastic games.","A winning condition admits chromatic finite-memory strategies in every infinite arena exactly when it is omega-regular, tying strategy memory to automata-theoretic regularity.","Under finite memory, behavioral, mixed, and general randomized strategies form a strict expressiveness hierarchy; the classical equivalence between behavioral and mixed strategies collapses."],"supporting_citations":[{"why":"Supplies the memoryless-determinacy characterization and the one-to-two-player lift that the paper seeks to generalize.","marker":"[35]"},{"why":"Gives the finite-memory analogue via arena-independent chromatic memory structures, with monotonicity and selectivity modulo a memory structure.","marker":"[9]"},{"why":"Extends the characterization and lift to stochastic games, from MDPs to SGs.","marker":"[11]"},{"why":"Proves the equivalence between chromatic finite-memory determinacy in infinite arenas and omega-regularity.","marker":"[13]"},{"why":"Establishes the strict taxonomy of randomized finite-memory strategy classes, showing the classical behavioral/mixed equivalence fails under finite memory.","marker":"[41]"},{"why":"Shows payoff sets in multi-objective MDPs are the convex hull of pure payoffs, bounding the randomness needed for any target payoff.","marker":"[42]"},{"why":"Serves as the canonical textbook treatment of games on graphs and the Mealy machine representation that the paper questions.","marker":"[32]"},{"why":"Articulates the 'simple strategies are better' premise in synthesis that the paper challenges.","marker":"[31]"}],"fun_headline_variants":["Why counting Mealy states gets simplicity wrong","Strategy simplicity is not what Mealy machines say","One-counter insight reshapes synthesis simplicity","The beholder decides if a controller is simple","Reactive synthesis: simplicity is representation-dependent"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that 'practical simplicity'—how easy a strategy is to explain, verify, and implement—is a meaningful property that can be discussed without a formal definition; if it cannot be made precise, the paper's call for a representation-agnostic theory lacks a well-defined target.","fun_headline_variants_meta":{"raw":{"variants":["Why counting Mealy states gets simplicity wrong","Strategy simplicity is not what Mealy machines say","One-counter insight reshapes synthesis simplicity","The beholder decides if a controller is simple","Reactive synthesis: simplicity is representation-dependent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1193,"prompt_tokens":627,"completion_tokens":566,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":371,"completion_tokens_details":{"reasoning_tokens":499}},"tokens_in":371,"tokens_out":566,"duration_ms":5571,"temperature":1.0,"reasoning_tokens":499,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T10:20:42.398263+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A computed falsifier: define a formal 'program complexity' for strategies, say the size of a while-loop-plus-counter program that computes the next action, and check whether minimal Mealy-state size and minimal program size diverge on a family of games. The paper's energy-Büchi example predicts an exponential gap; proving that for every omega-regular objective the two measures are polynomially related would refute the representation-dependence claim.","supporting_citations":[{"cited_title":"In: Abadi, M., de Alfaro, L","cited_arxiv_id":null,"evidence_quote":"Supplies the memoryless-determinacy characterization and the one-to-two-player lift that the paper seeks to generalize."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the strict taxonomy of randomized finite-memory strategy classes, showing the classical behavioral/mixed equivalence fails under finite memory."},{"cited_title":"CoRR abs/2502.18296 (2025)","cited_arxiv_id":null,"evidence_quote":"Shows payoff sets in multi-objective MDPs are the convex hull of pure payoffs, bounding the randomness needed for any target payoff."}],"review_version":1}