You are not logged in | Log in

Eliminating randomness from infinite games

Speaker(s)
Eryk Kopczyński
Affiliation
Uniwersytet Warszawski
Date
May 7, 2008, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

Consider infinite games played on a graph by two antagonistic players Eve and Adam. Each position in the game graph belongs to one of two players, who decides which move he or she takes; the winner is decided based on the infinite play. This model can be extended in several ways: introducing "random" positions where the next move is chosen randomly; letting the game result to be any value in a bounded subset of reals instead of win or loss; or positions where the two players simultaneously choose their next action, and the move chosen depends on these two actions. I will show how these extensions reduce to the basic model. As a side result we get that the Axiom of Determinacy implies that all sets are Lebesgue measurable. The talk is partly based on works of D. A. Martin.