Infinite-duration poorman-bidding games

DOI10.1007/978-3-030-04612-5_2zbMATH Open1443.91070arXiv1804.04372OpenAlexW2797251385MaRDI QIDQ2190378FDOQ2190378

Authors: Guy Avni, Thomas A. Henzinger, Rasmus Ibsen-Jensen 

Publication date: 18 June 2020

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.

Full work available at URL: https://arxiv.org/abs/1804.04372

Recommendations

• Infinite-duration Bidding Games
• Infinite-duration bidding games
• Bidding mechanisms in graph games
• Bidding games on Markov decision processes
• Bidding games and efficient allocations

zbMATH Keywords

complexity problemsbidding gamestwo-player games on graphs

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Algorithmic game theory and complexity (91A68)

Cites Work

• Algorithmic Game Theory
• Alternating-time temporal logic
• Tug-of-war and the infinity Laplacian
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Title not available (Why is that?)
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Title not available (Why is that?)
• Optimizing scrip systems: crashes, altruists, hoarders, sybils and collusion
• Reasoning about strategies: on the model-checking problem
• Rational synthesis
• Title not available (Why is that?)
• Computer Science Logic
• Title not available (Why is that?)
• Hierarchical network formation games
• On (Subgame Perfect) Secure Equilibrium in Quantitative Reachability Games
• Network-formation games with regular objectives
• Nash Equilibrium for Upward-Closed Objectives
• Games with secure equilibria
• Strategy logic
• Bidding games and efficient allocations
• Discrete bidding games
• Sequential auctions and externalities
• The efficiency of best-response dynamics
• Title not available (Why is that?)
• Combinatorial games under auction play
• Dynamic resource allocation games
• An abstraction-refinement methodology for reasoning about network games
• Repairing multi-player games
• Deciding parity games in quasipolynomial time
• Bidding chess
• Infinite-duration poorman-bidding games
• Endgames in bidding chess
• Infinite-duration bidding games

Cited In (10)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• A Survey of Bidding Games on Graphs (Invited Paper)

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)