Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.16678 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914103063216128 |
|---|---|
| author | Keles, Feyza Duman Hellerstein, Lisa Marwaha, Kunal Musco, Christopher Yang, Xinchen |
| author_facet | Keles, Feyza Duman Hellerstein, Lisa Marwaha, Kunal Musco, Christopher Yang, Xinchen |
| contents | Consider $n$ independent, biased coins, each with a known probability of heads. Presented with an ordering of these coins, flip (i.e., toss) each coin once, in that order, until we have observed both a *head* and a *tail*, or flipped all coins. The Unanimous Vote problem asks us to find the ordering that minimizes the expected number of flips. Gkenosis et al. [arXiv:1806.10660] gave a polynomial-time $ϕ$-approximation algorithm for this problem, where $ϕ\approx 1.618$ is the golden ratio. They left open whether the problem was NP-hard. We answer this question by giving an exact algorithm that runs in time $O(n \log n)$. The Unanimous Vote problem is an instance of the more general Stochastic Boolean Function Evaluation problem: it thus becomes one of the only such problems known to be solvable in polynomial time. Our proof uses simple interchange arguments to show that the optimal ordering must be close to the ordering produced by a natural greedy algorithm. Beyond our main result, we compare the optimal ordering with the best adaptive strategy, proving a tight adaptivity gap of $1.2\pm o(1)$ for the Unanimous Vote problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16678 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Exact Algorithm for the Unanimous Vote Problem Keles, Feyza Duman Hellerstein, Lisa Marwaha, Kunal Musco, Christopher Yang, Xinchen Data Structures and Algorithms Consider $n$ independent, biased coins, each with a known probability of heads. Presented with an ordering of these coins, flip (i.e., toss) each coin once, in that order, until we have observed both a *head* and a *tail*, or flipped all coins. The Unanimous Vote problem asks us to find the ordering that minimizes the expected number of flips. Gkenosis et al. [arXiv:1806.10660] gave a polynomial-time $ϕ$-approximation algorithm for this problem, where $ϕ\approx 1.618$ is the golden ratio. They left open whether the problem was NP-hard. We answer this question by giving an exact algorithm that runs in time $O(n \log n)$. The Unanimous Vote problem is an instance of the more general Stochastic Boolean Function Evaluation problem: it thus becomes one of the only such problems known to be solvable in polynomial time. Our proof uses simple interchange arguments to show that the optimal ordering must be close to the ordering produced by a natural greedy algorithm. Beyond our main result, we compare the optimal ordering with the best adaptive strategy, proving a tight adaptivity gap of $1.2\pm o(1)$ for the Unanimous Vote problem. |
| title | An Exact Algorithm for the Unanimous Vote Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.16678 |