conference paper published yes Ali Asadi author 02d96aae-000e-11ec-b801-cadd0a5eefbb Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000-0002-2985-7724 Ehsan Kafshdar Goharshadi author 103b4fa0-896a-11ed-bdf8-87b697bef40d0000-0002-8595-0587 Pavol Kebis author 2e0132b3-4e98-11ef-b275-cf7281c2802a Kaushik Mallik author 0834ff3c-6d72-11ec-94e0-b5b0a4fb85980000-0001-9864-7475 GradSch department KrCh department ToHe department CONCUR: Conference on Concurrency Theory Bilateral Artificial Intelligence (Chatterjee) project Formal Methods for Stochastic Models: Algorithms and Applications project Interface Theory for Security and Privacy project Vigilant Algorithmic Monitoring of Software project 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 traditional bidding games - referred to as 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. In this work, 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. First, we show that, as a model, generalized bidding games are more expressive than pure bidding games, and we provide several applications. Second, and most importantly, we show that generalized Richman bidding games are structurally equivalent to simple stochastic games, a well-studied model: 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 (parity) and quantitative (mean-payoff and discounted-sum) specifications. From a computational perspective, 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∩coNP. Finally, 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. https://research-explorer.ista.ac.at/download/22920/22946/2026_LIPIcsCONCUR_Asadi.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2026Liverpool, United Kingdom eng Bidding GamesStochastic Games 1868-8969 9783959774475 2606.2942010.4230/LIPIcs.CONCUR.2026.13 391 A. Asadi, T.A. Henzinger, E. Goharshady, P. Kebis, K. Mallik, in:, 37th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. Asadi, Ali, Thomas A Henzinger, Ehsan Goharshady, Pavol Kebis, and Kaushik Mallik. “Generalized Bidding Games: Where Bidding and Stochastic Games Meet.” In <i>37th International Conference on Concurrency Theory</i>, Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.13">https://doi.org/10.4230/LIPIcs.CONCUR.2026.13</a>. Asadi A, Henzinger TA, Goharshady E, Kebis P, Mallik K. Generalized bidding games: Where bidding and stochastic games meet. In: <i>37th International Conference on Concurrency Theory</i>. Vol 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.13">10.4230/LIPIcs.CONCUR.2026.13</a> Asadi A, Henzinger TA, Goharshady E, Kebis P, Mallik K. 2026. Generalized bidding games: Where bidding and stochastic games meet. 37th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 391, 13:1-13:20. A. Asadi, T. A. Henzinger, E. Goharshady, P. Kebis, and K. Mallik, “Generalized bidding games: Where bidding and stochastic games meet,” in <i>37th International Conference on Concurrency Theory</i>, Liverpool, United Kingdom, 2026, vol. 391. Asadi, Ali, et al. “Generalized Bidding Games: Where Bidding and Stochastic Games Meet.” <i>37th International Conference on Concurrency Theory</i>, vol. 391, 13:1-13:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.13">10.4230/LIPIcs.CONCUR.2026.13</a>. Asadi, A., Henzinger, T. A., Goharshady, E., Kebis, P., &#38; Mallik, K. (2026). Generalized bidding games: Where bidding and stochastic games meet. In <i>37th International Conference on Concurrency Theory</i> (Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.13">https://doi.org/10.4230/LIPIcs.CONCUR.2026.13</a> 229202026-09-13T22:01:53Z2026-09-17T09:44:41Z