Secure equilibria in weighted games

DOI10.1145/2603088.2603109MaRDI QIDQ4635610zbMATH OpenOpenAlexFDO

Authors Véronique Bruyère, Noémie Meunier, Jean-François Raskin

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

games on weighted graphsmean-payoff and discounted sumquantitative objectivessecure equilibria

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 2-person games (91A05) Games involving graphs (91A43)

Abstract: We consider two-player non zero-sum infinite duration games played on weighted graphs. We extend the notion of secure equilibrium introduced by Chatterjee et al., from the Boolean setting to this quantitative setting. As for the Boolean setting, our notion of secure equilibrium refines the classical notion of Nash equilibrium. We prove that secure equilibria always exist in a large class of weighted games which includes common measures like sup, inf, lim sup, lim inf, mean-payoff, and discounted sum. Moreover we show that one can synthesize finite-memory strategy profiles with few memory. We also prove that the constrained existence problem for secure equilibria is decidable for sup, inf, lim sup, lim inf and mean-payoff measures. Our solutions rely on new results for zero-sum quantitative games with lexicographic objectives that are interesting on their own right.

Recommendations

• Games with secure equilibria
• Computer Science Logic
• Formal Methods for Components and Objects
• On (Subgame Perfect) Secure Equilibrium in Quantitative Reachability Games
• On equilibria in quantitative games with reachability/safety objectives

Cited in

(19)

• Solution of the Hotelling's game in secure strategies
• Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives
• A game-theoretic approach for the synthesis of complex systems
• On the existence of weak subgame perfect equilibria
• Equilibria in multi-player multi-outcome infinite sequential games
• On the existence of weak subgame perfect equilibria
• Constrained existence problem for weak subgame perfect equilibria with -regular Boolean objectives
• Better reply security and existence of equilibria in differential games
• scientific article; zbMATH DE number 1857530 (Why is no real title available?)
• Parameterized complexity of games with monotonically ordered \(\omega\)-regular objectives
• Optimal strategies in weighted limit games
• Infinite-duration bidding games
• Formal Methods for Components and Objects
• Reasoning about Quality and Fuzziness of Strategic Behaviors
• Subgame-perfect Equilibria in Mean-payoff Games (journal version)
• Arena-independent memory bounds for Nash equilibria in reachability games
• Arena-independent memory bounds for Nash equilibria in reachability games
• Equilibria for games with combined qualitative and quantitative objectives
• Games with secure equilibria

This page was built for publication: Secure equilibria in weighted games

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