[{"publication_identifier":{"issn":["10450823"],"isbn":["978-099924112-7"]},"oa":1,"type":"conference","date_published":"2018-07-17T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1804.08984","open_access":"1"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","related_material":{"record":[{"id":"8934","relation":"dissertation_contains","status":"public"}]},"project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"oa_version":"Preprint","month":"07","publication":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence","conference":{"end_date":"2018-07-19","location":"Stockholm, Sweden","name":"IJCAI: International Joint Conference on Artificial Intelligence","start_date":"2018-07-13"},"language":[{"iso":"eng"}],"day":"17","arxiv":1,"doi":"10.24963/ijcai.2018/653","abstract":[{"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.","lang":"eng"}],"year":"2018","citation":{"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.","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>.","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>","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."},"date_updated":"2025-06-02T08:53:44Z","external_id":{"arxiv":["1804.08984"],"isi":["000764175404118"]},"isi":1,"volume":2018,"date_created":"2019-02-13T13:26:27Z","article_processing_charge":"No","department":[{"_id":"KrCh"}],"publication_status":"published","intvolume":"      2018","title":"Computational approaches for stochastic shortest path on succinct MDPs","scopus_import":"1","_id":"5977","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Fu","first_name":"Hongfei","full_name":"Fu, Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir","last_name":"Goharshady","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir"},{"first_name":"Nastaran","last_name":"Okati","full_name":"Okati, Nastaran"}],"publisher":"IJCAI","quality_controlled":"1","ec_funded":1,"page":"4700-4707"},{"has_accepted_license":"1","month":"05","project":[{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23"},{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"oa_version":"Submitted Version","language":[{"iso":"eng"}],"conference":{"name":"IJCAI: International Joint Conference on Artificial Intelligence ","start_date":"2017-08-19","location":"Melbourne, Australia","end_date":"2017-08-25"},"type":"conference","date_published":"2017-05-30T00:00:00Z","publist_id":"6395","oa":1,"publication_identifier":{"issn":["10450823"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","related_material":{"record":[{"status":"public","id":"6006","relation":"later_version"}]},"file":[{"creator":"system","file_id":"5249","relation":"main_file","access_level":"open_access","file_name":"IST-2017-818-v1+1_allIJCAI_CR.pdf","content_type":"application/pdf","date_updated":"2018-12-12T10:16:58Z","file_size":365172,"date_created":"2018-12-12T10:16:58Z"}],"author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","last_name":"Avni","first_name":"Guy","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287"},{"full_name":"Guha, Shibashis","last_name":"Guha","first_name":"Shibashis"},{"full_name":"Kupferman, Orna","last_name":"Kupferman","first_name":"Orna"}],"scopus_import":"1","_id":"1003","pubrep_id":"818","title":"An abstraction-refinement methodology for reasoning about network games","article_processing_charge":"No","date_created":"2018-12-11T11:49:38Z","department":[{"_id":"ToHe"}],"publication_status":"published","file_date_updated":"2018-12-12T10:16:58Z","quality_controlled":"1","page":"70 - 76","publisher":"AAAI Press","external_id":{"isi":["000764137500011"]},"isi":1,"year":"2017","citation":{"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.","short":"G. Avni, S. Guha, O. Kupferman, in:, AAAI Press, 2017, pp. 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>.","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.","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>.","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>","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>"},"date_updated":"2023-09-22T09:49:00Z","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."}],"day":"30","doi":"10.24963/ijcai.2017/11","ddc":["004"]}]