Distributed monitoring of election winners

DOI10.1016/J.ARTINT.2019.07.007MaRDI QIDQ2289007zbMATH OpenOpenAlexWikidataFDO

Authors Arnold Filtser, Nimrod Talmon

Publication date 20 January 2020

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02206

zbMATH Keywords

communication complexitydistributed streamssublinear algorithms

Mathematics Subject Classification ID

Voting theory (91B12)

Abstract: We consider distributed elections, where there is a center and $k$ sites. In such distributed elections, each voter has preferences over some set of candidates, and each voter is assigned to exactly one site such that each site is aware only of the voters assigned to it. The center is able to directly communicate with all sites. We are interested in designing communication-efficient protocols, allowing the center to maintain a candidate which, with arbitrarily high probability, is guaranteed to be a winner, or at least close to being a winner. We consider various single-winner voting rules, such as variants of Approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules. For the voting rules we consider, we show that, using communication which is logarithmic in the number of voters, it is possible for the center to maintain such approximate winners; that is, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. We complement our protocols with lower bounds. Our results are theoretical in nature and relate to various scenarios, such as aggregating customer preferences in online shopping websites or supermarket chains and collecting votes from different polling stations of political elections.

Review text

This paper presents communication-efficient protocols for maintaining approximate winners in distributed vote streams. The communication complexity of general techniques for designing such protocols (namely, sampling-based protocols, protocols based on checkpoints, and protocols based on counting frequencies) have their communication complexity analyzed. Conditions are established under which, using communication which is logarithmic in the number of voters, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. For various single winner voting rules, including variants of approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules, an analysis of how to choose which protocol to use at which scenario, depending on the specific parameters of the problem at hand, is developed. The effect that the number of voters, the number of candidates, the number of sites and the required approximation have on the communication complexity of the protocols is studied. Lower bounds are obtained. An almost tight lower bound for plurality-winner-tracking is derived. It improves the state-of-the-art lower bound for count-tracking. An almost tight lower bound for deterministic protocols for approval-winner-tracking is also derived.

Recommendations

• A distributed voting scheme to maximize preferences
• The distortion of distributed voting
• The distortion of distributed voting
• On the evaluation of election outcomes under uncertainty
• The communication burden of single transferable vote, in practice

Cites work

• Algorithms for distributed functional monitoring
• Communication complexity
• Communication Complexity
• Continuous sampling from distributed streams
• Control and bribery in voting
• Determining possible and necessary winners given partial orders
• Distributed monitoring of election winners
• Functional Monitoring without Monotonicity
• Incompleteness and incomparability in preference aggregation: complexity results
• Optimal Random Sampling from Distributed Streams Revisited
• Optimal tracking of distributed heavy hitters and quantiles
• Optimizing positional scoring rules for rank aggregation
• Swap bribery

Cited in

(3)

• The communication burden of single transferable vote, in practice
• Distributed monitoring of election winners
• Robustness among multiwinner voting rules

This page was built for publication: Distributed monitoring of election winners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2289007)