Byzantine preferential voting
From MaRDI portal
Publication:2190409
DOI10.1007/978-3-030-04612-5_22zbMATH Open1443.91134arXiv1803.02720OpenAlexW2793424722MaRDI QIDQ2190409FDOQ2190409
Darya Melnyk, Yuyi Wang, Roger Wattenhofer
Publication date: 18 June 2020
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.
Full work available at URL: https://arxiv.org/abs/1803.02720
Recommendations
Cites Work
- Social choice and individual values
- Title not available (Why is that?)
- A NEW MEASURE OF RANK CORRELATION
- Voting schemes for which it can be difficult to tell who won the election
- Aggregating inconsistent information
- A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision
- Impossibility of distributed consensus with one faulty process
- Reaching Agreement in the Presence of Faults
- The Byzantine Generals Problem
- The computational difficulty of manipulating an election
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- Handbook of Computational Social Choice
- Title not available (Why is that?)
- A lower bound for the time to assure interactive consistency
- Reaching approximate agreement in the presence of faults
- Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
- Multidimensional approximate agreement in Byzantine asynchronous systems
- Asynchronous byzantine agreement protocols
- Byzantine vector consensus in complete graphs
- Multidimensional agreement in Byzantine systems
- Byzantine Agreement in Expected Polynomial Time
- Title not available (Why is that?)
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)
