Simon, Sunil and Wojtczak, Dominik 
ORCID: 0000-0001-5560-0546
(2017)
Constrained Pure Nash Equilibria in Polymatrix Games.
.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
SimonWojtczak.pdf - Author Accepted Manuscript Download (268kB) |
Abstract
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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | Extended version of a paper accepted to AAAI17 |
| Uncontrolled Keywords: | cs.GT, cs.GT |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 03 Jul 2017 13:48 |
| Last Modified: | 19 Jan 2023 07:02 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3008197 |
Share
Share
