The Complexity of Computational Problems About Nash Equilibria in Symmetric Win-Lose Games
- PDF / 1,000,731 Bytes
- 84 Pages / 439.37 x 666.142 pts Page_size
- 54 Downloads / 182 Views
(0123456789().,-volV)(0123456789().,-volV)
The Complexity of Computational Problems About Nash Equilibria in Symmetric Win-Lose Games Vittorio Bilo`1
•
Marios Mavronicolas2
Received: 3 September 2019 / Accepted: 24 August 2020 Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We revisit the complexity of deciding, given a bimatrix game, whether it has a Nash equilibrium with certain natural properties; such decision problems were early known to be N P-hard (Gilboa and Zemel in Games Econ Behav 1(1):80–93, 1989). We show that N P-hardness still holds under two significant restrictions in simultaneity: the game is win-lose (that is, all utilities are 0 or 1) and symmetric. To address the former restriction, we design win-lose gadgets and a win-lose reduction; to accomodate the latter restriction, we employ and analyze the classical GHR symmetrization (Griesmer et al. in On symmetric bimatrix games, IBM research paper RC-959, IBM Corp., T. J. Watson Research Center, 1963) in the win-lose setting. Thus, symmetric win-lose bimatrix games are as complex as general bimatrix games with respect to such decision problems. As a byproduct of our techniques, we derive hardness results for search, counting and parity problems about Nash equilibria in symmetric win-lose bimatrix games. Keywords Bimatrix games Win-lose games Symmetric games Nash equilibria Computational complexity
& Vittorio Bilo` [email protected] Marios Mavronicolas [email protected] 1
Department of Mathematics and Physics ‘‘Ennio De Giorgi’’, University of Salento, 73100 Lecce, Italy
2
Department of Computer Science, University of Cyprus, 1678 Nicosia, Cyprus
123
Algorithmica
1 Introduction 1.1 Framework and Motivation 1.1.1 Nash Equilibria, Win-Lose Bimatrix Games and Symmetric Games Among the most fundamental computational problems in Algorithmic Game Theory are those concerning the Nash equilibria [29, 30] of a game, where no player could unilaterally deviate to increase her expected utility. Such problems have been studied extensively [1, 4, 7, 9–14, 20, 25, 26] for 2-player games with rational utilities given by a bimatrix. There are two prominent special cases of such general bimatrix games: win-lose and symmetric. • Utilities are taken from f0; 1g in win-lose bimatrix games, originally put forward in [12]. • In a symmetric game [29, 30], players have identical strategy sets and the utility of a player is determined by the multiset of strategies chosen by her and the other players, with no discrimination. By a classical result of Nash, every symmetric game has a symmetric Nash equilibrium, where all players are playing the same mixed strategy [29, 30]. A symmetrization transforms a given bimatrix game into a symmetric one; the target is that a Nash equilibrium for the original bimatrix game can be reconstructed efficiently from a (symmetric) Nash equilibrium for the symmetric bimatrix game (cf. [8, 17, 21]). 1.1.2 The Search Problem The fundamental theorem of Nash [29, 30] that a Nash equilibr
Data Loading...
