Double-Oracle Algorithm for Computing an Exact Nash Equilibrium in Zero-Sum Extensive-Form Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F13%3A00213285" target="_blank" >RIV/68407700:21230/13:00213285 - isvavai.cz</a>
Result on the web
<a href="http://www.ifaamas.org/Proceedings/aamas2013/forms/authors.htm" target="_blank" >http://www.ifaamas.org/Proceedings/aamas2013/forms/authors.htm</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Double-Oracle Algorithm for Computing an Exact Nash Equilibrium in Zero-Sum Extensive-Form Games
Original language description
We investigate an iterative algorithm for computing an exact Nash equilibrium in two-player zero-sum extensive-form games with imperfect information. The approach uses the sequence-form representation of extensive-form games and the double-oracle algorithmic framework. The main idea is to restrict the game by allowing the players to play only some of the sequences of available actions, then iteratively solve this restricted game, and exploit fast best-response algorithms to add additional sequences to the restricted game for the next iteration. In this paper we (1) extend the sequence-form double-oracle method to be applicable on non-deterministic extensive-form games, (2) present more efficient methods for maintaining valid restricted game and computing best-response sequences, and finally we (3) provide theoretical guarantees of the convergence of the algorithm to a Nash equilibrium. We experimentally evaluate our algorithm on two types of games: a search game on a graph and simplifi
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
AAMAS '13 Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems
ISBN
978-1-4503-1993-5
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
335-342
Publisher name
IFAAMAS
Place of publication
County of Richland
Event location
Saint Paul, Minnesota
Event date
May 6, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—