An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F14%3A00224949" target="_blank" >RIV/68407700:21230/14:00224949 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.jair.org/papers/paper4477.html" target="_blank" >http://www.jair.org/papers/paper4477.html</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

Popis výsledku v původním jazyce

Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive-form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play onlyselected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in mem

Název v anglickém jazyce

An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

Popis výsledku anglicky

Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive-form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play onlyselected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in mem

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F12%2F2054" target="_blank" >GAP202/12/2054: Bezpečnostní hry v extenzivní formě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Artificial Intelligence Research

ISSN

1076-9757

e-ISSN

—

Svazek periodika

51

Číslo periodika v rámci svazku

—

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

829-866

Kód UT WoS článku

000350466400011

EID výsledku v databázi Scopus

—