On asymptotic fairness in voting with greedy sampling

Abraham Gutierrez Sanchez, Sebastian Müller, Šebek Stjepan

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

Abstract

The basic idea of voting protocols is that nodes query a sample of other nodes and adjust their own opinion throughout several rounds based on the proportion of the sampled opinions. In the classic model, it is assumed that all nodes have the same weight. We study voting protocols for heterogeneous weights with respect to fairness. A voting protocol is fair if the influence on the eventual outcome of a given participant is linear in its weight. Previous work used sampling with replacement to construct a fair voting scheme. However, it was shown that using greedy sampling, i.e., sampling with replacement until a given number of distinct elements is chosen, turns out to be more robust and performant.
In this paper, we study fairness of voting protocols with greedy sampling and propose a voting scheme that is asymptotically fair for a broad class of weight distributions. We complement our theoretical findings with numerical results and present several open questions and conjectures.
Originalspracheenglisch
Seiten (von - bis)999-1032
Seitenumfang34
FachzeitschriftAdvances in Applied Probability
Jahrgang55
Ausgabenummer3
Frühes Online-DatumMai 2023
DOIs
PublikationsstatusVeröffentlicht - 10 Sept. 2023

ASJC Scopus subject areas

  • Informatik (sonstige)
  • Information systems
  • Diskrete Mathematik und Kombinatorik
  • Statistik und Wahrscheinlichkeit
  • Angewandte Mathematik

Fingerprint

Untersuchen Sie die Forschungsthemen von „On asymptotic fairness in voting with greedy sampling“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren