Suman Sadhukhan

CSL Conference 2026 Conference Paper

Mean-Payoff and Energy Discrete-Bidding Games

• Guy Avni
• Suman Sadhukhan

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.

AAMAS Conference 2025 Conference Paper

Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

• Guy Avni
• Martin Kurecka
• Kaushik Mallik
• Petr Novotný
• Suman Sadhukhan

Graph games are fundamental in strategic reasoning of multi-agent systems and their environments. We study a new family of graph games which combine stochastic environmental uncertainties and auction-based interactions among the agents, formalized as bidding games on (finite) Markov decision processes (MDP). Normally, on MDPs, a single decision-maker chooses a sequence of actions, producing a probability distribution over infinite paths. In bidding games on MDPs, two players—called the reachability and safety players—bid for the privilege of choosing the next action at each step. The reachability player’s goal is to maximize the probability of reaching a given target vertex, whereas the safety player’s goal is to minimize it. These games generalize traditional bidding games on graphs, and the existing analysis techniques do not extend. For instance, the central property of bidding games on graphs is the existence of a threshold budget, which is the necessary and sufficient budget to guarantee winning for the reachability player. For MDPs, the threshold becomes a relation between budgets and probabilities of reaching the target. We devise value-iteration algorithms that approximate thresholds and optimal policies for general MDPs, and compute the exact solutions for acyclic MDPs, and show that finding thresholds is at least as hard as simple-stochastic games.

Highlights Conference 2025 Conference Abstract

Mean-payoff and Energy Discrete-Bidding Games

• Suman Sadhukhan

Highlights Conference 2024 Conference Abstract

Auction-Based Scheduling

• Suman Sadhukhan

Sequential decision-making tasks often require satisfaction of multiple, partially-contradictory objectives. Existing approaches are monolithic, where a single policy (a function that chooses an action in each state) fulfills all objectives. We present auction-based scheduling, a decentralized framework for multi-objective sequential decision making. Each objective is fulfilled using a separate and independent policy. Composition of policies is performed at runtime, where at each step, the policies simultaneously bid from pre-allocated budgets for the privilege of choosing the next action. The framework allows policies to be independently created, modified, and replaced. We study path planning problems on finite graphs with two temporal objectives and present algorithms to synthesize policies together with bidding policies in a decentralized manner. \t\t We consider three categories of decentralized synthesis problems, parameterized by the assumptions that the policies make on each other. We identify a class of assumptions called assume-admissible for which synthesis is always possible for graphs whose every vertex has at most two outgoing edges. \t\t This is a joint work with Guy Avni and Kaushik Mallik, a version of which has been published at TACAS'24.

ECAI Conference 2023 Conference Paper

Reachability Poorman Discrete-Bidding Games

• Guy Avni
• Tobias Meggendorfer
• Suman Sadhukhan
• Josef Tkadlec
• Dorde Zikelic

We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets.

Highlights Conference 2023 Conference Abstract

Reachability Poorman Discrete-Bidding Games

• Suman Sadhukhan

We consider "bidding games", a class of two-player zero-sum "graph games". The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token (ties are broken according to a predefined mechanism). Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, "poorman discrete-bidding" in which the granularity of the bids is restricted and the higher bid is paid to the bank. In contrast, in "Richman continuous-bidding" bids can be arbitrarily small and are paid to the other player. While the latter mechanism is technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on "threshold budgets", which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We show existence of thresholds when Player 1 wins bidding ties. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets. This is a joint work with Guy Avni, Tobias Meggendorfer, Josef Tkadlec, and Djordje Zikelic. Contributed talk given by Suman Sadhukhan