The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form

Ahmad Nahhas () and H. W. Corley ()
Additional contact information
Ahmad Nahhas: Center on Stochastic Modeling, Optimization, and Statistics (COSMOS), UT Arlington College of Engineering, The University of Texas at Arlington, Arlington, TX 76019, USA
H. W. Corley: Center on Stochastic Modeling, Optimization, and Statistics (COSMOS), UT Arlington College of Engineering, The University of Texas at Arlington, Arlington, TX 76019, USA

International Game Theory Review (IGTR), 2018, vol. 20, issue 04, 1-13

Abstract: The mixed Berge equilibrium (MBE) is an extension of the Berge equilibrium (BE) to mixed strategies. The MBE models mutually support in a k-person noncooperative game in normal form. An MBE is a mixed-strategy profile for the k players in which every k − 1 players have mixed strategies that maximize the expected payoff for the remaining player’s equilibrium strategy. In this paper, we study the computational complexity of determining whether an MBE exists in a k-person normal-form game. For a two-person game, an MBE always exists and the problem of finding an MBE is PPAD-complete. In contrast to the mixed Nash equilibrium, the MBE is not guaranteed to exist in games with three or more players. Here we prove, when k ≥ 3, that the decision problem of asking whether an MBE exists for a k-person normal-form game is NP-complete. Therefore, in the worst-case scenario there does not exist a polynomial algorithm that finds an MBE unless P=NP.

Keywords: Mixed Berge equilibrium; computational complexity; NP-complete (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021919891850010X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:20:y:2018:i:04:n:s021919891850010x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021919891850010X

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().