Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives
Guy Avni, Martin Kurečka, Kaushik Mallik, Petr Novotný, Suman Sadhukhan · 2024
Read Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives by Guy Avni, Martin Kurečka, Kaushik Mallik, Petr Novotný, Suman Sadhukhan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19609.txt.
Introduction
Guy Avni and co-authors present a 2024 paper on games where players bid for control inside a chance-driven system. A Markov decision process normally has one decision maker steering toward a goal. Here two rivals bid at each step for the right to pick the next action, while chance still shapes the outcomes.
One player wants to maximize the chance of reaching a target state, and the other wants to minimize it. In older bidding games on plain graphs, a single threshold budget decides who can force a win. With chance in play, that threshold becomes a relation between budgets and reach probabilities. The authors build value-iteration algorithms that estimate the thresholds. The work extends bidding game theory to stochastic settings.
Catalog record
| CREATOR | Guy Avni, Martin Kurečka, Kaushik Mallik, Petr Novotný, Suman Sadhukhan |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-19609
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives Guy Avni, Martin Kurečka, Kaushik Mallik, Petr Novotný, Suman Sadhukhan Abstract . 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 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 traditional bidding games is the existence of a threshold budget, which is a necessary and sufficient budget to guarantee winning for the reachability player. For MDPs, the threshold becomes a relation between the 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 solving simple-stochastic games . A. El Fallah Seghrouchni, Y. Vorobeychik, S. Das, A. Nowe (eds.) Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA 1. Introduction Graph games are fundamental for reasoning about strategic interactions between agents in multi-agent systems, with ( Fisman et al., 2010 ; Kupferman et al., 2016 ; Wooldridge et al., 2016 ) or without ( Alur et al., 2002 ) external environments. Environments, when present, are commonly modeled using stochastic processes, like Markov decision processes (MDP) ( Sutton and Barto, 1998 ) in reinforcement learning (single-agent), and stochastic games in the multi-agent setting ( Condon, 1992 ; Filar and Vrieze, 1997 ; Chatterjee and Henzinger, 2012 ) . We study games which combine stochastic environments with auction-based interactions among players, formalized as bidding games on MDP arenas . An MDP is a graph whose vertices are partitioned into control vertices and random vertices, and the game involves the players moving a token along the edges of the graph. The rules of the game are as follows. The two players are allocated initial budgets, normalized in a way that their sum is 1 . When the token reaches a control vertex, an auction is held to determine who chooses where the token goes next. In these auctions, the players simultaneously submit bids from their available budgets, the higher bidder moves the token and pays his bid amount to the lower bidder. When the token reaches a random vertex, it automatically moves to one of the successors according to the transition probabilities of the MDP (without affecting the budgets of the players). We consider the quantitative reachability objectives, where the goal of the first player, called the reachability player , is to maximize the probability that a given target vertex is reached, and the goal of the second player, called the safety player , is to minimize it. Figure 1. A bidding game on an MDP. The control and random vertices are denoted as circular and diamond-shaped, respectively. The probabilistic transitions (marked with arcs) use the uniform distribution. The target for the reachability player is t . The dashed paths are the viable reachability policies for the setting of Ex. 1.1 . a start b c d e f l_{2} t l_{1} Example 1.1. Consider the game in Fig. 1 and the initial budget allocation \langle 0.75+\epsilon,0.25-\epsilon\rangle for the two players. We show how the reachability player can reach the target t with probability at least 0.5 . Initially, the token moves randomly from a . If it reaches c , the reachability player avoids l_{1} by winning the auction with the bid 0.25 (which exceeds the opponent’s budget) and proceeding to d with new budgets \langle 0.5+\epsilon,0.5-\epsilon\rangle . At d , he bids 0.5 , to force the game to e , from which t is reached with probability 0.5 . If, on the other hand, the token moves to b from a , with probability 0.5 it moves to l_{2} and the reachability player loses. If the token reaches d , since no biddings were made, the budgets remain \langle 0.75+\epsilon,0.25-\epsilon\rangle . At d , the reachability player bids 0.25 , proceeds to f with budgets \langle 0.5+\epsilon,0.5-\epsilon\rangle , and then bids 0.5 to force the game to t . Thus, each path b,d,f,t and c,d,e,t , after a , occur with probability 0.5 , and the total probability to reach t from a is 0.5 . Bidding games on MDPs generalize traditional bidding games on graphs , i.e., on MDPs without any random vertices. Bidding games on graphs have a rich pedigree, going back to the seminal work of Lazarus et al. ( Lazarus et al., 1996 ; Lazarus et al., 1999 ) , followed by a series of extensions to various payment schemes ( Avni et al., 2019a ; Avni et al., 2018 ; Avni et al., 2019b ; Avni et al., 2021 ) , non-zero-sum games ( Meir et al., 2018 ) , discrete bidding aimed for practical applications ( Develin and Payne, 2010 ; Aghajohari et al., 2019 ; Avni and Sadhukhan, 2022 ; Avni et al., 2023b ) , partial-information games ( Avni et al., 2023a ) , and bidding games with charging ( Avni et al., 2024a ) . We point out a distinction between traditional and our setups. In the traditional setup, moving the token is memoryless, i.e., there is a winning policy that chooses the same successor from each vertex upon winning the bidding. As seen in the MDP in Ex. 1.1 , the reachability player’s choice at d is not memoryless. Applications Our results have an immediate application in auction-based scheduling ( Avni et al., 2024b ) , which is a decentralized multi-objective decision-making framework. In this framework, we are given an arena, modeling the environment, a pair of specifications \varphi_{0},\varphi_{1} , and we want to compute a pair of policies \sigma_{0},\sigma_{1} that will be composed at runtime with the policies bidding against each other at each step for choosing the next action. The goal is to synthesize \sigma_{0},\sigma_{1} such that their runtime composition fulfills \varphi_{0}\land\varphi_{1} . The advantage is modularity, where the policies can be independently designed, and if one specification changes, only the relevant policy needs to be updated. The synthesis algorithms in auction-based scheduling solve two independent zero-sum bidding games for \sigma_{0} and \sigma_{1} (on the same arena). As zero-sum bidding games have been studied only on graphs, auction-based scheduling is restricted to graph arenas until now. Our work will lead to a decentralized solution of multi-objective reachability on MDPs using auction-based scheduling. Fair resource allocation studies how to allocate a collection of items to a set of agents in a fair manner, where various definitions of fairness exist ( Amanatidis et al., 2022 ; Aziz