Efektivní algoritmy pro hledání vítězů v proudech volebních lístků
| Thesis title in Czech: | Efektivní algoritmy pro hledání vítězů v proudech volebních lístků |
|---|---|
| Thesis title in English: | Efficient Algorithms for Finding Winners in Vote Streams |
| Key words: | Proudové algoritmy|výpočetní teorie voleb|systém jednoho přenosného hlasu|nejčastější prvky|vzorkování |
| English key words: | streaming algorithms|computational social choice|Single Transferable Vote|heavy hitters|sampling |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | Mgr. Pavel Veselý, Ph.D. |
| Author: | hidden - assigned by the advisor, waiting for guarantor's approval |
| Date of registration: | 06.12.2024 |
| Date of assignment: | 12.12.2024 |
| Advisors: | doc. Mgr. Martin Koutecký, Ph.D. |
| Guidelines |
| Řešitel se zaměří na proudové (streaming) algoritmy pro odhad vítěze velkých voleb na základě různých pravidel studovaných v oblasti výpočetní teorie voleb ("computational social choice"). Konkrétně se zaměří na pravidla založená na bodování kandidátů dle pořadí ("scoring rules", tedy zobecněná pluralita), nebo na jejich vzájemném poměřování (např. Copeland, Maximin) a také na v praxi používaný systém jednoho přenosného hlasu (“Single Transferable Vote”, STV). Cílem je experimentálně vyhodnotit efektivitu a přesnost použití algoritmů pro náhodné vzorkování volebních lístků nebo hledání nejčastějších lístků (např. algoritmus Misra-Gries. Řešitel se též pokusí navrhnout lepší proudové algoritmy a to hlavně pro STV, např. s pomocí tzv. hierarchical heavy hitters. Dále je cílem prozkoumat pro jednotlivá pravidla definice chyby algoritmu, která budou dávat smysl pro dané pravidlo a zároveň půjdou efektivně spočítat. Algoritmy budou otestovány na synteticky vygenerovaných volebních lístcích, např. z exponenciální nebo Zipfovské distribuce, a také na skutečných volebních datech v knihovně PrefLib.
Práce navazuje na řešitelův ročníkový projekt "Vote streams". |
| References |
| [1] Arnab Bhattacharyya, Palash Dey: Fishing out Winners from Vote Streams. CoRR abs/1508.04522 (2015)
[2] Arnab Bhattacharyya, Palash Dey, David P. Woodruff: An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related Problems. ACM Trans. Algorithms 15(1): 2:1-2:27 (2019) [3] Palash Dey, Nimrod Talmon, Otniel van Handel: Proportional Representation in Vote Streams. AAMAS 2017: 15-23 [4] Palash Dey, Arnab Bhattacharyya: Sample Complexity for Winner Prediction in Elections. AAMAS 2015: 1421-1430 [5] Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava: Finding Hierarchical Heavy Hitters in Data Streams. VLDB 2003: 464-475 [6] Cormode, Graham, and Ke Yi. Small summaries for big data. Cambridge University Press, 2020. |