α-Rank: Multi-Agent Evaluation by Evolution

Abstract We introduce α-Rank, a principled evolutionary dynamics methodology, for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous-time and...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Shayegan Omidshafiei, Christos Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau, Wojciech M. Czarnecki, Marc Lanctot, Julien Perolat, Remi Munos
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2019
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/fdd2f745b2844cf49e6facb5a043ddfa
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:fdd2f745b2844cf49e6facb5a043ddfa
record_format	dspace
spelling	oai:doaj.org-article:fdd2f745b2844cf49e6facb5a043ddfa2021-12-02T15:09:30Zα-Rank: Multi-Agent Evaluation by Evolution10.1038/s41598-019-45619-92045-2322https://doaj.org/article/fdd2f745b2844cf49e6facb5a043ddfa2019-07-01T00:00:00Zhttps://doi.org/10.1038/s41598-019-45619-9https://doaj.org/toc/2045-2322Abstract We introduce α-Rank, a principled evolutionary dynamics methodology, for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous-time and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, in the type of interactions (beyond dyadic), and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions, and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). α-Rank automatically provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics in terms of basins of attraction and sink components. This is a direct consequence of the correspondence we establish to the dynamical MCC solution concept when the underlying evolutionary model’s ranking-intensity parameter, α, is chosen to be large, which exactly forms the basis of α-Rank. In contrast to the Nash equilibrium, which is a static solution concept based solely on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley’s Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. Our α-Rank method runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce mathematical proofs that not only provide an overarching and unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the α-Rank methodology. We illustrate the method in canonical games and empirically validate it in several domains, including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.Shayegan OmidshafieiChristos PapadimitriouGeorgios PiliourasKarl TuylsMark RowlandJean-Baptiste LespiauWojciech M. CzarneckiMarc LanctotJulien PerolatRemi MunosNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 9, Iss 1, Pp 1-29 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Shayegan Omidshafiei Christos Papadimitriou Georgios Piliouras Karl Tuyls Mark Rowland Jean-Baptiste Lespiau Wojciech M. Czarnecki Marc Lanctot Julien Perolat Remi Munos α-Rank: Multi-Agent Evaluation by Evolution
description	Abstract We introduce α-Rank, a principled evolutionary dynamics methodology, for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous-time and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, in the type of interactions (beyond dyadic), and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions, and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). α-Rank automatically provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics in terms of basins of attraction and sink components. This is a direct consequence of the correspondence we establish to the dynamical MCC solution concept when the underlying evolutionary model’s ranking-intensity parameter, α, is chosen to be large, which exactly forms the basis of α-Rank. In contrast to the Nash equilibrium, which is a static solution concept based solely on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley’s Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. Our α-Rank method runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce mathematical proofs that not only provide an overarching and unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the α-Rank methodology. We illustrate the method in canonical games and empirically validate it in several domains, including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.
format	article
author	Shayegan Omidshafiei Christos Papadimitriou Georgios Piliouras Karl Tuyls Mark Rowland Jean-Baptiste Lespiau Wojciech M. Czarnecki Marc Lanctot Julien Perolat Remi Munos
author_facet	Shayegan Omidshafiei Christos Papadimitriou Georgios Piliouras Karl Tuyls Mark Rowland Jean-Baptiste Lespiau Wojciech M. Czarnecki Marc Lanctot Julien Perolat Remi Munos
author_sort	Shayegan Omidshafiei
title	α-Rank: Multi-Agent Evaluation by Evolution
title_short	α-Rank: Multi-Agent Evaluation by Evolution
title_full	α-Rank: Multi-Agent Evaluation by Evolution
title_fullStr	α-Rank: Multi-Agent Evaluation by Evolution
title_full_unstemmed	α-Rank: Multi-Agent Evaluation by Evolution
title_sort	α-rank: multi-agent evaluation by evolution
publisher	Nature Portfolio
publishDate	2019
url	https://doaj.org/article/fdd2f745b2844cf49e6facb5a043ddfa
work_keys_str_mv	AT shayeganomidshafiei arankmultiagentevaluationbyevolution AT christospapadimitriou arankmultiagentevaluationbyevolution AT georgiospiliouras arankmultiagentevaluationbyevolution AT karltuyls arankmultiagentevaluationbyevolution AT markrowland arankmultiagentevaluationbyevolution AT jeanbaptistelespiau arankmultiagentevaluationbyevolution AT wojciechmczarnecki arankmultiagentevaluationbyevolution AT marclanctot arankmultiagentevaluationbyevolution AT julienperolat arankmultiagentevaluationbyevolution AT remimunos arankmultiagentevaluationbyevolution
_version_	1718387854157021184

α-Rank: Multi-Agent Evaluation by Evolution

Ejemplares similares