{"id":"986047a3-7261-4856-9a65-45c1b89e8469","arxiv_id":"1908.02488","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new Epistemic Strategy Logic internalizes uniformity and other strategy properties in the object language, and its perfect-information core BSL is shown equiexpressive with Strategy Logic.","lead":"The paper introduces a strategy logic for games with imperfect information where strategy restrictions like uniformity are expressed inside the logic rather than hardwired. It shows a branching-time variant of Strategy Logic is equivalent to the original, and adds knowledge operators to capture uniform, de re, and de dicto strategies.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4.3 encodings enforce uniformity only for the existential coalition, not for complement agents, so the ESL translations of ATL with imperfect information are not equivalent to the stated semantics.","rationale":"The reader's identified weak point—whether weak uniformity on outcomes extends to global uniformity for knowledge objectives—is a real gap in §4.3, but there is a more immediate obstruction: the presented encodings do not translate the standard semantics at all, because only the coalition is made uniform. Since the paper's stated goal is to subsume existing imperfect-information strategic logics without hardwiring uniformity, the encodings must explicitly force uniformity for every agent whose strategies are quantified or ranged over; Section 4.3 only does this for the existential prefix. The simple counterexample shows the difference is not merely technical. The verdict should therefore be REJECT for the current manuscript, though a revised version that universally quantifies over complement agents and conjoins their a_j-wUniform formulas could restore the subsumption claim.","tokens_in":12527,"tokens_out":28674,"duration_ms":339090,"concrete_test":"Formalise the ICGS described above: agents a (single action) and b (L,R); states s0, sL, sR, win, lose; transitions as in the attack; AP={p}; µ(win)={p}; let b's indistinguishability relation ∼b be the universal relation on finite histories. Then run two model-checking checks on the same model: (1) evaluate the §4.3 basic-semantics encoding ∃x_a (a,x_a)(a-wUniform ∧ A F p) under ESL semantics; (2) evaluate the standard ATL-IR satisfaction of ⟨⟨a⟩⟩Fp under uniform strategies for all agents. The concern is confirmed iff check (1) returns false and check (2) returns true.","verdict_should_be":"REJECT","load_bearing_attack":"The subsumption claim in the abstract and §4.3 is unsupported because the example encodings translate only the coalition's existential strategies into ESL and add a_i-wUniform only for those agents. For the 'basic semantics' of ⟨⟨A⟩⟩Fp, after binding A the formula continues with 'AFp'. In ESL, with the complement unbound, the universal path quantifier A ranges over all completions of the remaining agents, i.e. over arbitrary strategies, including non-uniform ones. But the standard ATL semantics cited ([15]) requires every agent's strategy to be uniform. Hence the ESL encoding is stricter than the semantic condition it claims to express: it can fail even when all uniform complement strategies succeed, because a non-uniform complement strategy can steer the play to failure. Concretely, take agents a (only action 0) and b (actions L,R), states s0, sL, sR, win, lose, where b cannot distinguish any histories (or at least s0, sL, sR). Let δ(s0,L)=sL, δ(s0,R)=sR, δ(sL,L)=win, δ(sL,R)=lose, δ(sR,R)=win, δ(sR,L)=lose, and µ(win)={p}. Every uniform b-strategy plays one action everywhere and wins, so standard ⟨⟨a⟩⟩Fp holds. But the paper's encoding gives ¬A F p because the arbitrary b-strategy 'L at s0, R at sL' loses. Repeating a-wUniform after knowledge operators cannot fix this; a faithful translation must universally quantify over complement variables and add a_j-wUniform for each complement agent.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an extension of Strategy Logic (SL) designed to handle imperfect information. It first introduces BSL, a branching-time version of SL with a path quantifier and an unbinding operator, and claims that BSL is equiexpressive with SL via linear translations. It then adds action propositions and distributed-knowledge operators to obtain ESL, and argues that ESL can express properties of strategies that are usually hardwired into the semantics, such as uniformity, de re and de dicto strategy quantifiers, and memorylessness. The paper therefore claims that ESL subsumes most existing epistemic strategic logics with imperfect information.","tokens_in":12788,"tokens_out":8266,"duration_ms":100102,"significance":"If the claims are correct, the paper offers a genuinely useful conceptual contribution: instead of fixing uniformity or other strategy constraints in the semantics, one can state them in the object language, which would unify several existing logics. The BSL-versus-SL equiexpressivity result, with translations in both directions, is also interesting and potentially reusable. The paper also gives concrete formulas for de re and de dicto readings of an ATL-style formula, which makes the proposal falsifiable. However, the manuscript as written has several load-bearing gaps: a type error in the definition of weak uniformity, an encoding of the basic ATL semantics that omits uniformity requirements for complement agents, and multiple central results stated without proof.","major_comments":[{"comment":"Definition 3 is ill-typed. It says that for an initial path ρ, a strategy σ is weakly uniform if, for all initial paths ρ′ ∈ Out(ρ, [a ↦ σ]) and ρ′′ ∈ Paths∗ with ρ′ ∼a ρ′′, σ(ρ′) = σ(ρ′′). But Out(ρ, [a ↦ σ]) is defined as the set of infinite paths extending ρ, so its elements are not initial paths and are not in the domain of a strategy σ. The relation ∼a is also defined only on finite sequences of valuations. This type error affects Propositions 3 and 4, which are precisely the results establishing that a-wUniform and a-wUniform-aux express weak uniformity. The intended meaning is presumably that ρ′ ranges over finite prefixes of outcomes, e.g. ρ′ ∈ Pref(Out(ρ, [a ↦ σ])), but this must be stated and the subsequent propositions re-verified with the corrected definition.","section":"§4.2, Definition 3"},{"comment":"The proposed translation of the basic ATL semantics is not equivalent to the standard semantics from [15]. The displayed formula only quantifies existentially over strategies for agents in A, binds them, and adds ai-wUniform for those agents. The complement Ag \\ A remains unbound, so the path quantifier A in AFp ranges over all completions of the complement agents' strategies, including non-uniform ones. In the standard semantics, all agents' strategies, including those of the complement, are required to be uniform. Concretely, consider agents a and b where a has only action 0, b cannot distinguish any histories, and the transition structure is: from s0, b chooses L to sL or R to sR; from sL, b chooses L to win(p) or R to lose; from sR, b chooses R to win(p) or L to lose. Every uniform b-strategy (always L or always R) leads to a state satisfying p, so standard ⟨⟨{a}⟩⟩Fp holds. But the paper's translation evaluates AFp under an assignment that leaves b unbound, and the non-uniform b-strategy 'L at s0, R at sL' produces a losing path, so the translation returns false. A faithful encoding would need to universally quantify over complement strategies and add the uniformity condition for each complement agent as well. This flaw directly undermines the paper's claim to subsume prior ATL-based logics with imperfect information.","section":"§4.3, translation of basic ⟨⟨A⟩⟩Fp"},{"comment":"Lemma 1 in Section 3.3 and Propositions 3 and 4 in Section 4.3 are stated without proof, but they are load-bearing. Lemma 1 is needed for Proposition 2 and hence for the reverse direction of Theorem 1, the main equiexpressivity result. Propositions 3 and 4 are what connect the syntactic formula a-wUniform with the semantic notion of weak uniformity, and they underwrite all the translations in Section 4.3. The note that some proofs are omitted by lack of space is not sufficient for these central claims; the full proofs should be supplied or the claims should be clearly marked as conjectural.","section":"§3.3 and §4.3, Lemma 1 and Propositions 3 and 4"},{"comment":"The paper claims that ESL 'subsumes most, if not all, the variants of epistemic strategic logics with imperfect information that we know about,' but the evidence provided is only the translation of a single ATL-style formula, not a general embedding of any of those logics. Moreover, the paragraph after the de re translation acknowledges that weak uniformity may not be sufficient for objectives involving knowledge, and informally suggests repeating the uniformity formula after knowledge operators, but no formal statement or proof is given. Either a rigorous embedding theorem should be supplied, or the scope of the subsumption claim should be substantially narrowed.","section":"Abstract and Conclusion"}],"minor_comments":[{"comment":"Theorem 1 says the translations are 'linear in both directions,' but the translation in Definition 2 has complexity O(2^{|Ag|}|φ|). This is linear in the formula size only when the agent set is fixed; the statement should be qualified accordingly to avoid confusion.","section":"§3.3, Theorem 1"},{"comment":"The notation Dc = AcAg is ambiguous; it should be written as Ac^{Ag}, the set of functions from Ag to Ac.","section":"§2.1"},{"comment":"There are several typographical errors, such as 'c an' in the abstract and 'F or' in Section 3.3; a careful proofreading pass is needed.","section":"Abstract and Introduction"},{"comment":"The relation ∼A is defined on sequences of extended valuations, but the last paragraph of Definition 3 and the semantics of D_A would be clearer if the paper explicitly stated whether the related initial paths must have the same length or may have different lengths; this affects the reading of the knowledge operator.","section":"§4.2, semantics of D_A"}],"recommendation":"major_revision","confidential_remarks":"The concrete counterexample in the second major comment is decisive for the claimed subsumption result: the Section 4.3 encodings do not express the standard ATL-with-imperfect-information semantics as written. However, the underlying idea of internalizing uniformity in the logic is promising and the flaw appears repairable by adding universal quantification and uniformity conditions for complement agents. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know up front. First, the perfect-information part is solid: BSL adds a path quantifier and an unbinding operator to SL, and Theorem 1 gives linear translations both ways, so BSL is a notational variant with cleaner semantics and no complexity cost. The idea of internalizing uniformity in the logic rather than hardwiring it into the semantics is genuinely attractive. Second, the main subsumption claim for ESL in Section 4.3 does not survive close reading: the encodings of ATL with imperfect information bind and uniformize only the existential coalition. Complement agents remain unbound, and the path quantifier ranges over all their completions, including non-uniform strategies. Standard basic semantics from [15] requires every agent's strategy to be uniform. The stress-test example is real: with agent b having two actions and any constant action succeeding, a non-uniform b that loses makes the ESL translation false while the standard formula is true. The fix is straightforward—universally quantify over complement variables and add a_j-wUniform for each complement agent—but as written the abstract's claim to subsume most strategic logics with imperfect information is unsupported.\n\nWhat the paper does well: the BSL/SL equiexpressive proof is credible; Propositions 1 and 2 and Theorem 1 are sketched but plausible; the discussion of de re, de dicto, and weak uniformity is thoughtful. The remark that weak uniformity may need to be repeated after knowledge operators for harder objectives is honest, though only argued informally.\n\nSoft spots in proportion. Lemma 1 and Propositions 3 and 4 are stated without proof; saying proofs are omitted for lack of space is not enough for results that carry the paper. Definition 3 is ill-typed: Out returns infinite paths, while uniformity must be checked on finite prefixes. That is an easy fix, not a fatal flaw. The complement-uniformity gap, by contrast, is load-bearing. It directly contradicts the semantic condition the encoding claims to express. BSL+ strict expressiveness being a conjecture is fine if labeled as such.\n\nWho this is for: people in multi-agent verification and epistemic strategic logic will find the BSL material useful and the ESL framework a good starting point. It deserves a serious referee, but the ESL part needs real revision before it can be trusted.\n\nRecommendation: send to peer review on a conditional basis. The authors need to supply the missing proofs, fix Definition 3, and either fix the complement-uniformity encoding or narrow the subsumption claim. I would cite Theorem 1 but not the subsumption as it stands.","headline":"Solid perfect-information core (BSL equiexpressive with SL), but the ESL encodings that are supposed to subsume uniform-strategy semantics never constrain complement agents' strategies, so the central subsumption claim fails as stated.","tokens_in":13370,"tokens_out":5283,"would_cite":true,"duration_ms":61168,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B45","03B70","68Q60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper builds Branching-time Strategy Logic (BSL), proves BSL and SL equiexpressive via linear translations, and obtains Epistemic Strategy Logic (ESL), where uniform, de re, de dicto, and memoryless strategies are expressed in the…","keywords":["Epistemic Strategy Logic","Strategy Logic","imperfect information","uniform strategies","weak uniformity","branching-time logic","distributed knowledge","concurrent game structures"],"falsifier":"Search a small two-agent ICGS for an ESL sentence of the form $\\langle x\\rangle (a,x)(a\\text{-wUniform} \\wedge AG\\,K_a(a\\text{-wUniform} \\wedge AFp))$ and an assignment on which it holds even though the chosen strategy is not globally uniform, because some indistinguishable history outside its own outcome receives a different action, while no globally uniform strategy satisfies the sentence. One such example settles the Section 4.3 sufficiency step.","tokens_in":12236,"feed_emoji":"♟️","tokens_out":9907,"duration_ms":96509,"temperature":0.7,"pith_summary":"Strategy Logic (SL) treats strategies as first-class objects but cannot compare different outcomes of the same partial strategy assignment, and it has no way to talk about players' information. This paper introduces Branching-time Strategy Logic (BSL), which adds a path quantifier $E$ ranging over the outcomes of a partially assigned strategy set together with an unbinding operator that removes an agent from an assignment, and proves that BSL and SL are equiexpressive via linear translations in both directions. It then extends BSL with distributed knowledge operators $D_A$ over equivalence relations on partial plays, obtaining Epistemic Strategy Logic (ESL), and shows that properties normally fixed in the semantics, namely uniformity, de re and de dicto readings, and memorylessness, can be written as formulas of the logic. If the paper is right, one logic can cover most existing strategic logics with imperfect information, epistemic or not, without changing the semantics for each variant.","feed_headline":"SL and its branching-time twin BSL are equiexpressive","feed_subtitle":"ESL expresses uniform, de re, de dicto, and memoryless strategies in the logic, not in the semantics.","key_machinery":"The paper's mechanism has two layers. In BSL, the load-bearing additions are the path quantifier $E$, which ranges over the outcome set $\\mathrm{Out}(s,\\chi)$ of a partial assignment and so lets a formula inspect several plays generated by the same strategy, and the unbinding operator $(a,?)$, which deletes agent $a$ from the assignment so that all outcomes of that agent's strategy can be compared; the mutual translation $\\mathrm{tr}$/$\\mathrm{tr}'_A$ shows these additions are syntactic sugar in the perfect-information setting. In ESL, the extra machinery is the set of action propositions $p^a_c$ (one for each agent-action pair, attached to states in the unfolded game), the distributed knowledge operator $D_A$ whose semantics quantify over initial paths equivalent under the intersection of the agents' indistinguishability relations, and the weak-uniformity formula $a\\text{-wUniform}$, which at every reachable point of every outcome asserts that agent $a$ knows a single action is being played along all related outcomes. That formula, combined with unbinding and with knowledge operators placed before or after strategy quantifiers, carries the encodings of uniform, de re, de dicto, and memoryless strategies.","core_discovery":"The central claim is that the strategic side-conditions of imperfect-information games can be internalized in the logic. Theorem 1 states that SL and BSL are equiexpressive: the translation $\\mathrm{tr}$ replaces SL's temporal operators by $E$-quantified BSL operators, and the reverse translation $\\mathrm{tr}'_A$ simulates every $E$ by existentially quantifying fresh strategies and binding every currently unbound agent, with the parameter $A$ remembering which agents are unbound. On top of BSL, ESL evaluates formulas on initial paths, uses action propositions $p^a_c$ to make chosen actions observable, and interprets $D_A$ via the relation $\\sim_A=\\bigcap_{a\\in A}\\sim_a$. The paper proves that a strategy $\\sigma$ is weakly uniform for agent $a$ in $\\rho$ exactly when the formula $a\\text{-wUniform}$, which unbinds all other agents and asserts $AG(\\bigvee_{c\\in Ac} K_a A X p^a_c)$, holds; de re, de dicto, and memoryless variants are then obtained by placing strategy quantifiers and $D_A$ in different orders around this formula. The upshot is that uniform, de re, de dicto, and memoryless requirements no longer need to be hardwired into the semantics of the strategic quantifier.","pith_inferences":["A formal proof of the Section 4.3 sufficiency claim would let one define a syntactic fragment of ESL in which one uniformity conjunct per knowledge operator guarantees full uniformity; without it, the subsumption claim rests on an informal argument.","The BSL/SL equivalence suggests that path quantifiers and unbinding are safe additions in perfect information, so the real payoff of the design is as scaffolding for epistemic extensions; a similar operator pair might lift other first-class-object logics to imperfect information.","The action-proposition technique could likely be turned into a direct translation from a wide range of epistemic ATL variants into ESL, making the 'subsumes most logics' statement checkable formula by formula."],"forward_implications":["BSL inherits SL's complexity profile: its model-checking problem is nonelementary decidable and its satisfiability problem is $\\Sigma^1_1$-hard, so the new operators are free in expressivity and worst-case cost.","A single ESL formula family replaces the semantic variants of ATL-style logics: the uniform, de dicto, and de re readings of 'coalition $A$ can force $Fp$' differ only in where the quantifiers and knowledge operators sit.","The paper's encoding of memorylessness via an artificial agent related by 'same last state' gives a template for expressing other strategy restrictions in the language instead of in the model.","The authors state that model checking ESL is certainly undecidable with perfect-recall relations and several agents, so the generality of ESL comes with a worst-case price in the imperfect-information setting."],"supporting_citations":[{"why":"Introduces Strategy Logic, whose syntax, semantics, and sentence notion BSL extends and translates to.","marker":"[9]"},{"why":"Supplies the model-checking and satisfiability results that Corollaries 1 and 2 transfer to BSL.","marker":"[18]"},{"why":"Defines the de re and de dicto strategic semantics that Section 4.3 renders inside ESL.","marker":"[14]"},{"why":"States the standard uniform-strategy condition that the paper's weak uniformity is compared with.","marker":"[4]"},{"why":"Introduces the unbinding operator in a strategy-logic setting that BSL adapts.","marker":"[16]"},{"why":"Introduces ATL, the family of logics whose imperfect-information variants ESL aims to subsume.","marker":"[1]"}],"fun_headline_variants":["ESL internalizes uniform strategies, SL and BSL equiexpressive","Imperfect-info strategies now expressible in Strategy Logic itself","Branching-time BSL matches SL, uniformity in-logic","Uniform, de re, de dicto strategies now in ESL's grasp"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The encoding assumes that weak uniformity, which checks only the outcomes of the strategy being evaluated, can be extended to genuine global uniformity for simple objectives, and that repeating the weak-uniformity formula after each knowledge operator handles harder objectives; the paper argues this informally in Section 4.3 and gives no proof.","fun_headline_variants_meta":{"raw":{"variants":["ESL internalizes uniform strategies, SL and BSL equiexpressive","Imperfect-info strategies now expressible in Strategy Logic itself","Branching-time BSL matches SL, uniformity in-logic","Uniform, de re, de dicto strategies now in ESL's grasp"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000422,"raw_usage":{"total_tokens":2186,"prompt_tokens":982,"completion_tokens":1204,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":1129}},"tokens_in":598,"tokens_out":1204,"duration_ms":11101,"temperature":1.0,"reasoning_tokens":1129,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:43:11.645877+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search a small two-agent ICGS for an ESL sentence of the form $\\langle x\\rangle (a,x)(a\\text{-wUniform} \\wedge AG\\,K_a(a\\text{-wUniform} \\wedge AFp))$ and an assignment on which it holds even though the chosen strategy is not globally uniform, because some indistinguishable history outside its own outcome receives a different action, while no globally uniform strategy satisfies the sentence. One such example settles the Section 4.3 sufficiency step.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the de re and de dicto strategic semantics that Section 4.3 renders inside ESL."},{"cited_title":"In: Proceedings Fourth International Symposium on Games, Automata, Logics and Formal V erification, GandALF 2013, Borca di Cadore, Dolomites, Italy, 29-31th August 2013","cited_arxiv_id":null,"evidence_quote":"Introduces the unbinding operator in a strategy-logic setting that BSL adapts."}],"review_version":1}