Narzędzia użytkownika

Narzędzia witryny


2021:magiera:start
PRZEWODNICZĄCY I RADA DYSCYPLINY INFORMATYKI
AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE
zapraszają na
publiczną dyskusję nad rozprawą doktorską

mgr inż. Krzysztofa Magiery
Algorithms for and Computational Complexity of the Election Control Problems in Restricted Domains
Termin: 23 czerwca 2021r., godz. 10:00
Miejsce: Online https://tinyurl.com/w72zd3w
PROMOTOR: prof. dr hab. inż. Piotr Faliszewski, Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
RECENZENCI: dr hab. Marcin Dziubiński, Uniwersytet Warszawski
prof. Sylvain Bouveret, Université Grenoble Alpes
Z rozprawą doktorską i opiniami recenzentów można się zapoznać w
Czytelni Biblioteki Głównej AGH, al. Mickiewicza 30

Algorithms for and Computational Complexity of the Election Control Problems in Restricted Domains

mgr inż. Krzysztof Magiera

W poniższej rozprawie doktorskiej podejmujemy temat złożoności obliczeniowej problemów kontroli wyborów z zawężoną dziedziną preferencji. Dyskutujemy szereg konfiguracji poprzez rozpatrywanie różnych metod wyborczych w kontekście kilku najbardziej popularnych kryteriów zawężania dziedziny: preferencji jednowierzchołkowych, preferencji z pojedynczym przecięciem, oraz preferencji spełniających warunek top-monotonicity.

W problemach kontroli wyborów rozpatrujemy scenariusz, w którym poprzez działanie czynników zewnętrznych możliwy jest wpływ na wynik głosowania – zmiana taka może być następstwem zmiany listy kandydatów czy konkretnych głosów, które zostaną przyjęte podczas głosowania. Przy badaniu złożoności obliczeniowej problemów kontroli mamy zadany sposób wybierania zwycięzcy oraz dozwoloną metodę kontroli (np. usuwanie kandydatów). Traktując listę kandydatów oraz preferencje wyborców jako dane wejściowe, pytamy jak trudne obliczeniowo jest stwierdzenie czy możliwe jest aby wybrany przez nas kandydat wygrał, wykonując ustaloną liczbę modyfikacji (możliwe jest również rozpatrywanie kontroli w której chcemy doprowadzić do tego aby wybrany kandydat nie wygrał). Dla dużej części popularnych systemów wyborczych i metod kontroli problemy te okazują się być $\np$-zupełne. Istotnym czynnikiem jest tutaj jednak fakt, że analiza złożoności obliczeniowej dotyczy przypadków pesymistycznych. Wiemy zatem, że dla wielu spośród popularnych systemów wyborczych i metod manipulacji istnieją konfiguracje, dla których stwierdzenie czy możemy wpłynąć na wynik jest bardzo skomplikowane obliczeniowo – nie mamy jednak pewności czy takie pesymistyczne konfiguracje w praktyce będą się w ogóle pojawiać. Aby odnieść się do tego zagadnienia musimy postarać się znaleźć sposób na modelowanie bardziej realistycznych profili wyborczych – jest to w istocie celem omawianych w tej rozprawie zawężonych dziedzin preferencji. Zawężanie dziedziny polega tutaj na wprowadzeniu odgórnych ograniczeń na kształt preferencji głosujących. Jedną z najbardziej popularnych i najczęściej omawianych metod zawężania dziedziny preferencji jest założenie o jednowierzchołkowości –- zakładamy w niej, że istnieje liniowe uszeregowanie kandydatów, względem którego preferencje głosujących maleją jednostajnie w obu kierunkach począwszy od najbardziej preferowanego kandydata przez danego głosującego. Jeśli narzucimy takie dodatkowe kryterium na zbiór rozpatrywanych profili wyborczych okazuje się, że duża część problemów kontroli, które w ogólnym przypadku były trudne obliczeniowo, może zostać rozwiązana w czasie wielomianowym.

W poniższej rozprawie koncentrujemy się na kontynuacji idei badania trudności problemów kontroli poprzez wprowadzanie ograniczeń na kształt profili. Staramy się odpowiedzieć na pytanie czy biorąc pod uwagę inne metody zawężania dziedziny preferencji otrzymamy podobne rezultaty co w przypadku jednowierzchołkowości – w tym celu omawiamy również kryteria pojedynczego przecięcia oraz top-monotonicity. W pierwszej części rozprawy skupiamy się nad problemem rozpoznawania czy dany profil spełnia kryteria danej metody zawężania dziedziny preferencji – jeśli nie jesteśmy w stanie w czasie wielomianowym stwierdzić czy dany profil spełnia dane kryterium, to również, nawet jeśli istnieje, nie wiemy kiedy wykorzystać ,,szybszy'' algorytm, dostosowany do działania dla danego kryterium. W rozprawie prezentujemy nowatorską metodę rozpoznawania zawężonych dziedzin, która oparta jest na sprowadzeniu problemu rozpoznawania do problemu spełnialności SAT-2CNF. Prócz wykorzystania naszego podejścia do rozpoznawania kryterium jednowierzchołkowości i pojedynczego przecięcia, dla których znane są już wielomianowe metody rozpoznawania, pokazujemy również, że może być zastosowane przy rozpoznawaniu kryterium top-monotonic, dla którego wielomianowy algorytm nie był wcześniej znany.

W kolejnych rozdziałach przechodzimy do omawiania konkretnych wariantów problemów kontroli z zawężoną dziedziną preferencji – omawiamy warianty kontroli przez dodawanie i usuwanie kandydatów i głosujących, rozpatrując głosowanie większościowe, aprobatowe oraz metodę Condorcet, przy kryterium pojedynczego przecięcia. Następnie rozpatrujemy rozszerzenie decyzyjnego problemu kontroli polegające na zliczaniu możliwych scenariuszy, w których wybrany kandydat wygrywa. Pokazujemy algorytmy wielomianowe rozwiązujące problem zliczania w kontroli dla głosowania większościowego, $k$-Approval oraz dla metody Condorceta przy kryterium jednowierzchołkowości.

W końcowej części rozprawy poruszamy temat kontroli dla metody wyborczych których celem jest wyłonienie grupy zwycięzców (tzw. \emph{multiwinner elections}). Ze względu na fakt, że metody multiwinner w ostatnich czasach dopiero zyskują na popularności, na moment powstawania tej pracy nie istniały wyniki dla tych metod nawet bez narzucania dodatkowych kryteriów na profile głosów. Prezentujemy tutaj dowody $\np$-trudności dla wybranych sposobów kontroli przy metodach multiwinner: Approval Voting oraz Satisfaction Approval Voting.

Dokumenty

Rozprawa
Recenzja - dr hab. Marcin Dziubiński
Recenzja - prof. Sylvain Bouveret


Ważniejsze publikacje doktoranta:

  1. Krzysztof Magiera, Piotr Faliszewski: Recognizing Top-Monotonic Preference Profiles in Polynomial Time. Journal of Artificial Intelligence Research, Vol. 66, str. 57-84, 2019 (praca prezentowana na konferencji IJCAI-2018),
  2. Krzysztof Magiera, Piotr Faliszewski: How hard is control in single-crossing elections? Autonomous Agents and Multiagent Systems, Vol. 31(3), str. 606-627, 2017 (praca prezentowana na konferencji ECAI-2014).

2021/magiera/start.txt · ostatnio zmienione: 2021/06/10 23:15 przez Krzysztof Magiera