From First-Order to Second-Order Rationality: Advancing Game Convergence with Dynamic Weighted Fictitious Play
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916382376984576 |
|---|---|
| author | Ju, Qi Hei, Falin Liu, Yuxuan Fang, Zhemei Luo, Yunfeng |
| author_facet | Ju, Qi Hei, Falin Liu, Yuxuan Fang, Zhemei Luo, Yunfeng |
| contents | Constructing effective algorithms to converge to Nash Equilibrium (NE) is an important problem in algorithmic game theory. Prior research generally posits that the upper bound on the convergence rate for games is $O\left(T^{-1/2}\right)$. This paper introduces a novel perspective, positing that the key to accelerating convergence in game theory is rationality. Based on this concept, we propose a Dynamic Weighted Fictitious Play (DW-FP) algorithm. We demonstrate that this algorithm can converge to a NE and exhibits a convergence rate of $O(T^{-1})$ in experimental evaluations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12164 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | From First-Order to Second-Order Rationality: Advancing Game Convergence with Dynamic Weighted Fictitious Play Ju, Qi Hei, Falin Liu, Yuxuan Fang, Zhemei Luo, Yunfeng Computer Science and Game Theory Constructing effective algorithms to converge to Nash Equilibrium (NE) is an important problem in algorithmic game theory. Prior research generally posits that the upper bound on the convergence rate for games is $O\left(T^{-1/2}\right)$. This paper introduces a novel perspective, positing that the key to accelerating convergence in game theory is rationality. Based on this concept, we propose a Dynamic Weighted Fictitious Play (DW-FP) algorithm. We demonstrate that this algorithm can converge to a NE and exhibits a convergence rate of $O(T^{-1})$ in experimental evaluations. |
| title | From First-Order to Second-Order Rationality: Advancing Game Convergence with Dynamic Weighted Fictitious Play |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.12164 |