PaperlayerView exact revision on arXiv

Source-linked AI summary

On Extensions of the Unanimous Vote Problem

Evan J. R. Brody, Haya Diwan, Lisa Hellerstein, Thomas Lidbetter

arXiv:2609.36508v1cs.DS

TL;DR

The paper studies extensions of the non-adaptive Unanimous Vote problem, including repeated coin flips and dice with different stopping rules. It develops greedy and approximation approaches, establishing structural results and approximation guarantees for these variants.

  • Problem

    The paper examines how the non-adaptive Unanimous Vote setting extends to repeated coin flips and dice stopped after two distinct outcomes or after all d outcomes appear.

    Source: §1 · p. 2

  • Method

    It uses a greedy rule for unlimited flips, relates an optimal sequence to a mechanical word, combines generalized greedy rules for two-outcome stopping, and reduces the all-outcomes problem to Submodular Ranking.

    Source: §1 · p. 2, §2.2 · p. 3, §2.4 · p. 6

  • Results

    The Unlimited-Flips adaptivity gap is 1.2, the particular optimal sequence is periodic exactly when log_h t is rational, the two-outcome dice problem has a PTAS, and the all-outcomes problem has an O(log d)-approximation.

    Source: §1 · p. 2, §2.4 · p. 6

  • Takeaways & Limitations

    The Submodular Ranking reduction can also apply to other non-adaptive stochastic probing problems when appropriate submodular functions with small goal values can be constructed.

    Source: §5 · p. 11

    The Submodular Ranking approach yields good approximation bounds only when appropriate submodular functions with small goal values can be constructed, which is not possible for all problems.

    Source: §5 · p. 11

Abstract

from arXiv · show

The Unanimous Vote problem is to determine a fixed order in which to flip each of $n$ biased coins, where each coin can be flipped only once, such that the expected number of flips until seeing both a head and a tail (or flipping all coins) is minimized. Duman Keles et al. (arXiv:2510.16678 [cs.DS]) gave an $\mathcal{O}(n \log n)$-time algorithm for this problem. Extensions of the Unanimous Vote problem are a rich source of stochastic optimization problems. We focus on three: (1) a variant in which each coin can be flipped arbitrarily many times (a solution is thus an infinite sequence of coin choices), (2) a generalization with $d$-sided dice, that can each be rolled once, where dice must be rolled until two different outcomes are observed (or all dice have been rolled), and (3) a different generalization with $d$-sided dice, where dice must be rolled until all $d$ outcomes have been observed. For (1), we show that there is an optimal sequence which follows a simple greedy rule; the same rule only gives a 1-additive approximation for the original problem (arXiv:2510.16678 [cs.DS]). The rule also yields a correspondence between a particular optimal sequence and a related mechanical word, which we exploit to characterize the conditions under which this optimal sequence is periodic. We establish tight multiplicative and additive adaptivity gaps for this variant. For (2), we show that two different generalizations of the greedy rule from (arXiv:2510.16678 [cs.DS]) can be combined to obtain a PTAS. For (3), we give an $\mathcal{O}(\log d)$-approximation algorithm by reducing the problem to Submodular Ranking (arXiv:1007.2503 [cs.DS]); the same reduction technique can be used to yield approximation algorithms for other stochastic probing problems. Finally, we pose a number of related open questions.

1 Introduction

The paper extends the Unanimous Vote problem through repeated coin flips and two dice-based stopping rules, giving structural results and approximation algorithms. It also connects the Submodular Ranking reduction to other stochastic probing problems.

1 Introduction

  • The Unanimous Vote problem minimizes expected flips until both a head and a tail appear; an exact O(n log n)-time algorithm resolves its complexity.It is a Stochastic Boolean Function Evaluation problem, and its non-adaptive variant is the first nontrivial SBFE problem known to be solvable in polynomial time.Source: §1 · p. 2
  • For Unlimited-Flips, an optimal sequence has adaptivity gap 1.2, and the paper relates a particular optimal sequence’s periodicity to a mechanical word.The periodicity characterization appears in the later section on this variant.Source: §1 · p. 2
  • For dice stopped after two distinct outcomes, generalizing the greedy algorithm yields a PTAS; exact optimization is NP-hard when d is part of the input.The hardness result is stated in Appendix C.2.Source: §1 · p. 2
  • For dice rolled until all d outcomes appear, the paper gives an O(log d)-approximation via Submodular Ranking [AG11].The authors note that this reduction approach can also apply to other non-adaptive stochastic probing problems.Source: §1 · p. 2

1.1 Related Work

  • The Submodular Ranking reduction is a non-adaptive analogue of the Q-value approach [Bac+18], but it cannot improve the approximation bound for uniform matroids.Its applicability depends on constructing appropriate submodular functions with small goal values.Source: §1.1 · p. 3

2 The Unlimited-Flips Unanimous Vote Problem

For the unlimited-flips variant, the paper establishes a greedy optimal sequence and characterizes its adaptivity gaps. It also characterizes when a particular optimal sequence is periodic.

2.1 Preliminaries

  • A position is 0-biased when prior flips are more likely all tails than all heads, and 1-biased when they are more likely all heads than all tails.Equal probabilities make the position unbiased.Source: §2.1 · p. 3

2.2 Greedy is Optimal

  • An optimal Unlimited-Flips sequence can follow the greedy rule at every position, choosing only the lowest- and highest-bias coins.If both extreme biases lie on the same side of 1/2, an optimal sequence uses only one extreme coin; if they straddle 1/2, it chooses coin 1 at 1-biased positions and coin n at 0-biased or unbiased positions.Source: §2.2 · pp. 3–4

2.3 Adaptivity Gap

  • The multiplicative and additive adaptivity gaps are exactly 1.2 and 1/2, respectively.The lower bounds for both arise at the instance p1 = 0, p2 = 1/2, where the adaptive cost is 5/2 and the non-adaptive cost is 3.Source: §2.3 · p. 4

2.4 Periodicity

  • For the particular optimal sequence considered, periodicity holds if and only if log_h t is rational.The sequence is connected to a mechanical word; the characterization assumes 0 < p1 < 1/2 < pn < 1, with separate optimal sequences described for boundary cases.Source: §2.4 · pp. 5–6

3 d-ary Unanimous Vote

The paper studies dice-ordering problems with different stopping rules and develops greedy and approximation algorithms for them. It also considers unlimited rolls and establishes bounds on adaptivity gaps.

3 d-ary Unanimous Vote

  • The d-ary Unanimous Vote problem orders independent dice to minimize expected rolls until two distinct colors appear or all dice are rolled.Each die is rolled at most once.Source: §3 · p. 6

3.1 1-Additive Approximation Algorithm

  • A polynomial-time algorithm combines two generalized greedy rules, with the associated adaptivity gap at most 3/2 and additive adaptivity gap at most 1.The rules construct the permutation’s prefix and suffix, separated by a crossover point.Source: §3.1 · pp. 7–8

3.2 Polynomial-Time Approximation Scheme and Hardness

  • A PTAS is available for the d-ary problem, while exact optimization is NP-hard when d is part of the input.The PTAS brute-forces the first ⌈1/ε⌉ positions and applies Algorithm 1 to the remainder.Source: §3.2 · p. 8

3.3 The Unlimited-Rolls Variant

  • For Unlimited-Rolls, a greedy sequence achieves a 1-additive approximation to the adaptive optimum; the adaptivity gap is at most 3/2 and the additive gap at most 1.Neither of the two greedy rules is optimal in general, despite both being optimal for Unlimited-Flips.Source: §3.3 · pp. 8–9

4 Finite Coupon Collection Problem

The Finite Coupon Collection problem stops after all d outcomes have appeared or all dice have been rolled. The paper reduces it to Submodular Ranking and obtains a polynomial-time O(log d)-approximation.

4 Finite Coupon Collection Problem

  • The problem rolls each die at most once and stops when all d outcomes have appeared or all dice have been rolled.The objective is to minimize the expected number of rolls.Source: §4 · p. 9
  • A polynomial-time O(log d)-approximation is obtained for Finite Coupon Collection by reducing it to Submodular Ranking.The reduction omits realizations that do not contain all colors and estimates greedy scores by sampling.Source: §4 · pp. 9–10
  • For each realization, the reduction uses a monotone submodular function that reaches 1 when the stopping condition is met.The realization-indexed functions and their probabilities form the Submodular Ranking instance, whose objective equals the permutation's expected cost.Source: §4 · p. 10
  • Including every realization yields an exponential-time O(log n)-approximation, while excluding realizations missing colors changes the bound to O(log d).For realizations missing colors, every permutation costs n, so they do not affect comparisons between permutations.Source: §4 · p. 10
  • The polynomial-time algorithm estimates each remaining die's greedy score from sampled realizations conditioned on containing all colors.The proof relies on the Submodular Ranking guarantee tolerating estimates within a constant factor of true scores.Source: §4 · p. 10

5 Generalizing the Reduction to Submodular Ranking

The paper generalizes its Submodular Ranking reduction to non-adaptive stochastic probing by representing each realization's stopping condition with a monotone submodular function. The approach gives O(log 1/ε)-approximation bounds when the functions are constructible and evaluable, but the bound can be poor or unavailable for some problems.

5 Generalizing the Reduction to Submodular Ranking

  • The reduction applies to non-adaptive probing with at-most-once probes and random outcomes in [d], when the stopping condition has suitable realization-dependent functions.Each function must be monotone submodular, evaluable in polynomial time, and equal 1 exactly when probing its selected set meets the stopping condition.Source: §5 · p. 10
  • The resulting O(log 1/ε)-approximation is measured against the optimal non-adaptive strategy, and its quality depends on ε.Here ε is the smallest positive marginal increase of any constructed function from a single element.Source: §5 · p. 10
  • The reduction transfers the Q-value approach's O(log T) bound for decision-tree Boolean functions to the analogous non-adaptive problem.The Q-value approach instead addresses adaptive SBFE and yields its bound through Stochastic Submodular Cover.Source: §5 · pp. 10–11
  • Unlike the Q-value approach, the sampling-based reduction works for any distribution with sample access, but suitable small-goal submodular functions are not available for every problem.The Q-value approach's stated guarantee applies only to independent query distributions.Source: §5 · p. 11

6 Open Questions

The paper leaves open exact and structural questions for d-ary and unlimited-roll Unanimous Vote, alongside computational questions for Finite Coupon Collection. It also identifies further stopping-rule variants and broader questions about unlimited-probe sequences.

6 Open Questions

  • For constant d, whether d-ary Unanimous Vote has an efficient exact algorithm remains open.The paper notes that its NP-hardness result does not apply when d is constant.Source: §6 · p. 11
  • For unlimited rolls, a simple description of an optimal d-ary sequence remains unknown, as does the computational hardness of Finite Coupon Collection.The authors conjecture other techniques may yield stronger results for Finite Coupon Collection because their Submodular Ranking approach cannot exploit input-distribution independence.Source: §6 · p. 11
  • A Finite Coupon Collection variant that also stops when collecting every color becomes impossible is left unaddressed and is described as more challenging.The example has two dice left but three colors still to collect.Source: §6 · p. 11
  • The paper raises broader questions about computability, periodicity, and the relationship between single-probe and unlimited-probe variants.These questions arise for problems whose solutions are infinite probing sequences.Source: §6 · pp. 11–12

LLM Usage Disclosure

The authors disclose LLM assistance in proof-related code, a reduction, and a mechanical-word insight, as well as proofreading. They state that LLMs did not write any part of the manuscript and that the authors take responsibility for its soundness.

LLM Usage Disclosure

  • Claude generated two adaptivity-gap Lean files using lemmas supplied by Aristotle.Source: LLM Usage Disclosure · p. 12
  • Claude constructed the Appendix C.2 reduction and used Algorithm 1 ideas to design the PTAS of Theorem 6.Source: LLM Usage Disclosure · p. 12
  • Gemini suggested a mechanical-word connection, and LLMs were also used to check proofs for mistakes and typos.The authors state that LLMs did not write any manuscript text and that they take full responsibility for soundness.Source: LLM Usage Disclosure · p. 12

A Missing Proofs From Section 2

The proof shows that an infinite coin sequence can be changed, without increasing expected cost, until it uses only the two extreme-bias coins. For a sequence that violates the endpoint rule, replacing or swapping choices improves its expected cost.

A Missing Proofs From Section 2

  • Replacing the first non-extreme coin in a sequence with coin 1 or coin n can be done without increasing expected cost.Repeating this operation yields a sequence using only the two extreme coins, whether the number of non-extreme positions is finite or infinite.Source: A Missing Proofs From Section 2 · p. 14
  • When p1 < pn < 1/2, replacing any use of coin 1 with coin n strictly improves expected cost.The case 1/2 < p1 < pn is symmetric.Source: A Missing Proofs From Section 2 · pp. 14–15
  • When p1 ≤ 1/2 ≤ pn, a violating use of coin 1 at a 0-biased position can be swapped with the next coin n, or changed to n if none follows.The proof also handles an infinite run of coin 1 choices; at an unbiased position, choosing coin 1 or n has no effect on expected cost.Source: A Missing Proofs From Section 2 · pp. 15–16

B Adaptivity Gap and Additive Adaptivity Gap

The section compares optimal adaptive and non-adaptive strategies for the Unlimited-Flips problem. It establishes lower bounds on both adaptivity gaps and uses a small collection of non-adaptive sequences to prove upper bounds.

B Adaptivity Gap and Additive Adaptivity Gap

  • Among the adaptive strategies that first flip one coin and then choose an endpoint coin based on the result, at least one of a1 or an is optimal.The candidate strategies first flip coin i, then repeatedly flip coin 1 after heads or coin n after tails.Source: B Adaptivity Gap and Additive… · p. 16
  • The Unlimited-Flips adaptivity gap is at least 1.2, and its additive adaptivity gap is at least 1/2.The lower-bound proof uses an instance where several non-adaptive sequences have identical expected costs.Source: B Adaptivity Gap and Additive… · pp. 16–17
  • The upper-bound proofs reduce the non-adaptive search to a small collection of candidate sequences, including sequences that always use coin n, start with coin 1, or alternate between endpoint coins.For the two bounds, the proof selects among these candidates under the assumption p1 + pn ≤ 1.Source: B Adaptivity Gap and Additive… · pp. 17–18
  • The proof applies separate lemmas to establish the multiplicative and additive upper bounds for the adaptivity gaps.The multiplicative bound uses candidate sequences from Lemmas 9–11; the additive bound also uses the sequence from Lemma 12.Source: B Adaptivity Gap and Additive… · p. 19

C Missing Proofs from Section 3

The proof bounds the expected cost of the dice-ordering algorithm by analyzing its stopping probabilities around a crossover point and comparing those probabilities with an adaptive strategy's cost.

C Missing Proofs from Section 3

  • If the permutation has no crossover point, its expected cost is at most 3, and OPT is at least 2.With a crossover point, the proof bounds the probability of stopping at or after it using an adaptive strategy that seeks an outcome different from a selected color.Source: C Missing Proofs from Section 3 · pp. 20–22
  • At the algorithm's crossover position, the proof establishes a stopping probability of at least 1/2 under its stated ordering conditions.The argument assumes the remaining dice have probability at least 1/2 of the selected color.Source: C Missing Proofs from Section 3 · pp. 19–21

C.1 Counterexamples to the Optimality of Greedy Rules A and B

The section gives examples showing that the two greedy rules do not always produce an optimal sequence for the Unlimited-Rolls variant. For rule B, alternating the dice costs less than following the rule in the specified instance.

C.1 Counterexamples to the Optimality of Greedy Rules A and B

  • For greedy rule A, the two unique greedy sequences in the specified instance have identical expected cost, while the comparison sequence rolls only die 1.The passage identifies the comparison sequence but does not provide its expected cost.Source: §C.1 · p. 22
  • For greedy rule B, the specified two-die instance gives cost 2.7 for the greedy sequence and approximately 2.647 for alternating dice.The greedy sequence uses die 1 only; the alternating sequence has expected cost 45/17.Source: §C.1 · p. 22

C.2 NP-Hardness of d-ary Unanimous Vote

The d-ary Unanimous Vote problem is NP-hard by reduction from Exact Cover by 3-sets. The paper also presents a PTAS that combines prefix enumeration with greedy choices and suffix ordering around a crossover point.

C.2 NP-Hardness of d-ary Unanimous Vote

  • The d-ary Unanimous Vote problem is NP-hard, via a reduction from X3C that distinguishes YES and NO instances by optimal expected cost.The reduction constructs dice from the X3C subsets and uses the optimal expected cost to distinguish the instances.Source: §C.2 · p. 23

C.3 PTAS for d-ary Unanimous Vote

  • For each length-K prefix, Algorithm 2 uses greedy rule A until reaching the suffix crossover point or exhausting the dice.The crossover point is defined as the earliest position after which changing the suffix cannot alter the specified comparison.Source: §C.3 · p. 24
  • After the crossover point, the algorithm adds remaining dice in non-decreasing order of r_i.At that step, r is the color guaranteed by Lemma 7.Source: §C.3 · p. 24
  • The PTAS achieves an expected cost at most (1 + ε) times optimal by enumerating prefixes of length K and comparing the resulting permutations.The proof bounds the cost of the permutation matching the optimal prefix by (1 + ε) times the optimal cost.Source: §C.3 · p. 24

D Approximating the Greedy Choice with Sampling

The section analyzes sampling to approximate greedy scores in the Submodular Ranking reduction. With high-probability score estimates, the resulting ordering has an O(log d) expected-cost approximation guarantee.

D Approximating the Greedy Choice with Sampling

  • When a greedy score is high enough, sampling estimates it within a constant factor with high probability; otherwise, that ordering suffix has low enough probability of being reached.The analysis uses K = 32n^4 ln(2n^3) retained samples.Source: D Approximating the Greedy Choice with… · pp. 26–27
  • If the probability of retaining a realization is below 1/n, the analysis bounds the expected cost increase by at most one roll.When enough samples are retained, a union bound gives probability at least 1 − 1/n that all greedy steps have the required sample count.Source: D Approximating the Greedy Choice with… · p. 27
  • The probability that any sampled choice in the high-score prefix falls below one quarter of the best score is at most 1/n.Conditioned on no such event, each choice retains at least one quarter of the exact greedy score, to which the [AG11] analysis applies.Source: D Approximating the Greedy Choice with… · p. 28
  • The sampled ordering has expected cost at most O(log d) times optimal, with an additional expected cost of at most one roll from the sampling analysis.The guarantee uses the approximation result of [AG11] and accounts for the event that enough realizations are retained after rejection.Source: D Approximating the Greedy Choice with… · p. 28
Loading 2609.36508v1…