2026-07-23T05:46:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25457 2026-03-19T13:28:50Z ddc:004 open_access

Mean-Payoff and Energy Discrete-Bidding Games Avni, Guy Sadhukhan, Suman Bidding games Discrete-bidding Mean-payoff games energy games A bidding game is played on a graph as follows. A token is placed on an initial vertex and both players are allocated budgets. In each turn, the players simultaneously submit bids that do not exceed their available budgets, the higher bidder moves the token, and pays the bid to the lower bidder. We focus on discrete-bidding, which are motivated by practical applications and restrict the granularity of the players' bids, e.g, bids must be given in cents. We study, for the first time, discrete-bidding games with mean-payoff and energy objectives. In contrast, mean-payoff continuous-bidding games (i.e., no granularity restrictions) are understood and exhibit a rich mathematical structure. The threshold budget is a necessary and sufficient initial budget for winning an energy game or guaranteeing a target payoff in a mean-payoff game. We first establish existence of threshold budgets; a non-trivial property due to the concurrent moves of the players. Moreover, we identify the structure of the thresholds, which is key in obtaining compact strategies, and in turn, showing that finding threshold is in NP and coNP even in succinctly-represented games. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy Avni and Suman Sadhukhan 2026 Is Part Of LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2026.32 urn:nbn:de:0030-drops-254573 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode