  Graph games lie at the algorithmic core of many automated design problems in
computer science. These are games usually played between two players on a given
graph, where the players keep moving a token along the edges according to
pre-determined rules, and the winner is decided based on the infinite path
traversed by the token from a given initial position. In bidding games, the
players initially get some monetary budgets which they need to use to bid for
the privilege of moving the token at each step. Each round of bidding affects
the players' available budgets, which is the only form of update that the
budgets experience. We introduce bidding games with charging where the players
can additionally improve their budgets during the game by collecting
vertex-dependent charges. Unlike traditional bidding games (where all charges
are zero), bidding games with charging allow non-trivial recurrent behaviors.
We show that the central property of traditional bidding games generalizes to
bidding games with charging: For each vertex there exists a threshold ratio,
which is the necessary and sufficient fraction of the total budget for winning
the game from that vertex. While the thresholds of traditional bidding games
correspond to unique fixed points of linear systems of equations, in games with
charging, these fixed points are no longer unique. This significantly
complicates the proof of existence and the algorithmic computation of
thresholds for infinite-duration objectives. We also provide the lower
complexity bounds for computing thresholds for Rabin and Streett objectives,
which are the first known lower bounds in any form of bidding games (with or
without charging), and we solve the following repair problem for safety and
reachability games that have unsatisfiable objectives: Can we distribute a
given amount of charge to the players in a way such that the objective can be
satisfied?
