---
_id: '5977'
abstract:
- lang: eng
  text: 'We consider the stochastic shortest path (SSP)problem for succinct Markov
    decision processes(MDPs), where the MDP consists of a set of vari-ables, and a
    set of nondeterministic rules that up-date the variables. First, we show that
    several ex-amples from the AI literature can be modeled assuccinct MDPs.  Then
    we present computationalapproaches for upper and lower bounds for theSSP problem:
    (a) for computing upper bounds, ourmethod is polynomial-time in the implicit descrip-tion
    of the MDP; (b) for lower bounds, we present apolynomial-time (in the size of
    the implicit descrip-tion) reduction to quadratic programming. Our ap-proach is
    applicable even to infinite-state MDPs.Finally, we present experimental results
    to demon-strate the effectiveness of our approach on severalclassical examples
    from the AI literature.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Hongfei
  full_name: Fu, Hongfei
  id: 3AAD03D6-F248-11E8-B48F-1D18A9856A87
  last_name: Fu
- first_name: Amir
  full_name: Goharshady, Amir
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Nastaran
  full_name: Okati, Nastaran
  last_name: Okati
citation:
  ama: 'Chatterjee K, Fu H, Goharshady AK, Okati N. Computational approaches for stochastic
    shortest path on succinct MDPs. In: <i>Proceedings of the Twenty-Seventh International
    Joint Conference on Artificial Intelligence</i>. Vol 2018. IJCAI; 2018:4700-4707.
    doi:<a href="https://doi.org/10.24963/ijcai.2018/653">10.24963/ijcai.2018/653</a>'
  apa: 'Chatterjee, K., Fu, H., Goharshady, A. K., &#38; Okati, N. (2018). Computational
    approaches for stochastic shortest path on succinct MDPs. In <i>Proceedings of
    the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>
    (Vol. 2018, pp. 4700–4707). Stockholm, Sweden: IJCAI. <a href="https://doi.org/10.24963/ijcai.2018/653">https://doi.org/10.24963/ijcai.2018/653</a>'
  chicago: Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Nastaran
    Okati. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.”
    In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial
    Intelligence</i>, 2018:4700–4707. IJCAI, 2018. <a href="https://doi.org/10.24963/ijcai.2018/653">https://doi.org/10.24963/ijcai.2018/653</a>.
  ieee: K. Chatterjee, H. Fu, A. K. Goharshady, and N. Okati, “Computational approaches
    for stochastic shortest path on succinct MDPs,” in <i>Proceedings of the Twenty-Seventh
    International Joint Conference on Artificial Intelligence</i>, Stockholm, Sweden,
    2018, vol. 2018, pp. 4700–4707.
  ista: 'Chatterjee K, Fu H, Goharshady AK, Okati N. 2018. Computational approaches
    for stochastic shortest path on succinct MDPs. Proceedings of the Twenty-Seventh
    International Joint Conference on Artificial Intelligence. IJCAI: International
    Joint Conference on Artificial Intelligence vol. 2018, 4700–4707.'
  mla: Chatterjee, Krishnendu, et al. “Computational Approaches for Stochastic Shortest
    Path on Succinct MDPs.” <i>Proceedings of the Twenty-Seventh International Joint
    Conference on Artificial Intelligence</i>, vol. 2018, IJCAI, 2018, pp. 4700–07,
    doi:<a href="https://doi.org/10.24963/ijcai.2018/653">10.24963/ijcai.2018/653</a>.
  short: K. Chatterjee, H. Fu, A.K. Goharshady, N. Okati, in:, Proceedings of the
    Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI,
    2018, pp. 4700–4707.
conference:
  end_date: 2018-07-19
  location: Stockholm, Sweden
  name: 'IJCAI: International Joint Conference on Artificial Intelligence'
  start_date: 2018-07-13
date_created: 2019-02-13T13:26:27Z
date_published: 2018-07-17T00:00:00Z
date_updated: 2025-06-02T08:53:44Z
day: '17'
department:
- _id: KrCh
doi: 10.24963/ijcai.2018/653
ec_funded: 1
external_id:
  arxiv:
  - '1804.08984'
  isi:
  - '000764175404118'
intvolume: '      2018'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.08984
month: '07'
oa: 1
oa_version: Preprint
page: 4700-4707
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings of the Twenty-Seventh International Joint Conference on Artificial
  Intelligence
publication_identifier:
  isbn:
  - 978-099924112-7
  issn:
  - '10450823'
publication_status: published
publisher: IJCAI
quality_controlled: '1'
related_material:
  record:
  - id: '8934'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Computational approaches for stochastic shortest path on succinct MDPs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2018
year: '2018'
...
---
_id: '1003'
abstract:
- lang: eng
  text: Network games (NGs) are played on directed graphs and are extensively used
    in network design and analysis. Search problems for NGs include finding special
    strategy profiles such as a Nash equilibrium and a globally optimal solution.
    The networks modeled by NGs may be huge. In formal verification, abstraction has
    proven to be an extremely effective technique for reasoning about systems with
    big and even infinite state spaces. We describe an abstraction-refinement methodology
    for reasoning about NGs. Our methodology is based on an abstraction function that
    maps the state space of an NG to a much smaller state space. We search for a global
    optimum and a Nash equilibrium by reasoning on an under- and an overapproximation
    defined on top of this smaller state space. When the approximations are too coarse
    to find such profiles, we refine the abstraction function. Our experimental results
    demonstrate the efficiency of the methodology.
article_processing_charge: No
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Shibashis
  full_name: Guha, Shibashis
  last_name: Guha
- first_name: Orna
  full_name: Kupferman, Orna
  last_name: Kupferman
citation:
  ama: 'Avni G, Guha S, Kupferman O. An abstraction-refinement methodology for reasoning
    about network games. In: AAAI Press; 2017:70-76. doi:<a href="https://doi.org/10.24963/ijcai.2017/11">10.24963/ijcai.2017/11</a>'
  apa: 'Avni, G., Guha, S., &#38; Kupferman, O. (2017). An abstraction-refinement
    methodology for reasoning about network games (pp. 70–76). Presented at the IJCAI:
    International Joint Conference on Artificial Intelligence , Melbourne, Australia:
    AAAI Press. <a href="https://doi.org/10.24963/ijcai.2017/11">https://doi.org/10.24963/ijcai.2017/11</a>'
  chicago: Avni, Guy, Shibashis Guha, and Orna Kupferman. “An Abstraction-Refinement
    Methodology for Reasoning about Network Games,” 70–76. AAAI Press, 2017. <a href="https://doi.org/10.24963/ijcai.2017/11">https://doi.org/10.24963/ijcai.2017/11</a>.
  ieee: 'G. Avni, S. Guha, and O. Kupferman, “An abstraction-refinement methodology
    for reasoning about network games,” presented at the IJCAI: International Joint
    Conference on Artificial Intelligence , Melbourne, Australia, 2017, pp. 70–76.'
  ista: 'Avni G, Guha S, Kupferman O. 2017. An abstraction-refinement methodology
    for reasoning about network games. IJCAI: International Joint Conference on Artificial
    Intelligence , 70–76.'
  mla: Avni, Guy, et al. <i>An Abstraction-Refinement Methodology for Reasoning about
    Network Games</i>. AAAI Press, 2017, pp. 70–76, doi:<a href="https://doi.org/10.24963/ijcai.2017/11">10.24963/ijcai.2017/11</a>.
  short: G. Avni, S. Guha, O. Kupferman, in:, AAAI Press, 2017, pp. 70–76.
conference:
  end_date: 2017-08-25
  location: Melbourne, Australia
  name: 'IJCAI: International Joint Conference on Artificial Intelligence '
  start_date: 2017-08-19
date_created: 2018-12-11T11:49:38Z
date_published: 2017-05-30T00:00:00Z
date_updated: 2023-09-22T09:49:00Z
day: '30'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.24963/ijcai.2017/11
external_id:
  isi:
  - '000764137500011'
file:
- access_level: open_access
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:16:58Z
  date_updated: 2018-12-12T10:16:58Z
  file_id: '5249'
  file_name: IST-2017-818-v1+1_allIJCAI_CR.pdf
  file_size: 365172
  relation: main_file
file_date_updated: 2018-12-12T10:16:58Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 70 - 76
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Moderne Concurrency Paradigms
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication_identifier:
  issn:
  - '10450823'
publication_status: published
publisher: AAAI Press
publist_id: '6395'
pubrep_id: '818'
quality_controlled: '1'
related_material:
  record:
  - id: '6006'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: An abstraction-refinement methodology for reasoning about network games
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...