Paths to Equilibrium in 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.18079

In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms. A fundamental question about strategic dynamics is such: for a given game and initial strategy profile, is it always possible to construct a satisficing path that terminates at an equilibrium? The resolution of this question has implications about the capabilities or limitations of a class of MARL algorithms. We answer this question in the affirmative for normal-form games. Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.

Related Topics

Concepts

Mathematical economics Extensive-form game Equilibrium selection Computer science Economics Mathematics Repeated game Game theory

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Paths to Equilibrium in 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.18079

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

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.18079

Direct OA link when available
Concepts: Mathematical economics, Extensive-form game, Equilibrium selection, Computer science, Economics, Mathematics, Repeated game, 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/W4393299878
doi	https://doi.org/10.48550/arxiv.2403.18079
ids.doi	https://doi.org/10.48550/arxiv.2403.18079
ids.openalex	https://openalex.org/W4393299878
fwci
type	preprint
title	Paths to Equilibrium in Games
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
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.890999972820282
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/T12137
topics[1].field.id	https://openalex.org/fields/20
topics[1].field.display_name	Economics, Econometrics and Finance
topics[1].score	0.8403000235557556
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	Economic theories and models
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C144237770
concepts[0].level	1
concepts[0].score	0.6539738178253174
concepts[0].wikidata	https://www.wikidata.org/wiki/Q747534
concepts[0].display_name	Mathematical economics
concepts[1].id	https://openalex.org/C146930158
concepts[1].level	4
concepts[1].score	0.4907597005367279
concepts[1].wikidata	https://www.wikidata.org/wiki/Q656416
concepts[1].display_name	Extensive-form game
concepts[2].id	https://openalex.org/C164407509
concepts[2].level	4
concepts[2].score	0.4272956848144531
concepts[2].wikidata	https://www.wikidata.org/wiki/Q5384490
concepts[2].display_name	Equilibrium selection
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.39469391107559204
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C162324750
concepts[4].level	0
concepts[4].score	0.3542354106903076
concepts[4].wikidata	https://www.wikidata.org/wiki/Q8134
concepts[4].display_name	Economics
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.3454732894897461
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C202556891
concepts[6].level	3
concepts[6].score	0.29091280698776245
concepts[6].wikidata	https://www.wikidata.org/wiki/Q1584646
concepts[6].display_name	Repeated game
concepts[7].id	https://openalex.org/C177142836
concepts[7].level	2
concepts[7].score	0.29070961475372314
concepts[7].wikidata	https://www.wikidata.org/wiki/Q44455
concepts[7].display_name	Game theory
keywords[0].id	https://openalex.org/keywords/mathematical-economics
keywords[0].score	0.6539738178253174
keywords[0].display_name	Mathematical economics
keywords[1].id	https://openalex.org/keywords/extensive-form-game
keywords[1].score	0.4907597005367279
keywords[1].display_name	Extensive-form game
keywords[2].id	https://openalex.org/keywords/equilibrium-selection
keywords[2].score	0.4272956848144531
keywords[2].display_name	Equilibrium selection
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.39469391107559204
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/economics
keywords[4].score	0.3542354106903076
keywords[4].display_name	Economics
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.3454732894897461
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/repeated-game
keywords[6].score	0.29091280698776245
keywords[6].display_name	Repeated game
keywords[7].id	https://openalex.org/keywords/game-theory
keywords[7].score	0.29070961475372314
keywords[7].display_name	Game theory
language	en
locations[0].id	pmh:oai:arXiv.org:2403.18079
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
locations[0].pdf_url	https://arxiv.org/pdf/2403.18079
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
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.18079
locations[1].id	doi:10.48550/arxiv.2403.18079
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.18079
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	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2403.18079
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-03-29T00:00:00
display_name	Paths to Equilibrium in Games
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
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.890999972820282
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/W2025486390, https://openalex.org/W4244028092, https://openalex.org/W3125138254, https://openalex.org/W3124955087, https://openalex.org/W2035148334, https://openalex.org/W3035137804, https://openalex.org/W3203771163, https://openalex.org/W4248854763, https://openalex.org/W2153002690, https://openalex.org/W2011982489
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2403.18079
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
best_oa_location.pdf_url	https://arxiv.org/pdf/2403.18079
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
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.18079
primary_location.id	pmh:oai:arXiv.org:2403.18079
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
primary_location.pdf_url	https://arxiv.org/pdf/2403.18079
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
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.18079
publication_date	2024-03-26
publication_year	2024
referenced_works_count	0
abstract_inverted_index.A	102
abstract_inverted_index.a	20, 32, 111, 124, 145, 163, 179
abstract_inverted_index.In	0
abstract_inverted_index.We	150
abstract_inverted_index.an	43, 130
abstract_inverted_index.as	15
abstract_inverted_index.at	129
abstract_inverted_index.by	36
abstract_inverted_index.do	68
abstract_inverted_index.in	39, 49, 57, 79, 98, 154
abstract_inverted_index.is	46, 108, 118
abstract_inverted_index.it	119
abstract_inverted_index.of	22, 29, 134, 144, 147
abstract_inverted_index.or	142
abstract_inverted_index.to	122, 173, 176
abstract_inverted_index.Our	160
abstract_inverted_index.The	132
abstract_inverted_index.and	5, 11, 82, 95, 114
abstract_inverted_index.any	80
abstract_inverted_index.are	91, 171
abstract_inverted_index.but	72
abstract_inverted_index.for	85, 110, 157
abstract_inverted_index.has	137
abstract_inverted_index.its	55
abstract_inverted_index.key	172
abstract_inverted_index.new	16
abstract_inverted_index.not	53, 69, 74
abstract_inverted_index.one	50
abstract_inverted_index.the	58, 76, 140, 155
abstract_inverted_index.who	45
abstract_inverted_index.MARL	100, 148
abstract_inverted_index.This	25, 61
abstract_inverted_index.best	47
abstract_inverted_index.data	17
abstract_inverted_index.does	52, 73
abstract_inverted_index.game	6, 113
abstract_inverted_index.many	99
abstract_inverted_index.next	59
abstract_inverted_index.path	126
abstract_inverted_index.play	175
abstract_inverted_index.that	65, 127, 166
abstract_inverted_index.this	89, 135, 152
abstract_inverted_index.thus	83
abstract_inverted_index.way,	81
abstract_inverted_index.with	88
abstract_inverted_index.about	105, 139
abstract_inverted_index.agent	44
abstract_inverted_index.along	178
abstract_inverted_index.arise	96
abstract_inverted_index.class	146
abstract_inverted_index.given	112
abstract_inverted_index.paper	26
abstract_inverted_index.path.	181
abstract_inverted_index.such:	109
abstract_inverted_index.their	13
abstract_inverted_index.where	42
abstract_inverted_index.(MARL)	4
abstract_inverted_index.agents	8, 67, 78
abstract_inverted_index.allows	84
abstract_inverted_index.always	120
abstract_inverted_index.answer	151
abstract_inverted_index.called	92
abstract_inverted_index.games.	159
abstract_inverted_index.merely	63
abstract_inverted_index.paths,	94
abstract_inverted_index.period	51
abstract_inverted_index.policy	37
abstract_inverted_index.revise	12
abstract_inverted_index.reward	167
abstract_inverted_index.switch	54, 70
abstract_inverted_index.driving	174
abstract_inverted_index.initial	115
abstract_inverted_index.insight	165
abstract_inverted_index.period.	60
abstract_inverted_index.reveals	162
abstract_inverted_index.studies	27
abstract_inverted_index.theory,	7
abstract_inverted_index.updates	170
abstract_inverted_index.analysis	161
abstract_inverted_index.arrives,	18
abstract_inverted_index.dynamics	107
abstract_inverted_index.inspired	35
abstract_inverted_index.interact	10
abstract_inverted_index.learning	3
abstract_inverted_index.pairwise	33
abstract_inverted_index.possible	121
abstract_inverted_index.profile,	117
abstract_inverted_index.property	90
abstract_inverted_index.question	104, 136, 153
abstract_inverted_index.requires	64
abstract_inverted_index.sequence	21
abstract_inverted_index.strategy	23, 56, 116
abstract_inverted_index.updating	38
abstract_inverted_index.Sequences	87
abstract_inverted_index.constrain	75
abstract_inverted_index.construct	123
abstract_inverted_index.learning,	41
abstract_inverted_index.naturally	97
abstract_inverted_index.producing	19
abstract_inverted_index.profiles.	24
abstract_inverted_index.sequences	28
abstract_inverted_index.strategic	106, 169
abstract_inverted_index.constraint	34, 62
abstract_inverted_index.optimizing	66
abstract_inverted_index.repeatedly	9
abstract_inverted_index.resolution	133
abstract_inverted_index.responding	48
abstract_inverted_index.satisfying	31
abstract_inverted_index.strategies	14, 30
abstract_inverted_index.terminates	128
abstract_inverted_index.affirmative	156
abstract_inverted_index.algorithms.	101, 149
abstract_inverted_index.equilibrium	177
abstract_inverted_index.fundamental	103
abstract_inverted_index.limitations	143
abstract_inverted_index.multi-agent	1
abstract_inverted_index.normal-form	158
abstract_inverted_index.satisficing	93, 125, 180
abstract_inverted_index.strategies,	71
abstract_inverted_index.capabilities	141
abstract_inverted_index.equilibrium?	131
abstract_inverted_index.exploration.	86
abstract_inverted_index.implications	138
abstract_inverted_index.deteriorating	168
abstract_inverted_index.reinforcement	2, 40
abstract_inverted_index.non-optimizing	77
abstract_inverted_index.counterintuitive	164
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile