Podczas prezentacji skupię się na metrykach dotyczących uczciwości 
i wydajności dla reguł głosowania. Omówię je na przykładzie dwóch reguł: 
Utilitarian Greedy oraz Method of Equal Shares, głównie opierając się na 
pracy “Participatory Budgeting: Data, Tools, and Analysis”. Opowiem 
także o pojęciu rdzenia w kontekście wyborów komitetowych.

[slides]

Podczas prezentacji omówię, jak można podejść do problemu znajdowania  grup wyborców o podobnych preferencjach. Na wstępnie omówię model wyborczy, z którym będziemy pracować, problemy z nim oraz dlaczego grupy podobnych wyborców nas interesują. Pierwszym istotnym zagadnieniem, które omówię, będzie próba zdefiniowania podobieństwa wyborców, co okaże się nie takie łatwe. Później przejdę do adaptacji znanych algorytmów klastrowania pod wybrane dystanse. Powiem też, jak można wizualizować otrzymane wyniki.

[slides]

Na najbliższym seminarium przestawię propozycje dwóch tematów magisterskich:

1. Hipoteza Osborna o sekwencyjnej rywalizacji wyborczej w modelu lokacyjnym.
2. Obliczanie równowagi Nasha w grze półkownik Blotto z liniowymi kosztami.

Problem 2 był już wspomniany na jednym z początkowych spotkań seminaryjnych. Tym razem zaproponuję podejście do obliczania równowag Nasha w tym problemie. O problemie 1 jeszcze nie mówiłem. Zapraszam zwłaszcza osoby, które wciąż szukają tematu pracy magisterskiej.

In the presented work we aim to spot shortcomings of using a convolutional architecture as a Go policy network. By comparing it to an equivalently trained Transformer policy and employing explainable AI methods such as Ceteris Paribus, we can see where each network under and overperforms. This work points in the direction of further research of Transformer architectures in positional games such as Go, where previously it was believed Convolutions were State of The Art.

[slides]

Podczas prezentacji przedstawię pracę “A Generalised Theory of Proportionality in Collective Decision Making” autorstwa Tomáša Masaříka, Piotra Skowrona i Grzegorza Pierczyńskiego. Przedstawię omawiany w pracy model wyborczy, w którym pewna ilość kandydatów zostaje wybrana z uwzględnieniem danych ograniczeń. Model uogólnia wybory komitetowe, elekcje z ograniczeniami związanych z różnorodnością, model z niezależnymi kolektywnymi decyzjami oraz model kolektywnego planowania. Przedstawię aksjomaty proporcjonalności w tym uogólnionym modelu, które też uogólniają najsilniejsze znane aksjomaty w istniejących modelach i nie wymagają żadnej spójności grup.

[slides]

W ramach prezentacji przedstawię algorytm opisany w pracy “Faster and Simpler Algorithm for Optimal Strategies of Blotto Game”(Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi HajiAghayi, Saeed Seddighin), pozwalający na praktyczne znajdywanie optymalnych strategii w grze blotto. Ten algorytm rozwiązuje problem w czasie wielomianowym i, w odróżnieniu od wcześniejszych rozwiązań, jest dość szybki aby dało się go stosować w praktyce. Algorytm sprowadza szukanie strategii do programowania liniowego, a dzięki odpowiedniemu wykorzystaniu struktury gry blotto, udaje się pokazać, że wynikowy program liniowy jest maksymalnie wielomianowej wielkości. Podczas prezentacji pokażę jak odpowiednia reprezentacja strategii graczy i wyników gry pozwala na zredukowanie liczby nierówności w programie liniowym. Uzasadnię, że program liniowy stworzony przez algorytm jest optymalny i opowiem o efektywności tego algorytmu w praktyce.

[slides]

W trakcie prezentacji opowiem o zagadnieniu tworzenia
grupowych miar centralności z wierzchołkowych. Omówię oczywiste i
wcześniej znane sposoby rozszerzania i pokażę ich silne i słabe strony.
Przedstawię nowy schemat służący do rozszerzania miar centralności na
wiele różnych sposobów. Wytłumaczę intuicje stojące za nim i intuicje
stojące za różnymi wariantami grupowych miar, które tworzy. Opowiem o
jego ekspresywności, czyli jakie grupowe miary centralności można nim
tworzyć. Pokażę, jak mają się wcześniej znane sposoby do nowego
schematu. Omówię, jak można korzystać ze schematu dla pewnych klas
wierzchołkowych miar centralności.

[slides]

W ramach prezentacji, opierając się o następujące prace: “Justified representation in approval-based committee voting” (Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh), oraz “Proportional Participatory Budgeting with Additive Utilities” (Dominik Peters, Grzegorz Pierczyński, and Piotr Skowron), przedstawię kryteria próbujące uchwycić pojęcie proporcjonalności w kontekście wyborów z głosowaniem przez aprobaty. Omówię wybrane kryteria w kontekście popularnych metod wyborczych zarówno dla wyborów komitetowych jak i budżetów partycypacyjnych.

[slides]

Podczas prezentacji omówię pracę ‘Participatory Budgeting with Cumulative Votes’ (Piotr Skowron, Arkadii Slinko, Stanisaw Szufa, Nimrod Talmon). Przedstawię omówione w niej metody głosowania o budżet. Oprócz tego opiszę własności które mogą zostać spełnione przez tego rodzaju głosowania. Dodatkowo przedstawię metryki pozwalające na porównywanie efektywności różnych metod głosowań. Na koniec porównam wyniki symulacji i danych z prawdziwych głosowań, jakie byłyby uzyskane przy użyciu przedstawionych wcześniej metod.

[slides]

Podczas prezentacji omówię pracę “Induced, endogenous and exogenous centrality” (Martin G. Everett, Stephen P. Borgatti). Przedstawię opisaną w niej ogólną metodę konstruowania indukowanej miary centralności, wykorzystującą niezmienniki grafu oraz opiszę pożądane cechy tych niezmienników. Podejście to pozwala na naturalną interpretację miary centralności jako wpływu wierzchołka na wartość niezmiennika, umożliwia dostosowanie jej do konkretnych potrzeb oraz naturalne uogólnienie centralności wierzchołka do grupowej centralności. Dodatkowo, przedstawię wewnętrzną, zewnętrzną i całkowitą centalność oraz ich interpretacje, analizując je na kilku dobrze znanych rodzajach centralności: degree, betweenness, reverse-closeness.

[slides]

Prezentacja dotyczy pracy “Attachment Centrality: An Axiomatic Approach to Connectivity in Networks” (Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, Makoto Yokoo). W jej trakcie przedstawię kilka aksjomatów związanych z łącznością sieci i przeanalizuję ich spełnialność przez standardowe miary centralności Degree, Closeness i Betweenness. Następnie zaprezentuję miarę centralności Attachment, jedyną spełniającą pewien zestaw tych właściwości. Miara ta jest równoważna wartości Myersona dla jednej z gier koalicyjnych ograniczonych grafem. Jedną z zalet miary Attachment są jej cechy, które pozwalają na jej efektywniejsze liczenie niż wartości Myersona. Na koniec opiszę zastosowanie tej miary do analizy sieci terrorystycznej, odpowiedzialnej za zamachy w Madrycie w 2004 roku.

[slides]

Badanie struktur sieci w rzeczywistości najczęściej przeprowadza się na modelach opartych o pewnego rodzaju graf lub wariancję na jego temat. Aby lepiej zrozumieć systemy, które są poddane zmianom oraz ewolucji w czasie, możemy skonstruować model badań na sieciach temporalnych. Są to grafy z ustalonym zestawem wierzchołków, których zbiór krawędzi zależny jest od konkretnego punktu w czasie. Na takim dynamicznym modelu można przeprowadzać pomiary, które pozwalają scharakteryzować daną sieć oraz pomagają wyciągać racjonalne wnioski w przypadku potencjalnych zagrożeń zewnętrznych lub błędów rozprzestrzeniających się w sieci.

W trakcie prezentacji chciałbym bardziej przybliżyć model grafów czasowych i charakterystykę przeprowadzania pomiarów na takiej strukturze. Następnie, opierając się na konkretnej pracy naukowej na ten temat, przedstawię metrykę szacowania zakłóceń w sieciach temporalnych oraz pomiary szkodliwości ataków, zarówno losowych, jak i tych przeprowadzonych bardziej inteligentnie. Przedstawię wyniki zarówno dla przykładów sieci dynamicznych istniejących w rzeczywistości, jak i również dla sieci sztucznie wygenerowanych.

[slides]

Problem lokalizacyjny polega na wybraniu punktu w wierzchołku lub na krawędzi grafu zanurzonego w przestrzeni metrycznej tak by minimalizował on sumę odległości od idealnych lokalizacji agentów. W przypadku gdy preferencje agentów nie są zawczasu znane pewnego rodzaju rozwiązaniem tego problemu jest mechanizm – obiekt matematyczny, który wyznacza wynik jako funkcję zgłoszeń agentów.

Ważną, rozważaną w literaturze, cechą mechanizmu jest odporność na manipulację (agenci nie zyskują podając zgłoszenia niezgodne z ich prawdziwymi preferencjami). Wiadomo, że istnieje tradeoff między optymalnością mechanizmu a jego odpornością na manipulację często mierzony współczynnikiem aproksymacji. W przypadku grafu posiadającego przynajmniej jeden cykl istnieje znaczny rozstrzał między znanym dolnym a górnym ograniczeniem na współczynnik aproksymacji najlepszego, odpornego na manipulację mechanizmu. W ramach swojej pracy magisterskiej próbuję zmniejszyć “dziurę” między owymi znanymi ograniczeniami.

Podczas prezentacji zamierzam najpierw wprowadzić Państwa w tematykę wspomnianą powyżej. Następnie chcę poglądowo przedstawić swój dotychczas najsilniejszy wynik. Z użyciem technik programowania liniowego ustala on w pewnych przypadkach lepsze niż znane oszacowanie górne współczynnika aproksymacji odpornych na manipulację mechanizmów. Na koniec planuję podzielić się z Państwem swoimi doświadczeniami z pracy nad takim teoretycznym zagadnieniem.

[slides]

[slides]

I will present possible topics for a master thesis in the areas of game theory and mechanism design.

I will give an overview of centrality measures and discuss possible topics for the master’s theses.

[slides]