Generalizing Better Response Paths and Weakly Acyclic Games Article Swipe

PDF

Bora Yongacoglu , Gürdal Arslan , Lacra Pavel , Serdar Yüksel ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2403.18086

Weakly acyclic games generalize potential games and are fundamental to the study of game theoretic control. In this paper, we present a generalization of weakly acyclic games, and we observe its importance in multi-agent learning when agents employ experimental strategy updates in periods where they fail to best respond. While weak acyclicity is defined in terms of path connectivity properties of a game's better response graph, our generalization is defined using a generalized better response graph. We provide sufficient conditions for this notion of generalized weak acyclicity in both two-player games and $n$-player games. To demonstrate that our generalization is not trivial, we provide examples of games admitting a pure Nash equilibrium that are not generalized weakly acyclic. The generalization presented in this work is closely related to the recent theory of satisficing paths, and the counterexamples presented here constitute the first negative results in that theory.

Related Topics

Concepts

Combinatorics Mathematics Mathematical economics Best response Computer science Game theory

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2403.18086
PDF: https://arxiv.org/pdf/2403.18086
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4393299756

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2403.18086

Digital Object Identifier
Title: Generalizing Better Response Paths and Weakly Acyclic Games

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-03-26

Full publication date if available
Authors: Bora Yongacoglu, Gürdal Arslan, Lacra Pavel, Serdar Yüksel

List of authors in order
Landing page: https://arxiv.org/abs/2403.18086

Publisher landing page
PDF URL: https://arxiv.org/pdf/2403.18086

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2403.18086

Direct OA link when available
Concepts: Combinatorics, Mathematics, Mathematical economics, Best response, Computer science, Game theory

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

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4393299756
doi	https://doi.org/10.48550/arxiv.2403.18086
ids.doi	https://doi.org/10.48550/arxiv.2403.18086
ids.openalex	https://openalex.org/W4393299756
fwci
type	preprint
title	Generalizing Better Response Paths and Weakly Acyclic Games
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11798
topics[0].field.id	https://openalex.org/fields/18
topics[0].field.display_name	Decision Sciences
topics[0].score	0.8902999758720398
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	Optimal Experimental Design Methods
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.8521000146865845
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/T11031
topics[2].field.id	https://openalex.org/fields/18
topics[2].field.display_name	Decision Sciences
topics[2].score	0.7727000117301941
topics[2].domain.id	https://openalex.org/domains/2
topics[2].domain.display_name	Social Sciences
topics[2].subfield.id	https://openalex.org/subfields/1803
topics[2].subfield.display_name	Management Science and Operations Research
topics[2].display_name	Game Theory and Applications
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C114614502
concepts[0].level	1
concepts[0].score	0.4679628312587738
concepts[0].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[0].display_name	Combinatorics
concepts[1].id	https://openalex.org/C33923547
concepts[1].level	0
concepts[1].score	0.45790764689445496
concepts[1].wikidata	https://www.wikidata.org/wiki/Q395
concepts[1].display_name	Mathematics
concepts[2].id	https://openalex.org/C144237770
concepts[2].level	1
concepts[2].score	0.4409255385398865
concepts[2].wikidata	https://www.wikidata.org/wiki/Q747534
concepts[2].display_name	Mathematical economics
concepts[3].id	https://openalex.org/C32407928
concepts[3].level	3
concepts[3].score	0.41943058371543884
concepts[3].wikidata	https://www.wikidata.org/wiki/Q2733833
concepts[3].display_name	Best response
concepts[4].id	https://openalex.org/C41008148
concepts[4].level	0
concepts[4].score	0.3724024295806885
concepts[4].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[4].display_name	Computer science
concepts[5].id	https://openalex.org/C177142836
concepts[5].level	2
concepts[5].score	0.2804858684539795
concepts[5].wikidata	https://www.wikidata.org/wiki/Q44455
concepts[5].display_name	Game theory
keywords[0].id	https://openalex.org/keywords/combinatorics
keywords[0].score	0.4679628312587738
keywords[0].display_name	Combinatorics
keywords[1].id	https://openalex.org/keywords/mathematics
keywords[1].score	0.45790764689445496
keywords[1].display_name	Mathematics
keywords[2].id	https://openalex.org/keywords/mathematical-economics
keywords[2].score	0.4409255385398865
keywords[2].display_name	Mathematical economics
keywords[3].id	https://openalex.org/keywords/best-response
keywords[3].score	0.41943058371543884
keywords[3].display_name	Best response
keywords[4].id	https://openalex.org/keywords/computer-science
keywords[4].score	0.3724024295806885
keywords[4].display_name	Computer science
keywords[5].id	https://openalex.org/keywords/game-theory
keywords[5].score	0.2804858684539795
keywords[5].display_name	Game theory
language	en
locations[0].id	pmh:oai:arXiv.org:2403.18086
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license	cc-by
locations[0].pdf_url	https://arxiv.org/pdf/2403.18086
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2403.18086
locations[1].id	doi:10.48550/arxiv.2403.18086
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2403.18086
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5017866507
authorships[0].author.orcid
authorships[0].author.display_name	Bora Yongacoglu
authorships[0].author_position	first
authorships[0].raw_author_name	Yongacoglu, Bora
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5072860374
authorships[1].author.orcid	https://orcid.org/0000-0002-8295-1509
authorships[1].author.display_name	Gürdal Arslan
authorships[1].author_position	middle
authorships[1].raw_author_name	Arslan, Gürdal
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5038039270
authorships[2].author.orcid	https://orcid.org/0000-0002-2849-0318
authorships[2].author.display_name	Lacra Pavel
authorships[2].author_position	middle
authorships[2].raw_author_name	Pavel, Lacra
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5005401257
authorships[3].author.orcid	https://orcid.org/0000-0001-6099-5001
authorships[3].author.display_name	Serdar Yüksel
authorships[3].author_position	last
authorships[3].raw_author_name	Yüksel, Serdar
authorships[3].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2403.18086
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Generalizing Better Response Paths and Weakly Acyclic Games
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11798
primary_topic.field.id	https://openalex.org/fields/18
primary_topic.field.display_name	Decision Sciences
primary_topic.score	0.8902999758720398
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	Optimal Experimental Design Methods
related_works	https://openalex.org/W4389370903, https://openalex.org/W2803931294, https://openalex.org/W3021641094, https://openalex.org/W2038329795, https://openalex.org/W1151949413, https://openalex.org/W2245247999, https://openalex.org/W1554758635, https://openalex.org/W2282604764, https://openalex.org/W2354539280, https://openalex.org/W2038156579
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2403.18086
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://arxiv.org/pdf/2403.18086
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2403.18086
primary_location.id	pmh:oai:arXiv.org:2403.18086
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license	cc-by
primary_location.pdf_url	https://arxiv.org/pdf/2403.18086
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2403.18086
publication_date	2024-03-26
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	21, 61, 71, 108
abstract_inverted_index.In	16
abstract_inverted_index.To	94
abstract_inverted_index.We	76
abstract_inverted_index.in	32, 41, 54, 87, 121, 144
abstract_inverted_index.is	52, 68, 99, 124
abstract_inverted_index.of	12, 23, 56, 60, 83, 105, 131
abstract_inverted_index.to	9, 46, 127
abstract_inverted_index.we	19, 28, 102
abstract_inverted_index.The	118
abstract_inverted_index.and	6, 27, 91, 134
abstract_inverted_index.are	7, 113
abstract_inverted_index.for	80
abstract_inverted_index.its	30
abstract_inverted_index.not	100, 114
abstract_inverted_index.our	66, 97
abstract_inverted_index.the	10, 128, 135, 140
abstract_inverted_index.Nash	110
abstract_inverted_index.best	47
abstract_inverted_index.both	88
abstract_inverted_index.fail	45
abstract_inverted_index.game	13
abstract_inverted_index.here	138
abstract_inverted_index.path	57
abstract_inverted_index.pure	109
abstract_inverted_index.that	96, 112, 145
abstract_inverted_index.they	44
abstract_inverted_index.this	17, 81, 122
abstract_inverted_index.weak	50, 85
abstract_inverted_index.when	35
abstract_inverted_index.work	123
abstract_inverted_index.While	49
abstract_inverted_index.first	141
abstract_inverted_index.games	2, 5, 90, 106
abstract_inverted_index.study	11
abstract_inverted_index.terms	55
abstract_inverted_index.using	70
abstract_inverted_index.where	43
abstract_inverted_index.Weakly	0
abstract_inverted_index.agents	36
abstract_inverted_index.better	63, 73
abstract_inverted_index.employ	37
abstract_inverted_index.game's	62
abstract_inverted_index.games,	26
abstract_inverted_index.games.	93
abstract_inverted_index.graph,	65
abstract_inverted_index.graph.	75
abstract_inverted_index.notion	82
abstract_inverted_index.paper,	18
abstract_inverted_index.paths,	133
abstract_inverted_index.recent	129
abstract_inverted_index.theory	130
abstract_inverted_index.weakly	24, 116
abstract_inverted_index.acyclic	1, 25
abstract_inverted_index.closely	125
abstract_inverted_index.defined	53, 69
abstract_inverted_index.observe	29
abstract_inverted_index.periods	42
abstract_inverted_index.present	20
abstract_inverted_index.provide	77, 103
abstract_inverted_index.related	126
abstract_inverted_index.results	143
abstract_inverted_index.theory.	146
abstract_inverted_index.updates	40
abstract_inverted_index.acyclic.	117
abstract_inverted_index.control.	15
abstract_inverted_index.examples	104
abstract_inverted_index.learning	34
abstract_inverted_index.negative	142
abstract_inverted_index.respond.	48
abstract_inverted_index.response	64, 74
abstract_inverted_index.strategy	39
abstract_inverted_index.trivial,	101
abstract_inverted_index.admitting	107
abstract_inverted_index.potential	4
abstract_inverted_index.presented	120, 137
abstract_inverted_index.theoretic	14
abstract_inverted_index.$n$-player	92
abstract_inverted_index.acyclicity	51, 86
abstract_inverted_index.conditions	79
abstract_inverted_index.constitute	139
abstract_inverted_index.generalize	3
abstract_inverted_index.importance	31
abstract_inverted_index.properties	59
abstract_inverted_index.sufficient	78
abstract_inverted_index.two-player	89
abstract_inverted_index.demonstrate	95
abstract_inverted_index.equilibrium	111
abstract_inverted_index.fundamental	8
abstract_inverted_index.generalized	72, 84, 115
abstract_inverted_index.multi-agent	33
abstract_inverted_index.satisficing	132
abstract_inverted_index.connectivity	58
abstract_inverted_index.experimental	38
abstract_inverted_index.generalization	22, 67, 98, 119
abstract_inverted_index.counterexamples	136
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile