IDEAS home Printed from https://ideas.repec.org/a/gam/jgames/v9y2018i3p39-d153858.html
   My bibliography  Save this article

An Abstraction-Refinement Methodologyfor Reasoning about Network Games †

Author

Listed:
  • Guy Avni

    (The Institute of Science and Technology Austria (IST Austria), Am Campus 1, 3400 Klosterneuburg, Austria
    These authors contributed equally to this work.)

  • Shibashis Guha

    (Université Libre de Bruxelles, Avenue Franklin Roosevelt 50, 1050 Bruxelles, Belgium
    These authors contributed equally to this work.)

  • Orna Kupferman

    (School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel
    These authors contributed equally to this work.)

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 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.

Suggested Citation

  • Guy Avni & Shibashis Guha & Orna Kupferman, 2018. "An Abstraction-Refinement Methodologyfor Reasoning about Network Games †," Games, MDPI, vol. 9(3), pages 1-21, June.
    • Handle: RePEc:gam:jgames:v:9:y:2018:i:3:p:39-:d:153858
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2073-4336/9/3/39/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2073-4336/9/3/39/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 529-549, March.
    2. McLennan, Andrew & Tourky, Rabee, 2010. "Simple complexity from imitation games," Games and Economic Behavior, Elsevier, vol. 68(2), pages 683-688, March.
    3. Rahul Savani & Bernhard Stengel, 2015. "Game Theory Explorer: software for the applied game theorist," Computational Management Science, Springer, vol. 12(1), pages 5-33, January.
    4. Guzmán, Cristóbal & Riffo, Javiera & Telha, Claudio & Van Vyve, Mathieu, 2022. "A sequential Stackelberg game for dynamic inspection problems," European Journal of Operational Research, Elsevier, vol. 302(2), pages 727-739.
    5. Hau Chan & Michael Ceyko & Luis Ortiz, 2017. "Interdependent Defense Games with Applications to Internet Security at the Level of Autonomous Systems," Games, MDPI, vol. 8(1), pages 1-60, February.
    6. Eleonora Braggion & Nicola Gatti & Roberto Lucchetti & Tuomas Sandholm & Bernhard von Stengel, 2020. "Strong Nash equilibria and mixed strategies," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(3), pages 699-710, September.
    7. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    8. Vincent Conitzer, 2019. "The Exact Computational Complexity of Evolutionarily Stable Strategies," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 783-792, August.
    9. Guzman, Cristobal & Riffo, Javiera & Telha, Claudio & Van Vyve, Mathieu, 2021. "A Sequential Stackelberg Game for Dynamic Inspection Problems," LIDAM Discussion Papers CORE 2021036, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Theodore T. Allen & Olivia K. Hernand & Abdullah Alomair, 2020. "Optimal Off-line Experimentation for Games," Decision Analysis, INFORMS, vol. 17(4), pages 277-298, December.
    11. Vipin P. Veetil & Richard E. Wagner, 2015. "Treating Macro Theory as Systems Theory: How Might it Matter?," Advances in Austrian Economics, in: New Thinking in Austrian Political Economy, volume 19, pages 119-143, Emerald Group Publishing Limited.
    12. Jugal Garg & Ruta Mehta & Vijay V. Vaziranic, 2018. "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 996-1024, August.
    13. Jiang, Albert Xin & Leyton-Brown, Kevin & Bhat, Navin A.R., 2011. "Action-Graph Games," Games and Economic Behavior, Elsevier, vol. 71(1), pages 141-173, January.
    14. Martin Bichler & Nils Kohring & Stefan Heidekrüger, 2023. "Learning Equilibria in Asymmetric Auction Games," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 523-542, May.
    15. Amir Ali Ahmadi & Jeffrey Zhang, 2021. "Semidefinite Programming and Nash Equilibria in Bimatrix Games," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 607-628, May.
    16. Rota Bulò, Samuel & Bomze, Immanuel M., 2011. "Infection and immunization: A new class of evolutionary game dynamics," Games and Economic Behavior, Elsevier, vol. 71(1), pages 193-211, January.
    17. Nicola, Gatti & Mario, Gilli & Fabio, Panozzo, 2016. "Further results on verification problems in extensive-form games," Working Papers 347, University of Milano-Bicocca, Department of Economics, revised 15 Jul 2016.
    18. Clempner, Julio B. & Poznyak, Alexander S., 2015. "Computing the strong Nash equilibrium for Markov chains games," Applied Mathematics and Computation, Elsevier, vol. 265(C), pages 911-927.
    19. Fabrice Talla Nobibon & Laurens Cherchye & Yves Crama & Thomas Demuynck & Bram De Rock & Frits C. R. Spieksma, 2016. "Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms," Operations Research, INFORMS, vol. 64(6), pages 1197-1216, December.
    20. Matthias Köppe & Christopher Thomas Ryan & Maurice Queyranne, 2011. "Rational Generating Functions and Integer Programming Games," Operations Research, INFORMS, vol. 59(6), pages 1445-1460, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jgames:v:9:y:2018:i:3:p:39-:d:153858. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.