--- _id: '6006' 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 over-approximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. We extend the abstraction-refinement methodology to labeled networks, where the objectives of the players are regular languages. Our experimental results demonstrate the effectiveness of the methodology. ' article_number: '39' 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. Games. 2018;9(3). doi:10.3390/g9030039 apa: Avni, G., Guha, S., & Kupferman, O. (2018). An abstraction-refinement methodology for reasoning about network games. Games. MDPI AG. https://doi.org/10.3390/g9030039 chicago: Avni, Guy, Shibashis Guha, and Orna Kupferman. “An Abstraction-Refinement Methodology for Reasoning about Network Games.” Games. MDPI AG, 2018. https://doi.org/10.3390/g9030039. ieee: G. Avni, S. Guha, and O. Kupferman, “An abstraction-refinement methodology for reasoning about network games,” Games, vol. 9, no. 3. MDPI AG, 2018. ista: Avni G, Guha S, Kupferman O. 2018. An abstraction-refinement methodology for reasoning about network games. Games. 9(3), 39. mla: Avni, Guy, et al. “An Abstraction-Refinement Methodology for Reasoning about Network Games.” Games, vol. 9, no. 3, 39, MDPI AG, 2018, doi:10.3390/g9030039. short: G. Avni, S. Guha, O. Kupferman, Games 9 (2018). date_created: 2019-02-14T14:17:54Z date_published: 2018-09-01T00:00:00Z date_updated: 2023-09-22T09:48:59Z day: '01' ddc: - '004' department: - _id: ToHe doi: 10.3390/g9030039 file: - access_level: open_access checksum: 749d65ca4ce74256a029d9644a1b1cb0 content_type: application/pdf creator: kschuh date_created: 2019-02-14T14:20:31Z date_updated: 2020-07-14T12:47:16Z file_id: '6008' file_name: 2018_MDPI_Avni.pdf file_size: 505155 relation: main_file file_date_updated: 2020-07-14T12:47:16Z has_accepted_license: '1' intvolume: ' 9' issue: '3' language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: 264B3912-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02369 name: Formal Methods meets Algorithmic Game Theory - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication: Games publication_identifier: issn: - 2073-4336 publication_status: published publisher: MDPI AG quality_controlled: '1' related_material: record: - id: '1003' relation: earlier_version status: public scopus_import: 1 status: public title: An abstraction-refinement methodology for reasoning about network 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: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9 year: '2018' ...