Doktoraty Wydziału IET

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
^  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 ====

 {{ :2021:magiera:rozprawa.pdf |Rozprawa}} \\
 {{ :2021:magiera:recenzja-dziubinski.pdf |Recenzja - dr hab. Marcin Dziubiński}} \\
 {{ :2021:magiera:recenzja-bouveret.pdf |Recenzja - prof. Sylvain Bouveret}}

----

 **Ważniejsze publikacje doktoranta**:

  - 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),
  - 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).

----
Doktoraty Wydziału IET

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
