Earlier Version

An abstraction-refinement methodology for reasoning about network games

G. Avni, S. Guha, O. Kupferman, in:, AAAI Press, 2017, pp. 70–76.

Download
OA IST-2017-818-v1+1_allIJCAI_CR.pdf 365.17 KB

Conference Paper | Published | English

Scopus indexed
Author
Avni, GuyIST Austria; Guha, Shibashis; Kupferman, Orna
Department
Abstract
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.
Publishing Year
Date Published
2017-05-30
Page
70 - 76
Conference
IJCAI: International Joint Conference on Artificial Intelligence
Conference Location
Melbourne, Australia
Conference Date
2017-08-19 – 2017-08-25
ISSN
IST-REx-ID

Cite this

Avni G, Guha S, Kupferman O. An abstraction-refinement methodology for reasoning about network games. In: AAAI Press; 2017:70-76. doi:10.24963/ijcai.2017/11
Avni, G., Guha, S., & 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. https://doi.org/10.24963/ijcai.2017/11
Avni, Guy, Shibashis Guha, and Orna Kupferman. “An Abstraction-Refinement Methodology for Reasoning about Network Games,” 70–76. AAAI Press, 2017. https://doi.org/10.24963/ijcai.2017/11.
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.
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.
Avni, Guy, et al. An Abstraction-Refinement Methodology for Reasoning about Network Games. AAAI Press, 2017, pp. 70–76, doi:10.24963/ijcai.2017/11.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar