Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games
While fictitious play is guaranteed to converge to Nash equilibrium in certain game classes, such as two-player zero-sum games, it is not guaranteed to converge in non-zero-sum and multiplayer games. We show that fictitious play in fact leads to improved Nash equilibrium approximation over a variet...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
LibraryPress@UF
2025-05-01
|
| Series: | Proceedings of the International Florida Artificial Intelligence Research Society Conference |
| Subjects: | |
| Online Access: | https://journals.flvc.org/FLAIRS/article/view/138636 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849321706416504832 |
|---|---|
| author | Sam Ganzfried |
| author_facet | Sam Ganzfried |
| author_sort | Sam Ganzfried |
| collection | DOAJ |
| description |
While fictitious play is guaranteed to converge to Nash equilibrium in certain game classes, such as two-player zero-sum games, it is not guaranteed to converge in non-zero-sum and multiplayer games. We show that fictitious play in fact leads to improved Nash equilibrium approximation over a variety of game classes and sizes than (counterfactual) regret minimization, which has recently produced superhuman play for multiplayer poker. We also show that when fictitious play is run several times using random initializations it is able to solve several known challenge problems in which the standard version is known to not converge, including Shapley's classic counterexample. These provide some of the first positive results for fictitious play in these settings, despite the fact that worst-case theoretical results are negative.
|
| format | Article |
| id | doaj-art-5f22ee14706e4d8e9a49df76851276e1 |
| institution | Kabale University |
| issn | 2334-0754 2334-0762 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | LibraryPress@UF |
| record_format | Article |
| series | Proceedings of the International Florida Artificial Intelligence Research Society Conference |
| spelling | doaj-art-5f22ee14706e4d8e9a49df76851276e12025-08-20T03:49:41ZengLibraryPress@UFProceedings of the International Florida Artificial Intelligence Research Society Conference2334-07542334-07622025-05-0138110.32473/flairs.38.1.138636Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer GamesSam Ganzfried0Ganzfried Research While fictitious play is guaranteed to converge to Nash equilibrium in certain game classes, such as two-player zero-sum games, it is not guaranteed to converge in non-zero-sum and multiplayer games. We show that fictitious play in fact leads to improved Nash equilibrium approximation over a variety of game classes and sizes than (counterfactual) regret minimization, which has recently produced superhuman play for multiplayer poker. We also show that when fictitious play is run several times using random initializations it is able to solve several known challenge problems in which the standard version is known to not converge, including Shapley's classic counterexample. These provide some of the first positive results for fictitious play in these settings, despite the fact that worst-case theoretical results are negative. https://journals.flvc.org/FLAIRS/article/view/138636game theoryfictitious playinitializationregret minimizationmultiplayer Nash equilibrium |
| spellingShingle | Sam Ganzfried Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games Proceedings of the International Florida Artificial Intelligence Research Society Conference game theory fictitious play initialization regret minimization multiplayer Nash equilibrium |
| title | Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games |
| title_full | Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games |
| title_fullStr | Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games |
| title_full_unstemmed | Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games |
| title_short | Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games |
| title_sort | empirical analysis of fictitious play for nash equilibrium computation in multiplayer games |
| topic | game theory fictitious play initialization regret minimization multiplayer Nash equilibrium |
| url | https://journals.flvc.org/FLAIRS/article/view/138636 |
| work_keys_str_mv | AT samganzfried empiricalanalysisoffictitiousplayfornashequilibriumcomputationinmultiplayergames |