Efektivní algoritmy pro hledání vítězů v proudech volebních lístků
| Název práce v češtině: | Efektivní algoritmy pro hledání vítězů v proudech volebních lístků |
|---|---|
| Název v anglickém jazyce: | Efficient Algorithms for Finding Winners in Vote Streams |
| Klíčová slova: | Proudové algoritmy|výpočetní teorie voleb|systém jednoho přenosného hlasu|nejčastější prvky|vzorkování |
| Klíčová slova anglicky: | streaming algorithms|computational social choice|Single Transferable Vote|heavy hitters|sampling |
| Akademický rok vypsání: | 2024/2025 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | Mgr. Pavel Veselý, Ph.D. |
| Řešitel: | skrytý - zadáno vedoucím/školitelem, čeká na schválení garantem |
| Datum přihlášení: | 06.12.2024 |
| Datum zadání: | 12.12.2024 |
| Konzultanti: | doc. Mgr. Martin Koutecký, Ph.D. |
| Zásady pro vypracování |
| Ř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". |
| Seznam odborné literatury |
| [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. |