Original title: Double Oracle algoritmus pro hry s nekompaktními množinami strategií
Translated title: Double Oracle Algorithm for Games with Non-compact Strategy Sets
Authors: Štraitová, Jolana ; Kroupa, Tomáš (advisor) ; Spurný, Jiří (referee)
Document type: Bachelor's theses
Year: 2026
Language: eng
Abstract: [eng] [cze]
The Double Oracle algorithm computes an equilibrium of a game by iteratively finding an equilibrium of a subgame and updating strategy sets via best responses to the current equilibrium. Convergence is known for infinite continuous two-player zero-sum games with compact strategy sets. This thesis studies an extension to infinite continuous two- player zero-sum games with non-compact strategy sets. The main obstacles are existence of an equilibrium, existence of best responses, and existence of a weakly convergent subsequence in a sequence of probability measures. We apply literature to state sufficient conditions for existence of an equilibrium and of best responses. We show as a novel corollary that if one of the strategy sets is compact, then the key assumptions for existence of a solution and existence of best responses are equivalent. We address the possible convergence of the algorithm. Double Oracle algoritmus počítá ekvilibrium hry iterativním hledáním ekvilibrií pod- her a aktualizací množiny strategií o nejlepší odpovědi na aktuální ekvilibrium. Kon- vergence k ekvilibriu hry je dokázána pro nekonečné spojité dvouhráčové zero-sum hry s kompaktními množinami strategií. Tato práce zkoumá rozšíření algoritmu pro neko- nečné spojité dvouhráčové zero-sum hry s nekompaktními množinami strategií. Hlavními překážkami jsou existence ekvilibria, existence nejlepších odpovědí a existence slabě kon- vergentní podposloupnosti v posloupnosti pravděpodobnostních měr. V práci uvedeme, za jakých postačujících podmínek plynoucích z literatury existuje ekvilibrium hry a nejlepší odpovědi obou hráčů. Jako nový důsledek ukážeme, že za předpokladu, že jedna množina strategií je kompaktní, jsou klíčové předpoklady pro existenci řešení a existenci nejlepších odpovědí ekvivalentní. Dále se věnujeme možnému důkazu konvergecne algoritmu.
Keywords: continuous game|Nash equilibrium|Double Oracle algorithm; spojitá hra|Nashovo ekvilibrium|Double Oracle algoritmus

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/211538

Permalink: http://www.nusl.cz/ntk/nusl-780775


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses