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.

---