Infinite-duration poorman-bidding games
From MaRDI portal
Publication:2190378
Abstract: In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. Such games are central in formal verification since they model the interaction between a non-terminating system and its environment. We study {em bidding games} in which the players bid for the right to move the token. Two bidding rules have been defined. In {em Richman} bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. {em Poorman} bidding is similar except that the winner of the bidding pays the "bank" rather than the other player. While poorman reachability games have been studied before, we present, for the first time, results on {em infinite-duration} poorman games. A central quantity in these games is the {em ratio} between the two players' initial budgets. The questions we study concern a necessary and sufficient ratio with which a player can achieve a goal. For reachability objectives, such {em threshold ratios} are known to exist for both bidding rules. We show that the properties of poorman reachability games extend to complex qualitative objectives such as parity, similarly to the Richman case. Our most interesting results concern quantitative poorman games, namely poorman mean-payoff games, where we construct optimal strategies depending on the initial ratio, by showing a connection with {em random-turn based games}. The connection in itself is interesting, because it does not hold for reachability poorman games. We also solve the complexity problems that arise in poorman bidding games.
Recommendations
Cites work
- scientific article; zbMATH DE number 5869590 (Why is no real title available?)
- scientific article; zbMATH DE number 988850 (Why is no real title available?)
- scientific article; zbMATH DE number 4124989 (Why is no real title available?)
- scientific article; zbMATH DE number 549853 (Why is no real title available?)
- scientific article; zbMATH DE number 5685899 (Why is no real title available?)
- Algorithmic Game Theory
- Alternating-time temporal logic
- An abstraction-refinement methodology for reasoning about network games
- Bidding chess
- Bidding games and efficient allocations
- Combinatorial games under auction play
- Computer Science Logic
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Deciding parity games in quasipolynomial time
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Discrete bidding games
- Dynamic resource allocation games
- Endgames in bidding chess
- Games with secure equilibria
- Hierarchical network formation games
- Infinite-duration bidding games
- Infinite-duration poorman-bidding games
- Nash Equilibrium for Upward-Closed Objectives
- Network-formation games with regular objectives
- On (Subgame Perfect) Secure Equilibrium in Quantitative Reachability Games
- Optimizing scrip systems: crashes, altruists, hoarders, sybils and collusion
- Rational synthesis
- Reasoning about strategies: on the model-checking problem
- Repairing multi-player games
- Sequential auctions and externalities
- Strategy logic
- The efficiency of best-response dynamics
- Tug-of-war and the infinity Laplacian
Cited in
(10)- A Survey of Bidding Games on Graphs (Invited Paper)
- scientific article; zbMATH DE number 7561655 (Why is no real title available?)
- scientific article; zbMATH DE number 7327943 (Why is no real title available?)
- scientific article; zbMATH DE number 7649928 (Why is no real title available?)
- Infinite-duration Bidding Games
- Bidding mechanisms in graph games
- Discrete Richman-bidding scoring games
- Infinite-duration bidding games
- Infinite-duration poorman-bidding games
- Bidding games on Markov decision processes
This page was built for publication: Infinite-duration poorman-bidding games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2190378)
