Iterative Methods for First-Order Nash Equilibria in Zero-Sum Games
| Název práce v češtině: | Iterativní metody pro Nashova ekvilibria prvního řádu v hrách s nulovým součtem |
|---|---|
| Název v anglickém jazyce: | Iterative Methods for First-Order Nash Equilibria in Zero-Sum Games |
| Klíčová slova: | teorie her|Nashovo ekvilibrium|iterativní metody |
| Klíčová slova anglicky: | game theory|Nash equlibrium|iterative methods |
| Akademický rok vypsání: | 2024/2025 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Ing. Tomáš Kroupa, Ph.D. |
| Řešitel: | Bc. Jan Pijálek - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 30.05.2024 |
| Datum zadání: | 30.05.2024 |
| Datum potvrzení stud. oddělením: | 18.07.2024 |
| Datum a čas obhajoby: | 05.09.2024 10:00 |
| Datum odevzdání elektronické podoby: | 18.07.2024 |
| Datum odevzdání tištěné podoby: | 18.07.2024 |
| Datum proběhlé obhajoby: | 05.09.2024 |
| Oponenti: | doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D. |
| Konzultanti: | RNDr. Martin Černý |
| Zásady pro vypracování |
| The problem of efficient computing of Nash equilibria has recently received renewed interest, since it has found many applications in areas such as reinforcement and adversarial learning. Due to the specific conditions of the applications, one has to resort to relaxations of this concept, so called first-order Nash equilibria.
The aim of this work is to first implement the stochastic gradient descent algorithm (RNI-SGD) from [1] for the Nikaido-Isoda function formulation of the computation of first-order Nash equilibria and then to verify experimentally the behaviour of the algorithm using examples. The student might consider examples from [1] or , e.g., https://gitlab.fel.cvut.cz/kosohmar/StayOnTheRidge.jl. An additional goal might be to apply the algorithm to some problem of robust learning or adversarial machine learning. |
| Seznam odborné literatury |
| [1] TSAKNAKIS, Ioannis; HONG, Mingyi. Finding First-Order Nash Equilibria of Zero-Sum Games with the Regularized Nikaido-Isoda Function. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:1189-1197, 2021.
[2] RAZAVIYAYN, Meisam; HUANG, Tianjian; LU, Songtao; NOUIEHED, Ma- her; SANJABI, Maziar; HONG, Mingyi. Nonconvex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances. IEEE Signal Processing Magazine. 2020, vol. 37, no. 5, pp. 55–66. issn 1053-5888, issn 1558-0792. Available from doi: 10.1109/MSP.2020.3003851. [3] DASKALAKIS, Constantinos; GOLOWICH, Noah; SKOULAKIS, Stratis; ZAMPETAKIS, Manolis. STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games. arXiv, 2022. Available from doi: 10.48550/ARXIV.2210.09769. Version Number: 1. |