An abstraction-refinement methodology for reasoning about network games Conference Paper

Author(s): Avni, Guy; Guha, Shibashis; Kupferman, Orna
Title: An abstraction-refinement methodology for reasoning about network games
Affiliation IST Austria
Abstract: {\em 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, {\em 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 over-approximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we {\em refine} the abstraction function. Our experimental results demonstrate the efficiency of the methodology.
Keywords: Network games; abstraction-refinement; Nash equilibrium
Conference Title: IJCAI: International Joint Conference on Artificial Intelligence
Conference Dates: August 19 - 25, 2017
Conference Location: Melbourne, Australia
ISBN: 978-1-57735-770-4
Publisher: AAAI Press  
Date Published: 2017-05-30
Sponsor: European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013, ERC grant no 278410) and the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award).
Open access: yes (repository)
IST Austria Authors
  1. Guy Avni
    6 Avni