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.

---