Quickly Determining Who Won an Election

Lisa Hellerstein*, Naifeng Liu*, Kevin Schewior*

*Kontaktforfatter

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstract

This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absolute or relative, depending on the version) wins. After the voters have made their choices, each vote can be inspected to determine which candidate received that vote. The time (or cost) to inspect each of the votes is known in advance. The task is to (possibly adaptively) determine the order in which to inspect the votes, so as to minimize the expected time to determine which candidate has won the election. We design polynomial-Time constant-factor approximation algorithms for both the absolute-majority and the relative-majority version. Both algorithms are based on a two-phase approach. In the first phase, the algorithms reduce the number of relevant candidates to O(1), and in the second phase they utilize techniques from the literature on stochastic function evaluation to handle the remaining candidates. In the case of absolute majority, we show that the same can be achieved with only two rounds of adaptivity.

OriginalsprogEngelsk
Titel15th Innovations in Theoretical Computer Science Conference, ITCS 2024
RedaktørerVenkatesan Guruswami
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdatojan. 2024
Artikelnummer61
ISBN (Elektronisk)9783959773096
DOI
StatusUdgivet - jan. 2024
Begivenhed15th Innovations in Theoretical Computer Science Conference, ITCS 2024 - Berkeley, USA
Varighed: 30. jan. 20242. feb. 2024

Konference

Konference15th Innovations in Theoretical Computer Science Conference, ITCS 2024
Land/OmrådeUSA
ByBerkeley
Periode30/01/202402/02/2024
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind287
ISSN1868-8969

Bibliografisk note

Publisher Copyright:
© 2024 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Quickly Determining Who Won an Election'. Sammen danner de et unikt fingeraftryk.

Citationsformater