Cwiczenia z Algorytmicznych Aspektow Teorii Gier

• Gra Hex. Dowod Hex Theorem, czyli, ze nie moze byc remisu. Dowod J. Nasha, ze pierwszy gracz ma strategie wygrywajaca (metoda strategy-stealing).
• Gra Nim. Charakteryzacja pozycji wygrywajacych. Nieskonczony Nim: wysokosc slupka zapalek moze byc dowolna liczba porzadkowa mniejsza od omega^omega. Partie nieskonczonego Nima sa skonczone. Charakteryzacja pozycji wygrywajacych.
• Gra Chomp (Czekolada). Gramy na punktach kratowych prostokata [0,M]x[0,N]. Gracze na przemian wybieraja punkt (x,y) i zjadaja wszystko, co jest w prostokacie wyznaczonym przez (x,y) i (M,N). Trzeba zjesc co najmniej jedna kostke w kazdej rundzie. Przegrywa ten, kto zje ostatnia kostke. Pierwszy gracz ma strategie wygrywajaca (metoda strategy-stealing).

• Pebbling Games. Gramy na spojnych skierowanych grafach (acyklicznych). Cel: polozyc kamyk na ustalonym wierzcholku. Dostepne ruchy: podniesienie kamyka z wierzcholka, polozenie kamyka w wierzcholku, pod warunkiem, ze na koncach wszystkich wchodzacych strzalek leza kamyki (jak brak wchodzacych strzalek, to tez dobrze). Pytanie: ile potrzeba kamieni? Zeby polozyc kamien w korzeniu drzewa o wysokosci h, wystarcza h+2 kamienie. Do przemyslenia: wystarczy O(log(n)), gdzie n jest liczba wierzcholkow drzewa. Istnieje graf o stopniu wejsciowym 2, ktorego pewien wierzcholek wymaga pierwiastek z n kamieni.
• Alternujace maszyny Turinga, czyli MT ze stanami uniwersalnymi i egzystencjalnymi. Klasa AP sklada sie z jezykow rozpoznawanych przez alternujace MT w czasie wielomianowym. QSAT jest AP-zupelny.
• Geografia. Gracze buduja sciezke w grafie skierowanym. Startuja z ustalonego wierzcholka i wybieraja na przemian krawedzie. Wierzcholki nie moga sie powtarzac. Przegrywa ten, kto nie moze zrobic ruchu. Problem rozstrzygniecia, czy dla danego grafu pierwszy gracz ma strategie wygrywajaca jest AP-zupelny (redukcja QSAT).
• O problemach AP-zupelnych mozna poczytac w: Christos H. Papadimitriou, Zlozonosc obliczeniowa, WNT 2002.

• Jeszcze o Geografii. Istnieje taki graf do geografii, ze I gracz ma strategie wygrywajaca, ale nie ma pozycyjnej strategii wygrywajacej. Geografia pozostaje AP-zupelna nawet wtedy, gdy ograniczymy sie do grafow planarnych (przerabiamy grafy powstale z redukcji QSAT na grafy planarne).
• AP = PSPACE. Pokazalismy, ze ATIME (f(n)) jest zawarte w DSPACE (f(n)^2) oraz DSPACE (f(n)) zawarte w ATIME (f(n)^2) dla funkcji f co najmniej liniowej i konstruowalnej.
• Literatura: Christos H. Papadimitriou, Zlozonosc obliczeniowa, WNT 2002.

• Go jest PSPACE-zupelne. Rozwazamy nastepujacy problem: Czy biale maja strategie wygrywajaca dla danej sytuacji poczatkowj na planszy NxN? Dowodzimy PSPACE-zupelnosci tego problemu redukujac do niego planarna wersje Geografii. Dowod mozna znalezc w ksiazce Papadimitriou.
• Sabotage. Gramy na skierowanym multigrafie z wyroznionym wierzcholkiem poczatkowym i koncowym. Ewa (gracz lokalny) rozpoczyna w wierzcholku poczatkowym i w kazdej rundzie przesuwa sie do ktoregos z sasiednich wierzcholkow. Adam (gracz globalny) w kazdej rundzie usuwa jedna krawedz. Ewa wygrywa jesli uda jej sie dojsc do wierzcholka koncowego. Pokazujemy, ze problem rozstrzygniecia, ktory z graczy ma strategie wygrywajaca jest PSPACE-zupelny. Dowod przebiega przez redukcje QSAT. Literatura: C. Loeding, Ph. Rohde, Solving the sabotage game is PSPACE-hard.
• Wartosc drzewa gry. Dla kazdego algorytmu deterministcznego obliczajacego wartosc drzewa gry istnieje takie drzewo, dla ktorego algorytm bedzie musial zajrzec do wszystkich lisci. Dowod: rozwazamy gre miedzy Algorytmem i Spoilerem. Algorytm zadaje Spoilerowi pytania o wartosci w lisciach. Przez indukcje ze wzgledu na wysokosc drzewa gry pokazujemy, ze Spoiler ma strategie pozwalajaca na odpowiadanie w taki sposob, zeby istnialy drzewa o dwoch roznych wartosciach, zgodne z dotychczasowymi odpowiedziami, dopoki Algorytm nie spyta o wszystkie liscie.

• Zrandomizowany algorytm obliczania wartosci drzewa gry dla dowolnego drzewa wejsciowego odwiedza srednio 3^(h/2) lisci. Patrz: Motwani, Randomized Algorithms, Rozdz. 2.
• Zadanie 1 z pierwszej serii zadan zaliczeniowych z 2003 roku. Rozwiazanie: adaptacja algorytmu MIN-MAX.
• Policjanci i zlodziej jako przyklad gry na przetrwanie. Gramy na cyklu o n wierzcholkach. Dwaj policjanci zajmuja dwa wybrane wierzcholki. Nastepnie zlodziej wybiera wierzcholek. Dalej w kazdej rundzie jeden z policjantow moze sie ruszyc na sasiedni wierzcholek, a nastepnie zlodziej przechodzi na dowolny wierzcholek. Zlodziej przegrywa, gdy na obu sasiednich wierzcholkach stoja policjanci. Zlodziej ma strategie wygrywajaca wttw, gdy n>6. Patrz: notatki do wykladu z 2003 roku.
• Rozwijanie grafow i zwijanie regularnych drzew. Mowimy, ze (nieskonczone) drzewo T jest regularne jesli ma tylko skonczenie wiele nieizomorficznych poddrzew. Dowolna arene G z ustalona pozycja poczatkowa p mozna rozwinac do areny T_G bedacej (byc moze nieskoncznym) drzewem regularnym w taki sposob, zeby gry na przetrwanie na G i T_G byly rownowazne (pozycjami w T_G sa sciezki w G wychodzace z p). Arene T, ktora jest regularnym drzewem, mozna zwinac do rownowaznej skonczonej areny G_T (pozycjami w G_T sa nieizomorficzne poddrzewa T).

• Pushdown games. Problem rozwiazywania gier na grafach konfiguracji automatu ze stosem jest EXPTIME-zupelny.
  Literatura: I. Walukiewicz, Pushdown processes: games and model checking.
• Gra Banacha-Mazura. Gracze konstruuja zstepujacy ciag odcinkow otwartych zawartych w odcinku jednostkowym [0,1]. Ewa wybiera 1 odcinek, Adam wybiera 2 odcinek, Ewa wybiera 3 odcinek, ... Ewa wygrywa, jesli w przecieciu odcinkow znajdzie sie punkt z zadanego z gory zbioru F. Pytanie: Jak "duzy" musi byc zbior F zeby Ewa miala strategie wygraywajaca? Jesli F jest otwarty lub dopelnienie F jest przeliczalne, to Ewa ma strategie wygrywajaca. Problem do zastanowienia: znalezc slabszy warunek wystarczajacy, najlepiej konieczny (bez zagladania do Wikipedii).

• Hierarchia borelowska. Mowimy, ze zbior A jest typu F_sigma jesli mozna go przedstawic w postaci przeliczalnej sumy zbiorow domknietych. Dualnie, zbior A jest typu G_delta jesli mozna go przedstawic w postaci przeliczalnego przeciecia zbiorow otwartych. Z praw DeMorgana wynika, ze dopelnienie zbioru typu F_sigma jest zbiorem typu G_delta i odwrotnie. Kazdy zbior domkniety jest oczywiscie zbiorem typu F_sigma. Cwiczenie: pokazac, ze jest rowniez zbiorem typu G_delta. Ponownie z praw DeMorgana dostajemy, ze zbiory otwarte sa G_delta i F_sigma. Rodzina zbiorow borelowskich ustalonej przestrzeni topologicznej, to domkniecie rodziny zbiorow otwartych ze wzgledu na operacje przeliczalnej sumy i dopelnienia. Uwaga: zbiorow borelowskich nie jest za duzo. W szczegolnosci istnieja zbiory nieborelowskie (choc w przyrodzie rzadko sie z nimi stykamy).
• Topologia w przestrzeni nieskonczonych ciagow zero-jedynkowych. Definiujemy metryke w przestrzeni {0,1}^omega wzorem
  d(x_1 x_2 ... , y_1 y_2 ...) = 2^(-h), gdzie h=min{i: x_i != y_i}.
  Pytanie: czym jest kula o promieniu 2^(-n) dookola slowa x_1 x_2 ... ? Zbior A zawarty w {0,1}^omega jest domkniety wttw, gdy jest zbiorem galezi pewnego nieskonczonego drzewa binarnego. Zbior B jest otwarty wttw, gdy jest postaci M{0,1}^omega dla pewnego antylancucha M zawartego w {0,1}*.
• Moga sie przydac notatki do wykladu z 2003 roku.

• Charakterystyka zbiorow G_delta. Charakterystyke zbiorow otwartych mozna wyrazic rowniez tak: A jest otwarty wttw, gdy jest postaci \exists M dla pewnego antylancucha M zawartego w {0,1}*, tzn. ze zbior A sklada sie ze slow, ktorych pewien (skonczony) prefiks nalezy do M. Korzystajac z tego faktu pokazujemy, ze zbior B jest typu G_delta wttw, gdy jest postaci \exists ^\infty N, dla pewnego zbioru N zawartego w {0,1}*, to znaczy sklada sie ze slow, ktore maja nieskonczenie wiele (skonczonych) prefiksow w zbiorze N.
• Determinacja gier. Rozwazamy ogolne gry postaci G=(Pos_E, Pos_A, Move, F), gdzie F jest podzbiorem Pos^omega. Ewa wygrywa rozgrywke wttw, gdy ciag odwiedzanych pozycji nalezy do F. Przyjmujemy na Pos^omega metryke taka, jak dla {0,1}^omega. Charakterystyki zbirow otwartych, domknietych, G_delta uogolniaja sie naturalnie na ten przypadek. Korzystajac z charakterystyki zbiorow G_delta pokazujemy, ze gry z warunkiem wygraywajacym F typu G_delta sa zdeterminowane. Dowod przebiega przez rozwiniecie grafu gry do drzewa i zinterpretowanie warunku wygrywajacego F jako warunku powtorkowego w grze na wynikowym drzewie (za dobre pozycje przyjmujemy skonczonwe sciezki ze zbioru N). Teza wynika z determinacji gier powtorkowych. Zachodzi duzo ogolniejsze twierdzenie Martina: zdeterminowana jest kazda gra z borelowskim warunkiem wygrywajacym F.

• Jeszcze troche topologii. Zbior (0*1)^omega nie jest typu F_sigma (dowod przez rozumowanie przekatniowe).
• Duzo iteracji. Niech Remain_A (M) = gfp Y. Adam(Y /\ M). Fakt: Remain_A (M) to pozycje, z ktorych Adam ma strategie zeby w pierwszym ruchu wejsc do M i juz tam pozostac (lub wygrac w skonczonej liczbie ruchow). Cwiczenie 1: Zaproponowac gry powtorkowe (Pos_E, Pos_A, Move, L) o skonczonym rozgalezieniu, dla ktorych trzeba 1, 2, 3, ..., omega, omega+1, omega+2, ..., omega*2, omega*3, ..., omega*omega, ... iteracji operatora Remain_A (X \/ dopelnienie(L)) na zbiorze pustym, aby otrzymac najmniejszy punkt staly. Cwiczenie 2: Zaproponowac arene, dla ktorej potrzeba dowolna liczbe (porzadkowa!) iteracji.

• Globalizacja lokalnych strategii. Rozwazamy gry postaci (Pos_A, Pos_E, Mov, W), gdzie W jest zbiorem nieskonczonych sciezek na arenie, ktore sa wygrywajace dla Ewy. Pozostale sciezki sa wygrywajace dla Adama. Nie zakladamy nic o mocy zbioru pozycji. Zalozmy, ze Ewa ma pozycyjna strategie wygrywajaca z kazdej pozycji v z pewnego ustalonego zbioru Z. Czy jest prawda, ze Ewa ma globalna (niezalezna od pozycji poczatkowej) pozycyjna strategie wygrywajaca ze zbioru Z?
• Rozwiazaywanie gier parzystosci jest w NP i co-NP. Rozwazmy nastepujacy problem: Dana gra parzystosci G i ustalony wierzcholek v. Pytamy, czy Ewa ma strategie wygrywajaca z v. Na mocy twierdzenia o pozycyjnej determinacji gier parzystosci, jedno z dwojga ma pozycyjna strategie wygrywajaca. Zatem swiadkiem dla "Ewa ma strategie z v" jest pozycyjna strategia dla Ewy, zas swiadkiem dla "Ewa nie ma strategii z v" jest pozycyjna strategia dla Adama. Pozostaje pokazac, ze sprawdzenie, czy strategia pozycyjna jest wygrywajaca mozna przeprowadzic w czasie wielomianowym. Pokazac, ze wystarczy nastepujacy fakt: jesli przeciwnik ma zawsze tylko jedna mozliwosc ruchu, to mozemy w czasie wielomianowym obliczyc, kto ma strategie z zadanej pozycji. Udowodnic ten fakt.

• Gry z warunkiem Mullera. Warunek Muullera: {F_1, F_2, ..., F_r}, F_i jest zbiorem pozycji. Dla rozgrywki v_0 v_1 ... przez inf(v_0 v_1 ...) oznaczamy zbior wszystkich pozycji pojawiajacych sie nieskonczenie czesto wsrod v_0 v_1 .... Ewa wygrywa rozgrywke v_0 v_1 ..., o ile inf(v_0 v_1 ...)=F_i dla pewnego i. Zadanie: skonstruowac oszczednie rownowazna gre z warunkiem parzystosci.

• Etykiety na krawedziach. Rozwazamy areny skonczone z rankami na krawedziach. Dopuszczamy wiecej niz jedna krawedz z v do w, jesli maja rozne ranki. Ewa wygrywa rozgrywke e_1, e_2, ... w grze ze zbiorem wygrywajacym W, o ile ciag rank(e_1), rank(e_2), ... nalezy do zbioru W. O zbiorze W powiemy, ze jest pozycyjnie zdeterminowany w sensie wierzcholkowym (krawedziowym), jesli kazda skonczona arena z rankami w wierzcholkach (na krawedziach) i warunkiem wygrywajacym W zadaje pozycyjnie zdeterminowana gre. Wykazac, ze pozycyjna determinacja zbioru W w sensie krawedziowym implikuje determinacje w sensie wierzcholkowym. Czy jest rowniez odwrotnie?
• Gry Ehrenfeuchta-Mycielskiego. Rozwazamy areny skonczone z kosztem (dodatnim lub ujemnym) c(v,w) przypisanym kazdej krawedzi. Zakladamy, ze z kazdej pozycji istnieje ruch. Wariant nieskonczony: po rozgrywce v_1, v_2, ... Adam placi Ewie kwote liminf_n [c(v_1, v_2) + ... + c(v_{n-1}, v_n)]/n. Cwiczenie: wyplata jest zawsze skonczona. Wariant skonczony: rozgrywke konczymy w momencie, gdy zamkniety zostanie pierwszy cykl i Adam placi Ewie srednia wartosc z tego cyklu, tzn. dla cyklu v_1, v_2, ..., v_m wyplata wynosi [c(v_1, v_2) + ... + c(v_{m-1},v_m)]/m.
  Zadanie: Zalozmy, ze Ewa posiada strategie pozycyjna, ktora w wariancie skonczonym gwarantuje jej wyplate nie mniejsza niz a. Pokazac, ze rowniez w wariancie nieskonczonym wyplata bedzie nie mniejsza niz a.

• Aukcje. W aukcji biora udzial gracze 1,2, ... , n, chcacy uzyskac pewien obiekt w zamian za oplate. Gracz i wycenia obiekt ma v_i, przy czym v_1 > v_2 > ... > v_n. Gracze jednczesnie podaja stawki a_i. Obiekt dostaje gracz o najnizszym numerze sposrod tych, ktorzy podali najwyzsza stawke. Gracz placi za przedmiot stawke, ktora sam podal. Sformalizowac aukcje jako gre strategiczna. Przenalizowac rownowagi Nasha. Udowodnic, ze w kazdej rownowadze Nasha obiekt kupuje gracz 1.
• Aukcje drugiej stawki. Roznica w stosunku do powyzszego jest jedynie w cenie: kupujacy placi najwyzsza sposrod stawek ktore podali pozostali gracze. Sformalizowac ten wariant aukcji jako gre strategiczna. Cwiczenie 1: pokazac, ze stawka v_i jest strategia slabo dominujaca dla gracza i, tzn. dla zadnych ustalonych ruchow przeciwnikow gracz nic nie zyskuje zmieniajac v_i na inna strategie. Cwiczenie 2: pokazac, ze istnieja rownowagi Nasha, w ktorych obiektu nie kupuje gracz 1.
• Twierdzenie Brouwera: kazda ciagla funkcja z kwadratu jednostkowego w siebie posiada punkt staly. Dowod za pomoca twierdzenia o remisach w heksie.