Li, H;
Huang, W;
Duan, Z;
Mguni, DH;
Shao, K;
Wang, J;
Deng, X;
(2024)
A survey on algorithms for Nash equilibria in finite normal-form games.
Computer Science Review
, 51
, Article 100613. 10.1016/j.cosrev.2023.100613.
![]() |
Text
A survey on algorithms for Nash equilibria in finite normal form games.pdf - Accepted Version Access restricted to UCL open access staff until 29 December 2024. Download (451kB) |
Abstract
Nash equilibrium is one of the most influential solution concepts in game theory. With the development of computer science and artificial intelligence, there is an increasing demand on Nash equilibrium computation, especially for Internet economics and multi-agent learning. This paper reviews various algorithms computing the Nash equilibrium and its approximation solutions in finite normal-form games from both theoretical and empirical perspectives. For the theoretical part, we classify algorithms in the literature and present basic ideas on algorithm design and analysis. For the empirical part, we present a comprehensive comparison on the algorithms in the literature over different kinds of games. Based on these results, we provide practical suggestions on implementations and uses of these algorithms. Finally, we present a series of open problems from both theoretical and practical considerations.
Type: | Article |
---|---|
Title: | A survey on algorithms for Nash equilibria in finite normal-form games |
DOI: | 10.1016/j.cosrev.2023.100613 |
Publisher version: | http://dx.doi.org/10.1016/j.cosrev.2023.100613 |
Language: | English |
Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
Keywords: | Nash equilibrium, Game theory, Approximation algorithms |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/10188588 |
Archive Staff Only
![]() |
View Item |