Arrangement
YOU ARE HERE: News & Events » Events archive » Event

CAGT Seminar: Daniel Andersson

2008.10.28 | Troels Bjerre Sørensen

Date Tue Nov 11
Time 14:15 15:15
Location DI-Turing-014

Title: Deterministic Graphical Games Revisited
Speaker: Daniel Andersson
Time: Tue Nov 11th 2008, 14:15-15:00
Location: Turing-014
Abstract:

We revisit Washburn's deterministic graphical games, a natural generalization of the perfect information win/lose games commonly solved by retrograde analysis. We study the complexity of solving deterministic graphical 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.

Joint work with Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen.

CS Calendar
Comments on content: 
Revised 2012.05.21