Vi undersöker problemet med vinnarbestämning från beräkningsteorin för socialt val i dataströmsmodellen. Specifikt anser vi att uppgiften att sammanfatta en godtyckligt beordrad ström av n röster på m kandidater i en liten rymd datastruktur för att kunna få vinnaren bestäms av folkliga röstningsregler. Som vi visar, att hitta den exakta vinnaren kräver att lagra i stort sett alla röster. Så vi fokuserar på problemet med att hitta en ε-vinnare, en kandidat som kunde vinna genom en förändring av högst ε bråkdel av rösterna. Vi visar icke-triviala övre och nedre gränser för utrymme komplexiteten i ε-vinnare beslutsamhet för flera omröstningsregler, inklusive k-godkännande, k-veto, scoring regler, godkännande, maximin, Bucklin, Copeland, och pluralitet med avrinning.
I det första dokumentet ger REF en analys av streamingalgoritmernas utrymmeskomplexitet för vissa röstregler för enskilda vinnare.
Fishing out Winners from Vote Streams
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}