An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU)

Abstract: 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 the approximation ratio 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 + o(1) for the Unanimous Vote problem.