Decidim is one of several popular software packages for running online PB voting platforms. This platform support voting but does not have implemented algorithms for counting ballots and selecting projects. The task would be to add such a functionality to it.

Recently we have created a tool called Pabustats, which allows to compare several voting rules for Participatory Budgeting. For each election we can compute different statistics concerning distribution of voters’ happiness and efficiency of spending public money. The task is to extend this tool so that it supports additional statistics, some of which might be hard to compute in a polynomial time.

This project concerns applying know clustering techniques in order to divide the voters into subgroups, based on how similarly these voters vote. Second, one should evaluate on data whether some of the election rules discriminate some of the groups of voters. The best source of data is Pabulib.

Consider a population with dichotomous (approval) preferences over a set of 300 alternatives. Assume that 50% of the population approves of the first 100 alternatives, 30% of the next 100 alternatives, and 20% of the last 100. Suppose that we want to obtain a ranking of the alternatives that reflects the preferences of the population. Perhaps the most straightforward approach is to use Approval Voting (AV), which ranks the alternatives from the most frequently approved to the least frequently approved. A striking property of the resulting ranking is that half of the population does not approve any of the first 100 alternatives in the ranking.

In many scenarios, rankings produced by Approval Voting are highly unsatisfactory; rather, it is desirable to interleave alternatives supported by different (sufficiently large) groups. For instance, consider an anonymous user running a search engine to find results for the query “Armstrong”. If 50% of the users performing this search would like to see results for Neil Armstrong, 30% for Lance Armstrong, and 20% for Louis Armstrong, it is not desirable to only place results referring to Neil Armstrong in the top part of the ranking; rather, results related to each of the Armstrongs should be displayed in appropriately high positions.

Good methods for proportional rankings exist if we have approval preferences. The goal is to extend these results to non-binary preferences.

This project is about designing a new rule in an important voting framework. The rule will be closely inspired by the known rule from the social choice theory. It is about proving theorems about properties of the rule with a close guidance by the supervisor. It is about combining the idea of the Condorcet winner with the idea of sequential proportional approval voting. A very interesting theoretical work that could serve as an introduction to a PhD.

Celem projektu jest zastosowanie reguł wyborczych z wyborów komitetowych do grafów i analiza uzyskanych w ten sposób grupowych miar centralności. Dobrym punktem wyjścia byłaby implementacja tych metod w istniejącym kalkulatorze centralności rozwijanym na wydziale. Analiza może być teoretyczna, ale wchodzi w grę także analiza eksperymentalna.

Celem pracy jest zbadanie klasycznych miar centralności, czyli funkcji oceniających istotność wierzchołków w grafie, pod kątem własności sprawiedliwości. Sprawiedliwość (ang. fairness) jest własnością zaproponowaną przez Myersona w grach koalicyjnych, która mówi, że oba wierzchołki zyskują tyle samo na dodaniu krawędzi pomiędzy nimi. Większość miar centralności nie spełnia sprawiedliwości. W pracy odpowiemy na pytanie jaka jest maksymalna proporcja zysku jednego wierzchołka do zysku drugiego. O ile odpowiedź na to pytanie może być prosta w przypadku nieskomplikowanych miar centralności (np. miary beta), to w przypadku centralności opartych na rekurencyjnych definicjach (np. PageRanka czy centralności wektora własnego) będzie to stanowiło wyzwanie.

Celem projektu jest stworzenie biblioteki oceniającej grupy cech w algorytmach uczenia maszynowego. Biblioteka będzie rozszerzeniem biblioteki SHAP, która ocenia pojedyncze cechy. Biblioteka powinna pozwalać zarówna na ocenę zadanej grupy cech, ale także mogłaby pokazywać (przy pomocy grafu) synergię pomiędzy cechami w oparciu o obliczenie oceny każdej pary cech.

Celem projektu jest opracowanie i implementacja algorytmu obliczającego równowagę Nasha w wariancie gry Pułkownik Blotto, w którym prawdopodobieństwo zwycięstwa na poszczególnych polach bitew jest określone przez funkcję sukcesu kontestu, której wartość zależy od zasobów przypisanych do pól.

Celem projektu jest opracowanie i implementacja algorytmu obliczającego równowagę Nasha w wariancie gry Pułkownik Blotto, w którym gracze mogą kupować zasoby i koszty zasobów są liniowe.

Celem projektu jest opracowanie i implementacja algorytmu wyznaczającego równowagę Nasha gry w ukrywanie i eksplorację sieci, w której strategie ukrywającego to grafy spójne nad zadanym zbiorem wierchołków co najwyżej jednym cyklem wraz z wybranym wierzchołkiem (ukryciem), a strategie szukającego to strategie realizujące rozszerzające się przeszukiwanie (eksplorację) grafu. Interesującymi problemami związanymi z tym tematem jest opracowanie strategii szukającej gwarantujące lepszy oczekiwany czas znalezienia ukrycia niż znane strategie.

Celem projektu jest opracowanie opracowanie odpornego na manipulację i jak najbardziej wydajnego mechanizmu allokacji ograniczonej liczby zasobów obronnych do wierzchołków grafu w sytuacji, gdy planista nie zna połączeń między wierzchołkami grafu i musi informację o połączeniach uzyskać od wierzchołków. Każdy wierzchołek chce mieć przydzielony zasób obronny oraz chce by zasób obronny był przydzielony jego ustalonemu sąsiadowi.

How important events in a scientist’s career affect their centrality?

Is it possible to effectively hide from link prediction algorithms based on graph neural networks?

Can anomaly detection algorithms be used to identify the nodes who perform strategic rewiring of the network?

Can Explainable AI be used to develop more effective, personalized hiding methods?

We have recently created a simple library Pabutools which contains the implementation of the most important voting rules for participatory budgeting. There are several rules, which are more complex and NP-hard to compute. These rules are mainly based on Integer Linear Programming. The task is to add an efficient implementation of such rules to the library.

We have recently created a simple library Pabutools which contains the implementation of the most important voting rules for participatory budgeting. There are several rules, which are more complex and NP-hard to compute. These rules are mainly based on Integer Linear Programming. The task is to add an efficient implementation of such rules to the library.

The project is about extending the recent work with my undergraduate student. Have a look at this paper.

Przepływowa centralność pośrednictwa (ang. flow betweenness centrality) jest opartą na przepływach alternatywą do centralności pośrednictwa. Miara ta ocenia istotność wierzchołka w grafie, porównując przepływ pomiędzy dowolnymi parami wierzchołków w grafie z danym wierzchołkiem i bez niego. Celem pracy będzie stworzenie aksjomatycznej charakteryzacji przepływowej centralności pośrednictwa, czyli wskazanie prostych własności, które unikalnie ją charakteryzują. W tym celu zamierzamy wykorzystać niedawną charakteryzację miar witalności do których przepływowa centralność pośrednictwa należy [Skibski 2021]. Punktem wyjścia do naszej charakteryzacji będzie skupienie się na prostszym wariancie centralności, w którym ustalony jest jeden wierzchołek docelowy (tzn. centralność nie rozpatruje wszystkich par wierzchołków, a tylko te, w których jeden wierzchołek jest ustalony).

Centralność łączenia jest miarą centralności, która ocenia rolę wierzchołków w utrzymywaniu grafu spójnym. Miara ta opiera się na teorii gier koalicyjnych i wykorzystuje wartość Shapleya, aby wziąć pod uwagę wkład marginalny wierzchołka do wszystkich spójnych podgrafów w grafie. Niedawno zaproponowane zostało rozszerzenie tej centralności do grup wierzchołków, nazwane grupową centralnością łączenia. Obliczanie zarówno wierzchołkowej jak i grupowej miary łączenia jest #P-zupełne. Celem pracy będzie opracowanie algorytmów aproksymacyjnych dla dwóch problemów: (1) obliczania grupowej centralności łączenia dla zadanej grupy wierzchołków oraz (2) znajdowania grupy wierzchołków, która spośród grup o zadanej wielkości ma największą grupową centralność łączenia. W algorytmach wykorzystana zostanie charakteryzacja miary jako różnicy potencjału (pewnej funkcji oceny grafu) pełnego grafu oraz grafu powstałego po usunięciu wierzchołka lub grupy wierzchołków.

Miary centralności to funkcje, które oceniają istotność elementów w sieci. Celem pracy jest zastosowanie tych miar w szachach w celu wskazania istotności pól oraz bierek na szachownicy w konkretnej pozycji. Źródłem sieci powiązań między polami i bierkami będą możliwe ruchy jakie mogą zostać wykonane w danej pozycji. Użyteczność wykorzystanych miar centralności będzie mierzona w oparciu o ruchy proponowane przez silnik szachowy Stockfish. Dotyczy to różnych konfiguracji silnika oraz analizy partii graczy o różnych rankingach. Wizualnym zwieńczeniem pracy będzie stworzenie rozszerzenia do przeglądarki Google Chrome dla strony lichess.org, które będzie pozwalała na wyświetlanie istotności pól na planszy w trakcie rozgrywki.

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 ramach pracy zajmę się tym problemem w sytuacji, gdy idealne punkty agentów nie są znane i wymagane jest stworzenie mechanizmu, który wyznacza rozwiązanie jako funkcję idealnych pozycji zgłoszonych przez agentów i jest jednocześnie odporny na manipulację (tzn. zgłaszanie nieprawdziwej lokalizacji w celu uzyskania rozwiązanie leżącego bliżej prawdziwej idealnej lokalizacji agenta). Rozwiązaniem tego problemu jest zaproponowanie mechanizmu, który minimalizuje sumę odległości od idealnych lokalizacji agentów w klasie mechanizmów odpornych na manipulację.

Celem projektu jest zbadanie nowych klas odpornych na manipulację mechanizmów na małych grafach z cyklem i dla ograniczonej liczby agentów, w tym opracowanie mechanizmów poprawiających znane ograniczenia na współczynnik aproksymacji.