Volby a volební systémy

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ů:

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (volitelný předmět)