On satisficing in quantitative games

DOI10.1007/978-3-030-72016-2_2zbMATH Open1467.68161arXiv2101.02594OpenAlexW3150261213MaRDI QIDQ2044188FDOQ2044188

Krishnendu Chatterjee, Moshe Y. Vardi, Suguman Bansal

Publication date: 4 August 2021

Abstract: Several problems in planning and reactive synthesis can be reduced to the analysis of two-player quantitative graph games. {em Optimization} is one form of analysis. We argue that in many cases it may be better to replace the optimization problem with the {em satisficing problem}, where instead of searching for optimal solutions, the goal is to search for solutions that adhere to a given threshold bound. This work defines and investigates the satisficing problem on a two-player graph game with the discounted-sum cost model. We show that while the satisficing problem can be solved using numerical methods just like the optimization problem, this approach does not render compelling benefits over optimization. When the discount factor is, however, an integer, we present another approach to satisficing, which is purely based on automata methods. We show that this approach is algorithmically more performant -- both theoretically and empirically -- and demonstrates the broader applicability of satisficing overoptimization.

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Programming involving graphs or networks (90C35) Applications of game theory (91A80) Games involving graphs (91A43)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of mean payoff games on graphs
• Stochastic Games
• Automata, logics, and infinite games. A guide to current research
• Better Quality in Synthesis through Quantitative Objectives
• Recognizing safety and liveness
• Permissive strategies: from parity games to safety games
• Exact and Approximate Determinization of Discounted-Sum Automata
• Quantitative fair simulation games
• Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
• Model checking quantitative hyperproperties
• Formal specification for deep neural networks
• Comparator automata in quantitative verification
• Universal graphs and good for games automata: new tools for infinite duration games

Cited In (3)

• Satisfying and optimality in \(2\times 2\) common interest games
• Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
• Quantitative games with interval objectives

This page was built for publication: On satisficing in quantitative games

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