Synchronisation Games on Hypergraphs



Simon, Sunil and Wojtczak, Dominik
(2017) Synchronisation Games on Hypergraphs. In: Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017-8-19 - 2017-8-26.

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

Download (236kB)

Abstract

<jats:p>We study a strategic game model on hypergraphs where players, modelled by nodes, try to coordinate or anti-coordinate their choices within certain groups of players, modelled by hyperedges. We show this model to be a strict generalisation of symmetric additively separable hedonic games to the hypergraph setting and that such games always have a pure Nash equilibrium, which can be computed in pseudo-polynomial time. Moreover, in the pure coordination setting, we show that a strong equilibrium exists and can be computed in polynomial time when the game possesses a certain acyclic structure.</jats:p>

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: 3801 Applied Economics, 3803 Economic Theory, 38 Economics, 4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences
Depositing User: Symplectic Admin
Date Deposited: 31 May 2017 09:25
Last Modified: 20 Jun 2024 20:24
DOI: 10.24963/ijcai.2017/57
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007711