Constrained Pure Nash Equilibria in Polymatrix Games



Simon, Sunil and Wojtczak, Dominik ORCID: 0000-0001-5560-0546
(2017) Constrained Pure Nash Equilibria in Polymatrix Games. In: EUMAS 2017.

[thumbnail of SimonWojtczak.pdf] Text
SimonWojtczak.pdf - Author Accepted Manuscript

Download (303kB)

Abstract

<jats:p> We study the problem of checking for the existence of constrained pure Nash equilibria in a subclass of polymatrix games defined on weighted directed graphs. The payoff of a player is defined as the sum of nonnegative rational weights on incoming edges from players who picked the same strategy augmented by a fixed integer bonus for picking a given strategy. These games capture the idea of coordination within a local neighbourhood in the absence of globally common strategies. We study the decision problem of checking whether a given set of strategy choices for a subset of the players is consistent with some pure Nash equilibrium or, alternatively, with all pure Nash equilibria. We identify the most natural tractable cases and show NP or coNP-completness of these problems already for unweighted DAGs. </jats:p>

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: 3801 Applied Economics, 3803 Economic Theory, 38 Economics, 4901 Applied Mathematics, 49 Mathematical Sciences
Depositing User: Symplectic Admin
Date Deposited: 19 Jun 2018 11:50
Last Modified: 11 Dec 2024 11:53
DOI: 10.1609/aaai.v31i1.10599
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3022727