An Exact Algorithm for the Unanimous Vote Problem

Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha, Christopher Musco, Xinchen YangarXiv 2025 · DOI · arXiv

Abstract

The Unanimous Vote problem involves finding an optimal sequence to flip $n$ biased coins to determine if their outcomes are unanimous (all heads or all tails) while minimizing the expected number of flips. This paper presents an $O(n \log n)$ exact algorithm, resolving the complexity of a problem previously thought to be potentially NP-hard. We demonstrate that a near-greedy strategy is optimal and establish a tight adaptivity gap of 1.2.

Introduction

The Stochastic Boolean Function Evaluation (SBFE) framework seeks to minimize the cost of evaluating a Boolean function when inputs are stochastic. A fundamental instance is the "Unanimous Vote" problem: given $n$ independent coins with head probabilities $p_i$, determine if all outcomes are identical (the "Not-All-Equal" function). The objective is to find a fixed ordering of coins that minimizes the expected number of flips until a mismatch is found or all coins are exhausted.

Figure 1: Comparison of two coin orderings and their associated expected costs. Reordering the coins can significantly reduce the expected number of flips.

Methodology

The authors utilize interchange arguments to characterize the optimal ordering. They introduce the concept of "biased blocks" to describe the state of the evaluation as it progresses:

  • 0-biased: It is more likely that all previous flips were tails.
  • 1-biased: It is more likely that all previous flips were heads.
  • Unbiased: The initial state or a state where probabilities are balanced.

A key finding is the "Greedy Rule," which suggests selecting the coin that maximizes the immediate probability of termination. The authors prove that the optimal ordering is "almost greedy," adhering to this rule at all but potentially one position—the one immediately preceding the final block of coins.

Figure 3: Visualization of an optimal ordering partitioned into biased blocks. The sequence follows monotonicity rules within each block: 0-biased blocks (red) show increasing probabilities, while 1-biased blocks (blue) show decreasing probabilities to maximize termination chance.

The resulting algorithm is highly efficient, running in $O(n \log n)$ time. It works by sorting initial probabilities and then generating a small number of candidate orderings based on the greedy rule and its minor variations. This approach moves the problem from the realm of "hard to approximate" to "easy to solve exactly."

Key Insights

  • Near-Optimality of Greedy: A simple greedy approach is remarkably effective, typically differing from the absolute optimum by at most one expected flip. This suggests that for many practical applications, the greedy heuristic is sufficient.
  • Structural Monotonicity: Within biased blocks, coins must follow specific sorting orders based on $p_i$ to maintain optimality. Specifically, 0-biased blocks should have decreasing $p_i$, and 1-biased blocks should have increasing $p_i$.
  • Adaptivity Gap: The paper proves the adaptivity gap is exactly 1.2. This means that even the most sophisticated "adaptive" strategy that reacts to each flip's outcome can only be 20% better than the best fixed "non-adaptive" ordering. This provides a fundamental limit on the value of adaptivity for this problem class.

Conclusion

By providing an $O(n \log n)$ exact algorithm, this work provides a definitive solution to the Unanimous Vote problem. While the current model assumes unit costs for each flip, future research may extend these findings to arbitrary costs ($c_i$) or other symmetric Boolean functions like the "$k$-of-$n$" function, where the output is 1 if at least $k$ inputs are 1.

Summary updated

BibTeX
@misc{keles2025exact,
  author = {Feyza Duman Keles and Lisa Hellerstein and Kunal Marwaha and Christopher Musco and Xinchen Yang},
  title = {{An Exact Algorithm for the Unanimous Vote Problem}},
  year = {2025},
  eprint = {2510.16678},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.16678},
}
Figure