Synchronisation Games on Hypergraphs Article Swipe

PDF

YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.24963/ijcai.2017/57

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.

Related Topics

Mathematical Analysis

Concepts

Nash equilibrium Hypergraph Separable space Polynomial Mathematical economics Game theory Coordination game Time complexity Mathematics Best response Computer science Combinatorics Mathematical analysis

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.24963/ijcai.2017/57
PDF: https://www.ijcai.org/proceedings/2017/0057.pdf
OA Status: gold
Cited By: 13
References: 42
Related Works: 10
OpenAlex ID: https://openalex.org/W2732465864

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2732465864

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.24963/ijcai.2017/57

Digital Object Identifier
Title: Synchronisation Games on Hypergraphs

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2017

Year of publication
Publication date: 2017-07-28

Full publication date if available
Authors: Sunil Simon, Dominik Wojtczak

List of authors in order
Landing page: https://doi.org/10.24963/ijcai.2017/57

Publisher landing page
PDF URL: https://www.ijcai.org/proceedings/2017/0057.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: gold

Open access status per OpenAlex
OA URL: https://www.ijcai.org/proceedings/2017/0057.pdf

Direct OA link when available
Concepts: Nash equilibrium, Hypergraph, Separable space, Polynomial, Mathematical economics, Game theory, Coordination game, Time complexity, Mathematics, Best response, Computer science, Combinatorics, Mathematical analysis

Top concepts (fields/topics) attached by OpenAlex
Cited by: 13

Total citation count in OpenAlex
Citations by year (recent): 2024: 1, 2023: 1, 2021: 5, 2020: 3, 2019: 1

Per-year citation counts (last 5 years)
References (count): 42

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2732465864
doi	https://doi.org/10.24963/ijcai.2017/57
ids.doi	https://doi.org/10.24963/ijcai.2017/57
ids.mag	2732465864
ids.openalex	https://openalex.org/W2732465864
fwci	1.57845171
type	article
title	Synchronisation Games on Hypergraphs
biblio.issue
biblio.volume
biblio.last_page	408
biblio.first_page	402
topics[0].id	https://openalex.org/T11031
topics[0].field.id	https://openalex.org/fields/18
topics[0].field.display_name	Decision Sciences
topics[0].score	0.9995999932289124
topics[0].domain.id	https://openalex.org/domains/2
topics[0].domain.display_name	Social Sciences
topics[0].subfield.id	https://openalex.org/subfields/1803
topics[0].subfield.display_name	Management Science and Operations Research
topics[0].display_name	Game Theory and Applications
topics[1].id	https://openalex.org/T10991
topics[1].field.id	https://openalex.org/fields/20
topics[1].field.display_name	Economics, Econometrics and Finance
topics[1].score	0.9919000267982483
topics[1].domain.id	https://openalex.org/domains/2
topics[1].domain.display_name	Social Sciences
topics[1].subfield.id	https://openalex.org/subfields/2002
topics[1].subfield.display_name	Economics and Econometrics
topics[1].display_name	Game Theory and Voting Systems
topics[2].id	https://openalex.org/T12137
topics[2].field.id	https://openalex.org/fields/20
topics[2].field.display_name	Economics, Econometrics and Finance
topics[2].score	0.9889000058174133
topics[2].domain.id	https://openalex.org/domains/2
topics[2].domain.display_name	Social Sciences
topics[2].subfield.id	https://openalex.org/subfields/2002
topics[2].subfield.display_name	Economics and Econometrics
topics[2].display_name	Economic theories and models
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C46814582
concepts[0].level	2
concepts[0].score	0.8196091651916504
concepts[0].wikidata	https://www.wikidata.org/wiki/Q23389
concepts[0].display_name	Nash equilibrium
concepts[1].id	https://openalex.org/C2781221856
concepts[1].level	2
concepts[1].score	0.7986075282096863
concepts[1].wikidata	https://www.wikidata.org/wiki/Q840247
concepts[1].display_name	Hypergraph
concepts[2].id	https://openalex.org/C70710897
concepts[2].level	2
concepts[2].score	0.7431354522705078
concepts[2].wikidata	https://www.wikidata.org/wiki/Q680081
concepts[2].display_name	Separable space
concepts[3].id	https://openalex.org/C90119067
concepts[3].level	2
concepts[3].score	0.5366681814193726
concepts[3].wikidata	https://www.wikidata.org/wiki/Q43260
concepts[3].display_name	Polynomial
concepts[4].id	https://openalex.org/C144237770
concepts[4].level	1
concepts[4].score	0.4821750521659851
concepts[4].wikidata	https://www.wikidata.org/wiki/Q747534
concepts[4].display_name	Mathematical economics
concepts[5].id	https://openalex.org/C177142836
concepts[5].level	2
concepts[5].score	0.4690435528755188
concepts[5].wikidata	https://www.wikidata.org/wiki/Q44455
concepts[5].display_name	Game theory
concepts[6].id	https://openalex.org/C107257861
concepts[6].level	2
concepts[6].score	0.467507928609848
concepts[6].wikidata	https://www.wikidata.org/wiki/Q656316
concepts[6].display_name	Coordination game
concepts[7].id	https://openalex.org/C311688
concepts[7].level	2
concepts[7].score	0.45213738083839417
concepts[7].wikidata	https://www.wikidata.org/wiki/Q2393193
concepts[7].display_name	Time complexity
concepts[8].id	https://openalex.org/C33923547
concepts[8].level	0
concepts[8].score	0.44913449883461
concepts[8].wikidata	https://www.wikidata.org/wiki/Q395
concepts[8].display_name	Mathematics
concepts[9].id	https://openalex.org/C32407928
concepts[9].level	3
concepts[9].score	0.44533589482307434
concepts[9].wikidata	https://www.wikidata.org/wiki/Q2733833
concepts[9].display_name	Best response
concepts[10].id	https://openalex.org/C41008148
concepts[10].level	0
concepts[10].score	0.4274214506149292
concepts[10].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[10].display_name	Computer science
concepts[11].id	https://openalex.org/C114614502
concepts[11].level	1
concepts[11].score	0.3116530776023865
concepts[11].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[11].display_name	Combinatorics
concepts[12].id	https://openalex.org/C134306372
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[12].display_name	Mathematical analysis
keywords[0].id	https://openalex.org/keywords/nash-equilibrium
keywords[0].score	0.8196091651916504
keywords[0].display_name	Nash equilibrium
keywords[1].id	https://openalex.org/keywords/hypergraph
keywords[1].score	0.7986075282096863
keywords[1].display_name	Hypergraph
keywords[2].id	https://openalex.org/keywords/separable-space
keywords[2].score	0.7431354522705078
keywords[2].display_name	Separable space
keywords[3].id	https://openalex.org/keywords/polynomial
keywords[3].score	0.5366681814193726
keywords[3].display_name	Polynomial
keywords[4].id	https://openalex.org/keywords/mathematical-economics
keywords[4].score	0.4821750521659851
keywords[4].display_name	Mathematical economics
keywords[5].id	https://openalex.org/keywords/game-theory
keywords[5].score	0.4690435528755188
keywords[5].display_name	Game theory
keywords[6].id	https://openalex.org/keywords/coordination-game
keywords[6].score	0.467507928609848
keywords[6].display_name	Coordination game
keywords[7].id	https://openalex.org/keywords/time-complexity
keywords[7].score	0.45213738083839417
keywords[7].display_name	Time complexity
keywords[8].id	https://openalex.org/keywords/mathematics
keywords[8].score	0.44913449883461
keywords[8].display_name	Mathematics
keywords[9].id	https://openalex.org/keywords/best-response
keywords[9].score	0.44533589482307434
keywords[9].display_name	Best response
keywords[10].id	https://openalex.org/keywords/computer-science
keywords[10].score	0.4274214506149292
keywords[10].display_name	Computer science
keywords[11].id	https://openalex.org/keywords/combinatorics
keywords[11].score	0.3116530776023865
keywords[11].display_name	Combinatorics
language	en
locations[0].id	doi:10.24963/ijcai.2017/57
locations[0].is_oa	True
locations[0].source
locations[0].license
locations[0].pdf_url	https://www.ijcai.org/proceedings/2017/0057.pdf
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
locations[0].landing_page_url	https://doi.org/10.24963/ijcai.2017/57
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5018621353
authorships[0].author.orcid	https://orcid.org/0000-0002-7489-7477
authorships[0].author.display_name	Sunil Simon
authorships[0].countries	IN
authorships[0].affiliations[0].institution_ids	https://openalex.org/I94234084
authorships[0].affiliations[0].raw_affiliation_string	IIT Kanpur Kanpur, India
authorships[0].institutions[0].id	https://openalex.org/I94234084
authorships[0].institutions[0].ror	https://ror.org/05pjsgx75
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I94234084
authorships[0].institutions[0].country_code	IN
authorships[0].institutions[0].display_name	Indian Institute of Technology Kanpur
authorships[0].author_position	first
authorships[0].raw_author_name	Sunil Simon
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	IIT Kanpur Kanpur, India
authorships[1].author.id	https://openalex.org/A5001234060
authorships[1].author.orcid	https://orcid.org/0000-0001-5560-0546
authorships[1].author.display_name	Dominik Wojtczak
authorships[1].countries	GB
authorships[1].affiliations[0].institution_ids	https://openalex.org/I146655781
authorships[1].affiliations[0].raw_affiliation_string	University of Liverpool Liverpool, U.K.
authorships[1].institutions[0].id	https://openalex.org/I146655781
authorships[1].institutions[0].ror	https://ror.org/04xs57h96
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I146655781
authorships[1].institutions[0].country_code	GB
authorships[1].institutions[0].display_name	University of Liverpool
authorships[1].author_position	last
authorships[1].raw_author_name	Dominik Wojtczak
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	University of Liverpool Liverpool, U.K.
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://www.ijcai.org/proceedings/2017/0057.pdf
open_access.oa_status	gold
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Synchronisation Games on Hypergraphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T11031
primary_topic.field.id	https://openalex.org/fields/18
primary_topic.field.display_name	Decision Sciences
primary_topic.score	0.9995999932289124
primary_topic.domain.id	https://openalex.org/domains/2
primary_topic.domain.display_name	Social Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1803
primary_topic.subfield.display_name	Management Science and Operations Research
primary_topic.display_name	Game Theory and Applications
related_works	https://openalex.org/W2236801283, https://openalex.org/W2728657731, https://openalex.org/W1853631319, https://openalex.org/W2092374696, https://openalex.org/W2481143976, https://openalex.org/W2803932348, https://openalex.org/W3207342620, https://openalex.org/W2607684552, https://openalex.org/W4280496625, https://openalex.org/W3125633875
cited_by_count	13
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2023
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2021
counts_by_year[2].cited_by_count	5
counts_by_year[3].year	2020
counts_by_year[3].cited_by_count	3
counts_by_year[4].year	2019
counts_by_year[4].cited_by_count	1
counts_by_year[5].year	2018
counts_by_year[5].cited_by_count	1
counts_by_year[6].year	2017
counts_by_year[6].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.24963/ijcai.2017/57
best_oa_location.is_oa	True
best_oa_location.source
best_oa_location.license
best_oa_location.pdf_url	https://www.ijcai.org/proceedings/2017/0057.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	proceedings-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
best_oa_location.landing_page_url	https://doi.org/10.24963/ijcai.2017/57
primary_location.id	doi:10.24963/ijcai.2017/57
primary_location.is_oa	True
primary_location.source
primary_location.license
primary_location.pdf_url	https://www.ijcai.org/proceedings/2017/0057.pdf
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
primary_location.landing_page_url	https://doi.org/10.24963/ijcai.2017/57
publication_date	2017-07-28
publication_year	2017
referenced_works	https://openalex.org/W2493238591, https://openalex.org/W4238729853, https://openalex.org/W2244060074, https://openalex.org/W1484192075, https://openalex.org/W2062459871, https://openalex.org/W2950323636, https://openalex.org/W2161122111, https://openalex.org/W2046522142, https://openalex.org/W2005854342, https://openalex.org/W1997388358, https://openalex.org/W4252350499, https://openalex.org/W1598698067, https://openalex.org/W4291434518, https://openalex.org/W2587056309, https://openalex.org/W4241584151, https://openalex.org/W2148829783, https://openalex.org/W2030234114, https://openalex.org/W2293622451, https://openalex.org/W2104498537, https://openalex.org/W2204649750, https://openalex.org/W2561285773, https://openalex.org/W2038992031, https://openalex.org/W1648820898, https://openalex.org/W175230508, https://openalex.org/W3152027851, https://openalex.org/W2029448190, https://openalex.org/W906410999, https://openalex.org/W1997147068, https://openalex.org/W1987961481, https://openalex.org/W2134660637, https://openalex.org/W1999118892, https://openalex.org/W2147732297, https://openalex.org/W2403232853, https://openalex.org/W2160135758, https://openalex.org/W3118247429, https://openalex.org/W3102544512, https://openalex.org/W1988613094, https://openalex.org/W2033325972, https://openalex.org/W1523060149, https://openalex.org/W2103981148, https://openalex.org/W4296288933, https://openalex.org/W2558224039
referenced_works_count	42
abstract_inverted_index.a	2, 34, 53, 73, 88
abstract_inverted_index.We	0, 28
abstract_inverted_index.be	33, 59, 79
abstract_inverted_index.by	11, 26
abstract_inverted_index.in	61, 65, 81
abstract_inverted_index.of	23, 37
abstract_inverted_index.on	6
abstract_inverted_index.or	16
abstract_inverted_index.to	14, 32, 43
abstract_inverted_index.we	70
abstract_inverted_index.and	47, 77
abstract_inverted_index.can	58, 78
abstract_inverted_index.the	44, 66, 85
abstract_inverted_index.try	13
abstract_inverted_index.Nash	55
abstract_inverted_index.game	4, 86
abstract_inverted_index.have	52
abstract_inverted_index.pure	54, 67
abstract_inverted_index.show	29, 71
abstract_inverted_index.such	49
abstract_inverted_index.that	48, 72
abstract_inverted_index.this	30
abstract_inverted_index.time	83
abstract_inverted_index.when	84
abstract_inverted_index.games	42, 50
abstract_inverted_index.model	5, 31
abstract_inverted_index.study	1
abstract_inverted_index.their	18
abstract_inverted_index.time.	63
abstract_inverted_index.where	8
abstract_inverted_index.which	57
abstract_inverted_index.always	51
abstract_inverted_index.exists	76
abstract_inverted_index.groups	22
abstract_inverted_index.nodes,	12
abstract_inverted_index.strict	35
abstract_inverted_index.strong	74
abstract_inverted_index.within	20
abstract_inverted_index.acyclic	90
abstract_inverted_index.certain	21, 89
abstract_inverted_index.choices	19
abstract_inverted_index.hedonic	41
abstract_inverted_index.setting	46
abstract_inverted_index.computed	60, 80
abstract_inverted_index.modelled	10, 25
abstract_inverted_index.players,	9, 24
abstract_inverted_index.setting,	69
abstract_inverted_index.Moreover,	64
abstract_inverted_index.possesses	87
abstract_inverted_index.separable	40
abstract_inverted_index.strategic	3
abstract_inverted_index.symmetric	38
abstract_inverted_index.additively	39
abstract_inverted_index.coordinate	15
abstract_inverted_index.hypergraph	45
abstract_inverted_index.polynomial	82
abstract_inverted_index.structure.	91
abstract_inverted_index.equilibrium	75
abstract_inverted_index.hyperedges.	27
abstract_inverted_index.hypergraphs	7
abstract_inverted_index.coordination	68
abstract_inverted_index.equilibrium,	56
abstract_inverted_index.generalisation	36
abstract_inverted_index.anti-coordinate	17
abstract_inverted_index.pseudo-polynomial	62
cited_by_percentile_year.max	98
cited_by_percentile_year.min	89
countries_distinct_count	2
institutions_distinct_count	2
citation_normalized_percentile.value	0.84584139
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False