Seminarium Teorii Gier i Decyzji:

Streszczenie:
Podane zostaną pewne twierdzenia równoważne twierdzeniu Brouwera. Pokazane zostaną związki tych twierdzeń z istnieniem równowagi w pewnym modelu wymiany.

Streszczenie:
Zreferuję pracę J. Aspnesa i innych o przybliżaniu funkcji boole'owskich przez znak tzw. wielomianu głosowania. Zagadnienie jest jednym z uogólnień tradycyjnego problemu kapeluszy, w którym każdy z grupy ludzi widzi kolor kapeluszy wszystkich innych, ale nie widzi własnego, i ma stwierdzić kolor swojego (-1 albo 1) nie porozumiewając się z innymi, przy czym wolno mu wstrzymać się od głosu. Reguła decyzyjna, uzgodniona zawczasu (przed zobaczeniem kapeluszy) przez grupę jest tym lepsza, im większe jest prawdopodobieństwo, że ktoś z grupy prawidłowo poda kolor swojego kapelusza, a nikt się nie pomyli. Uogólnienie polega na (1) możliwości podania dowolnej liczby całkowitej zamiast +- 1, (2) wyznaczaniu wyniku większością głosów; reguła decyzyjna sprowadza się wtedy do wielomianu zmiennej boole'owskiej o współczynnikach całkowitych.

Streszczenie:
Gry w postaci funkcji rozbicia stanowią uogólnienie pojęcia gier kooperacyjnych. Funkcja charakterystyczna w takiej grze określa wartość danej koalicji w zależności od jej składu, ale także od podziału pozostałych graczy na koalicje. Dla takich gier proponowano różne uogólnienia wartości Shapleya. Mój referat będzie poświęcony propozycji nowej wartości gier w postaci funkcji partycji, którą nazywam uogólnioną wartością Owena. Wartość ta jest średnią wartości Owena obciętych gier kooperacyjnych z prekoalicjami, skonstruowanych na bazie oryginalnej gry w postaci funkcji partycji. Przedstawię sposób obliczania uogólnionej wartości Owena, a także jej własności i porównam je z własnościami znanych z literatury wartości gier w postaci funkcji partycji.

Streszczenie:
Praca zawiera opis eksperymentów kontynuujących badania Sosnowskiej nad intuicyjnym i dedukcyjnym rozumowaniem ze szczególnym uwzględnieniem koniunkcji i alternatywy zdań (błąd koniunkcji i błąd dyzjunkcji). Poprzednie wyniki wskazywały na brak zgodności rozumowań intuicyjnych z formalnymi. Badania amerykańskie (Charnes i inni) wskazują, że lepszą zgodność się uzyskuje, gdy badani są motywowani finansowo i mogą ze sobą współpracować. Zastosowano tę metodologię do badań polskich. Wyniki polskie potwierdzają amerykańskie jeśli chodzi o wpływ motywacji finansowej, nie potwierdzają wpływu współpracy grupowej. Negatywnie też zweryfikowano hipotezę Costello o równoważnosci błędów koniunkcji i dyzjunkcji.

Streszczenie:
Rozważanie własności (aksjomatów), jakie powinien spełniać system wyborczy, zostało zainicjowane przez Kennetha Arrowa w 1950 r. Arrow wykazał, że jeżeli chcemy dokonać (spełniajacej pewne sensowne warunki) agregacji preferencji indywidualnych w celu uzyskania wyboru społecznego, to jedynym sposobem jest skoncentrowanie wszystkich decyzji w jednym ręku (dyktatura). Jest wiele uogólnień twierdzenia Arrowa. Będziemy rozwaźali dowolny - niekoniecznie skończony - zbiór alternatyw i wykaźemy, źe jest to faktycznie twierdzenie o ultrafiltrach. W naszej teoriomnogościowej interpretacji twierdzenie Arrowa mówi, źe funkcja wyboru społecznego jest generowana przez pewien ultrafiltr.

Streszczenie:
Podczas referatu zostaną opisane własności grafów dwudzielnych spotykane w sieciach społecznych. Skupimy uwagę na trzech własnościach, które w naszej ocenie mają kluczowy wpływ na złożoność algorytmów rekomendujących. Tymi cechami są: rozkład stopni wierzchołków, wielkość sąsiedztwa oraz tranzytywność. Zostanie omówniony nowy generator grafów dwudzielnych stanowiący adaptację trzech modeli generujących klasyczne grafy (tj. modelu Barabasiego, modelu Liu i modelu Vazqueza).

Streszczenie:
Graf medianowy to graf spójny o następujacej własności: dla każdej trójki wierzchołków a1, a2, a3 istnieje jedyny wierzchołek x taki, że dla i,j=1,2,3 (i różne od j): d(ai, x) + d(x, aj) = d(ai, aj). Niech G i H beda dwoma grafami prostymi. Odwzorowanie f : V (H) --> V (G) zdefiniowane na zbiorach ich wierzchołków nazwiemy zachowującym krawędzie, jeśli przekształca wierzchołki sąsiednie na wierzchołki sąsiednie. Odwzorowanie zachowujące krawędzie f : V (H) --> V (G) nazwiemy retrakcją, jeśli f(V (H)) = V (G) i f|V (G) jest identycznością. Mówimy wtedy, ze graf G jest retraktem grafu H. Pokażemy, że grafy medianowe są dokładnie retraktami kostek.

Streszczenie:
Graf medianowy to graf spójny o następujacej własności: dla każdej trójki wierzchołków a1, a2, a3 istnieje jedyny wierzchołek x taki, że dla i,j=1,2,3 (i różne od j): d(ai, x) + d(x, aj) = d(ai, aj). Niech G i H beda dwoma grafami prostymi. Odwzorowanie f : V (H) --> V (G) zdefiniowane na zbiorach ich wierzchołków nazwiemy zachowującym krawędzie, jeśli przekształca wierzchołki sąsiednie na wierzchołki sąsiednie. Odwzorowanie zachowujące krawędzie f : V (H) --> V (G) nazwiemy retrakcją, jeśli f(V (H)) = V (G) i f|V (G) jest identycznością. Mówimy wtedy, ze graf G jest retraktem grafu H. Pokażemy, że grafy medianowe są dokładnie retraktami kostek oraz że grafy medianowe mają własność stałej kostki (dla odwzorowań zachowujących krawędzie).

Streszczenie:
W pierwszej części referatu przedstawimy grę wieloosobową z deterministycznymi priorytetami i poissonowskim strumieniem pojawiania się ofert, w której celem każdego gracza jest maksymalizowanie oczekiwanej wypłaty. Zaprezentujemy strategie Nasha dla tej gry. Następnie przedstawimy pewną wersję gry wieloosobowej z losowymi priorytetami. Na zakończenie pokażemy związki między prezentowanymi grami a problemem wielokrotnego stopowania i problemem alokacji. Prezentowane wyniki są uogólnieniem tych przedstawianych w referacie na seminarium Zespołu Teorii Gier IPI w 2008 roku.

Streszczenie:
Przedmiotem analizy jest dwuszczeblowy łańcuch zaopatrzenia i zbytu. Producent wytwarza jedno dobro. Jest ono przesyłane do sprzedawcy, który zaspokaja pojawiający się u niego popyt. Przyjmowane są założenia:
1) Produkcja odbywasię w cyklach. Cykl składa się z okresu produkcji i okresu postoju.
2) Towar jest przesyłany z magazynu producenta do magazynu sprzedawcy w uzgodnionych dyskretnych partiach jednakowej wielkości "consignment stock policies".
2') (alternatywnie wobec 2). Uzgadnia się dwie wielkości uwzględniając na ogół różne preferencje producenta i sprzedawcy.
Koszty produkcji i magazynowania są liniowe z ewentualną nieciągłością w zerze. W sytuacji centralnego zarządzania poszukuje się cyklu o minimalnym koszcie średnim - ekonomicznego cyklu produkcji i dystrybucji (ECPD). Porównuje się ECPD w przypadkach założeń 2) i 2').

Streszczenie:

1. Maksymalizacja symetrycznej funkcji zbioru po zbiorze partycji

Niech v będzie symetryczną funkcją zbioru określoną na podzbiorach skończonego zbioru N, tj. spełniającą warunek: v(Q) = v(R) dla dowolnych równolicznych podzbiorów Q i R zbioru N. Rozważamy problem poszukiwania maksimum dla sumy v(P₁) + v(P₂) + ... + v(P_k), gdzie P = (P₁, P₂,..., P_k) przebiega zbiór W wszystkich partycji (= rozbić) zbioru N. W pracy dyskutuje się, czy to maksimum można uzyskać ograniczając się tylko do pewnych "istotnie mniejszych" podzbiorów zbioru W.
(Ten temat, inspirowany grami kooperacyjnymi, może zainteresować także informatyków).

2. Funkcje słabo-wklęsłe i gry na kwadracie jednostkowym

W pracy definiuje się klasę funkcji słabo-wklęsłych, zwierającą zbiór wszystkich funkcji wklęsłych i jednocześnie zawartą w zbiorze wszystkich funkcji quasi-wklęsłych. Pokazuje się istnienie równowagi Nasha w grach 2-osobowych na kwadracie jednostkowym i znajduje jego postać, przy pewnych założeniach "słabo-wklęsłości" o funkcjach wypłaty graczy. Otrzymane wyniki uogólniają znane klasyczne twierdzenia o równowagach Nasha w grach.

Streszczenie:
Przypomniane zostaną pojęcia dotyczace stałych sympleksów w odwzorowaniach wielowartościowych kompleksów. Zostanie sformułowane twierdzenie o istnieniu stałego sympleksu i omówiony jego związek z innymi twierdzeniami o punktach stałych. Przedstawione będzie alternatywne sformułowanie w języku zbiorów cześciowo uporzadkowanych. Jeżeli wystarczy czasu, to pokażę też kilkanaście przykładów zbalansowanych pokryć niektórych prostych grafów.

Streszczenie:
Przedstawione zostanie pojęcie lokalnej równowagi Nasha dla gier niekooperacyjnych oraz szkic dowodu istnienia takich równowag przy odpowiednich założeniach. Do dowodu zostaną wykorzystane twierdzenia o punkcie stałym typu Brouwera.

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".