---
_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. <i>Games</i>. 2018;9(3). doi:<a href="https://doi.org/10.3390/g9030039">10.3390/g9030039</a>
  apa: Avni, G., Guha, S., &#38; Kupferman, O. (2018). An abstraction-refinement methodology
    for reasoning about network games. <i>Games</i>. MDPI AG. <a href="https://doi.org/10.3390/g9030039">https://doi.org/10.3390/g9030039</a>
  chicago: Avni, Guy, Shibashis Guha, and Orna Kupferman. “An Abstraction-Refinement
    Methodology for Reasoning about Network Games.” <i>Games</i>. MDPI AG, 2018. <a
    href="https://doi.org/10.3390/g9030039">https://doi.org/10.3390/g9030039</a>.
  ieee: G. Avni, S. Guha, and O. Kupferman, “An abstraction-refinement methodology
    for reasoning about network games,” <i>Games</i>, 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.” <i>Games</i>, vol. 9, no. 3, 39, MDPI AG, 2018, doi:<a href="https://doi.org/10.3390/g9030039">10.3390/g9030039</a>.
  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'
...