Continuous Positional Payoffs

DOI10.46298/LMCS-19(3:10)2023arXiv2012.09047MaRDI QIDQ6135780FDOQ6135780

Author name not available (Why is that?), Alexander Kozachinskiy

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: What payoffs are positionally determined for deterministic two-player antagonistic games on finite directed graphs? In this paper we study this question for payoffs that are continuous. The main reason why continuous positionally determined payoffs are interesting is that they include the multi-discounted payoffs. We show that for continuous payoffs, positional determinacy is equivalent to a simple property called prefix-monotonicity. We provide three proofs of it, using three major techniques of establishing positional determinacy -- inductive technique, fixed point technique and strategy improvement technique. A combination of these approaches provides us with better understanding of the structure of continuous positionally determined payoffs as well as with some algorithmic results.

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

Recommendations

• Continuous Positional Payoffs
• Continuity of the payoff functions
• scientific article; zbMATH DE number 3062461
• Continuous Time Repeated Games
• Continuous Nash equilibria
• Continuous implementation with payoff knowledge
• Contests with discontinuous payoffs
• Constant payoff in zero-sum stochastic games
• Continuous accumulation games on discrete locations
• scientific article; zbMATH DE number 978450

zbMATH Keywords

games on graphspositional strategiescontinuous payoffs

Mathematics Subject Classification ID

Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computer science (68-XX)

Cites Work

• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic Games
• Automata, logics, and infinite games. A guide to current research
• Title not available (Why is that?)
• Positional strategies for mean payoff games
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Pure Stationary Optimal Strategies in Markov Decision Processes
• Infinite games played on finite graphs
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Mathematical Foundations of Computer Science 2004
• Combinatorial structure and randomized subexponential algorithms for infinite games
• CONCUR 2005 – Concurrency Theory
• On the positional determinacy of edge-labeled games
• Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
• Exponential Lower Bounds for Policy Iteration
• Title not available (Why is that?)
• Deciding Parity Games in Quasi-polynomial Time
• Title not available (Why is that?)

Cited In (2)

• Continuous Positional Payoffs
• Continuous implementation with payoff knowledge

This page was built for publication: Continuous Positional Payoffs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135780)