---
_id: '12767'
abstract:
- lang: eng
  text: "Several problems in planning and reactive synthesis can be reduced to the
    analysis of two-player quantitative graph games. Optimization is one form of analysis.
    We argue that in many cases it may be better to replace the optimization problem
    with the satisficing problem, where instead of searching for optimal solutions,
    the goal is to search for solutions that adhere to a given threshold bound.\r\nThis
    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 over optimization."
acknowledgement: We thank anonymous reviewers for valuable inputs. This work is supported
  in part by NSF grant 2030859 to the CRA for the CIFellows Project, NSF grants IIS-1527668,
  CCF-1704883, IIS-1830549, the ERC CoG 863818 (ForM-SMArt), and an award from the
  Maryland Procurement Office.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Suguman
  full_name: Bansal, Suguman
  last_name: Bansal
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Moshe Y.
  full_name: Vardi, Moshe Y.
  last_name: Vardi
citation:
  ama: 'Bansal S, Chatterjee K, Vardi MY. On satisficing in quantitative games. In:
    <i>27th International Conference on Tools and Algorithms for the Construction
    and Analysis of Systems</i>. Vol 12651. Springer Nature; 2021:20-37. doi:<a href="https://doi.org/10.1007/978-3-030-72016-2">10.1007/978-3-030-72016-2</a>'
  apa: 'Bansal, S., Chatterjee, K., &#38; Vardi, M. Y. (2021). On satisficing in quantitative
    games. In <i>27th International Conference on Tools and Algorithms for the Construction
    and Analysis of Systems</i> (Vol. 12651, pp. 20–37). Luxembourg City, Luxembourg:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-030-72016-2">https://doi.org/10.1007/978-3-030-72016-2</a>'
  chicago: Bansal, Suguman, Krishnendu Chatterjee, and Moshe Y. Vardi. “On Satisficing
    in Quantitative Games.” In <i>27th International Conference on Tools and Algorithms
    for the Construction and Analysis of Systems</i>, 12651:20–37. Springer Nature,
    2021. <a href="https://doi.org/10.1007/978-3-030-72016-2">https://doi.org/10.1007/978-3-030-72016-2</a>.
  ieee: S. Bansal, K. Chatterjee, and M. Y. Vardi, “On satisficing in quantitative
    games,” in <i>27th International Conference on Tools and Algorithms for the Construction
    and Analysis of Systems</i>, Luxembourg City, Luxembourg, 2021, vol. 12651, pp.
    20–37.
  ista: 'Bansal S, Chatterjee K, Vardi MY. 2021. On satisficing in quantitative games.
    27th International Conference on Tools and Algorithms for the Construction and
    Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis
    of Systems, LNCS, vol. 12651, 20–37.'
  mla: Bansal, Suguman, et al. “On Satisficing in Quantitative Games.” <i>27th International
    Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>,
    vol. 12651, Springer Nature, 2021, pp. 20–37, doi:<a href="https://doi.org/10.1007/978-3-030-72016-2">10.1007/978-3-030-72016-2</a>.
  short: S. Bansal, K. Chatterjee, M.Y. Vardi, in:, 27th International Conference
    on Tools and Algorithms for the Construction and Analysis of Systems, Springer
    Nature, 2021, pp. 20–37.
conference:
  end_date: 2021-04-01
  location: Luxembourg City, Luxembourg
  name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
  start_date: 2021-03-27
date_created: 2023-03-26T22:01:09Z
date_published: 2021-03-21T00:00:00Z
date_updated: 2025-07-14T09:09:51Z
day: '21'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-72016-2
ec_funded: 1
external_id:
  arxiv:
  - '2101.02594'
file:
- access_level: open_access
  checksum: b020b78b23587ce7610b1aafb4e63438
  content_type: application/pdf
  creator: dernst
  date_created: 2023-03-28T11:00:33Z
  date_updated: 2023-03-28T11:00:33Z
  file_id: '12777'
  file_name: 2021_LNCS_Bansal.pdf
  file_size: 747418
  relation: main_file
  success: 1
file_date_updated: 2023-03-28T11:00:33Z
has_accepted_license: '1'
intvolume: '     12651'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 20-37
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 27th International Conference on Tools and Algorithms for the Construction
  and Analysis of Systems
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030720155'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On satisficing in quantitative games
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12651
year: '2021'
...