Nie jesteś zalogowany | Zaloguj się

Eliminating randomness from infinite games

Prelegent(ci)
Eryk Kopczyński
Afiliacja
Uniwersytet Warszawski
Termin
7 maja 2008 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

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.