Seminarium Teorii Gier i Decyzji:

Streszczenie:
Pojęcie alfa-wypukłości wprowadzili de Blasi i Pianigiani (2004). W referacie to pojęcie zostanie przedstawione i porównane z pojęciem wypukłości generowanej przez funkcję łączącą (ang. connecting function; dla przestrzeni topologicznej X jest to funkcja ciągła c:[0,1]xXxXŕX taka, ze c(t,x,x)=x, c(1,x,y)=c(0,y,x)=x; podzbiór X jest wypukły, jesli z każdymi elementami, x, y zawiera również c(t,x,y), dla dowolnego t) wprowadzonym wcześniej przez autora referatu (1991, 1992). Celem referatu jest wskazanie, że te dwa rodzaje wypukłości są identyczne.

Streszczenie:
Kopuły archimedesowskie to pewna ważna klasa obiektów statystycznych mających rozmaite własności analityczne. Niektóre z tych własności można wyrazić w języku algebraicznym. Prezantacja kopuł archimedesowskich będzie skoncentrowana na związku z teorią półgrup.

Streszczenie:
Rodzina grafów jest redukowalna jeśli istnieje dla niej lokalna reguła usuwania elementów grafu taka, że drogą kolejnych usunięć otrzymuje się graf o zadanych własnościach. W szczególności, interesują nas lokalne reguły prowadzące do (1) uzyskania grafu o jednym (dowolnie wybranym) wierzchołku, poprzez kolejne usuwanie wierzchołków i (2) uzyskania (dowolnego) drzewa rozpinającego grafu, poprzez kolejne usuwanie krawędzi.
W referacie przedstawione zostaną pewne klasy grafów, dla których takie reguły istnieją, ponadto klasy, dla których żadna taka reguła nie istnieje, oraz klasy, dla których takie reguły istnieją, lecz ich możliwości są ograniczone. Uzyskane wyniki mogą służyć określeniu strukturalnych własności sieci obliczeniowych odpornych na usuwanie z nich procesorów lub łączy między nimi.

Streszczenie:
We consider the issue of representing coalitional games in multi-agent systems with externalities, i.e. in systems where the performance of one coalition may be affected by the functioning of other co-existing coalitions. On top of the conventional partition function game representation (PFG), we propose a number of new representations based on a new notion of externalities. In contrast to conventional game theory, our new concept is not related to the process by which the coalitions are formed, but rather to the effect that each coalition may have on the entire system and vice versa. We show that the new representations are fully expressive and, for many classes of games, more concise than the conventional PFG one. Building upon the new representations, we propose a number of approaches to solve the coalition structure generation problem in systems with externalities. We show that, if externalities are characterised by various degrees of regularity, the new representations allow us to adapt some of the algorithms that were originally designed for domains with no externalities so that they can be used when externalities are present. Finally, building upon Rahwan et al. and Michalak et al., we present a unified method to solve the coalition structure generation problem in any system, with or without externalities, provided sufficient information is available.

Streszczenie:
Podczas referatu wprowadzone zostanie nowe (jak się zdaje) pojęcie rozwiązania dla symetrycznych gier dwuosobowych o sumie niezerowej: rozwiązanie kooperacyjne von Neumanna -- Pareto. Okazuje się, że rozwiązanie kooperacyjne ma wiele pożądanych własności, przede wszystkim spełnia kryterium Pareto oraz pozwala określić w sposób jednoznaczny cenę gry, istotny element klasycznej teorii von Neumanna, który nie ma dobrego odpowiednika w teorii Nasha. Co więcej nowa definicja wykazuje zgodność z definicją minimaksu von Neumanna w sytuacji, gdy gra symetryczna ma sumę zerową, co poniekąd "wyjaśnia", dlaczego w grach o sumie zerowej nie ma sensu rozpatrywać współpracy graczy.

Streszczenie:
Przedmiotem analizy jest łańcuch produkcji, zaopatrzenia i zbytu, jak i działanie jego poszczególnych ogniw. Zapasem i przesyłaniem jednego dobra zarządza się niezależnie na dwu szczeblach -- u producenta i u każdego ze sprzedawców (dystrybutorów). W wyniku tych wszystkich decyzji ustalają się wielkość produkcji oraz odpowiednia polityka przesyłania towaru (co do czasu i wielkości uzupełnień zapasów w magazynach u sprzedawców), tzn. ustala się pewien cykl produkcji i dystrybucji (CPD). Każdy ocenia średnią wartość (na jednostkę czasu) swoich kosztów uzyskania, magazynowania i przesyłania dobra. Poszukuje się "dobrego" - ekonomicznego cyklu równowagi produkcji i dystrybucji jako równowagi w niekooperacyjnej grze z ograniczeniami. Dowodzi się istnienia i podaje własności równowagi w grze Stackelberga z producentem jako liderem.

Streszczenie:
Zostanie zdefiniowana gra wielokryterialna (multiobjective) oraz równowaga w takiej grze. To pojęcie równowagi obejmuje jako szczególne przypadki równowagę Nasha oraz punkt optymalny w sensie Pareto. Przedstawiona zostanie idea dowodu istnienia takiej równowagi.

Streszczenie:
Prezentacja będzie się składała z dwóch części. W pierwszej przedstawimy model rozgrywki brydżowej, trudności z zastosowaniem tego modelu oraz rozważania na temat "adekwatności" modelu. W drugiej nastąpi konfrontacja modelu matematycznego z istniejąca teorią brydżową (nie tylko dotyczącą rozgrywki). Nastąpi to na pewnym poziomie ogólności (być może kontrowersyjnym). Potrzebne to jest ze względu na:

1. Podkreślenie znaczenia brydża jako przykładu gry będącej członkiem szerszej klasy gier.
2. Wprowadzenia pojęcia metametaheurystyki.

Streszczenie:
Na seminarium przedstawię własne wyniki na temat "egalitarnej" własności indeksów sily dla pewnych klas indeksów związanych z istnieniem przejść dla gracza oraz mocą koalicji, Własność ta polega na zmniejszaniu się różnic pomiedzy wartościami indeksów graczy dla ciągu gier powstających przez przecięcie ustalonej gry prostej (zupełnej) z grami większości, przy rosnących progach większości.

Streszczenie:
W referacie powrócę do określonej przez siebie parę lat temu klasy wartości proceduralnych (definicję pojęcia przypominam poniżej cytując fragment dawnego streszczenia). Przedstawię dwie charakterystyki aksjomatyczne tej klasy przy użyciu różnych warunków monotoniczności, w tym jedną nową. Pokażę, że klasa wartości proceduralnych jest identyczna z klasą wartości "odwrotnie proceduralnych", powstających w wyniku podziału krańcowych wkładów w koalicje z następnikami w uporządkowaniu graczy, a istotnie mniejsza od klasy wartości uzyskiwanych przy dowolnym rozdysponowaniu krańcowych wkładów pomiędzy wszystkich graczy. Scharakteryzuję klasę "egalitarnych wartości Shapleya" (van den Brink, Funaki i Ju 2007) jako podzbiór zbioru wartości proceduralnych o dodatkowej własności samodualności.

Pojęcie wartości proceduralnej:
"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".

Streszczenie:
Przedstawiamy podejście do uzyskania rozwiązań kooperacyjnych w grach wieloosobowych o sumie zmiennej na podstawie modelowania cechy altruistycznej w zachowaniu graczy. Scharakteryzowaniu ilościowego stopnia altruizmu każdego gracza w odniesieniu do każdego innego służą "współczynniki altruizmu". Taki współczynnik wpływa na wybór strategii w przypadku, gdy gracz może uzyskać niewiele, ale kosztem dużej straty innego gracza. Proponujemy dwa modele zachowania altruistycznego, podobne do modeli niepełnej informacji o preferencjach decydenta na podstawie trade-off. Udowodniono, że w każdym z tych modeli dowolne rozwiązanie gry Pareto-optymalne jest "równowagą altruistyczną" przy odpowiednio dużych współczynnikach altruizmu, nawet gdy równowaga Nasha nie istnieje. Proponujemy charakteryzację sytuacji gry w terminach dolnych granic na współczynniki altruizmu.

Streszczenie:
"Duże" gry ważonej większości to gry z niewielką liczbą graczy "dużych" o wagach odgraniczonych od zera, czyli stanowiących istotną część sumy wszystkich wag, oraz dużą liczbą graczy "małych" o wagach bliskich zeru. Oczywistym przykładem są tu gry większości rozgrywane przy głosowaniach na walnych zebraniach akcjonariuszy w systemie "jedna akcja - jeden głos". Takie gry wygodnie jest traktować jako gry tzw. oceaniczne z ustaloną liczbą graczy dużych i continuum ("oceanem") graczy małych, z których każdy z osobna nie waży nic, ale cały ocean ma wagę dodatnią i głosy jego podzbiorów dodatniej miary mogą być istotne dla wyniku głosowania.
Znana jest seria pięknych twierdzeń udowodnionych przez Shapleya i współautorów na temat interpretacji probabilistycznej wartości Shapleya gier oceanicznych oraz zbieżności wartości dużych gier (w których wagi dużych graczy są stałe, natomiast liczba małych graczy dąży do nieskończoności, ich indywidualne wagi do zera, a suma ich wag pozostaje stała) do wartości gry oceanicznej. W referacie przedyskutuję zbieżność innych znanych indeksów siły dla takich samych ciągów dużych gier ważonej większości. Okazuje się, że dla najprostszych takich ciągów zbieżność zachodzi, ale otrzymane granice są dosyć absurdalne. W szczególności indeksy Banzhafa, Hollera, Deegana-Packela i Johnstona zawsze w granicy przypisują całą siłę albo małym graczom, albo dużym. Co więcej w wielu przypadkach różne indeksy prowadzą dla tych samych ciągów gier do siły oceanu równej albo 0, albo 1. Uważam te wyniki za istotny argument na rzecz stosowania jako indeksu siły - przynajmniej dla gier z większą liczbą graczy - wartości Shapleya, a nie wymienionych wyżej indeksów.

Streszczenie:
Na poprzedniej konferencji przedstawiłam referat "Ryzyko porządkowe a rachunek zdarzeń", który zawierał wyniki badania, czy subiektywne ryzyko porządkowe rządzi się prawami rachunku prawdopodobieństwa. Wynik okazał się negatywny, zwłaszcza gdy chodzi o prawdopodobieństwo sumy zdarzeń. Badane było ryzyko zdarzeń negatywnych na przykładzie zachorowań na różne choroby. Obecnie to badanie powtórzone zostało w przypadku wybranych zdarzeń pozytywnych (takich jak dobre ukończenie studiów czy wysokie zarobki). Ponownie, wyniki nie są zgodne z regułami rachunku prawdopodobieństwa, przy czym ta niezgodność jest większa niż w przypadku zdarzeń negatywnych. Porównane zostały wyniki obu badań. Ponadto zagregowano metodami społecznego wyboru opinie respondentów dotyczące prawdopodobieństwa zdarzeń pozytywnych.

Streszczenie:
Na seminarium przedstawię własne wyniki na temat dominacji Lorentza w grach kooperacyjnych. Zdefiniuję porządek graczy w grach kooperacyjnych (ang. "desirability order") oraz operację przecięcia gry prostej i kooperacyjnej, które posłużą mi do uogólnienia dominacji Lorentza na monotoniczne gry kooperacyjne, w których relacja desirability jest spójna (gry liniowe). Przedstawię klasę indeksów, dla której zachodzi dominacja Lorentza. Klasa ta zawiera wszystkie unormowane półwartości (ang. "semivalues"), i rozszerza ją na przykład o wartość Johnstona. Wynik ten uogólnia twierdzenie Pelega o dominacji Lorentza opartej na indeksie Shapleya dla gier prostych.

Streszczenie:
Na podstawie pracy Gerda Wegnera "d-Collapsing and Nerves of Families of Convex Sets" zostaną zdefiniowane pojęcia nerwu skończonej rodziny zbiorów oraz d-reprezentowalnego kompleksu. Główny problem to charakterystyka d-reprezentowalnych kompleksów, który jest rozwiązany jedynie dla d=1. Jedna z najważniejszych własności d-reprezentowalnych kompleksów jest związana z twierdzeniem Helly ego; celem pracy Wegnera jest pewne rozszerzenie tej własności poprzez kompleksy d-załamywalne.

Streszczenie:
W niniejszym referacie przedstawimy dwie gry wieloosobowe z poissonowskim strumieniem ofert: grę z deterministycznymi priorytetami oraz grę z losowymi priorytetami, w której prawdopodobieństwo wylosowania priorytetu jest takie samo dla każdego gracza. W obu sytuacjach celem każdego gracza jest maksymalizowanie oczekiwanej wypłaty. Pokaźemy, że te gry można sprowadzić do problemu wielokrotnego stopowania rozważanego w pracy Stadje (1987). Takie podejście pozwala znaleźć punkt równowagi Nasha. Referat oparty jest częściowo na artykule Ferenstein i Krasnosielskiej "Nash equilibrium in a game version of Elfving problem".

Streszczenie:
"Wieloizbowe" gry proste opisują głosowania w wieloizbowych parlamentach, ale także np. w Radzie Unii Europejskiej. Formalnie, gra prosta v jest "dwuizbowa", gdy jest iloczynem (minimum) dwóch gier prostych y i z, tzn. wygrywające są w niej koalicje będące koalicjami wygrywającymi jednocześnie w grach y i z; zazwyczaj zakłada się przy tym, że y i z są grami ważonej większości. W referacie przedstawię zależności między rolami graczy (np. gracz zerowy, z prawem weta, silniejszy...) w grach y i z a ich rolami w grze będącej iloczynem. Pokażę także parę twierdzeń, na ogół negatywnych, dotyczących związków między indeksami siły w grach y, z, v. W szczególności okazuje się, że jeżeli y oraz z nie są grami kompletnymi z (prawie) jednakowym uporządkowaniem graczy pod względem "siły", to każdy sensowny indeks może dla któregoś z graczy w grze v przyjmować wartość większą od maksimum bądź mniejszą od minimum z jego indeksów w poszczególnych grach. Ma to pewne znaczenie przy rozważaniu konstrukcji systemów głosowania w ciałach takich jak Rada UE.

Streszczenie:
Przedstawiona zostanie szeroka klasa gier dynamicznych z czasem dyskretnym i z continuum graczy, w której oprócz globalnych zmiennych stanu każdy z graczy może mieć swoje prywatne zmienne stanu. Dla tej klasy gier udowodnimy twierdzenia o równoważności równowag otwartej i zamkniętej pętli, co nie jest typowe w grach ze skończoną liczbą graczy. Ponadto zaprezentowane zostanie uogólnienie twierdzenia o dostateczności równania Bellmana w optymalizacji dynamicznej z nieskończonym horyzontam czasowym, z funkcją celu o wartościach rzeczywistych rozszerzonych i bez założenia, że granica górna zdyskontowanej funkcji wartości jest równa zeru wzdłuż każdej trajektorii.

Streszczenie:
Omówione zostaną dwie klasy kompleksów: kompleksy rekurencyjnie ściągalne i kompleksy ściągalne. Pokażemy, że klasa kompleksów rekurencyjnie ściągalnych jest równoważna klasie kompleksów załamywalnych. Przedstawione zostaną zastosowania w teorii grafów.