istnienie strategii wygrywającej w grach skończonych

Zbiór wzorów, definicji i najczęściej poruszanych problemów z probabilistyki oraz statystyki matematycznej.
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

istnienie strategii wygrywającej w grach skończonych

Post autor: Dumel »

Różne problemy teorii gier można rozwiązywać z pomocą narzędzi jakich dostarcza teoria grafów. Każdą grę skończoną możemy reprezentować jako acykliczny graf skierowany (DAG). W grafie takim wierzchołki reprezentują możliwe pozycje w grze, a między dwoma wierzchołkami \(\displaystyle{ u,v}\) istnieje krawędź skierowana \(\displaystyle{ (u,v)}\) wtedy i tylko wtedy gdy z pozycji \(\displaystyle{ u}\) można przejść do pozycji \(\displaystyle{ v}\). Zauważmy że istnieje dokładnie jeden wierzchołek o zerowym stopniu wejściowym, reprezentujący pozycję początkową (P). Ponadto szczególne pozycje, do których dojście oznacza zwycięstwo któregoś z graczy w reprezentujmy przez jeden wierzchołek (K).
Zanim przejdziemy do meritum, potrzebne będzie nam jeszcze pojęcie jądra grafu.

Definicja: Jądrem grafu skierowanego nazywamy zbiór wierzchołków spełniający następujące warunki:
a) jest niezależny
b) dla dowolnego wierzchołka \(\displaystyle{ u}\) nienależącego do jądra istnieje krawędź skierowana \(\displaystyle{ (u,v)}\) taka, że \(\displaystyle{ v}\) należy do jądra.

przyda się nam również następujące
Spostrzeżenie: w każdym DAGu istnieje wierzchołek o zerowym stopniu wyjściowym.
(dowód jest dosyć trywialny, zostawiam jako pracę domową)

jesteśmy już przygotowani, aby udowodnić następujące
Twierdzenie: Każdy DAG \(\displaystyle{ G}\) posiada jądro, które jest jednoznacznie wyznaczone.
Dowód: Niech \(\displaystyle{ V_1}\) będzie zbiorem wierzchołków o zerowym stopniu wyjściowym (na mocy spostrzeżenia \(\displaystyle{ V_1}\) nie jest zbiorem pustym). Wszystkie wierzchołki należące do \(\displaystyle{ V_1}\) muszą należeć do jądra \(\displaystyle{ G}\). Niech \(\displaystyle{ W_1}\) będzie zbiorem wierzchołków incydentnych z wierzchołkami w \(\displaystyle{ V_1}\). Na mocy warunku a), żaden wierzchołek należący do \(\displaystyle{ W_1}\) nie może należeć do jądra. Ponadto wierzchołki te spełniają warunek b). Usuńmy teraz z grafu wszystkie wierzchołki należące do \(\displaystyle{ W_1 \cup V_1}\) wraz z incydentnymi z nimi krawędziami. Otrzymamy graf \(\displaystyle{ G'}\) który oczywiście też jest DAGiem. W \(\displaystyle{ G'}\) analogicznie jak poprzednio wybieramy zbiór należących do jądra wierzchołków o zerowym stopniu wyjściowym \(\displaystyle{ V_2}\), oraz zbiór \(\displaystyle{ W_2}\). Usuwamy wierzcholki z obu tych zbiorów oraz incydentne z nimi krawędzie itd. Postępowanie kontynuujemy tak długo jak to możliwe tj. aż usuniemy z pierwotnego grafu wszystkie wierzchołki.
przykład:
czarne wierzchołki należą do jądra
dla nas jednak ważniejszy niż samo twierdzenie jest płynący z niego
Wniosek: w każdej skończonej, dwuosobowej grze o pełnej informacji, w której nie ma remisów, istnieje strategia wygrywająca dla któregoś z graczy.
Dowód: rozpatrzmy przypadek w którym P należy do jądra a K reprezentuje zwycięstwo gracza, który wykonał ostatni ruch zanim gra dobnęła do tej pozycji końcowej. Na początku pierwszy gracz spycha drugiego gracza na pozycję reprezentowaną przez wierzchołek nienależący do jądra. Drugi gracz może (na mocy definicji jądra) zepchnąć rywala na pozycję w jądrze itd. Drugi gracz więc zawsze może zepchnąć rywala na jądro, więc ma strategię wygrywającą. Pozostałe przypadki są analogiczne.

Nie należy podanego wniosku uogólniać na wszystkie gry dwuosobowe. Oto przykład gry która zawsze kończy się zwycięstwem jednego z graczy, ale żaden nie ma strategii wygrywającej:
W tym samym czasie każdy z graczy A i B pisze niezależnie od drugiego na swojej kartce pewną liczbę rzeczywistą. Kto napisze większą liczbę wygrywa. Jeśli napiszą takie same wygrywa gracz A.

Nadmieńmy jeszcze, że gdy dopuszczamy remisy, jeden z graczy ma strategię zapewniającą co najmniej remis.
Gry które mogą ciągnąć się w nieskończoność można odpowiednio zmodyfikować, orzekając remis po kilkukrotnym dojściu do tej samej pozycji.
ODPOWIEDZ