We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form.
- Authors
Nahhas, Ahmad; Corley, H. W.
- 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.
- Subjects
MATHEMATICAL complex analysis; NONCOOPERATIVE games (Mathematics); NORMAL forms (Mathematics); NASH equilibrium; POLYNOMIALS
- Publication
International Game Theory Review, 2018, Vol 20, Issue 4, pN.PAG
- ISSN
0219-1989
- Publication type
Article
- DOI
10.1142/S021919891850010X