Piotr FALISZEWSKI

(Katedra Informatyki AGH)

Rola metryk w definiowaniu metod głosowania

Przez wybory rozumiemy parę $E = (C,V)$, gdzie $C$ to zbiór kandydatów a $V$ to zbiór wyborców, reprezentowanych jako liniowe porządki nad $C$. Na przyklad, jesli $C = \{a,b,c\}$ oraz mamy dwóch wyborców, $v_1$ i $v_2$, z których pierwszy ma porządek $a > c > b$, to interpretujemy to tak, że $v_1$ najbardziej lubi kandydata a, potem c, a na końcu b. Metoda głosowania to algorytm, który na podstawie oddanych glosów (tj. porządków zgłoszonych przez wyborców) określa, którzy kandydaci wygrali. Najbardziej popularna metoda, metoda większościowa, po prostu zlicza ilu wyborców uważa danego kandydata za najlepszego, a następnie wybiera tego, którego lubi najwięcej osób. Istnieje wiele innych, ciekawych metod.

Mimo, że łatwo podać różne metody zliczania głosów, ważne jest by uzasadnić czemu jedna lub druga metoda jest lepsza (lub chociażby rozsądna). Istnieje kilka sposobów by to zrobić. Po pierwsze, można pokazać, że dana metoda jest jedyna, która spełnia szereg rozsądnych aksjomatów. Po drugie, można pokazać, że dana metoda głosowania maksymalizuje prawdopodobieństwo, że wybrany zostanie ,właściwy" kandydat, zakładając, że glosy oddawane są według pewnego rozkładu prawdopodobieństwa warunkowanego tym, kto jest wlaściwym kandydatem (ang. maximum likelihood estimation).

Na tym wykładzie pokażemy trzecie podejście, oparte o pojęcia konsensusu oraz metryki. Najpierw przedstawimy dokładnie nasz model wyborów oraz nasze podejście oraz pokażemy, że kilka typowych metod głosowania daje się ,uzasadnić" w naszym systemie w bardzo naturalny sposób. Następnie pokażemy, że jeśli nie nałożymy na nasz model żadnych ograniczeń, to wszystkie metody głosowania dają się w nim uzasadnić. Na koniec zajmiemy się rozważeniem rozsądnych ograniczeń, które pozwola nam sie ograniczyć tylko do ,rozsadnych" metod głosowania. Przedstawimy także kilka ogólnych wyników dotyczących złożoności obliczeniowej wyznaczania zwyciężcy wyborów.

Serdecznie zapraszamy wszystkich chętnych!