Elections

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Department of Theoretical Computer Science

Synopsis:

We will cover the basics of (committee) elections and, in general, opinion aggregation.

Requirements:

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.

Syllabus of lectures:

1) motivation & single winner rules

2) single winner rules and their properties

3) Impossibility Theorems I

4) Strategic behaviour & manipulation in voting

5) Impossibility Theorems II

6) Domain restriction in voting

7) Computational complexity of Winner determination

8) Possible / Necessary Winner

9) Referenda

10) Committee Election I

11) Committee Election II

12) Liquid Democracy

Syllabus of tutorials:

1) motivation & single winner rules, single winner rules and their properties

2) Impossibility Theorems I, Strategic behaviour & manipulation in voting

3) Impossibility Theorems II, Domain restriction in voting

4) Computational complexity of Winner determination, Possible / Necessary Winner

5) Referenda, Committee Election I

6) Committee Election II, Liquid Democracy

Study Objective:

Be familiar with opinion aggregation and know winner-determination rules and their properties.

Study materials:

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.

Note:

Further information:

https://courses.fit.cvut.cz/NI-VOL/

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master specialization Computer Security, in Czech, 2020 (elective course)
• Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
• Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
• Master specialization Management Informatics, in Czech, 2020 (elective course)
• Master specialization Software Engineering, in Czech, 2020 (elective course)
• Master specialization System Programming, in Czech, version from 2020 (elective course)
• Master specialization Web Engineering, in Czech, 2020 (elective course)
• Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
• Master specialization Computer Science, in Czech, 2020 (elective course)
• Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (elective course)
• Study plan for Ukrainian refugees (elective course)
• Master specialization System Programming, in Czech, version from 2023 (elective course)
• Master specialization Computer Science, in Czech, 2023 (elective course)