Seminarium Teorii Gier i Decyzji:

Streszczenie:
Miary centralności oparte na teorii gier na dobre zagościły w literaturze zajmującej się analizą sieci społecznościowych. Niedawno zainteresowano się możliwością zastosowania tych technik także w badaniu organizacji terrorystycznych. Za kluczowych graczy uznawane są tu osoby, którzy łączą ze sobą różne części siatki terrorystycznej. W moim referacie przedstawię proponowane w literaturze sposoby znajdowania ich oraz omówię algorytmy zaprojektowane przez nas do tego celu.

Streszczenie:
Gdy liczba krajów strefy euro przekroczy 18 (czyli gdy dołączy Litwa), to w Europejskim Banku Centralnym będzie stosowane głosowanie z rotacją, czyli nie wszystkie państwa strefy euro będą głosować za każdym razem. Taką sytuacją można na różne sposoby opisać za pomocą gry kooperacyjnej. Także na różne sposoby można obliczać wartość tej gry. Na konferencji SING w Budapeszcie mówiłam o wartości Shapleya . Te wyniki krótko tu przedstawię, a potem opowiem, jak dla takich gier można obliczać wartość Banzhafa.

Streszczenie:
Referat będzie poświęcony liniowym i efektywnym wartościom gier kooperacyjnych ze strukturą komunikacji (grafem nieskierowanym), spełniającym dodatkowo warunek neutralności operatora niedowierzania. Warunek ten sformułowałem w swoich pracach z 2002 r.; w ostatnich latach funkcjonuje on w literaturze pod nazwą "collusion neutrality".
Rene van den Brink (Games Econ. Beh. 2012) pokazał, że choć w tradycyjnych grach kooperacyjnych takich wartości nie ma (co jest oczywiste), to po nałożeniu na zbiór graczy struktury komunikacji będącej drzewem i dopuszczeniu collusion tylko w spójnych w tym drzewie grupach graczy wszystkie powyższe warunki są spełniane przez "wartości hierarchiczne" (Demange 2004) i ich kombinacje wypukłe. Ostatnio różni autorzy głównie koreańscy uzyskali nowe wyniki dotyczące charakteryzacji takich wartości w grach "na drzewach", pokazali, że wyniku v.d. Brinka nie da się przenieść na grafy komunikacji mające cykle, i postawili parę otwartych pytań, które krótko przedyskutuję uzupełniając o własne.

Streszczenie:
Przedstawiony zostanie inny dowód twierdzenia "o podziale kanapki" na podstawie pracy Golasińskiego, Dowód ten wykorzystuje wielomiany liniowo niezależne o współczynnikach rzeczywistych. Ponadto przedstawione zostaną inne problemy podziału dóbr.

Streszczenie:
Przedstawię kilka rezultatów i problemów otwartych dotyczących rozmaitych wersji znanego zagadnienia podziału naszyjnika. W ogólności naszyjnik może mieć postać pokolorowanego grafu, który chcemy rozciąć minimalną liczbą cięć, tak aby otrzymane części dało się sprawiedliwie rozdzielić. Ponadto, graf może być umieszczony w pewien sposób w przestrzeni, zaś dopuszczalne cięcia mogą podlegać dodatkowym, geometrycznym restrykcjom. Przedstawię również pewne powiązania tej tematyki z teorią liczb i kombinatoryką na słowach.

Streszczenie:
Kolorowanie krawędzi grafu nazwiemy poprawnym, jeśli zbiory jednokolorowe nie zawierają cykli. Wzorując się na przykładach z kolorowania wierzchołków grafu, rozważymy kilka różnych dwuosobowych gier, w których prezenter ujawnia część informacji o grafie, jak na przykład: należenie danej krawędzi do grafu, listę kolorów dozwolonych dla danej krawędzi grafu, zbiór krawędzi na których można użyć danego koloru itp., a algorytm ma za zadanie doprowadzić do poprawnego pokolorowania wszystkich krawędzi grafu. Liczbę kolorów zapewniającą algorytmowi strategię wygrywającą powiążemy z najmniejszą liczbą kolorów potrzebną do poprawnego pokolorowania off-line krawędzi grafu. Otrzymane wyniki uogólnimy do matroidów.

Streszczenie:
Eksperyment dotyczący choroby azjatyckiej przedstawia sytuację, w której pewnej społeczności grozi śmiertelna ("azjatycka") choroba. Są dwa programy zapobiegania tej chorobie. Badany ma wybrać jeden z nich. Części badanych przedstawiana jest wersja podkreślająca śmierć części populacji, a części badanych – przeżycie części populacji. W zależności od tego, którą wersję dostaną badani (obie wersje sa probabilistycznie równoważne) inne są proporcje wybieranych programów przez badanych - to, w jaki sposób sformułowano zagadnienie, odbija się na podjętej decyzji.
Przeprowadzony na studentach SGH eksperyment miał sprawdzić czy

1. Kompetencje matematyczne powodują zmniejszenie efektu framingu
2. Bodziec dotyczący probabilistycznego wysiłku poznawczego powoduje zmniejszenie efektu framingu
3. Kompetencje matematyczne powodują ze więcej badanych spostrzega rownowaznośc programów.
4. Bodziec dotyczący probabilistycznego wysiłku poznawczego powoduje ze więcej badanych spostrzega rownowaznosc programów.

Wyniki dotyczące pytań 1 i 2 są niejednoznaczne, odpowiedź na pytanie 3 jest pozytywna, na pytanie 4 jest pozytywna gdy chodzi o studentów kierunków matematycznych.

Streszczenie:
Zamierzam przedstawić probabilistyczne ujęcie wartości Shapleya i wartości Banzhafa dla gier prostych. Oba indeksy są prawdopodobieństwami wpływu stanowiska gracza na wynik głosowania przy różnych założeniach dotyczących podobieństwa kryteriów podejmowania decyzji przez poszczególnych graczy - jednolitości lub niezależności poparcia głosowanych alternatyw. Przedstawię rozwinięcie tej koncepcji - propozycję cząstkowej jednolitości graczy (dla ustalonej struktury jednolitości zgromadzenia) oraz interpretację społeczną tego ujęcia jako sposobu modelowania niejednolitości wzorców podejmowania decyzji.
Przedstawię propozycję szacowania struktury jednolitości zgromadzenia na podstawie wyników przeprowadzonych głosowań metodą najwyższej wiarygodności.

Streszczenie:
A technique is proposed to represent games in characteristic function form as games in normal form, enabling the former to exploit the concepts of solution of the latter. A new solution for games in characteristic function form is then introduced and some properties are found. A generalization of a result of von Neumann and Morgenstern is thus obtained.

Streszczenie:
Problem galerii sztuki (AGP) został sformułowany w roku 1973, kiedy to V. Klee zadał pytanie, ilu strażników czasami potrzeba, ale zawsze wystarcza, aby strzec galerię w kształcie dowolnego wielokąta prostego o n wierzchołkach. Po pierwszych wynikach dotyczących tego problemu (Chvatal 1975, Fisk 1978), zaczęto formułować dalsze problemy, m.in. te dotyczące kompozycji odcinków prostych. W wariantach tych można wyróżnić dwa podejścia. W pierwszym z nich odcinki stanowią przeszkody na płaszczyźnie - wtedy chcemy strzec samą płaszczyznę (O'Rourke 1985), w drugim natomiast odcinki modelują sieć ulic miasta, a zatem chcemy strzec ulice (Ntafos 1986). Celem referatu jest omówienie wybranych wariantów AGP dla kompozycji odcinków/prostych z ostatnich kilku lat, wraz z przykładowymi ideami dowodów niektórych twierdzeń. W szczególności poruszone zostaną następujące zagadnienia: patrolowanie ulic, minimalne drzewo strzegące, strażnicy z latarkami, ochrona komórek, k-nadajniki.

Streszczenie:
W grafie spójnym każde dwie najdłuższe ścieżki mają wspólny wierzchołek. Hipoteza mówi, że w grafie n-spójnym każde dwie najdłuższe ścieżki mają n wspólnych wierzchołków. Przedstawione zostaną dotychczasowe wyniki dotyczące tej hipotezy.

Streszczenie:
Niesymetryczne uogólnienia wartości Shapleya generowane przez wagi przypisywane poszczególnym graczom niezależnie od samej gry kooperacyjnej rozważał jako pierwszy już sam Shapley (1953). Pierwszą ich poważną analizę przeprowadzili Kalai i Samet (IJGT 1987), argumentując, że te "ważone wartości" mogą dobrze opisywać sytuacje, w których znaczenie gracza zależy nie tylko od jego "siły" w samej grze (mierzonej zwykłą wartością Shapleya), ale też od zewnętrznych czynników nie uwzględnianych przez grę, np. tego, jak duże grupy ludzi reprezentują poszczególni gracze. Niestety okazuje się (Monderer, Samet i Shapley IJGT 1992; Radzik EJOR 2012), że te ważone wartości potrafią zachowywać się bardzo źle pod względem monotoniczności, np. zwiększenie wagi gracza w grze prostej może, ceteris paribus, prowadzić do zmniejszenia jego wartości. Radzik (2012) podaje bardzo prosty warunek dostateczny monotoniczności ważonej wartości ustalonej gry ze względu na wagę gracza: gra winna leżeć w nieujemnym stożku przestrzeni $n$-osobowych gier kooperacyjnych wyznaczonym w bazie gier jednomyślności. Okazuje się jednak, że ten warunek jest bardzo mocny, w szczególności nie spełnia go żadna gra prosta (poza samymi grami z bazy). W referacie pokażę, że zastąpienie bazy gier jednomyślności innymi, częściowo nowymi bazami składającymi się także z symetrycznych gier prostych - prowadzące do modyfikacji samej definicji ważonych wartości - nie rozwiązuje tego problemu. Sugeruje to wyraźnie, że ważone wartości niekoniecznie nadają się do modelowania i należy je traktować raczej jako ciekawostkę matematyczną. Zastanowię się także nad innymi pojęciami monotoniczności ważonych wartości i przedstawię pewne negatywne wyniki również na ich temat.

Streszczenie:
We disprove a conjecture by Professor Zdzisław Skupień that every tree of order n has at most 2^{n/2} minimal dominating sets. We construct a family of trees for which the number of minimal dominating sets exceeds 1.4167^n. We also provide an algorithm for listing all minimal dominating sets of a tree in time O(1.4656^n). This implies that every tree has at most 1.4656^n minimal dominating sets.

Streszczenie:
Referat będzie kontynuacją roboczego seminarium z wiosny br. Wtedy zaproponowałem procedurę rozszerzania klasy gier "dylemat więźnia". Teraz chciałbym tę procedurę uogólnić na dowolne klasy dwuosobowych gier wymiaru 2x2. Ta procedura zawsze daje się przeprowadzić, ale wydaje się, że prowadzi do sensownych wyników tylko wtedy, kiedy strategie graczy są w jakiś naturalny sposób uporządkowane, np. stopień agresji, stopień skłonności do współpracy, zakres korzystania ze wspólnych zasobów itd. W szczególności przykładami będą: dylemat więźnia, gra jastrzębia i gołębia, gra świń. Z grą koordynacji jest trochę inaczej.

Streszczenie:
Omówione zostanie twierdzenie Bapata o wieloetykietowaniu wierzchołków triangulacji sympleksu. Uogólnia ono klasyczny lemat Spernera. Przedstawione zostaną zastosowania tego twierdzenia do dowodu istnienia tzw. konektorów, w szczególności istnienia strategii wygrywającej w grze Hex.

Streszczenie:
Opowiem (w sposób lekko nieformalny) o wrażeniach z lipcowej europejskiej konferencji teorii gier SING-9 w Vigo i o niektórych wysłuchanych tam referatach, w szczególności o japońskich pracach dotyczących baz przestrzeni gier kooperacyjnych.