Stanisław Szufa, nasz współpracownik i doktorant na Wydziale Matematyki i Informatyki, otrzymał grant w konkursie PRELUDIUM Narodowego Centrum Nauki na projekt Problem Izomorfizmu Elekcji", który będzie realizowany w Centrum Badań Ilościowych nad Polityką. Gratulujemy jemu oraz jego opiekunowi naukowemu, członkowi Rady Naukowej CBIP Piotrowi Faliszewskiemu.

W naszym projekcie zamierzamy przedstawić rodzinę problemów (przybliżonego) izomorfizmu elekcji, które mają na celu zbadanie odległości pomiędzy elekcjami. Naszym celem jest znalezienie algorytmów, rozwiązujących te problemy (w tym, podejścia: dokładne, przybliżone i heurystyczne). Chcielibyśmy także zbadać właściwości problemu oraz przetestować jego skuteczność w praktyce. Przez elekcję rozumiemy zbiór kandydatów i zbiór wyborców, w którym każdy wyborca posiada pewne preferencje względem kandydatów. W zależności od rodzaju wyborów można stosować różne rodzaje głosów. Np. głos preferencyjny pozwala wyborcy na uszeregowanie wszystkich kandydatów zgodnie z jego preferencjami, podczas gdy głos aprobujący pozwala wyborcy na wskazanie zbioru aprobowanych kandydatów (pozostali kandydaci traktowani są jako odrzuceni). W naszych badaniach skupimy się na wyborach z głosami preferencyjnymi.

W problemie izomorfizmu elekcji mamy zadane dwie elekcje z takimi samymi liczbami kandydatów i wyborców każda, i pytamy, czy istnieją indywidualne dopasowania między kandydatami i między wyborcami obu elekcji, które przekształcają pierwszą elekcję w drugą. Jeśli możliwe jest dopasowanie kandydatów i wyborców w taki sposób, oznacza to, że te dwie elekcje są izomorficzne. Problem rozstrzygnięcia, czy dwie elekcje są izomorficzne, nazywamy problemem dokładnego izomorfizmu elekcji. Jednak w większości przypadków spodziewamy się, że tego rodzaju dopasowanie nie będzie możliwe i w takich sytuacjach chcielibyśmy obliczyć odległość między elekcjami. Ten bardziej ogólny problem (a właściwie tę rodzinę problemów) nazywamy przybliżonym izomorfizmem elekcji.