{"id":"e20e554b-27b9-479c-afd3-4de2e15ab7b3","arxiv_id":"2606.29420","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Generalized bidding games with player and bidding vertices are linearly interreducible with simple stochastic games, solvable in NP ∩ coNP for parity and mean-payoff, and have an NP-complete repair problem for vertex ownership assignment.","lead":"This paper introduces generalized bidding games on graphs that mix player-owned vertices with bidding vertices where players compete for the move using Richman bidding. It proves these games are linearly equivalent to simple stochastic games and gives complexity results for solving them under parity and mean-payoff objectives.","discovery_kind":"unification","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's UNVERDICTED stems from abstract-only access; the claim as described aligns with established correspondences and introduces no evident new risk factors.","tokens_in":1846,"tokens_out":219,"duration_ms":22201,"concrete_test":"Extract the explicit reduction constructions from the equivalence proof and measure the size of the output instance relative to the input; confirm both directions produce instances whose vertex/edge count is at most c·n for small constant c.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of linear interreducibility between generalized Richman bidding games and simple stochastic games follows directly from the model extension (player-1, player-2, and bidding vertices) mirroring the known pure-bidding to random-turn correspondence. The NP∩coNP retention for parity and mean-payoff is presented as inheriting from the special cases without additional assumptions beyond finite directed graphs and standard winning conditions. No internal inconsistency or unsecured step is visible in the stated argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces generalized bidding games on graphs combining player-1 vertices, player-2 vertices, and bidding vertices. It claims these are more expressive than pure bidding games, that generalized Richman bidding games are linearly interreducible with simple stochastic games (extending the pure-bidding/random-turn correspondence), that parity and mean-payoff instances remain in NP ∩ coNP, and that the repair problem of assigning owners to bidding vertices to meet a budget threshold is NP-complete with applications to compositional policy synthesis.","tokens_in":1928,"tokens_out":225,"duration_ms":32529,"significance":"If the linear interreducibility holds, the result supplies a structural bridge that transfers algorithmic techniques and complexity classifications between bidding games and stochastic games in a manner directly analogous to the known pure-bidding/random-turn link. Retention of the NP ∩ coNP bound for parity and mean-payoff objectives, together with the NP-completeness classification of the repair problem, constitutes a concrete advance for algorithmic game theory on graphs.","major_comments":[],"minor_comments":[],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their thorough reading and positive recommendation to accept the paper. The report correctly captures the main contributions regarding the expressiveness of generalized bidding games, their linear interreducibility with simple stochastic games, the retention of the NP ∩ coNP bound for parity and mean-payoff objectives, and the NP-completeness of the repair problem.","responses":[],"tokens_in":1356,"tokens_out":90,"duration_ms":9946,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that adding player-1 and player-2 vertices to Richman bidding games produces a model that is linearly interreducible with simple stochastic games. This is a direct structural extension of the known pure-bidding to random-turn correspondence, and the paper uses it to transfer the NP∩coNP bounds for parity and mean-payoff objectives.\n\nThe model definition is straightforward and the claim that it is strictly more expressive than pure bidding games is stated clearly. The repair problem—reassigning owners to bidding vertices to bring the winning budget below a target—is shown NP-complete and tied to compositional synthesis, which is a concrete application. The complexity results inherit from the special cases without extra assumptions beyond finite graphs and standard winning conditions.\n\nThe equivalence argument looks like it follows from the vertex types mirroring the probabilistic moves in stochastic games, with no visible circularity or extra parameters. The abstract presents the reductions as new rather than a restatement.\n\nOne minor soft spot is that the abstract gives no proof outline, so the exact linear reductions and how they preserve the objectives would need verification in the body. Nothing indicates the central claims are at risk.\n\nThis is for people working on graph games, bidding mechanisms, or stochastic games in algorithmic game theory. A reader who needs new modeling tools that combine fixed control with auctions would find it useful. It deserves peer review because the unification is new and the complexity statements are sharp.","headline":"Generalized bidding games mix owned and bidding vertices and reduce linearly to simple stochastic games, extending the pure-bidding/random-turn link.","tokens_in":2411,"tokens_out":362,"would_cite":true,"duration_ms":27293,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Generalized Richman bidding games are linearly interreducible with simple stochastic games.","keywords":["generalized bidding games","Richman bidding","simple stochastic games","parity objectives","mean-payoff objectives","NP ∩ coNP","game equivalence","repair problem"],"falsifier":"A concrete generalized bidding game instance whose winning budget threshold differs from the threshold obtained after applying the linear reduction to its corresponding simple stochastic game.","tokens_in":2768,"feed_emoji":"","tokens_out":649,"duration_ms":23018,"temperature":0.7,"pith_summary":"The paper defines generalized bidding games on graphs by adding bidding vertices alongside player-1 and player-2 vertices. It establishes that these games under Richman bidding rules are linearly interreducible with simple stochastic games, meaning each can be transformed into the other with linear blowup while preserving winning conditions. This equivalence transfers known results, so parity and mean-payoff versions of generalized bidding games remain solvable in NP intersect coNP. The model is shown to be strictly more expressive than pure bidding games. The authors also prove that a repair problem, which asks whether bidding vertices can be reassigned to owners to meet a target budget, is NP-complete.","feed_headline":"Generalized bidding games reduce linearly to stochastic games","feed_subtitle":"Richman bidding on mixed turn-based and bidding graphs matches simple stochastic games, keeping parity and mean-payoff problems in NP ∩ coNP","key_machinery":"Linear interreducibility between generalized Richman bidding games and simple stochastic games, which converts bidding vertices into probabilistic transitions while preserving the outcome for every budget threshold.","core_discovery":"Generalized Richman bidding games are structurally equivalent to simple stochastic games via linear interreducibility in both directions. As a result, the best known upper bounds for turn-based games and pure bidding games carry over directly: generalized bidding games with parity and mean-payoff specifications lie in NP ∩ coNP. Pure bidding games correspond to the special case of random-turn games, and the generalized version extends them exactly as simple stochastic games extend random-turn games.","pith_inferences":["Other variants of bidding rules might correspond to other classes of stochastic games through similar reductions.","The NP-completeness of the repair problem suggests it could serve as a building block for automated game design tools.","Results on mean-payoff objectives may transfer to related quantitative specifications via the same equivalence."],"forward_implications":["Algorithms and decision procedures for simple stochastic games apply directly to generalized bidding games.","Parity and mean-payoff generalized bidding games remain in NP ∩ coNP.","The repair problem of reassigning owners to bidding vertices to lower the winning budget below a target is NP-complete.","Applications exist in compositional policy synthesis for multi-objective verification settings."],"fun_headline_variants":["Generalized bidding equals stochastic games","Richman bidding matches stochastic games linearly","Mixed bidding graphs reduce to stochastic games","Bidding games interreducible with stochastic games","Generalized Richman bidding links to stochastic games"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The equivalence and complexity results hold when the games are played on finite directed graphs with the usual Richman payment rules and standard winning conditions on infinite paths.","fun_headline_variants_meta":{"raw":{"variants":["Generalized bidding equals stochastic games","Richman bidding matches stochastic games linearly","Mixed bidding graphs reduce to stochastic games","Bidding games interreducible with stochastic games","Generalized Richman bidding links to stochastic games"]},"model":"grok-4.3","cost_usd":0.003996,"raw_usage":{"total_tokens":2101,"prompt_tokens":790,"num_sources_used":0,"completion_tokens":62,"cost_in_usd_ticks":39962000,"prompt_tokens_details":{"text_tokens":790,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1249,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":790,"tokens_out":62,"duration_ms":13426,"temperature":1.0,"reasoning_tokens":1249,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-30T02:00:02.805296+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete generalized bidding game instance whose winning budget threshold differs from the threshold obtained after applying the linear reduction to its corresponding simple stochastic game.","supporting_citations":[],"review_version":1}