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, oraz badaniami własności systemów wyborczych. 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).
W ramach prowadzonych badań poszukuje się 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) oraz wyników opisujących własności aksjomatyczne analizowanych reguł. Poza problemem wyznaczania zwycięzców interesujące są także problemy oceny skuteczności danego kandydata, problemy porównywania wyborów, czy też problemy manipulacji wynikami.
Keywords: algorytmika, teoria złożoności obliczeniowej
Kontakt: Piotr Faliszewski
E-mail: faliszew@agh.edu.pl
Zespół badawczy: CSG
Kierownik Zespołu: Prof. Jacek Kitowski
Strona www zespołu: www.icsr.agh.edu.pl