{"id":"309fb1d6-c90d-45f6-a4d8-f98edf98ffa4","arxiv_id":"2501.18022","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A polynomial-time algorithm synthesizes admissible strategies for a leader who dynamically forms coalitions with at most one partner in deterministic multiplayer games with temporal preferences.","lead":"This paper introduces an algorithm that decides, turn by turn, which players should join forces and what each member should do, so that a leader robot can satisfy its preferences over long-term goals. It proves the algorithm runs in polynomial time in a restricted setting where the leader may partner with at most one other player at a time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof implicitly restricts P1's alternative strategies to rationalizable coalition proposals, but neither P1's strategy space nor the transition function defines non-rationalizable or rejected proposals, leaving the admissibility guarantee undefined on the full strategy space.","rationale":"The reader's verdict is CONDITIONAL and identifies the same soft spot: the acceptance rule for coalition proposals is not formalized and Theorem 2's proof restricts attention to rationalizable joint actions. I agree, and the concern is central rather than cosmetic because the definition of admissibility in Section 3 quantifies over all P1 strategies, while Algorithm 2 only searches over sequences of rationalizable joint actions. The proof of Theorem 2 bridges this gap with an unstated assumption: any other strategy can be assumed to induce only rationalizable joint actions. That assumption is exactly what the game model fails to define. A minimal counterexample shows the issue is not merely a missing sentence: if non-rationalizable proposals are allowed and obeyed, Algorithm 2's discarding rule can remove the unique rank-0 strategy, so the synthesized strategy is not admissible. If they are not allowed, the strategy space and the transition function must be amended before the theorem can be evaluated. Therefore the central claim is currently under-specified but plausibly repairable; the correct disposition is to keep the paper conditional on a formal model of proposal acceptance/rejection and a revised proof of Theorem 2 for the full strategy space. This is not an objection to the algorithmic idea or to the blocks-world experiment; it is a precise gap in the correctness argument.","tokens_in":13982,"tokens_out":8438,"duration_ms":92762,"concrete_test":"Construct the minimal two-player game with initial state s0. From s0, P1 has two actions: playing alone leads to s1 with Val1(s1)=1; proposing coalition {1,2} with a joint action (a1,a2) leads to s2 with Val1(s2)=0, but Val2(s2) > Val2(s0), so the coalition action is not rationalizable for P2 under Definition 10. Algorithm 2 discards the coalition action at line 9 and returns the rank-1 strategy. Now check the two possible semantics: (i) if P1's strategy space is unrestricted and P2 obeys every proposal, the discarded action gives a rank-0 outcome, so the returned strategy is not admissible, falsifying Theorem 2; (ii) if P2 rejects non-admissible proposals, specify the resulting state and transition rule, restrict Π_1 accordingly, and re-run the theorem's proof on that restricted class. Either way the admissibility claim must be re-derived under a fully specified model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3 defines a P1 strategy as a map from states to a coalition and a joint coalition action, with no restriction that the proposal be rationalizable; it also states that coalition members 'must accept the proposal if the proposed joint action is admissible for them.' The transition function in Definition 1 and this acceptance rule do not specify what happens when P1 proposes a non-admissible action. Theorem 2's proof then says: 'By Lemma 2, for any l' < l, no sequence of rationalizable joint actions can enforce a transition from v0 to a set of states with rank at most l' for P1. Therefore, any other strategy π' must satisfy MaxRank1(π) ≤ MaxRank1(π').' This 'therefore' is valid only if every alternative strategy in Π_1 gives rise to rationalizable joint actions. Lemma 2 only characterizes when Algorithm 2 discards a joint action; it says nothing about strategies that propose non-rationalizable actions. Under the natural reading where such proposals are legal moves, the discarded proposal may yield P1 a strictly lower rank, so π can be strictly dominated, contradicting Theorem 2. Under the reading where such proposals are illegal or lead to rejection, the semantics and the strategy space must be formalized and the theorem re-proved. Since the central claim quantifies over all strategies, this is a load-bearing gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic multiplayer games on graphs where a leader (P1) dynamically proposes a coalition and joint actions each round, while non-members follow admissible strategies. The authors extend the concept of admissibility to preferences over temporal goals, define a rank-based value function, and present Algorithm 2 to synthesize an admissible strategy for P1, claiming polynomial-time complexity and existence of admissible profiles in the considered subclass. The contributions are illustrated in a BlocksWorld domain, with evidence that dynamic coalitions outperform fixed ones and that preference alignment does not straightforwardly predict coalition formation.","tokens_in":14225,"tokens_out":7169,"duration_ms":61883,"significance":"If the technical issues were resolved, the paper would make a useful contribution by integrating coalition formation and strategy synthesis under incomplete preferences, and by connecting maximal sure winning with admissibility in a multiplayer setting. The proposed algorithm is a concrete, potentially practical construction, and the experimental illustration raises an interesting qualitative point about cooperation under aligned preferences. However, the central admissibility guarantee currently rests on an under-specified game model and a flawed proof of Proposition 1, so the significance cannot be fully assessed until these are repaired.","major_comments":[{"comment":"The game model does not define what happens when P1 proposes a joint action that is not admissible for a coalition member, or when a member rejects a proposal. The text says coalition members \"must accept the proposal if the proposed joint action is admissible for them,\" but the transition function T and the P1 strategy space (a map from states to a coalition and a joint action) allow non-admissible proposals to be legal moves. Theorem 2's proof uses Lemma 2 to conclude that any other strategy π' has MaxRank1(π) ≤ MaxRank1(π'), but Lemma 2 only characterizes rationalizable joint actions; it says nothing about strategies that propose non-rationalizable or rejected actions. Under the natural reading that such proposals are legal, the discarded proposal may give P1 a strictly lower rank, contradicting admissibility. Under the reading that such proposals are illegal or trigger rejection, the semantics and the strategy space must be formalized. This gap is load-bearing because the admissibility claim quantifies over all P1 strategies.","section":"Section 3, Definition 1 and Theorem 2"},{"comment":"The variable k is used both as the loop counter in the repeat-until loop and as the player index in \"for k ∈ [N]\\{1}\" on line 22. After the inner loop executes, k is overwritten to the last player index (or N-1), so the loop condition \"until V_{k+1} = V_k\" on line 27 no longer refers to the intended level-set index. This makes the loop termination and the stated time complexity O(r1_max |V|(...)) ill-defined. The player index should be renamed (e.g., j) and the pseudocode corrected.","section":"Algorithm 2, lines 4 and 22-26"},{"comment":"The proof of Proposition 1 misstates Definition 6. It says \"for every minimal path ρ′ in Min{Paths(π′_i)}, there exists a minimal path ρ ∈ Min{Paths(π_i)} such that ρ′ ≻_i ρ,\" but Definition 6 states the opposite direction: for every ρ ∈ Min(π_i), there exists ρ′ ∈ Min(π′_i) such that L(ρ) ≻ L(ρ′). With the correct direction, the inequality concluded as MaxRank_i(π_i) > MaxRank_i(π′_i) does not follow; from L(ρ) ≻ L(ρ′) one gets Rank(ρ) < Rank(ρ′), which implies MaxRank_i(π′_i) > MaxRank_i(π_i), not a contradiction. Since Proposition 1 is a key ingredient of Theorem 2, this proof error must be repaired.","section":"Section 4.1, proof of Proposition 1"}],"minor_comments":[{"comment":"The notation for rank is used inconsistently: Definition 9 assigns a rank to a state u, while Lemma 1 uses Rank_i(w) for a word and the proof refers to Rank_i(ρ). Please define the rank of a path/word explicitly and use consistent notation throughout.","section":"Section 2.3 and Lemma 1"},{"comment":"The expressions on lines 15-16 are under-specified: \"max{CoalVi(∆(v,aC,aj)}\" is missing a closing brace and does not indicate the set over which the maximum is taken (presumably over a_{-C}). Clarify the quantifiers so the definitions of c_j and a_j are unambiguous.","section":"Algorithm 2, lines 14-18"},{"comment":"The annotation \"CoalV : [0,1]\" in the figures has only two entries while the game has three players; the text should explain this notation or correct the displayed vectors.","section":"Figures 2 and 3"},{"comment":"The discussion of Figure 2 refers to \"the value of S2 for P3 is 3\" and \"rank 1 for P3\" with the notation CoalV(S3), but the relationship between Val, CoalV, and rank is not defined in the main text; please state how CoalV is derived from the algorithm's output and how it is read in the examples.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper leans substantially on prior work (Kulkarni et al. 2025, Rahmani et al. 2024) for the maximal sure winning and preference-planning machinery. The supplementary material containing the omitted proofs is not included in the submitted manuscript; given that the proof of Proposition 1 in the main text is incorrect as written, I strongly recommend that the authors provide the complete proofs in the revision. The variable-reuse bug in Algorithm 2 and the undefined rejection semantics are likely fixable, but they must be addressed before the central claim can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, quick take on arXiv:2501.18022. The core idea is good: in a subclass of deterministic multiplayer games where P1 proposes a coalition and joint actions each round, and others follow admissible strategies, they give a polynomial-time algorithm that synthesizes an admissible strategy for P1, using maximal sure winning and a rank-based value function. The connection between admissibility and maximal sure winning is a reasonable extension, and the blocks-world example illustrates the benefit of dynamic over fixed coalitions. If the correctness claim holds, this is useful for multi-agent planning.\n\nWhat the paper does well: it makes the model explicit enough to extend, gives a value-function characterization, proves existence of admissible profiles in the subclass, and states complexity. It also leans on prior work (Kulkarni et al. 2025, Rahmani et al. 2024) rather than hiding it, and the central algorithm is a genuine new extension, not a rehash.\n\nNow the soft spots, in proportion. The stress-test concern is real and load-bearing. Theorem 2's proof says that by Lemma 2, no alternative strategy can enforce a state of rank at most l' because Lemma 2 only rules out sequences of rationalizable joint actions. But P1's strategy space as defined is unrestricted: any map from states to coalitions and joint actions. Nothing in Definition 1 or the acceptance rule specifies what happens when P1 proposes a non-admissible action, or when a coalition member rejects. So the 'therefore' in Theorem 2 does not go through for the full strategy space. This is not a cosmetic gap; the admissibility guarantee is undefined on the domain where it is claimed. The fix is to formalize the game semantics: either restrict P1 to rationalizable proposals and prove that restriction is without loss, or define rejection states and re-prove the theorem. That is doable, but as written the central theorem is not proven.\n\nAlso minor but real: Algorithm 2 uses k as both the iteration counter and the player index in lines 22-25; this corrupts the loop termination and the CoalV update. A rename (e.g., i for players) is needed.\n\nThere are smaller presentation issues: Assumption 1 restricts coalitions to size at most 2, which is fine but limits generality; the paper should say more about why that subclass is interesting. No code or data for the experiment, just illustrative figures—fine for a theory paper, but not reproducible.\n\nBottom line: the idea deserves serious refereeing and the gaps look fixable, but the version I read is not correct as a formal paper. I would send it to review with a 'major revision' expectation, and I'd want the semantics of proposal acceptance and the proof of Theorem 2 redone.","headline":"The dynamic-coalition synthesis idea is plausible and worth refereeing, but Theorem 2's admissibility claim does not actually cover the full strategy space as written, and Algorithm 2 has a variable-name bug that needs cleanup.","tokens_in":14766,"tokens_out":2129,"would_cite":false,"duration_ms":255853,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that, in deterministic multiplayer games on graphs with partial-order preferences over temporal goals, a leader can synthesize an admissible dynamic-coalition strategy in polynomial time, and that admissible strategies…","keywords":["dynamic coalitions","games on graphs","partial-order preferences","temporal goals","admissibility","maximal sure winning","strategy synthesis","polynomial-time algorithm"],"falsifier":"Run Algorithm 2 on a small game in the subclass, say two players, three states, and two scLTL goals with an explicit preference order, obtain the synthesized strategy for P1, then exhaustively enumerate all finite-memory P1 strategies against rationalizable responses of the other player and compare the least-preferred outcomes under P1's preference order; if any alternative strategy yields a strictly preferred minimal outcome, Theorem 2 is false.","tokens_in":13775,"feed_emoji":"🤝","tokens_out":13706,"duration_ms":118416,"temperature":0.7,"pith_summary":"Sequential decision-making in multi-agent systems often requires players to form temporary coalitions to reach temporal goals that no single player can force on its own. This paper studies such settings as deterministic multiplayer games on graphs, where one leader, P1, proposes a coalition and a joint action in each round, players outside the coalition are assumed to follow admissible strategies, and the subclass restricts the leader to forming a coalition with at most one other player while the rest act independently. The paper's central claim is that admissible strategies—strategies no alternative can strictly improve in the worst case over the player's least-preferred outcomes—always exist in this subclass, and that an algorithm can synthesize them in polynomial time in the size of the product game. The mechanism is a rank-based value function that lets the leader progress toward states with lower rank by cooperating with at most one partner at a time. The paper also demonstrates in a blocks-world experiment that dynamic coalitions outperform fixed coalitions and that aligned preferences do not reliably encourage cooperation.","feed_headline":"Leader picks dynamic coalitions in polynomial time","feed_subtitle":"New algorithm finds coalition strategies that no alternative can beat in temporal-goal games.","key_machinery":"The load-bearing object is the rank function of Definition 9, an order-preserving map from the preference preorder to the natural numbers, together with the value function $Val(v) = [MaxRank_i(\\pi_i)]_{i\\in[N]}$ that records the best rank each player can guarantee from state $v$ without cooperation. Algorithm 2 uses these to construct level sets $V_k$ of states of rank at most $k$, then repeatedly expands a frontier $U_k$ of states from which P1 can force a visit to $V_k$ either alone or with one coalition partner. The $CandV$ and $CoalV$ maps record, respectively, the value each player would obtain under each joint coalitional action and the worst-case value over all rational coalition choices, and these maps provide the admissible actions for non-leader players. The bridge to admissibility is the theorem that a maximal sure winning strategy—one that minimizes the worst achievable rank—is admissible.","core_discovery":"The core claim is that admissibility in games on graphs with partial-order preferences is characterized by maximal sure winning: every maximal sure winning strategy is admissible (Proposition 1), and the rank of such a strategy is the smallest rank outcome the player can guarantee against adversarial choices of the other players. Algorithm 2 turns this characterization into a synthesis procedure for the leader: it builds level sets $V_k$ of states from which P1 can force a visit to states of rank at most $k$, either alone or through a coalition $\\{1,i\\}$, and it discards exactly the coalitional actions that are not rationalizable (Lemma 2). The strategy produced is admissible for P1 (Theorem 2), admissible strategies for the remaining players can be extracted from the intermediate $CandV$ and $CoalV$ maps, such a profile exists in every game of the subclass, and the procedure runs in $\\mathcal{O}(r^1_{\\max}|V|(|A_1|+\\sum_{j=2}^{N}|A_j||A_1|))$ time. The blocks-world experiment supports the corollary that dynamic coalitions can achieve outcomes no fixed coalition can guarantee. The main text notes that the proofs of Lemma 1 and subsequent results appear in the supplementary material.","pith_inferences":["The paper's own examples leave open whether the coalitional actions it keeps correspond to stable coalitions in the classical core sense; one testable extension is to check whether the rationalizability filter yields coalition structures that are stable under repeated play.","Since maximal sure winning was originally defined for two-player stochastic games with preferences, the same rank-and-value construction is a plausible route to generalize dynamic-coalition synthesis to stochastic games, though the paper only mentions stochastic generalization as future work.","The counter-intuitive preference-alignment result is based on two illustrative paths in one blocks-world instance; a systematic random-game study counting coalition switches against pairwise preference distance could determine whether the pattern is structural or an artifact of the example.","The paper notes but does not prioritize social welfare, yet its second blocks-world path satisfies all players' specifications; an extension could deliberately optimize the vector of guaranteed ranks and compare welfare outcomes."],"forward_implications":["If the central claim is correct, coalition formation and control strategy synthesis can be solved together rather than separately, at least in the subclass where P1 cooperates with at most one other player per round.","The polynomial-time guarantee means the algorithm can be applied to product games of practical size without enumerating all possible coalition structures.","Dynamic coalitions can be strictly better than fixed ones: in the blocks-world example, P1 must switch partners between rounds to achieve its most preferred temporal goal, something no single fixed coalition can accomplish.","Preference alignment is not a reliable predictor of cooperation: the experiments exhibit a case where P1 cooperates with a player whose preferences conflict with its own, while aligned preferences do not always produce coalitions.","The $CandV$ and $CoalV$ structures yield admissible strategies for all players, not just the leader, so the output is an admissible strategy profile rather than a single strategy."],"supporting_citations":[{"why":"Supplies the concept of maximal sure winning strategies, the rank function, and the value-assignment algorithm that this paper adapts to multiplayer deterministic games.","marker":"[Kulkarni et al., 2025]"},{"why":"Establishes the study of games on graphs with incomplete preferences that the paper extends to dynamic coalitions.","marker":"[Kulkarni et al., 2024]"},{"why":"Provides the preference model on words over temporal formulas, including undominated specifications and order lifting, used to compare outcomes.","marker":"[Rahmani et al., 2023]"},{"why":"Supplies the deterministic concurrent game-on-graph model that Definition 1 is based on.","marker":"[Bouyer et al., 2011]"},{"why":"Supplies the admissibility solution concept and the assume-admissible synthesis view that the paper generalizes to temporal preferences.","marker":"[Brenguier et al., 2015]"},{"why":"Supplies the syntactically co-safe LTL fragment and the DFA translation used to construct preference automata in the product game.","marker":"[Kupferman and Vardi, 2001]"},{"why":"Supplies the Stackelberg-Nash leader-follower model that motivates the leader's role in proposing coalitions and joint actions.","marker":"[Li et al., 2020]"}],"fun_headline_variants":["Dynamic coalitions beat static ones in temporal-goal games","Poly-time algorithm for dynamic coalition strategies","Maximal sure winning unlocks admissibility in graph games","When preferences conflict, dynamic coalitions still guarantee wins"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that players not in the coalition reliably follow their admissible strategies and that a coalition member accepts a proposal exactly when the proposed joint action is admissible for them, even though the game's transition function does not specify what happens if a player rejects or deviates; without such a behavioral rule, the admissibility guarantee is not well defined.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic coalitions beat static ones in temporal-goal games","Poly-time algorithm for dynamic coalition strategies","Maximal sure winning unlocks admissibility in graph games","When preferences conflict, dynamic coalitions still guarantee wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000219,"raw_usage":{"total_tokens":1470,"prompt_tokens":996,"completion_tokens":474,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":413}},"tokens_in":612,"tokens_out":474,"duration_ms":225515,"temperature":1.0,"reasoning_tokens":413,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T00:59:10.722288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a small game in the subclass, say two players, three states, and two scLTL goals with an explicit preference order, obtain the synthesized strategy for P1, then exhaustively enumerate all finite-memory P1 strategies against rationalizable responses of the other player and compare the least-preferred outcomes under P1's preference order; if any alternative strategy yields a strictly preferred minimal outcome, Theorem 2 is false.","supporting_citations":[{"cited_title":"Kulkarni, Jie Fu, and Ufuk Topcu","cited_arxiv_id":null,"evidence_quote":"Supplies the concept of maximal sure winning strategies, the rank function, and the value-assignment algorithm that this paper adapts to multiplayer deterministic games."},{"cited_title":"Kulkarni, Jie Fu, and Ufuk Topcu","cited_arxiv_id":null,"evidence_quote":"Establishes the study of games on graphs with incomplete preferences that the paper extends to dynamic coalitions."},{"cited_title":"Probabilistic planning with partially or- dered preferences over temporal goals","cited_arxiv_id":null,"evidence_quote":"Provides the preference model on words over temporal formulas, including undominated specifications and order lifting, used to compare outcomes."},{"cited_title":"Nash equilibria in concurrent games with b¨ uchi objectives","cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic concurrent game-on-graph model that Definition 1 is based on."},{"cited_title":"Assume-Admissible Synthesis","cited_arxiv_id":"1507.00623","evidence_quote":"Supplies the admissibility solution concept and the assume-admissible synthesis view that the paper generalizes to temporal preferences."},{"cited_title":"Model checking of safety proper- ties","cited_arxiv_id":null,"evidence_quote":"Supplies the syntactically co-safe LTL fragment and the DFA translation used to construct preference automata in the product game."}],"review_version":1}