Pith. sign in

REVIEW 27 references

Generalized Richman bidding games are linearly interreducible with simple stochastic games.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-30 02:00 UTC pith:74H74Z32

load-bearing objection Generalized bidding games mix owned and bidding vertices and reduce linearly to simple stochastic games, extending the pure-bidding/random-turn link.

arxiv 2606.29420 v1 pith:74H74Z32 submitted 2026-06-28 cs.GT

Generalized Bidding Games: Where Bidding and Stochastic Games Meet

Ali Asadi , Thomas A. Henzinger , Ehsan Kafshdar Goharshady , Pavol Kebis , Kaushik Mallik This is my paper
classification cs.GT
keywords generalized bidding gamesRichman biddingsimple stochastic gamesparity objectivesmean-payoff objectivesNP ∩ coNPgame equivalencerepair problem
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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.

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • 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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 0 minor

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.

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.

Simulated Author's Rebuttal

0 responses · 0 unresolved

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.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claim is the linear interreducibility between generalized Richman bidding games and simple stochastic games, presented as a structural result derived from extending the model with player-1, player-2, and bidding vertices. This extends a previously known special-case correspondence (pure bidding to random-turn games) without the new equivalence reducing to a self-definition, fitted parameter, or load-bearing self-citation chain. The NP∩coNP bounds are inherited from established results on the special cases under standard finite-graph and winning-condition assumptions. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard definitions of graph games, bidding rules, and winning conditions drawn from prior literature; no free parameters, ad-hoc axioms, or new invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions of finite directed graphs, Richman bidding, and temporal/quantitative winning conditions on infinite plays from prior game-theory literature.
    The model and equivalence are built directly on these background notions.

pith-pipeline@v0.9.1-grok · 5870 in / 1360 out tokens · 39968 ms · 2026-06-30T02:00:02.805296+00:00 · methodology

0 comments
read the original abstract

Two-player games on graphs are a classical framework for analyzing strategic decision making. In turn-based games, two players move a token along the edges of the graph, and the right to move the token is determined by the current vertex. In pure bidding games the right to move the token is determined at each step through bidding; here we consider Richman bidding, where the winning player of a bid pays the losing player. The winner is decided based on a temporal or quantitative specification evaluated over the resulting infinite play. We combine turn-based games and pure bidding games into generalized bidding games, with player-1 vertices, player-2 vertices, and bidding vertices. This natural and simple generalization of bidding games has far-reaching consequences. We show that, as a model, generalized bidding games are more expressive than pure bidding games, and we provide several applications. We also show that generalized Richman bidding games are structurally equivalent to simple stochastic games: they are linearly interreducible to each other. As was previously known, the special case of pure Richman bidding games corresponds to random-turn games. In other words, generalized bidding games extend pure bidding games in the same way that simple stochastic games extend random-turn games. We use this connection to solve generalized Richman bidding games for temporal and quantitativ specifications. We establish that generalized bidding games with parity and mean-payoff specifications retain the best known upper bounds for turn-based games and pure bidding games, namely $NP\cap coNP$. We study a repair problem that asks whether bidding vertices can be assigned owners so as to bring the threshold budget required to win the game below a given target. This problem has direct applications in compositional policy synthesis for multi-objective settings, and we show it to be NP-complete.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references

  1. [1]

    Anne Condon , title =. Inf. Comput. , volume =. 1992 , doi =

    1992

  2. [2]

    Advances in Computational Complexity Theory , editor =

    Condon, Anne , title =. Advances in Computational Complexity Theory , editor =. 1993 , publisher =

    1993

  3. [3]

    Henzinger , title =

    Krishnendu Chatterjee and Thomas A. Henzinger , title =. J. Comput. Syst. Sci. , volume =

  4. [4]

    All-Pay Bidding Games on Graphs , booktitle =

    Guy Avni and Rasmus Ibsen. All-Pay Bidding Games on Graphs , booktitle =. 2020 , doi =

    2020

  5. [5]

    Games and Economic Behavior , volume =

    Combinatorial games under auction play , author =. Games and Economic Behavior , volume =. 1999 , publisher =

    1999

  6. [6]

    Auction-Based Scheduling , booktitle =

    Guy Avni and Kaushik Mallik and Suman Sadhukhan , editor =. Auction-Based Scheduling , booktitle =. 2024 , doi =

    2024

  7. [7]

    Luca de Alfaro and Rupak Majumdar , title =. J. Comput. Syst. Sci. , volume =

  8. [8]

    Electron

    Mike Develin and Sam Payne , title =. Electron. J. Comb. , volume =. 2010 , doi =

    2010

  9. [9]

    TheoretiCS , volume =

    Guy Avni and Suman Sadhukhan , title =. TheoretiCS , volume =. 2025 , doi =

    2025

  10. [10]

    Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives , booktitle =

    Guy Avni and Martin Kurecka and Kaushik Mallik and Petr Novotn. Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives , booktitle =. 2025 , doi =

    2025

  11. [11]

    Henzinger , editor =

    Guy Avni and Thomas A. Henzinger , editor =. An Updated Survey of Bidding Games on Graphs (Invited Talk) , booktitle =. 2022 , doi =

    2022

  12. [12]

    Henzinger , editor =

    Guy Avni and Thomas A. Henzinger , editor =. A Survey of Bidding Games on Graphs (Invited Paper) , booktitle =. 2020 , doi =

    2020

  13. [13]

    Henzinger and Kaushik Mallik , editor =

    Guy Avni and Ehsan Kafshdar Goharshady and Thomas A. Henzinger and Kaushik Mallik , editor =. Bidding Games with Charging , booktitle =. 2024 , doi =

    2024

  14. [14]

    Henzinger and Rasmus Ibsen

    Guy Avni and Thomas A. Henzinger and Rasmus Ibsen. Infinite-Duration Poorman-Bidding Games , booktitle =. 2018 , doi =

    2018

  15. [15]

    Henzinger and Ventsislav Chonev , title =

    Guy Avni and Thomas A. Henzinger and Ventsislav Chonev , title =. J. 2019 , doi =

    2019

  16. [16]

    CoRR , volume =

    Hugo Gimbert and Edon Kelmendi , title =. CoRR , volume =. 2014 , url =

    2014

  17. [17]

    One-Counter Stochastic Games , booktitle =

    Tom. One-Counter Stochastic Games , booktitle =. 2010 , doi =

    2010

  18. [18]

    Principles of model checking , publisher =

    Christel Baier and Joost. Principles of model checking , publisher =. 2008 , isbn =

    2008

  19. [19]

    Pacific Journal of Mathematics , volume =

    Tarski, Alfred , title =. Pacific Journal of Mathematics , volume =. 1955 , doi =

    1955

  20. [20]

    A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games , booktitle =

    Rapha. A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games , booktitle =. 2025 , doi =

    2025

  21. [21]

    Henzinger , editor =

    Krishnendu Chatterjee and Thomas A. Henzinger , editor =. Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games , booktitle =. 2006 , doi =

    2006

  22. [22]

    Henzinger , editor =

    Krishnendu Chatterjee and Marcin Jurdzinski and Thomas A. Henzinger , editor =. Quantitative stochastic parity games , booktitle =. 2004 , timestamp =

    2004

  23. [23]

    Puterman , title =

    Martin L. Puterman , title =

  24. [24]

    Journal of mathematical analysis and applications , volume=

    Minimizing a threshold probability in discounted Markov decision processes , author=. Journal of mathematical analysis and applications , volume=. 1993 , publisher=

    1993

  25. [25]

    Krishnendu Chatterjee , title =. Theor. Comput. Sci. , volume =

  26. [26]

    Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information , journal =

    Marianne Akian and Jean Cochet. Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information , journal =

  27. [27]

    Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives , booktitle =

    Krishnendu Chatterjee and Laurent Doyen , editor =. Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives , booktitle =. 2016 , doi =

    2016