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

  • Each student needs to give one presentation in the academic year in order to pass. The topic and the abstract of the presentation must be sent to the organisers (all three of us) 8 days before the talk at latest (that is, on Wednesday, 10:15 am).
  • Attendance is mandatory: each student is entitled to two unexcused absences in a semester.
  • Each first-year student needs to have a topic of a Master Thesis approved in September. The approval process may take some time, so please do not wait too long, and try to find your topic in a proper advance.

2023/2024

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.

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.

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.

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]

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]

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: TBA

2024-03-14: Victoria Wesołowska

2024-03-21: Jan Małaśnicki

2024-03-26 (Tuesday!): TBA

2024-04-04: Grzegorz Kwacz

2024-04-11: Grzegorz Nowakowski

2024-04-18: Wiktor Grzankowski

2024-04-25: TBA

2024-05-09: Michał Lange

2024-05-16: TBA

2024-05-23: Michał Leszczyński

2024-06-06: Mateusz Ładysz

2024-06-13: Anna Stawiska