Simple Recursive Games

Simple item page
dc.creatorAndersson, Daniel
dc.creatorHansen, Kristoffer Arnsfelt
dc.creatorMiltersen, Peter Bro
dc.creatorSorensen, Troels Bjerre
dc.date2007-11-07
dc.date.accessioned2026-07-07T08:41:20Z
dc.date.available2026-07-07T08:41:20Z
dc.descriptionWe define the class of "simple recursive games". A simple recursive game is defined as a simple stochastic game (a notion due to Anne Condon), except that we allow arbitrary real payoffs but disallow moves of chance. We study the complexity of solving simple recursive games and obtain an almost-linear time comparison-based algorithm for computing an equilibrium of such a game. The existence of a linear time comparison-based algorithm remains an open problem.
dc.identifierhttps://arxiv.org/abs/0711.1055
dc.identifierhttp://arxiv.org/abs/0711.1055
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/141645
dc.subjectComputer Science and Game Theory
dc.subjectData Structures and Algorithms
dc.titleSimple Recursive Games
dc.typetext

Files

Collections

arXiv