} \pi \in
{\mathfrak{S}}_N} \theta^{c(\pi)}$. Then, it follows directly from the definitions that $${\mathcal{S}}(\bar{p}) = \max({\mathcal{S}}(p), {\mathcal{S}}(p^{\circ})).$$ This formula can be used to recursively determine ${\mathcal{S}}(\bar{1})$, the globally optimal probability of a win. To also keep track of the globally optimal strategy, let us say that $p$ is [**positive**]{} if ${\mathcal{S}}(p) \geq {\mathcal{S}}(p^{\circ})$ and [**negative**]{} otherwise. The positive prefixes represent locally optimal strikes.

With the setup given above, a globally optimal strike set for a weighted game of best choice consists of the subset $A$ of positive prefixes that are minimal when partially ordered by prefix-containment. The probability of winning is $\bigoplus_{p \in A} {\mathcal{S}}(p)$ where we define $\frac{a}{b} \oplus \frac{c}{d} =
\frac{a+c}{b+d}$ and use the standard denominator for all strike probabilities.

We first show that all of the probabilities are determined. The prefixes of size $N$ are positive, which serves as a base case for induction on the size of a prefix. Given the probabilities for prefixes of sizes greater than $i$, the ${\mathcal{S}}(p^{\circ})$ probabilities for each prefix of size $i$ can be obtained as $\bigoplus_{p\text{-prefixed } q \text{ of size }i+1}{\mathcal{S}}(\bar{q})$, and then the ${\mathcal{S}}(\bar{p})$ probabilities can be determined from the formula. (The $\oplus$ operation represents the probability 