Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Volby a volební systémy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-VOL Z,ZK 5 2P+1C česky
Garant předmětu:
Dušan Knop
Přednášející:
Dušan Knop
Cvičící:
Dušan Knop, Šimon Schierreich
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Volby a rozhodování se mezi nějakými alternativami jsou nedílnou součástí našich životů. Každý zná systémy, kdy dáváme jeden bod té alternativě, která je podle nás nejlepší, ale existuje mnoho jiných zajímavých možností jak volit vítěznou alternativu. Takové možnosti volby s sebou nesou dobré, ale i horší vlastnosti – v předmětu si řekneme jaké máme sledovat a ukážeme si, že některé kombinace vlastností nelze splnit (tedy neexistuje žádné pravidlo volby vítěze, které by splňovalo nějakou, velice dobrou, sadu vlastností). Jak to, že často je možné pozměnit preference jednoho agenta (popřípadě množiny agentů) takovým způsobem, že vyhraje lepší (pro daného agenta / skupinu agentů) alternativa než před touto změnou? Zaměříme se také na výpočetní (chcete-li algoritmickou) stránku všech zmiňovaných aspektů voleb. Jaká omezení jsou častá v „reálných volbách“ a proč to dělá nějaké problémy triviální a jiné nikoliv? Jaká jsou zajímavá volební pravidla pro volby komisí (popřípadě jejich dobré či špatné vlastnosti)?

Požadavky:

Předpokládáme, že student ovládá základní znalosti algoritmizace (které si mohl osvojit například v předmětu BI-AG1: Algoritmy a grafy I) a teorie složitosti (BI-AAG: Automaty a gramatiky). Výhodou je, pokud student absolvoval kurz NI-CPX, ale není podmínkou.

Osnova přednášek:

1.Motivace, přehled volebních pravidel s jedním vítězem

2.Volební pravidla a jejich charakteristiky

3.Věty o nemožnosti I

4.Strategické chování a manipulace

5.Věty o nemožnosti II

6.Restrikce domény voleb

7.Výpočetní složitost jako bariéra pro strategické chování

8.Co když nelze získat kompletní informace od voličů

9.Volby komisí I

10.Volby komisí II

11.Referenda a participatory budgeting

12.Judgment Aggregation

13.Rezerva(Liquid Democracy)

Osnova cvičení:

1.Motivace, přehled volebních pravidel s jedním vítězem. Volební pravidla a jejich charakteristiky

2.Věty o nemožnosti I.Strategické chování a manipulace

3.Věty o nemožnosti II.Restrikce domény voleb

4.Výpočetní složitost jako bariéra pro strategické chování.Co když nelze získat kompletní informace od voličů

5.Volby komisí

6.Referenda a participatory budgeting.Judgment Aggregation

7.Rezerva(Liquid Democracy)

Cíle studia:

Seznámit se s problematikou agregování preferencí agentů. Znát volební pravidla a jejich vlastnosti.

Studijní materiály:

Handbook of Computational Social Choice. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia (eds.). Dostupné online z http://www.cambridge.org/download_file/951600

E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko. Properties of Multiwinner Voting Rules. Social Choice and Welfare, 48(3): 599-632, 2017.

V. Conitzer, T. Sandholm, and J. Lang. When are Elections with Few Candidates Hard to Manipulate? Journal of the ACM, 54(3), Article 14, 2007

A.D. Taylor. The Manipulability of Voting Systems. The American Mathematical Monthly, 109(4):321-337, 2002.

E. Edith, M. Lackner, and D. Peters. Preference Restrictions in Computational Social Choice: A Survey. 2022.

Poznámka:

Výukové materiály na https://courses.fit.cvut.cz/NI-VOL/

Další informace:
https://courses.fit.cvut.cz/NI-VOL/
Rozvrh na zimní semestr 2024/2025:
Rozvrh není připraven
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 12. 12. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet7428106.html