Algorytmiczna teoria gier koalicyjnych 2015/16

Wykład odbywa się w poniedziałki w godzinach 14:15-15:45 w sali 4050.
Na ćwiczeniach są dwie grupy: pierwsza ma zajęcia w poniedziałki o 16:00 w sali 4050; druga we wtorki o 10:15 w sali 5070.

ĆWICZENIA 1. Wprowadzenie do ATGK (05-06.10.2015)

Przedstawiamy Algorytmiczną Teorię Gier Koalicyjnych, czyli mówimy co będziemy mówić na tym przedmiocie. Wprowadzamy gry koalicyjne, wartość Shapleya, jej aksjomaty i liczne zastosowania. [Slajdy z ATGK] Dla porządku, powtórzmy te definicje także tutaj.

Zbiór graczy będziemy oznaczali $N$. Koalicją nazywamy dowolny podzbiór graczy: $S \subseteq N$. Teraz, gra koalicyjna to funkcja która każdej koalicji przypisuje pewną liczbę rzeczywistą: $v: 2^N \rightarrow \mathbb{R}$. Przyjmujemy, że pusta koalicja ma zerową wartość: $v(\emptyset) = 0$. Prominentnym przykładem gry koalicyjne jest przykład dwóch firm które sprzedają koty i czapki po odpowiednio 4 i 2 złote, ale tworząc koalicje mogą sprzedawać koty w czapkach po 12 złotych. Ilustracja kotów i czapek znajduje się na slajdach.

Załóżmy, że wszyscy gracze współpracują i tworzą jedną, dużą koalicję wszystkich graczy, nazywaną grand coalition. Wartością gry $v$ nazywamy teraz podział wypłaty grand coalition ($v(N)$) pomiędzy graczy. Inaczej mówiąc, wartość gry to funkcja która bierze dowolną grę i zwraca wektor wypłat. Najsłynniejszą taką koncepcją jest wartość Shapleya, zdefiniowana następująco:

$$SV_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(|N|-|S|-1)!}{|N|!} (v(S \cup \{i\}) - v(S)).$$

Wartość $v(S \cup \{i\}) - v(S)$ jest nazywana wkładem marginalnym gracza $i$ do koalicji $S$ (czyli zyskiem jaki ma ta koalicja z dołączenia gracza $i$). Wartość Shapleya jest zatem ważoną sumą wkładów marginalnych. Interpretacja dla tej formuły jest następująca. Wyobraźmy sobie, że gracze przychodzą na pewne hipotetyczne miejsce spotkania jeden po drugim. Każdy gracz zmienia wartość obecnej już koalicji o swój wkład marginalny. Wartość Shapleya jest teraz średnim wkładem marginalnym gracza ze wszystkich możliwych permutacji w jakich gracze mogą przyjść na miejsce spotkania.

Wartość Shapleya jest sprawiedliwym sposobem podziału, bo spełnia aksjomaty sprawiedliwości (uczciwości) o których więcej powiemy za tydzień.

A na wykładzie było... Wprowadzenie do teorii gier.

ĆWICZENIA 2. Aksjomatyka wartości Shapleya (12-13.10.2015)

Rozmawiamy na temat aksjomatyki wartości Shapleya (tu: [slajdy z wartości Shapleya w trzech aksjomatykach]). Pokazujemy, że wszystkie cztery podstawowe aksjomaty Shapleya: Efektywność (EFF), Symetria (SYM), Addytywność (ADD) i Aksjomat Gracza-atrapy (NP) są potrzebne aby implikować jedną wartość przez podanie przykładów wartości (innych niż wartość Shapleya), które spełniają tylko 3 z 4 aksjomatów:

W końcu pokazujemy, że rzeczywiście implikują one jedną wartość - wartość Shapleya. W tym celu definiujemy klasę prostych gier zgodności (ang. unanimity games). Dla koalicji $S \subseteq N$, gra $u_S$ jest zdefiniowana następująco:

$$u_S(T) = \begin{cases} 1 & \mbox{jeżeli }S \subseteq T,\\0 & \mbox{wpp.} \end{cases}$$

Jak widzimy, w grze tej niezerowe wartości (równe $1$) mają tylko te koalicje które zawierają zbiór $S$.

Argumentujemy, że każdą grę można przedstawić jako liniową kombinację gier $u_S$. Przykładowo, gra z kotem i czapką ze slajdów wyżej to $4 \cdot u_{\{kot\}} + 2 \cdot u_{\{czapka\}} + 6 \cdot u_{\{kota, czapka\}}$. Formalnie, można pokazać, że prawdą jest następująca formuła:

$$v = \sum_{S \subseteq N} u_S \sum_{T \subseteq S} (-1)^{|S|-|T|} \cdot v(T).$$

Korzystając z Addytywności, wystarczy teraz pokazać zatem, że w grze $u_S$ aksjomaty implikują unikalny podział. To łatwo jednak zrobić. Wszyscy gracze nie należący do $S$ są graczami zerowymi (ich przyjście nie zmieni wartości z 0 na 1, bo wartość koalicji zależy wyłącznie od tego czy gracze z $S$ w niej są), więc z Aksjomatu Gracza-Zerowego (NP) muszą oni dostać wypłatę $0$. Pozostali gracze z Symetrii muszą dostać taką samą wypłatę. Z kolei wypłaty wszystkich muszą z Efektywności sumować się do $v(N) = 1$. A zatem dla $i \in S$ wypłata to $\frac{1}{|S|}$, a dla pozostałych graczy: $0$. To kończy dowód unikalności.

Łatwo sprawdzić, że wartość Shapleya spełnia wszystkie cztery aksjomaty. To ona musi być zatem tą unikalną wartością.

A na wykładzie było... Zaproszony wykład - Pan Marcin Waniek opowiadał o ukrywaniu się w sieci.

ĆWICZENIA 3. Gry głosowania ważonego (ang. Weighted Voting Games) (19-20.10.2015)

Zajmujemy się grami głosowania ważonego. W grach tych każdy gracz ma pewną ilość głosów $w_i$ i określony jest pewien próg (quota) $q$ potrzebnych głosów do przegłosowania ustawy. Będziemy zakładać, że próg jest próg jest większy niż połowa wszystkich głosów: $q > \frac{1}{2} \sum_{i \in N} w_i$. Gry te zapisujemy zwykle w taki sposób:

$$[q; w_1, w_2, \ldots, w_n].$$

Z tych danych dostajemy następującą definicję gry koalicyjnej:

$$v(S) = \begin{cases} 1 & \mbox{jeżeli }\sum_{i \in S} w_i \ge q,\\0 & \mbox{wpp.} \end{cases}$$

Koalicję z wartością $1$ nazywamy wygrywającą, a to z wartością $0$ -- przegrywającą.

Jak łatwo się domyślić, gry głosowania ważonego można używać jako model parlamentu - (gracze są wówczas partiami, a próg $q$ to - w naszym przypadku - połowa wszystkich głosów plus jeden). Dlatego w gorącym okresie wyborczym wybraliśmy akurat ten temat na zajęcia.

Siła gracza/partii nie jest prosta do określenia -- przykładowo jeżeli jeden gracz ma więcej niż $q$ głosów, to decyduje o wszystkim i jej siła jest równa $100%$, czyli $1$. Dlatego właśnie potrzebne są indeksy siły, które powiedzą jaka jest siła każdej partii.

Dwoma podstawowymi indeksami siły są: indeks siły Shapleya-Shubika (czyli po prostu wartość Shapleya zaaplikowana do gry $v$ zdefiniowanej powyżej) oraz indeks Banzhafa, będący (nieważoną) średnią wkładów marginalnych gracza:

$$BI_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{1}{2^{|N|-1}} (v(S \cup \{i\}) - v(S)).$$

Na zajęciach zajmujemy się najpierw policzeniem obu indeksów dla rozkładu mandatów jaki wynika z najnowszych sondaży wyborczych. Dla graczy $N = \{PIS, PO, KUKIZ, NOWOCZESNA\}$ gra głosowania ważonego przedstawia się wówczas tak:

$$[231; 221, 156, 45, 38].$$

W naszej analizie stwierdzamy, że zbiór koalicji wygrywających to:

$$W = \{\{PIS + cokolwiek\}, \{PO, KUKIZ, NOWOCZESNA\}\}.$$

Już teraz wiemy zatem, że wszystkie partie poza $PIS$ mają taką samą siłę w parlamencie, mimo różnej ilości mandatu.

Aby policzyć indeks Shapleya-Shubika dla $PIS$ zastanawiamy się w których permutacjach jego wkład marginalny będzie niezerowy. Łatwi zauważyć, że kiedy $PIS$ będzie w permutacji pierwszy to nie zmieni wartości koalicji: $v(\{PIS\}) - v(\emptyset) = 0 - 0 = 0$. Z kolei jeżeli $PIS$ będzie drugi lub trzeci, to zmieni koalicje przegrywającą na wygrywającą. W końcu, jak będzie czwarty to koalicje będzie już wygrywać bez niego i znowu będzie miał zerowy wkład marginalny. W efekcie, wychodzi nam, że $SV_{PIS}(v) = \frac{1}{2}$, a zatem z Efektywności mamy $SV_{PO}(v) = SV_{KUKIZ}(v) = SV_{NOWOCZESNA}(v) = \frac{1}{6}$.

Aby policzyć indeks Banzhafa nie rozważamy permutacji, a po prostu koalicje. $PIS$ nie zmieni wartości tylko dwóch koalicji - koalicji pustej i koalicji wszystkich pozostałych graczy. Jego indeks Banzhafa jest zatem równy $BI_{PIS}(v) = \frac{6}{8}$. Indeks Banzhafa nie spełnia Efektywności, indeks dla pozostałych partii musimy zatem także policzyć ręcznie. Łatwo jednak zauważyć, że każda inna partia zmienia przegrywającą koalicje na wygrywającą tylko jeżeli ta koalicja to $\{PIS\}$ albo $\{KUKIZ, NOWOCZESNA\}$ (w przypadku partii $PO$). Wszystkie pozostałe partie mają zatem wartości $BI_{PO}(v) = BI_{KUKIZ}(v) = BI_{NOWOCZESNA}(v) = \frac{2}{8}$.

Następnie, rozważamy jaki będzie rozkład sił, jeżeli do parlamentu wejdzie 7, a nie 4 partie. Korzystając z najnowszego sondażu IPSOS według którego tak jest podział mandatów przedstawia się następująco (kolejno: $PIS$, $PO$, $KUKIZ$, $ZL$, $NOWOCZESNA$, $PSL$, $KORWIN$):

$$[231; 187, 114, 41, 41, 26, 26, 25].$$

Z analogicznej analizy wychodzi nam, że siła $PIS$ zmalała jedynie minimalnie - $SV_{PIS}(v) = \frac{20}{42}$ - natomiast pozostałe partie podzieliły się prawie po równo resztą: $SV_{PO}(v) = \frac{4}{42}$, a dla pozostałych parti $SV_{i}(v) = \frac{3.(6)}{42}$.

W końcu, proponujemy ogólny algorytm do obliczenia indeksów siły. Z grubsza polega on na zliczeniu/wygenerowaniu wszystkich koalicji które są przegrywające bez danego gracza, a które zmienia on na wygrywające. Używamy do tego programowania dynamicznego oraz tablicy wielkości $q$ w której przechowujemy liczbę koalicji o danej sumie wag. Na koniec wiemy, że ostatnie $w_n$ wierszy (jeżeli liczyliśmy indeks siły gracza $n$) gracz zmieni na wygrywające. Dodając drugi wymiar -- wielkość koalicji -- możemy już policzyć nie tyle liczbę tych koalicji, ale i odpowiednie wagi potrzebne do wartości Shapleya.

Slajdy o weighted voting games. Powyższy algorytm zilustrowany jest na stronach 9-17.

A na wykładzie było... Cake cutting - problem podziału tortu.

ĆWICZENIA 4. Gry ważonego głosowania ograniczone grafem (26-27.10.2015)

Na dzisiejszych zajęciach rozważamy (może) bardziej realistyczny model parlamentu, w których niektóre partie mają zbliżone poglądy do siebie, a niektóre nie. Używamy do tego zaproponowanej przez (noblistę) Rogera Myersona koncepcji gry ograniczonej grafem. W tym modelu do gry $v$ dodajemy graf komunikacji $G$ pomiędzy graczami (gracze to wierzchołki), który ogranicza kooperację. Idea jest tu następuąca - jeżeli dana grupa nie może się ze sobą komunikować (nie jest połączona) to nie może osiągnąć korzyści z kooperacji. Obliczając wartość takiej koalicji bierzemy zatem pod uwagę sumę wartości spójnych fragmentów tej koalicji. Bardziej formalnie, jeżeli $K(S)$ to zbiór spójnych składowych grafu indukowanego przez zbiór wierzchołków $S$, to gra $v$ ograniczona grafem $G$ ma postać:

$$v/G(S) = \sum_{C \in K(S)} v(C).$$

Dla gier głosowania ważonego sytuacja komplikuje się niewiele -- koalicja graczy jest teraz wygyrwająca jeżeli istnieje w niej komponent (spójna składowa) który ma co najmniej $q$ głosów.

Dla gry $v/G$ chcemy policzyć teraz indeksy siły. Próbując zaaplikować algorytm z poprzednim zajęć napotykamy na problemy - nie możemy pamiętać tylko liczby koalicji o danej sumie wag, ponieważ kolejny gracz może się połączyć z niektórymi z nich, a z niektórymi nie. Musimy jakoś sobie z tym poradzić.

Zamiast generować i segregować koalicje podług sumy wag skupimy się na prostszym problemie obliczenia ile jest po prostu spójnych (indukowanych) podgrafów w grafie. Naszym pierwszym celem jest policzenie ich w drzewie binarnym.

Okazuje się, że dla drzewa wyznaczenie liczby podgrafów jest całkiem proste. Dobry algorytm przechodzi drzewo od liści do korzeni i w każdym wierzchołku trzyma informację o tym ile jest w poddrzewie ukorzenionym w tym wierzchołku spójnych podgrafów z nim i bez niego: $[N, M]$. Jak wyznaczać te liczby idąc bottom-up? Załóżmy, że wierzchołek $v$ ma dwóch synów $v_1$ i $v_2$ i w lewym poddrzewie ukorzenionym w $v_1$ jest $N_1$ podgrafów bez $v_1$ i $M_1$ podgrafów z $v_1$, a w prawym poddrzewie ukorzenionym w $v_2$ odpowiednio $N_2$ i $M_2$ podgrafów. Wypiszmy wszystkie spójne podgrafy w poddrzewie ukorzenionym w $v$:

Mamy zatem $M = N_1+N_2+M_1+M_2$ oraz $N = (N_1+1)(N_2+1)$.

Spróbujmy uogólnić nasz algorytm na przypadek kiedy oba poddrzewa nie są rozłączne, czyli $v_1$ i $v_2$ mogą być połączone ściężką nie przechodzącą przez $v$. Analogicznie możemy wyznaczyć liczbę podgrafów bez $v$, oraz z $v$ i maksymalnie jednym z wierzchołków $v_1, v_2$. Problem pojawia się jednak kiedy chcemy wyznaczyć liczbę podgrafów które zawierają wszystkie trzy wierzchołki. Nie możemy już po prostu wymnożyć liczby podgrafów z $v_1$ razy liczbę podgrafów z $v_2$, ponieważ te podgrafy mogą teraz na siebie zachodzić. Nie możemy jednak także wziąć (niezerowej w tym wypadku) liczby podgrafów z $v_1$ oraz $v_2$ - $v$ łącząc te wierzchołki może generować nowe podgrafy (jak w przypadku drzewa). Co zrobić? To dowiemy się na następnych zajęciach.

A na wykładzie było... Implementacja wartości Shapleya.

Zadanie 1, termin: 09.11.2015

Oblicz indeks siły Shapleya-Shubika oraz indeks Banzhafa dla austriackiego parlamentu. Podział mandatów jest następujący: SPO - 52, OVP - 47, FPO - 40, GRUNE - 24, STRONACH - 11, NEOS - 9. Przyjmujemy, że próg (quota) to zwykła większość głosów.

ĆWICZENIA 5. Dowolne gry ograniczone grafem (9-10.11.2015)

Zajmujemy się obliczaniem wartości Myersona, czyli wartości Shapley w grach ograniczonych grafem opisanych powyżej. Tym razem nie będziemy jednak ograniczać się do gier głosowania ważonego, a do dowolnej funkcji charakterystycznej. Tutaj są [slajdy o grach ograniczonych grafem].

Mogłoby się wydawać, że musimy przechodzić wszystkie koalicje, ale okazuje się, że nie jest to prawdą. Jeżeli będziemy rozpatrywać wkład marginalny do koalicji $C$ złożonej ze spójnych składowych $C_1, C_2, \ldots, C_k$ a gracz $i$ jest sąsiadem $C_1, C_2, \ldots, C_m$ spośród nich to jego wkład marginalny będzie równy $f(C_1 \cup C_2 \cup C_m \cup \{i\}) - (f(C_1) + f(C_2) + \ldots + f(C_m))$. Wkład ten nie zależy zatem od innych komponentów koalicji $C$ niż te, które $i$ łączy. Taki wkład (który możemy związać ze spójną koalicją wynikową $C_W = C_1 \cup C_2 \cup C_m \cup \{i\}$) musimy zatem policzyć dla dowolnego podzbioru nieistotnych wierzchołków. Z analizy na ćwiczeniach i permutacyjnej interpretacji wzoru na wartość Shapleya wyszło nam, że waga przy takim wkładzie marginalnym jest równa $\frac{(|C_W| - 1)!*|N(C_W)|!}{(|C_W| + |N(C_W)|)!}$ gdzie $N(C)$ to zbiór sąsiadów koalicji $C$.

Możemy zatem przejść wszystkie połączone koalicje i każdemu graczowi wewnątrz (i na zewnętrz) odpowiednio doliczyć jego wkład marginalny. Skupimy się zatem teraz na przejściu wszystkich połączonych koalicji. W teorii grafów oznacza to zatem enumerowania wszystkich spójnych indukowanych podgrafów grafu $G$. Zaczynamy od metody BFS która wygląda tak:

Następnie tworzymy jednak metodę DFS, która zwykle działa szybciej:

A na wykładzie było... Implementacja wartości Shapleya.

ĆWICZENIA 6. Aksjomatyka miar centralności (16-17.11.2015)

Gry koalicyjne są fajne, ale ich zasięg wykracza poza swoją dziedzinę. Tak jak matematyka uczy logicznego myślenia, tak gry koalicyjne powinny nas uczyć podejścia aksjomatycznego. Używamy go do zaksjomatyzowania miar centralności.

Miara centralności to funkcja która dla danego grafu i wierzchołka w nim ocenia jak ważny on jest bazując tylko na topografii sieci, czyli formalnie funkcja $F_v(G) \rightarrow \mathbb{R}$. Dla grafu $G = (V, E)$, trzy podstawowe miary centralności to:

Wymyślamy aksjomaty, które są spełnione przez możliwie jak najwięcej spośród tych trzech miar. Bez straty ogólności skupimy się na zajęciach poniedziałkowych. Pierwsze pomysły były takie:

Następnie pomyśleliśmy o czymś takim:

Potem doszliśmy do takich aksjomatów:

Po moich namowach proponujemy też inne aksjomaty:

... i na końcu takie:

A na wykładzie było... Nie wiem co :(.

ĆWICZENIA 7. Aksjomatyka miar centralności - nowa miara centralności na A (16-17.11.2015)

Przedstawiamy nową miarę centralności opartą na wartości Shapleya. Niestety nie mogę tu o niej pisać, ponieważ jest ściśle tajna.

A na wykładzie było... Nie wiem co :(.

Zadanie 2, termin: 30.11.2015

Zadanie dotyczy sieci wkładów marginalnych (ang. MC-Nets). Jedna reguła MC-Nets wygląda tak: $$p_1 \land p_2 \land p_l \land \lnot n_1 \land \lnot n_2 \land \ldots \land \lnot n_k \rightarrow V.$$ Wartość koalicji $S$ w takiej grze opisanej tą regułą jest zdefiniowana następująco: $$v(S) = \begin{cases} V & (\forall_{i \in \{1,\ldots,l\}} p_i \in S) \land (\forall_{i \in \{1,\ldots, k\}} n_i \not \in S) \land (S \not = \emptyset),\\0 & \mbox{wpp.}\end{cases}$$ Gra opisana zbiorem reguł to suma gier opisanych każdą z nich.

(A) Oblicz wartość Shapleya w grze opisanej regułą MC-net, czyli sieci wkładów marginalnych: $$\lnot n_1 \land \lnot n_2 \land \ldots \land \lnot n_k \rightarrow V.$$
(B) Załóżmy, że każdy z graczy ma pewną wydajność wyrażoną liczbą $w_i \in \mathbb{R}$. Opisz grę $(N, v)$ w której wartość koalicji to wydajność najlepszego gracza, czyli $$v(S) = max_{i \in S} \ w_i$$ za pomocą liniowej liczby reguł MC-Net.

ĆWICZENIA 8. Core (30-31.11.2015)

Shapley Value wskazuje nam jednoznacznie podział wypłaty $v(N)$ między graczy, który jest "jedynym sprawiedliwym" (według Shapleya). W literaturze gier koalicyjnych istenieje jednak więcej koncepcji podziału, które zwykle odnoszą się nie do sprawiedliwości, a stabilności danego podziału.

Bez wątpienia najpopularniejszą koncepcją jest rdzeń (ang. core). Mówimy, że dany podział wypłaty jest rdzeniu jeżeli nie istnieje koalicja która sama osiągnęła by więcej niż dostaje w tym podziale. Formalnie: $$ Core(v) = \{[x_1,\ldots,x_n] : \sum_{i \in N} x_i = v(N), \forall_{S \subseteq N} (\sum_{i \in S} x_i \ge v(S)) \}.$$

Przykładowo w grze $v(S) = |S|$ według tej koncepcji wszyscy powinni otrzymać wypłatę $1$: jeżeli ktoś dostanie mniej, wówczas będzie mógł się wydzielić; więcej nikt nie może dostać, jeżeli nikt nie dostanie mniej. Rdzeń nie jest jednak zwykle jednym podziałem, a całym ich zbiorem (niestety często zbiorem pustym). Np. w grze $v(\{1,2,3\})=v(\{1,2\})=v(\{1,3\})=v(\{2,3\})=1$ i $v(1)=v(2)=v(3)=0$ rdzeń jest pusty - każda para powinna dostać co najmniej $1$, ale wtedy wszyscy dostaną co najmniej $1.5$.

Na zajęciach rozważamy też inne gry:

A na wykładzie było... Team games.

ĆWICZENIA 9. Bargaining set (7-8.12.2015)

Rdzeń (patrz: ćwiczenia 8) jest bardzo restrykcyjną koncepcją, dlatego w literaturze proponowane są inne, które zwykle patrzą więcej niż jeden krok w przyszłość - czy "sprzeciwu" tej koalicji nie da się jakoś odeprzeć? Czy inni gracze nie mają riposty na ten argument? Tu pojawia się koncepcja bargaining set (pl. zbiór targowania?). Formalnie, rozważmy pewien podział wypłaty $[x_1, \ldots, x_n]$. Niech sprzeciwem gracza $i$ wobec gracza $j$ będzie koalicja $S$ w której jest $i$ i nie ma $j$ oraz pewien podział wypłaty $v(S)$ między koalicję, że wszyscy gracze otrzymują w nim więcej niż w pierwotnym podziale: $$\text{Sprzeciw } i \rightarrow j: (S, y), i \in S, j \not \in S, \forall_{k \in S} (y_k > x_k).$$ Teraz, ripostą na ten sprzeciw będzie koalicja $T$ (oczywiście z graczem $j$, ale bez gracza $i$) oraz pewien podział wypłaty $v(T)$ w którym wszyscy gracze którzy są też w $S$ (czyli Ci podkupowani: $S \cap T$) dostają co najmniej tyle co dostawali od $i$, a wszyscy inni - co najmniej tyle co w pierwotnym podziale. $$\text{Riposta } j \rightarrow i: (T, z), j \in S, i \not \in S, \forall_{k \in T \cap S} (z_k \ge y_k), \forall_{k \in T \setminus S} (z_k \ge x_k).$$ Teraz bargaining set to zbiór takich podziałów wypłaty, że na każdy Sprzeciw jest Riposta. Pisząc trochę nieformalnie wygląda on więc tak: $$ BargainingSet(v) = \{[x_1,\ldots,x_n] : \forall_{\text{Sprzeciw }i \rightarrow j} \exists_{\text{Riposta }j \rightarrow i}\}.$$

Przypomnijmy grę większościową dla trzech graczy z poprzednich ćwiczeń. Miała ona pusty rdzeń, natomiast bargaining set nie zawiera podziałów innych niż $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$: jeżeli najbogatszy gracz będzie dostawał $\frac{1}{3}+c$, wówczas jeden z pozostałych graczy może sprzeciwić się, dać sobie wypłatę jaką miał (plus epsilon), a trzeciemu graczowi dać resztę. Najbogatszy gracz nic nie odpowie - nie może on podkupić trzeciego gracza, bo wtedy jemu samemu zostałoby mniej niż miał na początku. Oczywiście bargaining set zawiera się w rdzeniu.

A na wykładzie było... Gry z restrykcjami.

Zadanie 3, termin: 21.12.2015

Zdefiniujmy grę "moja ciocia i ja" następująco: dla 4 graczy $\langle Ciocia,Ja,Brat,Siostra \rangle$ grupa graczy ma wartość $1$ jeżeli zarywa się pod nią ławka (i $0$ wpp), przy czym przyjmujemy, że ławka utrzymuje samą Ciocię lub maksymalnie dwie osoby z rodzeństwa. Udowodnij, że bargaining set składa się z podziałów $\{(1-3 \alpha, \alpha, \alpha, \alpha): \frac{1}{7} \le \alpha \le \frac{1}{5}\}$.

ĆWICZENIA 10. Gry koalicyjne z efektami zewnętrznymi (14-15.12.2015)

Zajmujemy się grami koalicyjnymi z efektami zewnętrznymi. W grach tych wartość koalicji może zależeć nie tylko od jej członków, ale także od tego jakie koalicje tworzą inni gracze. Gry te zwykle ilustrujemy psem w kapeluszu - profit firmy która sprzedaje psy w kapeluszu zależy od tego czy firma która sprzedaje koty połączy się z firmą która sprzedaje czapki.

Staramy się zaproponować rozszerzenie wartości Shapleya do gier z efektami zewnętrznymi. Próbujemy to zrobić od strony obliczeniowej - wartość Shapleya jest średnim wkładem w procesie wychodzenia (zwykle wchodzenia, ale tu wygodniej patrzeć na wychodzenie) graczy z grand coalition. Dla danej permutacji gracz wychodząc zabiera swój wkład marginalny z opuszczanej koalicji (czyli różnicę w wartości koalicji z nim i bez niego: $v(C \cup \{i\}) - v(C)$). W grach z efektami zewnętrznymi wartość koalicji po odejściu gracza zależy jednak od układu graczy którzy są poza nią. Nasz pomysł opiera się na przypisaniu tym przejściom różnych prawdopodobieństw. Dzięki temu dla danej permutacji policzymy wypłatę gracza jako wartość oczekiwaną z tego procesu. Wygląda to jakoś tak jak na rysunku poniżej:

Pozostaje zaproponować sensowne prawdopodobienstwa $\alpha_1, \alpha_2, \ldots$. Upraszczając trochę sytuację zauważamy, że tak naprawdę koncentrujemy się na patrzeniu na podział graczy jaki powstaje (na zewnątrz). Staramy się zatem zaproponować rozkład prawdopodobieństwa $p$ na zbiorze wszystkich podziałów zbioru $\{1,2,\ldots,n\}$ (przy czym patrzymy na to bardziej jak na proces stochastyczny).

Zaproponowaliśmy parę koncepcji:

Wszystkie pomysły ocenialiśmy według trzech kryteriów: dodatniość (ang. positivity), czyli czy wszystkie wagi są dodatnie; odporność na przeploty (ang. interchangeability), czyli czy prawdopodobieństwo powstania danego układu zależy od wybranej permutacji (np. u Bolgera dla permutacji $1,2,3$ układ $\{\{1,2\}, \{3\}\}$ powstanie z prawdopodobieństwem $\frac{1}{4}$, a $\{\{1,3\}, \{2\}\}$ - $\frac{1}{6}$) oraz odporność na dodatkowych graczy (ang. consistency), czyli czy prawdopodobieństwo podziału zależy od ilość graczy (np. u Hu i Yanga przy dwóch graczach prawdopodbieństwo dołączenia $1$ do $2$ przy permutacji $1,2,\ldots$ jest równe $\frac{1}{2}$, a przy trzech - jak na rysunku wyżej - $\frac{2}{5}$). Z powyższych propozycji tylko jedna spełnia wszystkie trzy kryteria i jest to wartośc Macho-Stadlera et al..

ĆWICZENIA 11. Coalition Structure Generation (21-22.12.2015)

Wyjątkowo zastępuje mnie Pan Tomasz Michalak....

A na wykładzie było... Zajmujemy się problemem znalezienia optymalnej struktury koalicyjnej, czyli podziału, który maksymalizuje sumę wypłat graczy (tu [slajdy o coalition structure generation], od strony 56). Prezentujemy algorytm Dynamic Programming (w slajdach od strony 60). Generalnie algorytm polega na tym, że dla każdej koalicji sprawdzamy optymalny podział ale tylko na dwie części. Teraz dla każdej wynikowej części rozpatrujemy dalsze podziały na dwa. Gdybyśmy robili to głupio, to byśmy powtarzali obliczenia, np. dzieląc $\{1,2,3\}$ na $\{1,2\}$ i $\{3\}$ oraz $\{1,2,3,4\}$ na $\{1,2\}$ i $\{3,4\}$ musimy w obu przypadkach sprawdzać czy wiekszą wartość ma koalicja $\{1,2\}$ czy suma koalicji $\{1\}$ i $\{2\}$. Stosując programowanie dynamicznie obliczamy optymalne podziały od najmniejszych koalicji, a potem tylko do nich sięgamy.

Zadanie 4, termin: 18.01.2016

Udowodnij, że algorytm DP do wyszukiwania optymalnej struktury koalicyjnej dla $n$ graczy działa w czasie $\mathcal{O}(3^n)$.

ĆWICZENIA 12. Gry koalicyjne z efektami zewnętrznymi - inne koncepcje (11-12.01.2016)

Wracając do tematu wartości Shapleya dla gier z efektami zewnętrznymi omawiamy inne (niż podejście marginalne) koncepcje (tu [slajdy na temat innych koncepcji]). Mówimy o podejściu uśredniania (ang. average approach), zbytnim uśrednianiu (wartości Albizuriego), które nie spełnia NP oraz o innym schemacie formowania się koalicji Grabisha i Funakiego. Zgodnie z ich koncepcją decydujemy się kumulować wypłatę spowodowaną łączeniem zewnętrznych koalicji, co spotyka się z ożywioną dyskusją (na slajdach jest przykład o co chodzi).

Zadanie 5, termin: 25.01.2016

Zaprojektuj nierekurencyjny algorytm, który wygeneruje wszystkie podziały zbioru $\{1,2,\ldots,n\}$ podług ich rozmiarów (tzn. najpierw podziały na jedną koalicję, potem podziały na dwie koalicje, itd). Inaczej formułując ten warunek moglibyśmy napisać "stwórz klasę PartitionGenerator z funkcją first() i next(), która zwracać będzie kolejne podziały zbioru według określonego porządku". W tym zadaniu można korzystać z komputerów, ale algorytm trzeba opisać.

Zadanie 6, termin: 25.01.2016

Na zajęciach poznaliśmy dwa algorytmy enumerowania indukowanych spójnych podgrafów: za pomocą DFSa oraz BFSa. Udowodnij, że pierwszy z algorytmów dla kliki $n$-elementowej wykonuje asymptotycznie dwa razy więcej sprawdzeń krawędzi niż drugi z nich (linie 9 w obu algorytmach).
Wskazówka: pokaż, że DFS wykonuje $2^{n-2} (n^2-n+4) - (n+1)$ sprawdzeń krawędzi, a BFS: $2^{n-1} (n^2-3n+2) + (n-1)$.



Zasady gry

Punkty doświadczenia można zdobywać za:

Wymagana punktacja na poszczególne levele.

Nie, LEVEL 6 jest nieosiągalny. Prowadzący mogą się pochwalić LEVELem 12.

Zadania oddajemy na kartkach (mogą być napisane ręcznie, ale BARDZO CZYTELNIE).


Oskar Skibski (oski@mimuw.edu.pl), Wydział Matematyki, Informatyki i Mechaniki