Gewinnstrategien und Determiniertheit
Wir können nun leicht den Begriff einer Gewinnstrategie definieren:
Definition (Gewinnstrategie und Gewinn)
Sei G(P, T) ein Spiel.
(a) | Eine Optionsstrategie S ⊆ T für I heißt eine Gewinnstrategie für Spieler I im Spiel G(P, T), falls gilt: [ S ] ⊆ P. |
(b) | Eine Optionsstrategie S ⊆ T für II heißt eine Gewinnstrategie für Spieler II im Spiel G(P, T), falls gilt: [ S ] ∩ P = ∅. |
(c) | Spieler I gewinnt G(P, T), falls eine Gewinnstrategie für I im Spiel G(P, T) existiert. Analog für Spieler II. |
Genauer müssten wir zwischen Gewinnoptionsstrategien und Gewinnstrategien unterscheiden.
Ist S eine Gewinnstrategie für I, so ist auch jede Optionsstrategie S′ ⊆ S eine Gewinnstrategie für I. Analoge Aussagen gelten für Spieler II.
Übung
Sei S eine Strategie für I im Spiel G(P, T). Dann sind äquivalent:
(i) | S ist eine Gewinnstrategie für I. |
(ii) | S gewinnt gegen alle Strategien des Gegners, d. h. es gilt S ✥ S′ ⊆ P für alle Strategien S′ für II. |
Eine analoge Aussage gilt wieder für Strategien für Spieler II.
Eine Gewinnstrategie ist also, wie es sein soll, jeder Strategie des Gegners überlegen. Offenbar können nicht beide Spieler zugleich eine Gewinnstrategie besitzen. Andererseits ist die Existenz einer Gewinnstrategie für einen der beiden Spieler keineswegs klar.
Definition (determinierte Spiele und determinierte Mengen in Folgenräumen)
Ein Spiel G(P, T) heißt determiniert, falls Spieler I oder Spieler II eine Gewinnstrategie im Spiel G(P, T) besitzt.
Ein P ⊆ SeqA heißt determiniert in ℕA, falls G(P, SeqA) determiniert ist.
Wir unterdrücken oft den Zusatz „in ℕA“ für determinierte Mengen P ⊆ ℕA, falls A aus dem Kontext heraus klar ist. Speziell gilt dies für den wichtigsten Fall A = ℕ und Mengen P ⊆ 𝒩.