Half-positionally determined winning conditions in infinite games

Speaker(s)

Eryk Kopczynski

Affiliation

Uniwersytet Warszawski

Date

Dec. 14, 2005, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

We consider half-positionally determined winning conditions in infinite games played on a graph by two antagonistic players Eve and Adam. We call a winning condition W _positionally determined_ if, for every infinite game (G,W) using this winning condition, one of the players has a positional (i.e. memoryless) winning strategy. We call a winning condition _half-positionally determined_ if we only require Eve's strategy to be positional, but Adam's strategy can be arbitrary. We will show some general properties of such winning conditions. While some properties of positionally determined conditions can be easily generalized to the case of half-positional determinacy, some cannot. We will also show some classes of half-positionally determined winning conditions; these classes are independent (none of them is included in another) and include: * Concave winning conditions, which, among others, include (generalized) parity conditions and Rabin conditions. Concavity is sufficient for half-positional determinacy only in case of games on finite arenas; * Geometric conditions, associated with convex subsets of [0,1]^n; * Monotonic winning conditions, given by a deterministic finite automaton with a monotonic transition function.

---