Seminarium Teorii Gier i Decyzji:

Streszczenie:
Let T be a tree with n vertices. The distance matrix of T is an $n \times n$ matrix $D = [d_{ij} ]$, with d_{ij} being the distance between vertices i and j if i is not equal to j, and d_{ii} = 0. According to a classical result of Graham and Pollak, the determinant of D is a function only of n and does not depend on the tree. A formula for the inverse of D was obtained by Graham and Lovasz. We discuss various recent extensions of these results. These include weighted versions, including matrix weights, a q-analogue and results for the "resistance distance" in an arbitrary graph.

Streszczenie:
Indeksy siły to funkcje wektorowe na grach prostych mające służyć jako miary względnej "siły" uczestników takich gier. Z "paradoksem" takiego indeksu mamy do czynienia wtedy, gdy pewna zmiana gry na korzyść danego gracza - czyli taka, po jakiej oczekiwalibyśmy jego "wzmocnienia" - prowadzi do zmniejszenia jego indeksu. Przedstawię kilka najważniejszych paradoksów indeksów siły (m. in. paradoks redystrybucji, rozmiaru oraz "obdarowania") i typowe konfiguracje, w jakich mogą one występować. Sformułuję także warunki, najczęściej w postaci różnych pojęć monotoniczności indeksu, zapobiegające występowaniu poszczególnych paradoksów.

Streszczenie:
Przedstawimy szczególną klasę ściągalnych kompleksów bez nieskończonych s-ścieżek i s-cykli oraz jej związek z kompleksami s-rekurencyjnie ściągalnymi. Pokażemy, ze takie kompleksy mają własność stałego sympleksu. Jest to pewne uogólnienie twierdzenia o stałej krawędzi, sformułowanego przez Nowakowskiego i Rivala.

Streszczenie:
Rozważa się cykl skierowany o liczności n>2. Początkowo każdy wierzchołek cyklu jest etykietowany tym samym symbolem. Należy podać zbiór instrukcji (jednakowy dla wszystkich wierzchołków) postaci (x,y)-> (x',y') przekształcających symbole x,y, sąsiednich wierzchołków na nowe x',y', tak, aby ich wykonanie (w dowolnej kolejności) doprowadziło koniec końców do uporządkowania wierzchołków.
Dowodzi się, że konstrukcja takiego zbioru instrukcji (protokołu elekcji) jest możliwa wtedy i tylko wtedy, gdy n jest liczbą pierwszą.

Streszczenie:
Tematem jest problem kapeluszy (ang. ''hat problem''). W tym problemie każdej spośród n osób zostaje nałożony niebieski lub czerwony kapelusz. Każdy widzi kapelusze pozostałych osób, ale nie widzi swojego. Następnie każdy jednocześnie stwierdza kolor swojego kapelusza lub rezygnuje z odpowiedzi. Drużyna wygrywa, jeżeli co najmniej jedna osoba poprawnie odgadnie kolor swojego kapelusza i nikt nie stwierdzi błędnie koloru swojego kapelusza. W przeciwnym wypadku drużyna przegrywa. Celem jest znalezienie strategii dającej jak największą szansę na wygraną. Problem kapeluszy posiada liczne zastosowania i powiązania z różnymi dziedzinami nauki (Informatyka: transmisja danych, programowanie liniowe, programowanie genetyczne, Ekonomia, Biologia, Matematyka: aproksymacja funkcji boolowskich, autoredukowalność ciągów losowych). Rozpatruję uogólniony problem kapeluszy z n osobami i q kolorami, i rozwiązuję go dla n = 3 i q = 3. Następnie rozpatruję problem kapeluszy na grafie, gdzie wierzchołki to ludzie i każdy widzi te osoby, z którymi jest połączony krawędzią. Badam problem kapeluszy dla grafów takich, że jedyną informacją którą znamy są stopnie wierzchołków. Rozpatrujemy także grafy, które posiadają wierzchołki o tym samym otwartym sąsiedztwie (nadal znamy jedynie stopnie wierzchołków).

Streszczenie:
Jak już wiemy, n-wymiarowa wersja twierdzenia Steinhausa (słaba) to nic innego jak twierdzenie Poincare czy twierdzenie Brouwera o punkcie stałym. Podczas wystąpienia przedstawię mocną wersję twierdzenia szachowego oraz zaprezentuję algorytm znajdujący drogi, o których mowa w twierdzeniu szachowym Steinhausa (mocna wersja dla n=2). Następnie opiszę jak konstruktywnie możemy szukać miejsc zerowych funkcji spełniających założenia twierdzenia Poincare dla n=3.

Streszczenie:
W modelach produkcji i dystrybucji przedmiotem analizy jest łańcuch produkcji, zaopatrzenia i zbytu. Zapasem zarządza się na dwu szczeblach -- u producenta i u sprzedawcy (dystrybutora). Zarządzającym może być centralny ośrodek który minimalizuje całkowity średni (na jednostkę czasu) koszt uzyskania, magazynowania i przesyłania dobra. Zarządzanie może być również zdecentralizowane.

Poszukuje się ,,dobrego" -- ekonomicznego cyklu produkcji i dystrybucji. Strukturę takiego cyklu określa się poprzez wielkości produkcji i odpowiednią politykę przesyłania towaru (alokację zapasów).

Przedstawione zostaną wyniki pracy: Braglia M. i L. Zavanella, Modelling an industrial strategy for inventory management in supply chains: the "Consignment Stock" case, International Journal of Production Research, 41 (2003) 3793--3808
oraz ich uogólnienia.

Streszczenie:
Przedstawimy własności kompleksów retraktowalnych, załamywalnych i rekursywnie ściągalnych. Udowodnimy także, że czapka Borsuka (dunce cap) nie jest rekursywnie ściągalna. Ponadto zdefiniujemy dwa algorytmy wyboru lidera w kompleksach.

Streszczenie:
Uzawa (1962) pokazał równoważność twierdzenia Brouwera o punkcie stałym pewnemu swojemu twierdzeniu o istnieniu punktu, dla którego wartość funkcji jest mniejsza od zera (jeśli funkcja ta spełnia warunek Walrasa). Zostaną przedstawione dwa nowe twierdzenia równoważne twierdzeniu Uzawy.

Streszczenie:
Charness, Levin i Karni (2008) przeprowadzili eksperyment, w którym uzyskali poprawę wyników w problemie Lindy (badani szacują prawdopodobieństwo części wspólnej zdarzeń wyżej niz jednego z tych zdarzeń) w sytuacji, gdy respondenci mogli współpracować ze sobą i byli powiadomieni, że istnieje prawidłowa odpowiedź i będzie ona premiowana wypłatą. W moim eksperymencie (subiektywne prawdopodobieństwo porządkowe zachorowania na różne choroby) badałam poprawność odpowiedzi dotyczących części wspólnej i sumy zdarzeń. Porównywałam wyniki bez współpracy i bodźców finansowych z sytuacją z możliwością współpracy i bodźcami finansowymi. Nie powtórzyły się wyniki z Charnessa i innych.

Streszczenie:
Charness, Levin i Karni (2008) przeprowadzili eksperyment, w którym uzyskali poprawę wyników w problemie Lindy (badani szacują prawdopodobieństwo części wspólnej zdarzeń wyżej niz jednego z tych zdarzeń) w sytuacji, gdy respondenci mogli współpracować ze sobą i byli powiadomieni, że istnieje prawidłowa odpowiedź i będzie ona premiowana wypłatą. W moim eksperymencie (subiektywne prawdopodobieństwo porządkowe zachorowania na różne choroby) badałam poprawność odpowiedzi dotyczących części wspólnej i sumy zdarzeń. Porównywałam wyniki bez współpracy i bodźców finansowych z sytuacją z możliwością współpracy i bodźcami finansowymi. Nie powtórzyły się wyniki z Charnessa i innych.

Streszczenie:
Na seminarium 17 listopada br. wykazaliśmy następujące twierdzenie (o istnieniu łańcucha): Dla dowolnego rozbicia $T(k)$ kostki $I^n$ i dowolnej funkcji kolorującej $F\colon T(k)\to \{1,...n\} istnieje liczba naturalna $i\in \{1,...n\}$ oraz łańcuch $P_1,...,P_r$ $i$-tego koloru taki, że $P_1\cap I^+_i \neq \emptyset$ i $P_r\cap I^-_i \neq \emptyset$. Gdzie $P_1,...,P_r\in T(k)$ jest łańcuchem jeśli $P_i\cap P_{i+1}$ jest niepuste. Postaram się wykazać, że to twierdzenie jest równoważne z Twierdzeniem Brouwera o punkcie stałym. Pragnę również dla n=3 zaprezentować nowy, algorytmiczny dowód Twierdzenia Poincare.

Streszczenie:
Tematem referatu jest praca M. Kaneko i J.J. Kline "Inductive game theory: A basic scenario", Journal of Mathematical Economics 44 (2008), 1332-1363. Indukcyjna teoria gier ma opisywać sytuacje, gdy gracze nie mają pełnej wiedzy o rozgrywanej grze, robią błędy, nie są racjonalni. Prezentowana praca definiuje problemy pamięci i przypominania sobie za pomocą gier ekstensywnych w słabej i mocnej formie. Jakaś gra rozgrywa sie rzeczywiście i ta gra z rzeczywistą pamięcią jest sytuacją obiektywną. Gracz pamięta tylko fragmenty tego co się działo dotyczące jego samego lub innych graczy. Na bazie tych fragmentów buduje inną sytuację - swoją indywidualną grę i pamięc. Związki pomiędzy tymi sytuacjami badane sa za pomocą morfizmów. Badane są także związki pomiędzy optymalizacją w tych grach.

Streszczenie:
H.Scarf i W.C. Breinard w pracy "How to compute equilibrium price in 1891" z 2005 roku, opisali słynną hydrauliczną maszynę Fishera (n=3) i zaprezentowali "analityczną" wersję tej maszyny. W komentarzu stwierdzają, że Fisher nie mógł podać pełnego rozwiązania problemu, gdyż nie znał twierdzenia Brouwera o punkcie stałym. Jednak twierdzenie Poincarego było znane w 1883 roku. Pokażemy, że wystarczyło wykorzystać to twierdzenie do rozwiązania problemy istnienia równowagi rynkowej. Zaprezentujemy nowy, algorytmiczny dowód tw. Poincarego dla n=3.

Streszczenie:
brak

Streszczenie:
Tematem referatu jest praca M. Kaneko i J.J. Kline "Inductive game theory: A basic scenario", Journal of Mathematical Economics 44 (2008), 1332-1363. Indukcyjna teoria gier ma opisywać sytuacje, gdy gracze nie mają pełnej wiedzy o rozgrywanej grze, robią błędy, nie są racjonalni. Prezentowana praca definiuje problemy pamięci i przypominania sobie za pomocą gier ekstensywnych w słabej i mocnej formie. Jakaś gra rozgrywa sie rzeczywiście i ta gra z rzeczywistą pamięcią jest sytuacją obiektywną. Gracz pamięta tylko fragmenty tego co się działo dotyczące jego samego lub innych graczy. Na bazie tych fragmentów buduje inną sytuację - swoją indywidualną grę i pamięc. Związki pomiędzy tymi sytuacjami badane sa za pomocą morfizmów. Badane są także związki pomiędzy optymalizacją w tych grach.

Streszczenie:
Przedstawiony zostanie analogon lematu Spernera dla wieloetykietowanych wierzchołków podziału symplicjalnego trójkata. Przy użyciu twierdzenia Bapata podana bedzie charakteryzacja takich wieloetykietowan w jezyku teorii grafów. Uogólnienia dla dowolnych sympleksów beda sformułowane.

Streszczenie:
Zaprezentowany będzie złożony ekosystem informatyczny: sztuczne społeczeństwo. Składa się ono z populacji algorytmów, rozgrywającej (w parach) wielokrotnie parametryzowany asymetryczny dylemat więźnia. Projekt ten można traktować jako nieskończony turniej Axelroda, w którym uczestniczy wielka liczba programów stosujących wszelkie możliwe do zaimplementowania indywidualne strategie.
Programy agentowe posiadają zróżnicowane, lecz stabilne cechy, tworzące charakter, oraz zmienne cechy związane z indywidualna kondycją ekonomiczną, biologiczną i społeczną. Programy posiadają pamięć i zdolność syntetyzowania zdobywanych doświadczeń. Gromadzą dobra, zmienia się ich wiedza, nastrój i zdrowie.
Oprócz cech indywidualnych, modelowane są różne rodzaje interakcji oraz tzw. urządzenia społeczne, realizowane poprzez finanse publiczne, tworzone przez różnorakie podatki i zużywane przez zadania opieki społecznej oraz redystrybucję.
System sprzęga w emergentny i nie wynikający wprost z założeń sposób parametry finansowe, antropologiczne, ekonomiczne i biologiczne. Stwarza środowisko bezkrwawej utopii czy eksperymentalnej ideologii. Pozwala na weryfikację różnych hipotez nauk społecznych i ekonomicznych.

Streszczenie:
Streszczenie drugiej części:
W głosowaniu aprobującym głosujący oddają głos na tyle alternatyw, na ile mają ochotę - mogą zagłosować na jedną osobę, mogą na 2, na 3 itd., mogą też nie zagłosować na nikogo. Powstaje pytanie, czy średnia liczba wybieranych alternatyw jest jakąś stałą, przynajmniej w odniesieniu do podobnych głosowań. Zostały zebrane i przeanalizowane pod tym kątem wyniki badań empirycznych dotyczących głosowania aprobującego przeprowadzonych przez referentkę.

Streszczenie:
Wartości odwrotnie proceduralne i uogólnione - ostatni referat o wartościach proceduralnych.
W referacie powrócę, w zamierzeniu ostatni raz, do określonej przez siebie parę lat temu klasy wartości proceduralnych gier kooperacyjnych (definicję pojęcia przypominam poniżej cytując fragment dawnego streszczenia). Przedstawię parę klas wartości spokrewnionych z wartościami proceduralnymi; wszystkie one powstają w wyniku podziału krańcowych wkładów (graczy w koalicje) z innymi graczami, ale na nieco innych zasadach niż wartości proceduralne. Są to:

• wartości odwrotnie proceduralne powstające przy podziale z następnikami (zamiast z poprzednikami) w uporządkowaniu graczy,
• wartości wspólnej puli, uzyskane przez oddawanie ustalonych części wkładów krańcowych do wspólnego worka i następnie podział tak utworzonej puli równo pomiędzy wszystkich,
• uogólnione wartości proceduralne powstające, gdy gracze dzielą się swymi wkładami zarówno z poprzednikami, jak z następnikami (w ustalonych proporcjach).

Pokażę, że dwie pierwsze klasy wartości są identyczne z klasą wartości proceduralnych, natomiast dla trzeciej przedstawię nową i moim zdaniem interesującą charakterystystykę przez układ postulatów analogiczny do znanego wcześniej dla wartości proceduralnych.

"W myśl klasycznej interpretacji probabilistycznej wartości Shapleya gier kooperacyjnych indywidualna wartość gracza (liczba) to wartość oczekiwana wkładu wnoszonego przez niego w koalicję jego "poprzedników" w losowym porządku przy założeniu, że wszystkie uporządkowania graczy są jednakowo prawdopodobne. Interesujące jest uogólnienie tego pojęcia na sytuacje, gdy zachowane jest założenie o losowym uporządkowaniu graczy, ale przy dowolnej kolejności, w jakiej tworzą oni wielką koalicję, każdy gracz jest zobowiązany do podzielenia się swoim krańcowym wkładem z "poprzednikami". Sposób podziału tych wkładów nazwiemy procedurą. Każda procedura wyznacza pewną wartość dla gier kooperacyjnych w sposób analogiczny do wartości Shapleya, ale przy uwzględnieniu wyznaczonej przez procedurę redystrybucji".