# New Bounds on the Accuracy of Majority Voting for Multi-Class Classification

arXiv: https://arxiv.org/abs/2309.09564 · HTML: https://mlsanity.com/paper/2309.09564/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 46 references that are in the map.
- First posted on arXiv 18 Sep 2023.

## Builds on (most cited first, 4 of 4)

- [Error Rate Bounds and Iterative Weighted Majority Voting for Crowdsourcing](https://mlsanity.com/paper/1411.4086/) (2014)
- [SoK: Oracles from the Ground Truth to Market Manipulation](https://mlsanity.com/paper/2106.00667/) (2021)
- [Federated Learning via Plurality Vote](https://mlsanity.com/paper/2110.02998/) (2021)
- [Astraea: A Decentralized Blockchain Oracle](https://mlsanity.com/paper/1808.00528/) (2018)

## Built on by (most cited first, 5 of 5)

- [Do We Truly Need So Many Samples? Multi-LLM Repeated Sampling Efficiently Scales Test-Time Compute](https://mlsanity.com/paper/2504.00762/) (2025)
- [Optimal Self-Consistency for Efficient Reasoning with Large Language Models](https://mlsanity.com/paper/2511.12309/) (2025)
- [Belief-Calibrated Multi-Agent Consensus Seeking for Complex NLP Tasks](https://mlsanity.com/paper/2510.06307/) (2025)
- [How Effectively Can BERT Models Interpret Context and Detect Bengali Communal Violent Text?](https://mlsanity.com/paper/2506.19831/) (2025)
- [From Detection to Correction: Backdoor-Resilient Face Recognition via Vision-Language Trigger Detection and Noise-Based Neutralization](https://mlsanity.com/paper/2508.05409/) (2025)

## Abstract (arXiv)

Majority voting is a simple mathematical function that returns the value that appears most often in a set. As a popular decision fusion technique, the majority voting function (MVF) finds applications in resolving conflicts, where a number of independent voters report their opinions on a classification problem. Despite its importance and its various applications in ensemble learning, data crowd-sourcing, remote sensing, and data oracles for blockchains, the accuracy of the MVF for the general multi-class classification problem has remained unknown. In this paper, we derive a new upper bound on the accuracy of the MVF for the multi-class classification problem. More specifically, we show that under certain conditions, the error rate of the MVF exponentially decays toward zero as the number of independent voters increases. Conversely, the error rate of the MVF exponentially grows with the number of independent voters if these conditions are not met. We first explore the problem for independent and identically distributed voters where we assume that every voter follows the same conditional probability distribution of voting for different classes, given the true classification of the data point. Next, we extend our results for the case where the voters are independent but non-identically distributed. Using the derived results, we then provide a discussion on the accuracy of the truth discovery algorithms. We show that in the best-case scenarios, truth discovery algorithms operate as an amplified MVF and thereby achieve a small error rate only when the MVF achieves a small error rate, and vice versa, achieve a large error rate when the MVF also achieves a large error rate. In the worst-case scenario, the truth discovery algorithms may achieve a higher error rate than the MVF. Finally, we confirm our theoretical results using numerical simulations.