Master’s Seminar
Games, Networks and Elections
About
This is a seminar for MSc students run at the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw. The seminar concerns research at the interface of computer science, artificial intelligence and economics. The topics of interest include game theory (both cooperative and non-cooperative), social networks analysis, social choice, as well as other topics related topics such as mechanism design, fair division, market design, and information economics. You can find a full description of the seminar in USOS.
The seminar is organised by Marcin Dziubiński, Oskar Skibski, and Piotr Skowron. The seminar takes place every Thursdays at 10:15 in room 4050 at the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw.
Organisation notes
2024/2025
2024–10-03: Piotr Skowron
A Generalised Theory of Proportionality in Collective Decision Making
We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a single constraint on the number of candidates that need to be selected), various elections with diversity constraints, the model of public decisions (where decisions needs to be taken on a number of independent issues), and the model of collective scheduling. A critical property of voting is that it should be fair — not only to individuals but also to groups of voters with similar opinions on the subject of the vote; in other words, the outcome of an election should proportionally reflect the voters’ preferences. We formulate axioms of proportionality in this general model. Our axioms do not require predefining groups of voters; to the contrary, we ensure that the opinion of every subset of voters whose preferences are cohesive-enough are taken into account to the extent that is proportional to the size of the subset. Our axioms generalise the strongest known satisfiable axioms for the more specific models. We explain how to adapt two prominent committee election rules, Proportional Approval Voting (PAV) and Phragmén Sequential Rule, as well as the concept of stable-priceability to our general model. The two rules satisfy our proportionality axioms if and only if the feasibility constraints are matroids.
Based on the following paper: https://arxiv.org/abs/2307.06077
[slides]
2023/2024
2024-06-06: Mateusz Ładysz
Routing Betweenness Centrality
Miara Betweenness-Centrality jest często stosowana w sieciach społecznych i komputerowych w celu oszacowania potencjalnych możliwości monitorowania i kontroli danych, jakie może mieć dany wierzchołek. Na prezentacji przedstawię miarę Routing Betweenness Centrality (RBC), która uogólnia miary Betweenness, takie jak Shortest Path Betweenness, Flow Betweenness czy Traffic Load Centrality. Następnie zaprezentuję algorytmy liczenia miary RCB dla pojedynczego wierzchołka oraz grupy wierzchołków.
2024-05-23: Michał Leszczyński
Shapley, Myerson i Owen — obliczanie oraz zastosowania koalicyjnych miar centralności
Wartości Shapleya, Myersona i Owena to szeroko znane podejścia do oceny wpływu wierzchołka na wartość koalicji. Podczas prezentacji opowiem o ich definicjach, interpretacjach oraz o miarach centralności wzorowanych na nich. Następnie omówię algorytmy dokładne oraz aproksymacyjne wykorzystywane do obliczania wspomnianych miar centralności. Na koniec przedstawię problemy, w których opisane miary centralności znajdują rozwiązania bliższe ludzkiej intuicji niż inne, typowe miary centralności.
2024-05-16: Victoria Wesołowska
Can LLMs read plots? — benchmark and evaluation
W pracy magisterskiej zajmuję się sprawdzeniem, czy wielomodalne Large Language Models potrafią czytać wykresy. W literaturze jest wiele badań oceniających możliwości LLMów, ale brakuje ścisłych testów, które w ilościowy sposób pozwoliłyby ocenić możliwości modeli. Dodatkowa trudność polega na tym, że nie ocenianie LLMów na gotowych zbiorach danych może dać błędne rezultaty — duże modele najprawdopodobniej zostały na nich już wytrenowane. Moim celem jest zatem stworzenie benchmarku, który pozwoli oceniać czy LLMy potrafią czytać wykresy i rozumować na ich podstawie.
2024-05-09: Michał Lange
Aksjomatyzacja Grupowego Closeness
Na prezentacji przypomnę krótko czym są miary centralności. Przedstawię fragment pracy “Closeness centrality via the Condorcet principle” Oskara Skibskiego, głównie samą aksjomatyzację closeness oraz próby rozszerzenia jej do grupowej. Następnie przedstawię fragment pracy “Axioms for Distance-Based Centralitiesa” Oskara Skibskiego i Jadwigi Sosnowskiej dotyczący Cut-Vertex i moją propozycję uogólnienia go do grupowych miar centralności. Na koniec przedstawię moją aksjomatyzację jednej wersji grupowego closeness.
2024-04-18: Wiktor Grzankowski
Rynkowe podejście do analizy wyborów komitetowych
Podczas prezentacji omówię zaproponowane w pracy “Market-Based Explanations of Collective Decisions” [Peters, Pierczyński, Shah, Skowron] koncepty analizy wyborów komitetowych. Skupię się na opisaniu aksjomatu Stable Priceability, wskazując jego zalety i nowatorskie podejście do tłumaczenia słuszności wybranych komitetów. Wskażę także, dlaczego znane aksjomaty, takie jak rdzeń, pomimo dużej złożoności obliczeniowej, nie gwarantują intuicyjnie sprawiedliwych wyborów.
2024-04-11: Grzegorz Nowakowski
NP-trudne metryki ewaluacji reguł głosowania w wyborach komitetowych
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.
2024–04-04: Grzegorz Kwacz
Klastrowanie wyborców na podstawie ich preferencji
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.
2024–03-21: Marcin Dziubiński
Propozycje tematów magisterskich
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.
2024–02-29: Antoni Hanke
Comparative Analysis of Convolutional and Transformer Architectures in Go Policy Networks
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.
2024–01-25: Adrian Górecki
Uogólniona teoria proporcjonalności w podejmowaniu kolektywnych decyzji
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.
2024–01-18: Dawid Sula
Znajdywanie optymalnych strategii w grze blotto
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.
2024–01-11: Piotr Kępczyński
Rozszerzanie wierzchołkowych miar centralności do grupowych miar
centralności
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]
2023–12-21: Franciszek Hnatów
Kryteria proporcjonalności w metodach głosowania przez aprobaty
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]
2023–12-07: Kacper Harasimowicz
Budżet partycypacyjny z kumulatywnym głosowaniem
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]
2023–11-30: Barbara Rosiak
Indukowana, wewnętrzna i zewnętrzna miara centralności
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]
2023–11-23: Michał Szczęśniak
Miara centralności Attachment: aksjomatyczne podejście do analizy łączności w sieciach.
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]
2023–11-16: Grzegorz Szumigaj
Sieci temporalne: ich struktura i podatność na błędy oraz ataki
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]
2023–11-09: Krzysztof Rogowski
Ograniczenie górne współczynnika aproksymacji optymalnego, odpornych na manipulację mechanizmu lokalizacyjnego na grafach z cyklem
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]
2023–10-26: Marcin Waniek
Presentation of MsC topics.
2023–10-19: Marcin Dziubiński
Presentation of MsC topics.
I will present possible topics for a master thesis in the areas of game theory and mechanism design.
2023–10-12: Oskar Skibski
Presentation of MsC topics.
I will give an overview of centrality measures and discuss possible topics for the master’s theses.
[slides]
2023–10-05: Piotr Skowron
Presentation of MsC topics.
During the presentation we will discuss the issue of fairness in the context of participatory budgeting. We will discuss the method of equal shares and the effect of implementing this rule in practice. A list of potential MsC topics that are related to the topic of participatory budgeting is available here.
[slides]
Plan of Presentations
2023-10-05: Presentation of MsC topics by Piotr Skowron.
2023-10-12: Presentation of MsC topics by Oskar Skibski.
2023-10-19: Presentation of MsC topics by Marcin Dziubiński.
2023-10-26: Presentation of MsC topics by Marcin Waniek.
2023-11-09: Krzysztof Rogowski.
2023-11-16: Grzegorz Szumigaj.
2023-11-23: Michał Szczęśniak.
2023-11-30: Barbara Rosiak.
2023-12-07: Kacper Harasimowicz.
2023-12-14: — no seminar —
2023-12-21: Franciszek Hnatów.
2024-01-11: Piotr Kępczyński.
2024-01-18: Dawid Sula.
2024-01-25: Adrian Górecki.
2024-02-29: Antoni Hanke
2024-03-07: — no seminar —
2024-03-14: — no seminar —
2024-03-21: Marcin Dziubiński
2024-03-26 (Tuesday!): — no seminar —
2024-04-04: Grzegorz Kwacz
2024-04-11: Grzegorz Nowakowski
2024-04-18: Wiktor Grzankowski
2024-04-25: — no seminar —
2024-05-09: Michał Lange
2024-05-16: Victoria Wesołowska
2024-05-23: Michał Leszczyński
2024-06-06: Mateusz Ładysz
2024-06-13: Anna Stawiska