{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:20:10Z","timestamp":1784830810160,"version":"3.55.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["S11402-N23 (RiSE\/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship)"],"award-info":[{"award-number":["S11402-N23 (RiSE\/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship)"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>\n            &lt;?tight?&gt;Two-player games on graphs are widely studied in formal methods, as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the\n            <jats:italic>bidding<\/jats:italic>\n            mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. The following bidding rule was previously defined and called Richman bidding. Both players have separate\n            <jats:italic>budgets<\/jats:italic>\n            , which sum up to 1. In each turn, a bidding takes place: Both players submit bids simultaneously, where a bid is legal if it does not exceed the available budget, and the higher bidder pays his bid to the other player and moves the token. The central question studied in bidding games is a necessary and sufficient initial budget for winning the game: a\n            <jats:italic>threshold<\/jats:italic>\n            budget in a vertex is a value\n            <jats:italic>t<\/jats:italic>\n            \u2208 [0, 1] such that if Player 1\u2019s budget exceeds\n            <jats:italic>t<\/jats:italic>\n            , he can win the game; and if Player 2\u2019s budget exceeds 1 \u2212\n            <jats:italic>t<\/jats:italic>\n            , he can win the game. Threshold budgets were previously shown to exist in every vertex of a reachability game, which have an interesting connection with\n            <jats:italic>random-turn<\/jats:italic>\n            games\u2014a sub-class of simple stochastic games in which the player who moves is chosen randomly. We show the existence of threshold budgets for a qualitative class of infinite-duration games, namely parity games, and a quantitative class, namely mean-payoff games. The key component of the proof is a quantitative solution to strongly connected mean-payoff bidding games in which we extend the connection with random-turn games to these games, and construct explicit optimal strategies for both players.\n          <\/jats:p>","DOI":"10.1145\/3340295","type":"journal-article","created":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T12:39:01Z","timestamp":1563280741000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Infinite-duration Bidding Games"],"prefix":"10.1145","volume":"66","author":[{"given":"Guy","family":"Avni","sequence":"first","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas A.","family":"Henzinger","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ventsislav","family":"Chonev","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems (MPI-SWS), Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 30th CONCUR. Retrieved from: https:\/\/arxiv.org\/abs\/1905","author":"Aghajohari M.","unstructured":"M. Aghajohari , G. Avni , and T. A. Henzinger . 2019. Determinacy in discrete-bidding infinite-duration games determinacy in discrete-bidding infinite-duration games . In Proceedings of the 30th CONCUR. Retrieved from: https:\/\/arxiv.org\/abs\/1905 .03588. M. Aghajohari, G. Avni, and T. A. Henzinger. 2019. Determinacy in discrete-bidding infinite-duration games determinacy in discrete-bidding infinite-duration games. In Proceedings of the 30th CONCUR. Retrieved from: https:\/\/arxiv.org\/abs\/1905.03588."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 26th CONCUR. 325--339","author":"Almagor S.","unstructured":"S. Almagor , G. Avni , and O. Kupferman . 2015. Repairing multi-player games . In Proceedings of the 26th CONCUR. 325--339 . S. Almagor, G. Avni, and O. Kupferman. 2015. Repairing multi-player games. In Proceedings of the 26th CONCUR. 325--339."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 35th FSTTCS. 380--393","author":"Almagor S.","unstructured":"S. Almagor , D. Kuperberg , and O. Kupferman . 2015. The sensing cost of monitoring and synthesis . In Proceedings of the 35th FSTTCS. 380--393 . S. Almagor, D. Kuperberg, and O. Kupferman. 2015. The sensing cost of monitoring and synthesis. In Proceedings of the 35th FSTTCS. 380--393."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"K. R. Apt and E. Gr\u00e4del. 2011. Lectures in Game Theory for Computer Scientists. Cambridge University Press.   K. R. Apt and E. Gr\u00e4del. 2011. Lectures in Game Theory for Computer Scientists. Cambridge University Press.","DOI":"10.1017\/CBO9780511973468"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"G. Avni S. Guha and O. Kupferman. 2018. An abstraction-refinement methodology for reasoning about network games. Games 9 3 (2018).  G. Avni S. Guha and O. Kupferman. 2018. An abstraction-refinement methodology for reasoning about network games. Games 9 3 (2018).","DOI":"10.3390\/g9030039"},{"key":"e_1_2_1_7_1","unstructured":"G.\n      Avni T. A.\n      Henzinger and \n      V.\n      Chonev\n  . \n  2017\n  . Infinite-duration bidding games. In Proceedings of the 28th \n  CONCUR volume \n  85\n   of \n  Lecture Notes in Computer Science\n  . 21:1--21:18.  G. Avni T. A. Henzinger and V. Chonev. 2017. Infinite-duration bidding games. In Proceedings of the 28th CONCUR volume 85 of Lecture Notes in Computer Science. 21:1--21:18."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th WINE.","author":"Avni G.","unstructured":"G. Avni , T. A. Henzinger , and R. Ibsen-Jensen . 2018. Infinite-duration poorman-bidding games . In Proceedings of the 14th WINE. G. Avni, T. A. Henzinger, and R. Ibsen-Jensen. 2018. Infinite-duration poorman-bidding games. In Proceedings of the 14th WINE."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 9th SAGT. 153--166","author":"Avni G.","unstructured":"G. Avni , T. A. Henzinger , and O. Kupferman . 2016. Dynamic resource allocation games . In Proceedings of the 9th SAGT. 153--166 . G. Avni, T. A. Henzinger, and O. Kupferman. 2016. Dynamic resource allocation games. In Proceedings of the 9th SAGT. 153--166."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 44th MFCS. Retrieved from: https:\/\/arxiv.org\/abs\/1905","author":"Avni G.","year":"2019","unstructured":"G. Avni , T. A. Henzinger , and \u0110. \u017dikeli\u0107. 2019 . Bidding mechanisms in graph games . In Proceedings of the 44th MFCS. Retrieved from: https:\/\/arxiv.org\/abs\/1905 .03588. G. Avni, T. A. Henzinger, and \u0110. \u017dikeli\u0107. 2019. Bidding mechanisms in graph games. In Proceedings of the 44th MFCS. Retrieved from: https:\/\/arxiv.org\/abs\/1905.03588."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.08.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"P. Bouyer R. Brenguier N. Markey and M. Ummels. 2015. Pure Nash equilibria in concurrent deterministic games. Logical Meth. Comput. Sci. 11 2 (2015).  P. Bouyer R. Brenguier N. Markey and M. Ummels. 2015. Pure Nash equilibria in concurrent deterministic games. Logical Meth. Comput. Sci. 11 2 (2015).","DOI":"10.2168\/LMCS-11(2:9)2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85778-5_4"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 38th ICALP. 332--343","author":"Br\u00e1zdil T.","unstructured":"T. Br\u00e1zdil , V. Brozek , K. Etessami , and A. Kucera . 2011. Approximating the termination value of one-counter MDPS and stochastic games . In Proceedings of the 38th ICALP. 332--343 . T. Br\u00e1zdil, V. Brozek, K. Etessami, and A. Kucera. 2011. Approximating the termination value of one-counter MDPS and stochastic games. In Proceedings of the 38th ICALP. 332--343."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 21st SODA. 863--874","author":"Br\u00e1zdil T.","unstructured":"T. Br\u00e1zdil , V. Brozek , K. Etessami , A. Kucera , and D. Wojtczak . 2010. One-counter Markov decision processes . In Proceedings of the 21st SODA. 863--874 . T. Br\u00e1zdil, V. Brozek, K. Etessami, A. Kucera, and D. Wojtczak. 2010. One-counter Markov decision processes. In Proceedings of the 21st SODA. 863--874."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"T. Brihaye V. Bruy\u00e8re J. De Pril and H. Gimbert. 2012. On subgame perfection in quantitative reachability games. Logical Meth. Comput. Sci. 9 1 (2012).  T. Brihaye V. Bruy\u00e8re J. De Pril and H. Gimbert. 2012. On subgame perfection in quantitative reachability games. Logical Meth. Comput. Sci. 9 1 (2012).","DOI":"10.2168\/LMCS-9(1:7)2013"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 3rd EMSOFT. 117--133","author":"Chakrabarti A.","unstructured":"A. Chakrabarti , L. de Alfaro , T. A. Henzinger , and M. Stoelinga . 2003. Resource interfaces . In Proceedings of the 3rd EMSOFT. 117--133 . A. Chakrabarti, L. de Alfaro, T. A. Henzinger, and M. Stoelinga. 2003. Resource interfaces. In Proceedings of the 3rd EMSOFT. 117--133."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_18"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.032"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.07.004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78929-1_6"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 13th CSL. 26--40","author":"Chatterjee K.","unstructured":"K. Chatterjee , R. Majumdar , and M. Jurdzinski . 2004. On Nash equilibria in stochastic games . In Proceedings of the 13th CSL. 26--40 . K. Chatterjee, R. Majumdar, and M. Jurdzinski. 2004. On Nash equilibria in stochastic games. In Proceedings of the 13th CSL. 26--40."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the DIMACS. 51--72","author":"Condon A.","year":"1990","unstructured":"A. Condon . 1990 . On algorithms for simple stochastic games . In Proceedings of the DIMACS. 51--72 . A. Condon. 1990. On algorithms for simple stochastic games. In Proceedings of the DIMACS. 51--72."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.37236\/357"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12002-2_16"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_19"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"M. Holtmann L. Kaiser and W. Thomas. 2012. Degrees of lookahead in regular infinite games. Logical Meth. Comput. Sci. 8 3 (2012).  M. Holtmann L. Kaiser and W. Thomas. 2012. Degrees of lookahead in regular infinite games. Logical Meth. Comput. Sci. 8 3 (2012).","DOI":"10.2168\/LMCS-8(3:24)2012"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ICALP. 45--60","author":"Hosch F. A.","unstructured":"F. A. Hosch and L. H. Landweber . 1972. Finite delay solutions for sequential conditions . In Proceedings of the ICALP. 45--60 . F. A. Hosch and L. H. Landweber. 1972. Finite delay solutions for sequential conditions. In Proceedings of the ICALP. 45--60."},{"key":"e_1_2_1_30_1","volume-title":"Dynamic Programming and Markov Processes","author":"Howard A. R.","unstructured":"A. R. Howard . 1960. Dynamic Programming and Markov Processes . The MIT Press . A. R. Howard. 1960. Dynamic Programming and Markov Processes. The MIT Press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1260"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0170-z"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2013.06.005"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"F. Klein and M. Zimmermann. 2016. How much lookahead is needed to win infinite games? Logical Meth. Comput. Sci. 12 3 (2016).  F. Klein and M. Zimmermann. 2016. How much lookahead is needed to win infinite games? Logical Meth. Comput. Sci. 12 3 (2016).","DOI":"10.2168\/LMCS-12(3:4)2016"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-009-0067-z"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 23rd TACAS. 229--246","author":"Kupferman O.","unstructured":"O. Kupferman and T. Tamir . 2017. Hierarchical network formation games . In Proceedings of the 23rd TACAS. 229--246 . O. Kupferman and T. Tamir. 2017. Hierarchical network formation games. In Proceedings of the 23rd TACAS. 229--246."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1998.0676"},{"key":"e_1_2_1_38_1","unstructured":"A. J. Lazarus D. E. Loeb J. G. Propp and D. Ullman. 1996. Richman games. Games No Chance 29 (1996) 439--449.  A. J. Lazarus D. E. Loeb J. G. Propp and D. Ullman. 1996. Richman games. Games No Chance 29 (1996) 439--449."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 23rd SODA. 869--886","author":"Paes Leme R.","year":"2012","unstructured":"R. Paes Leme , V. Syrgkanis , and \u00c9. Tardos. 2012 . Sequential auctions and externalities . In Proceedings of the 23rd SODA. 869--886 . R. Paes Leme, V. Syrgkanis, and \u00c9. Tardos. 2012. Sequential auctions and externalities. In Proceedings of the 23rd SODA. 869--886."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.08.005"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01769259"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631917"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"N. Nisan T. Roughgarden E. Tardos and V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press.   N. Nisan T. Roughgarden E. Tardos and V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00606-1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_2_1_47_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman M. L.","unstructured":"M. L. Puterman . 2005. Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley 8 Sons, Inc., New York, NY. M. L. Puterman. 2005. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley 8 Sons, Inc., New York, NY."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46081-8_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1228621.1228623"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050015"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340295","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:32Z","timestamp":1750268972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3340295"],"URL":"https:\/\/doi.org\/10.1145\/3340295","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}