{"id":"a8cdbaac-5bc6-4082-ac99-d587c891ceba","arxiv_id":"2510.24515","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A new game model for competitive prize collecting on graphs, with an ordinal-rank conditioning trick that improves multi-agent policy scaling and generalization in road-network simulations.","lead":"This paper introduces Stochastic Prize-Collecting Games, a competitive multi-agent routing game in which self-interested robots collect prizes on a graph, and proposes an 'ordinal rank' feature that helps shared policies scale to more agents. The authors report that rank-conditioned policies reach 87% to 95% of the optimal cooperative routing value in road-network experiments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is not established as stated: the proof ignores travel costs and remaining budget, so on a complete graph with arbitrary edge weights the 'i-th largest prize' action can be infeasible or dominated, invalidating the claimed unique PNE.","rationale":"The reader's weakest assumption identifies the same gap, and the detailed counterexample confirms it is load-bearing. Theorem 1 is the foundation for the uniqueness claim and the claimed equivalence with the TOP optimum, yet its proof never reasons from the actual value function (3) or from the budget transition. The counterexample is legal under the paper's definitions: a complete graph with arbitrary symmetric W, finite L, a single prize realization, and rank-based conflict resolution. It shows the 'i-th largest prize' response can be infeasible as part of a terminal-reaching tour and is dominated by a cheaper lower prize, so the central theoretical claim is unsupported as written. This also weakens the later Price-of-Anarchy interpretation, which presupposes that learned policies are near an equilibrium of the claimed kind. I am not dismissing the empirical OR results; those could survive with a repaired theorem. But the preprint's central claim is not established, so the reader's REJECT verdict should stand unchanged.","tokens_in":12648,"tokens_out":21922,"duration_ms":212736,"concrete_test":"Implement the paper's stage-game reward rule (2) on the 5-node complete graph: V={s,A,B,C,d}, n=2, L=2, W(s,A)=W(s,B)=W(s,C)=W(s,d)=1, W(A,d)=W(B,d)=10, W(C,d)=1, all remaining complete-graph weights finite, prizes p=(0,10,9,8,100), no prize repopulation. Enumerate all pure action pairs under rank-based conflict. The Theorem 1 profile (agent1->A, agent2->B) yields payoffs (10,9); agent2 can deviate to C for 8+100=108 and agent1 can deviate to d for 100. The enumeration will show the prescribed profile is not a PNE, directly falsifying Theorem 1 in the stated generality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV, Theorem 1 claims that on a complete graph, for any prize realization, the i-th agent's best response is to take the i-th largest remaining prize. The proof only compares deviations 'left' (taken by a senior) and 'right' (lower immediate prize), and uses W and l_i only in the terminal clause 'If the i-th prize is 0, or l_t is not sufficient to reach another prize, then move to d'. Since W is arbitrary and l_i is part of the state in the model, feasibility and the ability to still reach d are part of the payoff; the proof's monotonicity in the sorted prize vector does not follow. Concrete counterexample under the paper's single-realization, no-repopulation setting: V={s,A,B,C,d}, n=2, L=2, W(s,A)=W(s,B)=W(s,C)=W(s,d)=1, W(A,d)=W(B,d)=10, W(C,d)=1, prizes p_A=10, p_B=9, p_C=8, p_d=100. The Theorem 1 profile is agent1->A, agent2->B. Agent2's B-route cannot reach d and pays 9; deviating to C pays 8+p_d=108, so B is not a best response. Agent1 can also deviate to d for 100>10. Thus the claimed unique PNE fails as stated, and the gap propagates to Remark 1 and the abstract's equivalence with the TOP optimum.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Stochastic Prize-Collecting Games (SPCGs), a game-theoretic extension of the Team Orienteering Problem to self-interested agents with energy constraints, stochastic prizes, and rank-based conflict resolution. The central theoretical claim is that on complete graphs there is a unique pure Nash equilibrium in which the i-th ranked agent repeatedly takes the i-th largest remaining prize, and that this equilibrium coincides with the optimal routing solution of an equivalent cooperative TOP. The paper then introduces Ordinal Rank Search (ORS) to compute local ordinal ranks, and Fictitious Ordinal Response Learning (FORL) as an entropy-regulated sequential learning algorithm claimed to converge to a PNE when one exists. Empirical experiments on road-network graphs compare FORL, independent policy learning, and parameter sharing, and report 87%-95% optimality relative to a MILP solution of an equivalent TOP.","tokens_in":12985,"tokens_out":9457,"duration_ms":92752,"significance":"If the theoretical results were correct, the paper would offer a valuable and unusual result: a finite-horizon, simultaneous-move stochastic game on graphs with a unique pure equilibrium that matches a cooperative optimum under a simple rank-based priority rule. The ordinal-rank representation is also a plausible and interesting inductive bias for multi-agent RL on graphs, and the empirical study addresses an important practical setting. However, the paper's load-bearing theoretical claims are not sound as stated. Theorem 1 is falsified by a simple finite-budget example, and Proposition 3's convergence argument conflates determinism with equilibrium. Since these flaws directly support the abstract's uniqueness claim, the TOP-equivalence claim, and the interpretation of the empirical results as Price of Anarchy, the paper cannot be accepted in its current form.","major_comments":[{"comment":"The proof of Theorem 1 is not sound as stated. The argument compares only the immediate prize of the i-th largest remaining node with deviations 'left' and 'right', and treats the budget only in the terminal clause 'If the i-th prize is 0, or l_t is not sufficient to reach another prize, then move to d.' But the total payoff includes the remaining budget and the terminal reward, and on a complete graph with arbitrary travel costs W these determine whether a deviation is profitable. A concrete counterexample is V={s,A,B,C,d}, n=2, L=2, W(s,A)=W(s,B)=W(s,C)=W(s,d)=1, W(A,d)=W(B,d)=10, W(C,d)=1, and p_A=10, p_B=9, p_C=8, p_d=100. The claimed profile is agent1->A, agent2->B. Under the standard orienteering interpretation that the terminal reward is collected only if d is reached within the remaining budget, agent2 receives 9 from B but can receive 8+100=108 by deviating to C, so B is not a best response; agent1 similarly prefers d (100) to A (10). If instead d is reachable at any time regardless of budget, the theorem fails even with zero travel costs because the senior agent should always move to d immediately. Thus Theorem 1 needs either additional feasibility restrictions or a different terminal model; as written it does not support the claimed unique PNE, nor does Remark 1's assertion that the PNE team reward equals the equivalent TOP optimum.","section":"Section IV, Theorem 1 and Remark 1"},{"comment":"Proposition 3's convergence claim is circular and unsupported. The proof argues that if a PNE exists, then it is a pure strategy profile, hence has entropy zero, and the algorithm will not terminate until H_stop=0. This only establishes that a terminating policy may be deterministic; zero entropy is not a certificate of Nash equilibrium, and the algorithm's stopping rule is an entropy threshold, not a best-response check. Consequently the claim that FORL terminates at a PNE when one exists is not established. In the non-PNE case, the asserted chain H_{κ(t+1)} ≤ H(π^{θ_t}_j) ≤ H(π^{θ_t}_i) ≤ H_{κ(t)} for j<i is stated without proof and, even if true, bounds entropies rather than best-response distances. The abstract's statement that FORL is an 'entropy-regulated algorithm to obtain convergent policies' therefore overstates what is proved.","section":"Section V.B, Proposition 3"},{"comment":"The generalization from complete graphs to incomplete graphs via ordinal ranks is not formally established. Remark 2 says an agent only needs its rank, the player count, and the graph state to compute the PNE, but this rests entirely on Theorem 1, which applies at best to complete graphs. For incomplete graphs, Section V asserts that best responding to one's immediate opponents is sufficient, but no theorem or derivation is provided for this claim. Because the subsequent empirical success of OR-conditioning is interpreted through this unproved sufficiency, the paper should either prove a formal statement about localized stage games or clearly present the OR claim as a heuristic rather than as a consequence of the equilibrium analysis.","section":"Section IV, Remark 2 and Section V"},{"comment":"The reported 87%-95% figures are described as Price of Anarchy, but PoA is a worst-case ratio over equilibria, whereas the experiments evaluate one learned policy trajectory. The comparison to the MILP solution additionally presupposes both that the learned profile is at a PNE and that the PNE team reward equals the equivalent TOP optimum, both of which depend on the unsupported Theorem 1 and Proposition 3. These numbers should be presented as empirical optimality gaps of specific trained policies, not as formal PoA bounds.","section":"Section VI.B"}],"minor_comments":[{"comment":"The abstract contains a duplicated phrase: 'we also propose we propose Fictitious Ordinal Response Learning'.","section":"Abstract"},{"comment":"The text 'the robotsmustcompetein reward-scarce environments' is missing spacing; please correct the formatting.","section":"Section I"},{"comment":"In the prize re-drawing rule, the condition 'p_t = 0' should presumably be 'p_v^t = 0' or similar; the current notation is ambiguous.","section":"Section III"},{"comment":"The pseudocode appears to have an ordering issue for n=2: after j=1 satisfies the entropy condition, line 10 increments j to 2 and then line 11 immediately triggers the reset because j≥n, so the second agent is never updated in the fictitious-play stage. Please clarify the intended control flow.","section":"Algorithm 2"},{"comment":"The sentence 'compute their ordinal ranks... by sorting their global ranks in the ascending order' contains the typo 'λ . ∈Λ'; also the notation around ordinal rank computation could be made more explicit.","section":"Section V.A"},{"comment":"The MILP benchmark is attributed to [18], but [18] is a survey on the orienteering problem; a specific MILP formulation reference would be more appropriate.","section":"References"}],"recommendation":"reject","confidential_remarks":"The manuscript's central theoretical claims are not sound: Theorem 1 fails under finite budgets and travel costs, and Proposition 3 does not prove convergence to a PNE. These are load-bearing for the abstract, the TOP-equivalence claim, and the interpretation of the experiments as Price of Anarchy results. The empirical study and the ordinal-rank idea may have merit, but they cannot compensate for the theoretical errors as they stand. I recommend rejection; a future revision that corrects the theoretical statements and re-frames the empirical claims as heuristic comparisons could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new piece here is real: a simultaneous-move stochastic prize-collecting game with rank-based conflict resolution, plus the ordinal-rank (OR) representation and the FORL training scheme. The empirical story—OR-conditioned shared policies scaling better than global-rank ones, and beating global-state baselines—is plausible and worth a look. This is not just a rehash of the leader-follower paper [8]; the simultaneous-move setting genuinely changes the problem.\n\nWhat the paper does well: the experiments are suggestive, the OR idea is practical, and the two-agent counterexample in Theorem 2 (no PNE on a general graph) is a clean sanity check. The prose is mostly clear about what is being claimed, and the connection to TOP/MILP is useful.\n\nThe soft spots are in the theory, and they are load-bearing. Theorem 1 asserts a unique pure Nash equilibrium on complete graphs where the i-th agent always takes the i-th largest remaining prize. The proof only uses travel cost and remaining budget as a terminal condition; it never checks feasibility or opportunity cost of choosing a distant large prize versus a nearby smaller one plus terminal reward. The stress-test counterexample is valid and breaks the claim as stated. So the abstract's equivalence with the TOP optimum and Remark 1 do not follow. This is not a minor gap—it is the paper's central theoretical anchor. There is also a circular flavor in Proposition 3: identifying zero-entropy with PNE just restates that pure profiles have zero entropy; it does not prove best-response. The convergence claim therefore overreaches. No code or data are released, which makes the empirical claims harder to verify.\n\nWho this is for: readers working on competitive multi-robot routing, especially people interested in state aliasing via local rank features. They will get a useful model and an interesting training trick, but they should not cite the equilibrium theorem as proven. The ordinal-rank idea deserves a second paper with repaired theory and released artifacts.\n\nFor peer review: I would send it out, because the problem and the OR representation are worth referee time, but it needs substantial revision before acceptance. My verdict is skeptical on the current form, not on the idea.","headline":"New game formulation and a useful ordinal-rank feature, but Theorem 1's proof ignores travel costs and budget, so the central equilibrium claim is not yet established.","tokens_in":608,"tokens_out":732,"would_cite":false,"duration_ms":12496,"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":"This paper extends the Team Orienteering Problem to self-interested agents and proves that on complete graphs, rank-based conflict resolution yields a unique pure Nash equilibrium where each agent claims the prize matching its rank.","keywords":["Stochastic Prize-Collecting Games","Team Orienteering Problem","pure Nash equilibrium","ordinal rank","multi-agent reinforcement learning","fictitious play","graph routing","rank-based conflict resolution"],"falsifier":"Run a two-agent complete graph with start $s$, terminal $d$, budget $L=3$, edge costs $w(s,A)=1$, $w(A,d)=1$, $w(s,B)=2$, $w(B,d)=2$, $w(s,C)=0.5$, $w(C,d)=0.5$, and prizes $p_A=10$, $p_B=9$, $p_C=8$, with $p_d$ very large. If agent 1 takes $A$, agent 2's prescribed equilibrium action is $B$ (the second-largest prize), yielding 9 and no terminal reward because $3-2 < w(B,d)=2$; deviating to $C$ yields $8+p_d$, which is larger. This instance would refute Theorem 1 as stated.","tokens_in":12433,"feed_emoji":"🤖","tokens_out":12843,"duration_ms":107890,"temperature":0.7,"pith_summary":"The paper builds a bridge between cooperative routing and competitive routing. It introduces Stochastic Prize-Collecting Games (SPCGs), in which self-interested agents on a graph compete for stochastic prizes under travel budgets and a fixed rank-based conflict rule. Its central theoretical claim is that on complete graphs (and star graphs) this game has a unique pure Nash equilibrium: at each stage the $i$-th ranked agent should take the $i$-th largest remaining prize, and the resulting total reward matches the optimal cooperative Team Orienteering solution. On arbitrary graphs a pure equilibrium need not exist, so the paper proposes the ordinal rank, a local rank inside an agent's current neighborhood, as the right information for learning best responses. Experiments on road networks report that ordinal-rank-conditioned policies reach 87–95% of the optimal cooperative total reward and scale to far more agents than global-rank-conditioned policies.","feed_headline":"Rank order yields a unique equilibrium for competitive routing","feed_subtitle":"On complete graphs, the i-th agent should take the i-th largest prize; learned policies hit 87–95% of optimal.","key_machinery":"The argument is carried by two objects. The first is the rank-based conflict-resolution rule: when several agents visit the same node at the same time, the lowest-index (highest-ranked) agent takes the whole prize and everyone else receives zero. The second is the ordinal rank, $I_i = 1 + |\\{j \\in \\lambda(i) : j < i\\}|$, where $\\lambda(i)$ is the connected component containing $i$ in the separating graph, whose edges join agents with overlapping reachable sets. The ordinal rank collapses global position and opponent locations into a single local number; on complete graphs it coincides with global rank, and Theorem 1 reduces best response to a one-line rule, 'take the $i$-th largest remaining prize'. On incomplete graphs, it is the information that lets a myopic agent best-respond to its immediate opponents, and it is the conditioning variable that makes the shared learned policies generalize and scale.","core_discovery":"At its core, the paper claims that rank-based conflict resolution makes competitive prize-collecting routing strategically tractable. On a complete graph, for every prize realization, the $i$-th ranked agent's unique best response at every stage is to move to the $i$-th largest remaining prize; this profile is the unique pure Nash equilibrium, and its total team reward equals the optimal solution of the equivalent Team Orienteering Problem, so competition costs nothing in that setting. On arbitrary graphs the situation changes: the paper exhibits a two-agent game with no pure Nash equilibrium, showing that simultaneous moves destroy the Stackelberg guarantees of earlier leader-follower formulations. To make the equilibrium playable under local information, the paper defines the ordinal rank of an agent inside its connected component of the separating graph, computes it with Ordinal Rank Search (ORS), and trains policies with Fictitious Ordinal Response Learning (FORL), a sequential entropy-regulated fictitious-play scheme. Empirical evaluations on road networks report 87–95% of the optimal cooperative TOP reward, better zero-shot transfer to imbalanced prize distributions, and near-linear scaling to 25 agents for ordinal-rank-conditioned shared policies.","pith_inferences":["The paper leaves open whether ordinal-rank conditioning helps in other graph-structured multi-agent games, such as congestion games or auction-based task allocation, where an agent's payoff depends mainly on nearby better-ranked rivals.","The complete-graph result suggests a natural next test: SPCGs with random edge failures or time-varying travel costs, where the rank-matching rule may need to be replaced by a cost-aware ordinal response.","Because the Theorem 1 proof treats the budget only as a terminal condition, a stronger and untested extension would be a reachability-aware variant of the ordinal response rule; such a variant could close the gap between the paper's equilibrium claim and settings with highly non-uniform edge costs."],"forward_implications":["On complete graphs, self-interested agents do not need to model opponents' intentions: the rank-based conflict rule turns best response into a simple 'take the prize matching your rank' rule, and the equilibrium total reward equals the cooperative TOP optimum for the same budget.","On arbitrary graphs, pure equilibria can fail, so the right design question is what local information lets a learning agent approximate best responses; the paper shows that ordinal rank is one such effective statistic.","Because ordinal-rank conditioning aliases many global ranks into the same local state, a policy trained on a small team can be deployed zero-shot on larger teams with roughly linear reward growth in the tested road-network settings.","The FORL training procedure provides a convergent scheme in independent learning: it terminates at a pure Nash equilibrium when one exists and otherwise at a policy whose entropy lies between prescribed confidence bounds.","In the tested environments, the gap between the competitive equilibrium and the optimal cooperative routing solution is 5–13% of total reward, quantifying the price of anarchy for these games."],"supporting_citations":[{"why":"Defines the Team Orienteering Problem (TOP), the cooperative routing benchmark that SPCG equilibria are compared against.","marker":"[1]"},{"why":"Introduces the prior multi-agent prize-collecting orienteering game with leader-follower play; the SPCG is positioned as its simultaneous-move extension and the price-of-anarchy results are contrasted with it.","marker":"[8]"},{"why":"Supplies the mixed-integer linear programming formulation of the equivalent TOP used to compute the optimal cooperative solution in the experiments.","marker":"[18]"},{"why":"Provides the fictitious-play idea that FORL's alternating sequential policy updates are based on.","marker":"[16]"},{"why":"Gives the stochastic-game and Nash equilibrium formalism that defines the SPCG model and the PNE concept used in Theorems 1 and 2.","marker":"[15]"},{"why":"Provides the transformer architecture used to model the learned policies in the experiments.","marker":"[17]"}],"fun_headline_variants":["Unique equilibrium from rank order in competitive routing","Rank-based rules make prize-collecting routing games tractable","FORL: learning rank-based policies for competitive routing","Ordinal rank as inductive bias for multi-agent routing","Competitive routing games tamed by ordinal rank and FORL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the $i$-th largest remaining prize is always reachable with the agent's remaining budget and still leaves enough budget to reach the terminal; the proof of Theorem 1 only checks the budget as a terminal condition, so with general edge costs a cheaper nearby prize can dominate the rank-matching prize.","fun_headline_variants_meta":{"raw":{"variants":["Unique equilibrium from rank order in competitive routing","Rank-based rules make prize-collecting routing games tractable","FORL: learning rank-based policies for competitive routing","Ordinal rank as inductive bias for multi-agent routing","Competitive routing games tamed by ordinal rank and FORL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000366,"raw_usage":{"total_tokens":2030,"prompt_tokens":1071,"completion_tokens":959,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":687,"completion_tokens_details":{"reasoning_tokens":882}},"tokens_in":687,"tokens_out":959,"duration_ms":9144,"temperature":1.0,"reasoning_tokens":882,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:41:10.330630+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a two-agent complete graph with start $s$, terminal $d$, budget $L=3$, edge costs $w(s,A)=1$, $w(A,d)=1$, $w(s,B)=2$, $w(B,d)=2$, $w(s,C)=0.5$, $w(C,d)=0.5$, and prizes $p_A=10$, $p_B=9$, $p_C=8$, with $p_d$ very large. If agent 1 takes $A$, agent 2's prescribed equilibrium action is $B$ (the second-largest prize), yielding 9 and no terminal reward because $3-2 < w(B,d)=2$; deviating to $C$ yields $8+p_d$, which is larger. This instance would refute Theorem 1 as stated.","supporting_citations":[{"cited_title":"The team orienteering problem,","cited_arxiv_id":null,"evidence_quote":"Defines the Team Orienteering Problem (TOP), the cooperative routing benchmark that SPCG equilibria are compared against."},{"cited_title":"Prize collecting multiagent orienteer- ing: Price of anarchy bounds and solution methods,","cited_arxiv_id":null,"evidence_quote":"Introduces the prior multi-agent prize-collecting orienteering game with leader-follower play; the SPCG is positioned as its simultaneous-move extension and the price-of-anarchy results are contrasted with it."},{"cited_title":"Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations,","cited_arxiv_id":null,"evidence_quote":"Provides the fictitious-play idea that FORL's alternating sequential policy updates are based on."},{"cited_title":"Nash q-learning for general-sum stochastic games,","cited_arxiv_id":null,"evidence_quote":"Gives the stochastic-game and Nash equilibrium formalism that defines the SPCG model and the PNE concept used in Theorems 1 and 2."}],"review_version":2}