Byzantine preferential voting

DOI10.1007/978-3-030-04612-5_22MaRDI QIDQ2190409zbMATH OpenOpenAlexFDO

Authors Darya Melnyk, Yuyi Wang, Roger Wattenhofer

Publication date 18 June 2020

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

zbMATH Keywords

social choiceByzantine agreementmultivalueddistributed votingPareto-validity

Mathematics Subject Classification ID

Social choice (91B14) Voting theory (91B12)

Abstract: In the Byzantine agreement problem, n nodes with possibly different input values aim to reach agreement on a common value in the presence of t < n/3 Byzantine nodes which represent arbitrary failures in the system. This paper introduces a generalization of Byzantine agreement, where the input values of the nodes are preference rankings of three or more candidates. We show that consensus on preferences, which is an important question in social choice theory, complements already known results from Byzantine agreement. In addition preferential voting raises new questions about how to approximate consensus vectors. We propose a deterministic algorithm to solve Byzantine agreement on rankings under a generalized validity condition, which we call Pareto-Validity. These results are then extended by considering a special voting rule which chooses the Kemeny median as the consensus vector. For this rule, we derive a lower bound on the approximation ratio of the Kemeny median that can be guaranteed by any deterministic algorithm. We then provide an algorithm matching this lower bound. To our knowledge, this is the first non-trivial multi-dimensional approach which can tolerate a constant fraction of Byzantine nodes.

Recommendations

• Byzantine agreement with median validity
• Byzantine agreement with a rational adversary
• A distributed voting scheme to maximize preferences
• Multidimensional agreement in Byzantine systems
• On Byzantine generals with alternative plans

Cites work

• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 3405712 (Why is no real title available?)
• A NEW MEASURE OF RANK CORRELATION
• A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision
• A lower bound for the time to assure interactive consistency
• Aggregating inconsistent information: ranking and clustering
• Asynchronous byzantine agreement protocols
• Byzantine Agreement in Expected Polynomial Time
• Byzantine agreement with median validity
• Byzantine vector consensus in complete graphs
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Handbook of Computational Social Choice
• Impossibility of distributed consensus with one faulty process
• Multidimensional agreement in Byzantine systems
• Multidimensional approximate agreement in Byzantine asynchronous systems
• Reaching Agreement in the Presence of Faults
• Reaching approximate agreement in the presence of faults
• Social choice and individual values
• The Byzantine Generals Problem
• The computational difficulty of manipulating an election
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(1)

• Byzantine agreement with median validity

This page was built for publication: Byzantine preferential voting

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