Obliczeniowa Teoria Wyboru Społecznego
Zainteresowania naukowe dotyczą przede wszystkim obliczeniowej teorii wyboru społecznego (ang. computational social choice). W ramach tej dziedziny zajmujemy się algorytmiką, teorią złożoności obliczeniowej, badaniami własności systemów wyborczych, oraz analizą danych. W szczególności zajmujemy się teorią wyboru komitetów, czyli grup kandydatów wspólnie posiadających pewną własność. Najbardziej klasyczny problem wyboru komitetu to wybory parlamentarne, gdzie celem jest znalezienie grupy kandydatów, którzy będą proporcjonalnie reprezentować poglądy wyborców. Inne przykłady obejmują wybór finalistów zawodów (tutaj członkowie komitetu powinni być indywidualnie jak najlepsi) czy wybór towarów, które sklep internetowy umieszcza na swojej stronie domowej (tutaj „towary” będące członkami komitetów powinny być jak najbardziej różnorodne, by zachęcić jak najwięcej klientów). Ważnym przykładem wyborów komitetu są także wybory organizowane w ramach miejskich budżetów obywatelskich: Kandydatami są zgłoszone projekty i zadnie polega na wybraniu takich, które będą jak najbardziej satysfakcjonujące dla głosujących mieszkańców.
W ramach prowadzonych badań poszukujemy wyników dotyczących złożoności obliczeniowej wyznaczania komitetów według zadanych reguł wyborczych, poszukiwania algorytmów dla tego zadania (w tym algorytmów aproksymacyjnych, algorytmów klasy FPT, oraz heurystyk; większość analizowanych problemów jest NP-trudna), poszukiwania metod analizy wyników wyborów oraz wyników opisujących własności aksjomatyczne analizowanych reguł.
Druga z naszych linii badań dotyczy teoretycznych podstaw prowadzenia wyborczych eksperymentów obliczeniowych. Zajmujemy się tutaj, między innymi, analizą metod generowania danych wyborczych oraz porównaniem tak wygenerowanych danych do głosów oddawanych w faktycznych wyborach. W szczególności rozwijamy metodologię tzw. „mapy wyborów”. Mapa wyborów to zbiór instancji wyborów przedstawionych na płaszczyźnie jako punkty w taki sposób, że Euklidesowa odległości między dwoma punktami (dwiema instancjami) odpowiada ich stopniowi podobieństwa. Taka mapa pozwala efektywnie wizualizować wyniki eksperymentów numerycznych oraz analizować zależności między różnymi metodami generowania danych.
Keywords: algorytmika, teoria złożoności obliczeniowej, analiza danych, mapa wyborów
Kontakt: prof. dr hab. inż. Piotr Faliszewski BPP AGH
E-mail: faliszew@agh.edu.pl
Zespół badawczy: CSG
Kierownik Zespołu: prof. dr hab. inż. Jacek Kitowski BPP AGH
Strona www zespołu: www.icsr.agh.edu.pl, home.agh.edu.pl/~pragma/