Aarhus University Seal / Aarhus Universitets segl

Recent results on linear programming and graph-based two-player zero-sum games

Thomas Dueholm Hansen (Institut for Datalogi)
Algebra- og datalogiseminar
Torsdag, 10 november, 2016, at 14:15-15:15, in Aud. D4 (1531-219)

In this talk I give an introduction to turn-based stochastic games, a special case of Shapley's stochastic games from 1953, and show how they relate to linear programming and Markov decision processes. I present some recent algorithmic breakthroughs from the area, focusing in particular on my own work, and describe the future research directions that I find most promising. My main focus will be on simplex algorithms; the classical combinatorial algorithm for linear programming.

Kontaktperson: Anders Nedergaard Jensen