Elchanan Mossel's Amazing Dice Paradox

I recently came across this old video from the MindYourDecisions Youtube channel by Presh Talwalkar (which I find to often be a good source for interesting problems). At first I was sure the video was wrong. Then I thought some more and realized he was right. Finally, I am convinced that he is wrong, but about something else. This post is me shaking my angry fist at the internet and since it's about rolling a die, I figured it was close enough to being about games to count.

First, let's state the problem of the video:

You roll a fair dice until you get a 6. What is the expected number of rolls, including the roll of 6, conditioned on the event that all previous rolls were even numbers?

There are two curious changes from the way the problem is stated in most other places that are linked in the video. First, most statements use the singular "die" and not "dice". This is perhaps leaning on the possible internet origin post of the problem (it is attributed as originally coming from Elchanan Mossel given to undergrad students during a class at UPenn in 2014-5) which uses "dice" in the singular, though this is changed to "die" in the follow-up post. I find this choice curious because while I do see some usage of dice in the singular (perhaps more in non-American contexts like Shut Up and Sit Down - though even they've corrected dice to die) I see no argument for discarding die as the singular. That is, I've never seen any assertion that the singular "die" is incorrect. Even the dictionary used in the video says the following:

Historically, dice is the plural of die, but in modern English dice can be both the singular and the plural: throw the dice could mean a reference to either one or more than one dice

Note the word "can" is used, not "is". This is even more clear in the phrasing on the US version instead of the UK version of the same website:

Historically, dice is the plural of die, but in modern English dice is sometimes also used in the singular: throw the dice could mean a reference to either one or more than one dice

This would leave me with little support for labeling the singular "dice" as wrong, but I still don't see why someone accustomed to the singular "die" would choose to abandon it and introduce ambiguity. I'm used to the singular "die", though, and anything else just sounds weird. If you learned "dice" and are used to it, I could see it being otherwise.

Second, and perhaps more relevantly, most statements of the problem say that all rolls are even numbers instead of all previous rolls. The video makes a big distinction between these and claims them to give different answers. In fact, it claims that the answer to the "all rolls" version of the problem is the oft-given erroneous answer of 3. This is wrong, as I will try to demonstrate here. I will focus on how the two problems are the same. There are other good sources for how to approach the main problem, like the one here.

The common wrong answer of 3 comes from the idea that if we condition on rolling even numbers then that is equivalent to rolling a three-sided die with faces labeled 2, 4, and 6. However, that is not true. Instead, we can look at the problem setup to construct all sequences that end in a 6 and exclude those that contain odd numbers. Since 6 is an even number, we will see that conditioning on rolling all even numbers is the same as rolling all even numbers before the 6.

To quickly reference why the average number of rolls if we rolled a three-sided die until we got a particular side, we can look to our previous work with Memoir '44, where we found that the expected number of rolls needed to achieve a roll with probability $p$ is $1/p$. In this case the probability is $1/3$, so the expected number of rolls, $\mathbb{E}N_3$ is $1/(1/3)=3$. (The notation $N_3$ uses the subscript 3 because there are three sides to the die here.) We can find this by starting by the probability of getting a roll of length $n$,

\begin{align} P(N_3=n) = \left ( \frac{2}{3} \right ) ^{n-1} \cdot \frac{1}{3}, \end{align}

with an often-useful shortcut to computing the expected value for non-negative integer-valued random variables,

\begin{align} \mathbb{E} N = \sum_{n=0}^\infty P(N > n). \end{align}

There are more details in the previous post on the toughest unit in Memoir '44.

Let's start by looking at sequences of six-sided die rolls of length 1 that end in a 6. Actually, there's just one, as shown in Table 1. There I've annotated it with a * to indicate that it meets our conditioning criteria of containing only even numbers. All $1/1$ of the sequences are allowed.

\begin{align*} \begin{array}{c} 6 * \end{array} \end{align*} 

Table 1: Sequences of length 1

Now, let's look at sequences of length 2, where only $2/5$ are allowed.

\begin{align*} \begin{array}{ccccc} 16 \phantom{*} & 26 * & 36\phantom{*} & 46 * & 56\phantom{*} \end{array} \end{align*} 

Table 2: Sequences of length 2

Finally, let's look at sequences of length 3, where $4/25$ are allowed. We'll stop here lest the number of sequences gets too cumbersome.

\begin{align*} \begin{array}{ccccc} 116 \phantom{*} & 216 \phantom{*} & 316 \phantom{*} & 416 \phantom{*} & 516 \phantom{*} \\ 126 \phantom{*} & 226 * & 326 \phantom{*} & 426 * & 526 \phantom{*} \\ 136 \phantom{*} & 236 \phantom{*} & 336 \phantom{*} & 436 \phantom{*} & 536 \phantom{*} \\ 146 \phantom{*} & 246 * & 346 \phantom{*} & 446 * & 546 \phantom{*} \\ 156 \phantom{*} & 256 \phantom{*} & 356 \phantom{*} & 456 \phantom{*} & 556 \phantom{*} \end{array} \end{align*} 

Table 3: Sequences of length 3

It looks like for a sequence of length $n$, then $2^{n-1}$ of the $5^{n-1}$ sequences are allowed under the conditioning. This disproportionately removes long sequences, which is why the average is so short. You can think of it this way: the longer the sequence, the more likely it is to have at least one 1,3, or 5 before conditioning. The probability of a sequence being length $n$ is the probability that the first 6 was on roll $n$. Thus, all rolls before this must be something other than 6. The probability of this happening on each roll is $5/6$, while the probability of getting a 6 in round $n$ is $1/6$. Thus, if $N_6$ is a random variable equal to the length of the sequence of rolling a six-sided die, then

\begin{align} P(N_6=n) = \left ( \frac{5}{6} \right) ^{n-1} \cdot \frac{1}{6}. \end{align}

However, if we only allow sequences with even numbers, then there are only two valid choices for each roll before the last, thus the individual roll probability changes from $5/6$ to $2/3$ and the sequence probability changes accordingly. With only even rolls allowed, there are three options instead of six and two of them instead of five continue the sequence to be longer.  (Heads up for skimmers: this part is wrong and will be corrected later.)

\begin{align} P(N_6=n \, | \, \text{even rolls}) &= \left ( \frac{2}{3} \right) ^{n-1} \cdot \frac{1}{6} \qquad (1) \end{align}

Note that this probability is half of the probability $P(N_3=n)$ from above.

\begin{align} P(N_6=n \, | \, \text{even rolls}) &= \frac{1}{2} P(N_3=n) \end{align}

Using the definition of expected value for discrete-valued random variables,

\begin{align} \mathbb{E} N = \sum_n n \cdot P(N=n), \end{align}

we can find the expected value of $N_6$ given all even rolls.

\begin{align} \mathbb{E} \left [ N_6 \, | \, \text{even rolls} \right ] &= \sum_{n=1}^\infty n \cdot P(N_6=n \, | \, \text{even rolls}) \\ &=\sum_{n=1}^\infty n \cdot \frac{1}{2} \cdot P(N_3=n) \\ &=\frac{1}{2} \cdot \underbrace{\left (\sum_{n=1}^\infty n \cdot P(N_3=n) \right )}_{\mathbb{E} N_3}\\ &= \frac{1}{2} \cdot 3 \\ &= 1.5 \end{align}

That's a little hand-wavy though, so let's take this step slower. We're interested in conditional expectation, and thus conditional probability.

\begin{align} \mathbb{E}\left [N \, | \, A \right ] = \sum_n n \cdot P(N=n \, | \, A) \end{align}

Here $A$ is some generic event. Recall that conditional probability is given by the following,

\begin{align} P(N=n \, | \, A) = \frac{P( N=n \cap A)}{P(A)}, \end{align}

where $\cap$ means and, that is that both the thing on its left and its right are true. For an individual roll that continues the sequence (the roll doesn't equal 6), which we'll label as event $C$ for continuing, the conditional probability is as follows.

\begin{align} P(C \, | \, \text{even roll}) &= \frac{P(C \cap \text{even roll})}{P(\text{even roll})} \\ &=\frac{\;\cfrac{2}{6}\;}{\;\cfrac{3}{6}\;} \\ &=\frac{2}{3} \end{align}

Now we apply this to the probability of the final roll. We'll say the probability of ending is $P(E)$.

\begin{align} P(E \, | \, \text{even roll}) &= \frac{P(E \cap \text{even roll})}{P(\text{even roll})} \\ &=\frac{\;\cfrac{1}{6}\;}{\;\cfrac{3}{6}\;} \\ &=\frac{1}{3} \end{align}

This is not what we want. I've brought us to the wrong answer of 3!  (I haven't quite gotten there, but I think you can take the next few steps.)

At this point, I think it may be useful to acknowledge one of the commenters to the video for helping me to realize what was going on. I was convinced that the answer should be the same for the "previous" case as the all evens case and didn't believe that 1.5 was the correct answer.  Marce Villarino posted some python code that quickly convinced me that 1.5 must be right, but also helped me see that the two cases are actually the same. The code follows.

##### Record successive thows of a six sides die, untill a 6 is thrown.

##### If the record does not contain even number, record it's length.

import random

import time

def calcOnlySixStops(howManyTimes):

result = list()

start_time = time.time()

for i in range(howManyTimes):

a = list()

a.append(random.randint(1,6))

while a[-1] != 6:

a.append(random.randint(1,6))

if not((1 in a) or (3 in a) or (5 in a)):

result.append(len(a))

print("--- %s seconds ---" % (time.time() - start_time))

return result

lolailo = calcOnlySixStops(1000000)

print(sum(lolailo)/len(lolailo))

####### about 1.5

####### it takes ca. 43 seconds on my laptop

##### Same, but throw a three sided die.

def calcThreeSidedDie(howManyTimes):

result = list()

start_time = time.time()

for i in range(howManyTimes):

a = list()

a.append(random.choice([2,4,6]))

while a[-1] != 6:

a.append(random.choice([2,4,6]))

result.append(len(a))

print("--- %s seconds ---" % (time.time() - start_time))

return result

lolailo = calcThreeSidedDie(1000000)

print(sum(lolailo)/len(lolailo))

####### abt 3.0

####### it takes ca. 19 s on my laptop.

As you can see from the annotated results, or if you run it yourself, it shows that the expected value is approximately 1.5. It uses a Monte Carlo approach with a million trials, which seems sufficient here.  Also, if you look through the algorithm to condition on the previous rolls being even, you'll see that it's exactly the same as what you would do if you were to condition on all rolls being even.

The key error that we made is the same one to get the wrong answer most of the time, I think, just a little drawn out. Note that we conditioned on individual even rolls, not all rolls being even. That's the wrong event. If we want to take that approach, we need to condition the entire $P(N_6=n)$ on getting even rolls.  (We could also use the individual pieces, but we still must condition on getting all even rolls, not just the one under consideration at that moment.)

\begin{align} P(N_6=n \, | \, \text{even rolls}) &= \frac{P(N_6 =n \cap \text{even rolls})}{P(\text{even rolls})} \end{align}

The numerator is relatively easy to figure out. Based on what we saw above, we find that

\begin{align} P(N_6 =n \cap \text{even rolls}) = \left ( \frac{2}{6} \right)^{n-1} \cdot \frac{1}{6} \end{align}

To get this we we took the unconditioned probability of getting a certain number of rolls and combined it with the fraction of the rolls that meet our all evens criteria.  But what is the probability of even rolls? Note that this isn't the probability of getting even rolls given a length, it's the overall probability. Here it may be useful to turn things around.

\begin{align} P(\text{even rolls}) &= \sum_n P(\text{even rolls} \, | \, N_6=n) \cdot P(N_6=n) \\ &= \sum_n P(\text{even rolls} \cap N_6=n) \end{align}

Since we already know this joint probability from above, we can plug it in.

\begin{align} P(\text{even rolls}) &= \sum_{n=1}^\infty \left ( \frac{2}{6} \right)^{n-1} \cdot \frac{1}{6}\\ &= \frac{1}{6} \cdot \sum_{n=1}^\infty \left ( \frac{1}{3} \right)^{n-1} \end{align}

The above includes a geometric series. We can adjust the range and the exponent to make it look more familiar

\begin{align} P(\text{even rolls}) &= \frac{1}{6} \cdot \underbrace{\sum_{n=0}^\infty \left ( \frac{1}{3} \right)^{n}}_{\cfrac{1}{1-\cfrac{1}{3}}} \\ &= \frac{1}{6} \cdot \frac{3}{2}\\ & = \frac{1}{4} \end{align}

Does this number make sense? At first, it may seem like too few of the sequences. But consider that on each roll, we throw out half of the results. That is, every time we roll the die half of the results are excluded.
 

Now we have the pieces we need and we can find the average number of rolls.

\begin{align} P(N_6=n \, | \, \text{even rolls}) &=\frac{P(N_6 =n \cap \text{even rolls})}{P(\text{even rolls})} \\ &= \frac{\left ( \cfrac{2}{6} \right)^{n-1} \cdot \cfrac{1}{6}}{\cfrac{1}{4}} \\ P(N_6=n \, | \, \text{even rolls}) &=\left(\frac{1}{3} \right )^{n-1} \cdot \frac{2}{3} \label{eq:myd_2} \qquad (2)\end{align}

Leveraging our previous work with Memoir '44, this has the same form as asking how long it takes to get the first result, when the result occurs with probability $p=2/3$. Thus,

\begin{align} \mathbb{E} \left [ N_6 \, | \, \text{even rolls} \right ] &= \frac{1}{2/3}\\ &=1.5 \end{align}

Note that here we found that 

 \begin{align} P(N_6=n \, | \, \text{even rolls}) &= \left(\frac{1}{3} \right )^{n-1} \cdot \frac{2}{3}  \end{align}

which contradicts our earlier hand-wavy equation. Which one is right? Well, I generally trust more rigorous derivations, so I'm inclined towards the later. Interestingly, they both give the correct average. Let's go back to our simulation and look at not just the average, but also the distribution of lengths given all even rolls. By adding a calculation of the percentage of sequences of each length to the above simulation, we get the results in Table 4.

\begin{align*} \begin{array}{cccc} \text{Sequence length} & \text{Equation (1)} & \text{Equation (2)} & \text{Estimated probability} \\ \hline 1 & 0.1667 & 0.6667 & 0.6665 \\ 2 & 0.1111 & 0.2222 & 0.2226 \\ 3 & 0.0741 & 0.0741 & 0.0740 \\ 4 & 0.0494 & 0.0247 & 0.0241 \\ 5 & 0.0329 & 0.0082 & 0.0084 \\ 6 & 0.0219 & 0.0027 & 0.0029 \\ 7 & 0.0146 & 0.0009 & 0.0009 \\ 8 & 0.0098 & 0.0003 & 0.0004 \\ 9 & 0.0065 & 0.0001 & 0.0001 \end{array} \end{align*} Table 4: Simulated and theoretical sequence length conditional probabilities

As we can see, this lines up well with our second, revised, equation (2). Interestingly, equation (1) looks like it should have a higher expected number of rolls, as the probability of having sequences of length 1 and 2 is lower than simulated while the probability of sequences longer than 3 is higher. An observation that is useful to recall at this point is that equation (1) gave us that $P(N_6=n \, | \, \text{even rolls})$ is half of $P(N_3=n)$. However, further reflection indicates that that doesn't make sense as the sum of the probability over the whole sample space must be 1. The probability that there is some outcome is 1.

\begin{align} \sum_n P(N=n) = 1 \end{align}

If this is true of some function $f(n)$ such that $P(N=n)=f(n)$ it cannot be true of some other function $g(n) = f(n)/2$. That is, we should find that our incorrect equation gives the sum to be 0.5.

\begin{align} \sum_{n=1}^\infty \left ( \frac{2}{3} \right) ^{n-1} \cdot \frac{1}{6} & = \frac{1}{6} \cdot\underbrace{\sum_{n=0}^\infty \left ( \frac{2}{3} \right) ^n}_{\cfrac{1}{1-\cfrac{2}{3}}}\\ &= \frac{1}{6} \cdot 3 \\ & = \frac{1}{2} \end{align}

Indeed, that is the case. This is confirmation that equation (1) is incorrect.

Again, note that there is no sequence that would be included or excluded differently if we were to emphasis that we conditioned on rolling all even numbers before the 6. The two descriptions are logically equivalent and have the same expected number of rolls.

How often does each number come up in Space Base?

 In Space Base, every turn the active player rolls two six-sided dice. Each player then chooses to treat these as separate numbers or first sum them together and get the corresponding rewards or reward, respectively. Thus, in some sense, the question is not answerable, because it depends on each player's choice. The rulebook does a decent job on laying this out and speaking somewhat about the probabilities.

We previously found the probability of rolling each result on 2d6 for Catan, so we won't revisit that. Is there a good way to layer on top of that the idea that we can take either the sum of the dice or the results individually? The rulebook makes one choice. A quick glance at the table there may be misleading, as it shows the distribution of a regular 2d6 roll with die faces, but then show the numbers for a combination of sum and individual results.

If we want to get a single probability for how often each number comes up, we have to make a choice of how to handle the case where we roll doubles. Should we count that as two occurrences of the single die value or just one? It depends on what we care about. If we're trying to figure out the average return then I think it makes sense to choose, as the rulebook did, to count that as two results. You can see that in the number of times that they list a 1 showing up: 12 out of the 36 possible results of rolling two 6-sided dice, as shown in Table 1. Note that one of these times is when both dice are rolled together. Thus, there are only 11 rolls that produce these 12 ones. While the double roll makes up for there being only 11 outcomes that include a 1 being rolled in the average reward over many rolls, there may be cases where we are more interested in how many rolls include a given number and don't benefit from rolling doubles. In Space Base there are some cards that gain a charge cube when rolled, but can only hold one charge cube. Thus, rolling doubles of that number can be worse overall, as we don't have access to rewards from a second number.

\begin{align*} \begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1& {1},{1} & {1},2 & {1},3 & {1},4 & {1},5 & {1},6\\ 2& 2,{1} & 2,2 & 2,3 & 2,4 & 2,5 & 2,6\\ 3& 3,{1} & 3,2 & 3,3 & 3,4 & 3,5 & 3,6\\ 4& 4,{1} & 4,2 & 4,3 & 4,4 & 4,5 & 4,6\\ 5& 5,{1} & 5,2 & 5,3 & 5,4 & 5,5 & 5,6\\ 6& 6,{1} & 6,2 & 6,3 & 6,4 & 6,5 & 6,6\\ \end{array} \end{align*}

Table 1: Rolling ones on two 6-sided dice

We also need to choose how to handle the option to take the sum of the dice or the individual values. The rulebook includes both at full weight. That is, out of the 36 possible results of rolling two dice, it includes all the times that a 6 is rolled on individual dice as well as all the times that the sum of the two dice is 6. If this were the only number for which we received rewards, or if it were significantly better than our other rewards, then this makes sense, as we'd always choose 6 when it's an option. However, in many cases it could be that getting both a 2 and a 4, for example, is better than just getting the sum of 6. That may be an obvious choice or a difficult one. A way to handle this is to say that we don't know which way players are going to choose (though this may vary with strategy) and treat it as a random event with each option having equal probability. We can think of this as reducing the number of times each number comes up by a factor of 2.

Fortunately, we are spared some complexity by the fact that the sum and individual numbers are always different, since each die has a minimum value of 1. Otherwise, we'd have to consider what to do when the sum matches a single die. Actually, I think we'd always choose the single values, unless it was to use an ability to adjust the number that depends on using the sum. However, we'd still have to account for it in the math to avoid double counting.

There's also a choice of how to combine these two factors. I see two natural pairings. First, if looking at the average amount of return, I think it makes sense to assume that the sum and individual values are each used half the time. This gives something like a weighted probability that you get the rewards from a given number. (I say weighted, because it may sometimes involve double rewards, as discussed above.) Second, if looking at how often something is available, it makes sense to count double rolls as single, but include both individual values and the sum at full weight. This is essentially answering how many turns a given number is an option.

Those both give the middling option for the probabilities. Interestingly, the rulebook went with neither and instead prints the more optimistic combination of counting a double value as two result and including both individual numbers and sums. This does make sense if you're looking at the average reward of a number that is strictly better than everything else, but it ignores the counterfactual or opportunity cost of not choosing the other option. That is, if you're choosing between the sum 5 and the individual numbers 2 and 3, if you're looking at 5, the benefit of what's there has to be compared to the alternative of the rewards for both 2 and 3.

I suppose I should say something about the last of the four options: what does pairing no doubles with random sum or individual? It seems appropriate to use when you only get benefit from a single reward per turn, but it's a tossup as to whether the number would be chosen given the other choices.

\begin{align*} \begin{array}{c|cccc} \text{Method} & 1 & 2 & 3 & 4 \\ \hline P(\text{sum}) = P(\text{individual}) & 0.5 & 0.5 & 1 & 1 \\ \text{# single} & 11 & 12 & 11 & 12 \\ \hline 1 & \frac{5.5}{36} & \frac{6}{36} & \frac{11}{36} & \frac{12}{36}\\ 2 & \frac{6}{36} & \frac{6.5}{36} & \frac{12}{36} & \frac{13}{36}\\ 3 & \frac{6.5}{36} & \frac{7}{36} & \frac{13}{36} & \frac{14}{36}\\ 4 & \frac{7}{36} & \frac{7.5}{36} & \frac{14}{36} & \frac{15}{36}\\ 5 & \frac{7.5}{36} & \frac{8}{36} & \frac{15}{36} & \frac{16}{36}\\ 6 & \frac{8}{36} & \frac{8.5}{36} & \frac{16}{36} & \frac{17}{36}\\ 7 & \frac{3}{36} & \frac{3}{36} & \frac{6}{36} & \frac{6}{36}\\ 8 & \frac{2.5}{36} & \frac{2.5}{36} & \frac{5}{36} & \frac{5}{36}\\ 9 & \frac{2}{36} & \frac{2}{36} & \frac{4}{36} & \frac{4}{36}\\ 10 & \frac{1.5}{36} & \frac{1.5}{36} & \frac{3}{36} & \frac{3}{36}\\ 11 & \frac{1}{36} & \frac{1}{36} & \frac{2}{36} & \frac{2}{36}\\ 12 & \frac{0.5}{36} & \frac{0.5}{36} & \frac{1}{36} & \frac{1}{36}\\ \end{array} \end{align*}

Table 2: Probability of reward in Space Base

How many unique starting spice counts are there in Century: Spice Road?

Suppose you want all players to start with a unique setup in terms of the number of each of the four spices, with a total number of spices equal to 0 to the maximum 10 in a caravan. How many players could you have?

A first guess would be that each of the 10 caravan positions can have one of five possible values (one of the four spices or no spice). Thus, we might think that there are $5^{10}=9765625$ setups. However, as we don't distinguish, for example, one yellow (turmeric) and one red (saffron) from one red and one yellow, this dramatically over counts the number of unique setups.

One approach to dealing with this type of problem is to always order the spices in a certain way. Imagine the 10 caravan spaces laid out in a line, starting with brown (cinnamon), then green (cardamom), red (saffron), yellow (turmeric), and finally no spice. We can express each unique setup in terms of the number of each spice. Equivalently, we may note the transition points. For example, instead of focusing on 3 brown cubes, 2 green cubes, 1 red cube, 3 yellow cubes, and 1 blank space, we can look at the transitions after positions 3, 5, 6, and 9. In terms of numbers, this hasn't helped us much, though we have reduced down from five parameters to four (we could have done this other ways, since we know there are 10 total spots for cubes, so the initial numbers must sum to 10). However, if we look at the nine possible transition points between the ten caravan locations, we can see that each unique setup is a unique selection of four of those nine possible transition points. Selecting a subset from a larger set is a problem we know how to solve with our handy combination or binomial coefficient,

\begin{align} \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}, \end{align}

said as "n choose k".
 

However, that's not quite right. Let's consider what happens when we have none of one type of the spices. That means that two of our transition points overlap, which isn't accounted for when always choosing four transition points. We could handle this by adding up different scenarios, but that's ugly and boring. So while it could give us the answer, let's find something more elegant.

We're trying to count the number of ways to take 10 of something and allocate it into 5 buckets, where each bucket can hold 0 through 10. We can add one into each of the buckets and not change the situation. Since there are five buckets, that means adding five to the number of possible transition points. That is, the number of ways to take 15 of something and allocate it into 5 buckets where each bucket can hold 1 through 11 is the same. Thus, we can take $n+5-1$ choose $4$,

\begin{align} \binom{10+5-1}{4} = \binom{14}{4} = \frac{14!}{4! \cdot 10!} = 1001. \end{align}

As a check for this method, we can look at a simpler case, where it's easier to count or come up with the number in another way. Suppose there are only 2 spots on the caravan. Our formula above says there should be $\binom{2+5-1}{4} = \binom{5}{4} = 15$ setups. With only 2 caravan spots, there are only two types of pattern: two of one spice (including no spice) and one each of two different spices. For the two of one there are 5 ways to do this, and for the one of each, there are $\binom{5}{2} = 10$ ways of doing it. Summing these two ways we get 15. This isn't a perfect check, and it's probably more useful to use to think about the problem and how it works.

Should everyone always lose semi-coop games?

Unfortunately, in order to answer this question, we have to do a bit of taxonomy first, as "semi-coop", short for semi-cooperative, means different things to different people.

Some people call hidden team games like Battlestar Galactica and/or cooperative games with a possible traitor like Shadows over Camelot semi-coops. I can see the motivation for this as they look like a "cooperative, but ..." game, yet it doesn't seem necessary to differentiate these from other team games like Space Cadets: Dice Duel, Codenames, and The Resistance.

Instead, we are talking about games like CO₂, Legendary, and Dead of Winter. The through-line seems to be that these are games where players do not always win together (like a cooperative game), but they may all lose together. However, that definition includes games like Galaxy Trucker, which I don't think anyone would consider a semi-coop. A more precise definition would be that there is a condition that if not met means that none of the non-traitor players are eligible to win and instead lose. I specify non-traitor because many, but not all, of these games feature a traitor, who is essentially on a team with the game trying to make the rest of the players lose.

Within this definition I see three types of semi-coop, which have important distinctions that we'll get to.

In type I semi-coops, or single-winner semi-coops, either all players lose or one player wins while all other players lose. Examples include CO₂ (in "mostly competitive" mode), Robin Hood and the Merry Men, Castaways, and Divided Republic. Examples that include a possible traitor are AuZtralia, Homeland, and Republic of Rome (which has an opt-in traitor).

In type II semi-coops, or group-win semi-coops, there are two types of winning. Either all players lose or all players win, but if all players win there is also an individual winner. Examples include Legendary, Castle Panic (although it only uses the word "win" for the group win), Arkham Horror (group win plus "honorary title of First Citizen of Arkham"), Horizon Zero Dawn (although the terminology is confusing "Although all players have won..., the player with the most victory points...emerges as the winner of the game"), and Tomorrow (mentions "win" for both, but in separate sections of the rulebook). Archipelago is an example with a possible traitor.

Type III semi-coops, or separate-goal semi-coops, have separate win conditions for each player in addition to the group loss. An example is Forgotten Waters. Examples with a possible traitor include Dead of Winter, Nemesis, and New Angeles. Dead of Winter labels itself as a "meta-cooperative" game, but the term doesn't seem to have caught on, though it may be useful to describe type III semi-coops.

Games that don't fit this definition but some may call semi-coops include Cutthroat Caverns, Crisis, Bag of Dungeon (using an optional advanced rule), Hellapagos (whoever gets rescued wins, which can be any subset of players), Fog of Love (each player's performance is determined individually), Pax Emancipation (which has a first phase after which the game may end with any number of players may win except all, as well as a possible second phase which is purely competitive) and Core Space (which has the odd combination of a group win if an objective is completed and an individual win if it is not). While these games do feature the possibility of everyone losing, this is usually still determined on a per-player basis.

Type I: single-winner semi-coops

Let's look at a simplified model of a three player type I semi-coop game. Each player has two moves and chooses simultaneously: cooperate (C) or defect (D). If at least two players cooperate, this prevents the all lose scenario. If one player defects, that player is the winner. If all players cooperate, then the winner is randomly select from them.  This is depicted in Table 1, where each row represents an outcome based on the first player's move (P1), while each column represents the combined moves of the second and third players (P2 & P3).

\begin{align*} \begin{array}{c |c|c|c} \text{P1 \\P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline D & \text{All lose} & \text{All lose} & \text{P1 wins} \\ C & \text{All lose} & \text{P2 or P3 wins} & \text{P1 may win} \end{array} \end{align*} 

Table 1: A simple type I semi-coop game

Type I semi-coops have the issue that the best move is to defect, as defecting is a weakly dominant strategy, meaning that defecting is sometimes better but never worse than cooperating. This is perhaps more clear in Table 2, which is focused on the first player. Additionally, if players put any positive value to have fellow players also lose (that is, any preference for all lose to someone else wins), then defecting is even more incentivized, but remains a weakly dominant strategy.

\begin{align*} \begin{array}{c |c|c|c} \text{P1 \P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline D & \text{Lose} & \text{Lose} & \text{Win} \\ C & \text{Lose} & \text{Lose} & \text{May win} \end{array} \end{align*}

Table 2: First player's outcomes simple type I semi-coop game

Note that this model only holds if two players cannot easily spoil the victory of another. Additionally, it assumes individual victory and avoiding group loss are at odds with each other. This trade-off is not inherent. For example, suppose you have a game where players earn points throughout the game and all players lose if the sum of the points of all players is not sufficiently high. Now, consider two metrics for individual victory. In the first, the player with the fewest number of points is the individual winner. Here, as long as you lack the ability to manipulate other player's points, the lessons we learned above hold and we wouldn't expect there to be a winner (depending on the total point threashold), as all players tries to minimize their own scores. However, in the second metric, the player with the most number of points is the individual winner. Here, actions that avoid a group loss and obtain individual victory are likely perfectly aligned (there are likely some exceptions due to interactions with other players). Since players are trying to maximize their own scores to be the individual winner, the group loss condition is easily avoided. Of course, in such a situation, you may ask why a group loss condition is included in the game. (While I doubt such a game exists, you could include the rule to avoid dominant strategies that end the game very quickly and are not satisfying in some way. There may be better solutions than making the game semi-cooperative.) The defect or cooperate paradigm does not match with this second metric for an individual win.

Type II: group-win semi-coops

Let's move onto the more interesting type II semi-coop. Table 3 shows another model of a simple simultaneous-play semi-coop game. This time we've adjusted the values both to represent a type II semi-coop, but also to look at the payoffs for the first player, so that we can make use of a game theory analysis. We will assume that all lose is valued at 0, while group win or all win ($AW$) and individual win ($IW$) each have some positive unknown value (but common to all players).

\begin{align*}
\begin{array}{c |c|c|c}
\text{P1 \P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW+\frac{1}{3}IW
\end{array}
\end{align*}

Table 3: A simple type II semi-coop game

First, let's acknowledge some fragility to this system. Akin to how competitive games can break down if any of the players are not trying to win (it seems relevant to quote Reiner Knizia: "Remember: When playing a game, the goal is to win, but it is the goal that is important, not the winning..."), semi-cooperative games can break down if players do not accept the payoffs given by the game. While competitive games have their payoffs generally accepted and understood by most people, semi-cooperative games are more rare, especially type II semi-coops, which have multiple types of winning. Some players may ignore one or the other type of winning. If $IW$ is valued at 0, then the game is essentially cooperative, and all players will cooperate as it is a weakly dominant strategy. If $AW$ is valued at 0, then the game reverts to a type I. Some people also reject the idea that a group win is better than a group loss in a type II semi-coop (the interpretation is that in the case of a group loss, all players do as well as each other and so the game ends in a draw, which is preferable to a group win where you are losing to another player; the latter is interpreted as a simple loss), essentially valuing $AW<0$. In that case, as in type I, defecting is a weakly dominant strategy (it's better if exactly one other player cooperates, but doesn't matter if both others either cooperate or defect together). Under such a valuing of the outcomes the game breaks down as it does in a Type I semi-coop. Conversely, players of a Type I semi-coop may value avoiding the all-lose condition such that they effectively add a group win, turning it into a type II semi-coop. We will proceed assuming all players accept the value of both types of winning, while also acknowledging there is some ambiguity in that these games do not specify how much to care about the two types of winning relative to each other.

In this type II semi-coop there is no obviously best move. If both other players defect, it doesn't matter what the first player does. If one other player defects but one cooperates, then cooperation is preferred as this ensures that all win (including player one). On the other hand, if both other players cooperate, then defection is preferred, as that move guarantees obtaining the individual win.

This type II semi-coop has several Nash Equilibria. The first three pure-strategy Nash Equilibria are the cases where one player defects while the other two cooperate. There are three, because there's one for each player being the defector. This is a Nash Equilibrium because no player can do better by changing strategy. Suppose the first player is defecting while the other two are cooperating. This puts us in the third column. The first player is better off with a definite individual win than a one-third chance of an individual win. In both cases, the group win condition is guaranteed. The second and third players each face the choice between a group win and a group loss. Neither can unilaterally do anything to do better given the strategies of the other players. A lesson that we can take from this model is that if you can be the first to convince other players that you either have or will defect, you will likely be the individual winner. As such, these games may have a strong first-player advantage, depending on how quickly a player can establish defection.

Another pure strategy Nash Equilibrium is if all players defect. With all players defecting, the all lose outcome occurs, but no single player is in a position to change it. Here it is evident that the Nash Equilibrium is really about stability not about a how good a set of strategies is. Note that in this situation, though, any player may deviate from a defection strategy without detriment.

There is also a mixed-strategy (a mixed-strategy employs one of a number of pure strategies with a given set of corresponding probabilities) Nash Equilibrium of cooperate and defect. The mix depends on the relative valuing of the different outcomes. To find this Nash Equilibrium, we'll make use of the fact that we know that each component strategy must be a best response and have the same average payout. So the payout of defect and cooperate must be the same. Assume in the equilibrium that each player cooperates with probability $p$, and thus defects with probability $1-p$. The probability that both players 2 and 3 cooperate is $p^2$. The probability that they do one of each is $2 \cdot p \cdot (1 - p)$. Recall that the 2 comes from the fact that either player could be the one that cooperates, so there are two ways that it happens. The payoff for player one are thus as follows.

\begin{align}
u(D) &= p^2 \cdot \left ( AW + IW \right ) \\
u(C) &= 2 p(1-p) \cdot AW + p^2 \cdot \left ( AW +\frac{1}{3} IW \right )
\end{align}

So let's set these equal to find $p$.
\begin{align}
u(D) &= u(C) \\
p^2 \cdot \left ( AW + IW \right ) &= 2 p(1-p) \cdot AW + p^2 \cdot \left ( AW +\frac{1}{3} IW \right ) \\
p^2 \cdot \left (\frac{2}{3} IW \right ) &= 2 p(1-p) \cdot AW \\
p\cdot \frac{2}{3} IW &= 2 (1-p) \cdot AW \\
p\cdot \left (\frac{2}{3} IW + 2AW \right ) &= 2\cdot AW \\
p &= \frac{2 AW}{\frac{2}{3} IW + 2AW}
\end{align}

We can see our earlier conclusions about the simplified cases fall out from this. If $AW=0$, then $p=0$, as we're in the type I semi-coop case. If $IW=0$, then the game is cooperative and $p=1$. For positive values of both AW and IW, though, we find $0 < p < 1$. Note that this works even if having everyone win is valued significantly above having the individual win, as an individual win requires a group win. We can rewrite this based on the ratio of the two values, $r = AW / IW$.

\begin{align}
p &= \frac{2 AW}{\frac{2}{3} IW + 2AW} \\
p &= \frac{2 \frac{AW}{IW}}{\frac{2}{3} + 2\frac{AW}{IW}} \\
\require{cancel}p &= \frac{\cancel{2}\cdot 3 \frac{AW}{IW}}{\cancel{2} + \cancel{2}\cdot3\cdot\frac{AW}{IW}} \\
p& = \frac{3r}{1 + 3r}
\end{align}

This is a monotonically increasing function, as shown in Figure 1, so the more we care about the group win compared to the individual win, the more we cooperate (this is expected and perhaps obvious).

Figure 1: Probability of Cooperation in a Type II Semi-cooperative Game with Equal Player Standing

Suppose we value them equally, such that achieving individual victory has twice the total utility as being part of a group win. This means that we'll cooperate with probability $p=3/4$ or 75% of the time.

Operating under this strategy, we can find the probability that the group wins. This occurs when at most one player defects. The probability that all players cooperate is $p^3$. The probability that one player defects is $3\cdot p^2 \cdot (1-p)$. For $p=3/4$, this means the probability of a group win is,

\begin{align}
P(AW) &= p^3 + 3 \cdot p^2 \cdot (1-p) \\
&= 3p^2 - 2p^3 \\
&= 3 \cdot \left (\frac{3}{4} \right ) ^2 - 2 \cdot \left ( \frac{3}{4} \right ) ^3\\
&\approx 0.84.
\end{align}

This is shown in Figure 2 as a function of the ratio $r$.

Figure 2: Probability of Successful Cooperation in a Type II Semi-cooperative Game with Equal Player Standing

Type II with unequal standing

Now, let's consider a case where the players do not have equal standing. This perhaps models the end of the game. Let's assume players 1, 2, and 3 are in that rank, such that if all cooperate, then player 1 will win. However, if any one player defects (with the other two cooperating) the defecting player wins.

\begin{align*}
\begin{array}{c |c|c|c}
\text{P1 \ P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW+IW \\
\end{array}
\end{align*}

Table 4: A simple type II semi-coop game for player 1 while ahead

Here, for player 1, cooperate is weakly dominant, since the individual win is ensured if all player cooperate. Thus, player 1 likely cooperates.

\begin{align*}
\begin{array}{c |c|c|c}
\text{P2/3 \ P1 & P3/2} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW
\end{array}
\end{align*}

Table 5: A simple type II semi-coop game for players 2 or 3 while behind

However, players 2 and 3 are much more like the earlier analysis. We can check the previous Nash Equilibria to see if they still hold. All defect still is, as well as cases where any one player defects while the other two cooperate. However, player 1 defecting and others cooperating is now a weak Nash Equilibrium, as player 1 is no worse off for cooperating.

Due to the asymmetry introduced, when looking for an updated mixed-strategy Nash Equilibrium, let's say that the first player cooperates with probability $p_1$ and the second and third players each cooperate with probability $p_2$. We can now employ similar techniques as before, however, we'll have more equations as we have a new variable. We'll still assume that $AW$ and $IW$ are valued equally between all players. First, let's look at the payoffs for player 1.

\begin{align}
u(D_1) &= p_2^2 \cdot \left ( AW + IW \right ) \\
u(C_1) &= 2 p_2(1-p_2) \cdot AW + p_2^2 \cdot \left ( AW + IW \right ) \\
u(D_1) &= u(C_1)
\end{align}

From this point, we just do some algebra.

\begin{align}
\require{cancel}\cancel{p_2^2 \cdot \left ( AW + IW \right )} &= 2 p_2(1-p_2) \cdot AW + \cancel{p_2^2 \cdot \left ( AW + IW \right )}\\
0 &= 2 p_2(1-p_2) \cdot AW
\end{align}

Here there are two solutions, $p_2=0$ and $p_2=1$. This is somewhat of a contradiction, as we assumed a mixed-strategy for players 2 and 3, yet here we get pure strategies. If we look at the payoffs for player 1, we see the incorrect assumption that we made: that player 1 plays a mixed strategy. Cooperating is always as good as defection for player 1, and sometimes better. If players 2 and 3 are playing mixed strategies, then we should expect that sometimes one will cooperate and one will defect, which means that the only way for player 1 to have a best response 100% of the time is to cooperate.

Knowing this, we can actually simplify the game from, since we know player 1 will cooperate.

\begin{align*}
\begin{array}{c|c|c}
\text{P2/3 \ P3/2} & D & C \\ \hline
D & 0 & AW+IW \\
C & AW &AW
\end{array}
\end{align*}

Table 6: A simple type II semi-coop sub-game for players 2 & 3 if player 1 cooperates

Again using $p_2$ for the probability of cooperation for only players 2 and 3, we can find the payoffs for each move. We'll repeat the same method of setting the payoffs equal to each other.

\begin{align}
u(D) &= u(C)\\
p_2 \cdot \left (AW+IW \right ) &= AW\\
p_2 &= \frac{AW}{AW+IW}\\
p_2 &= \frac{r}{1+r}
\end{align}

We find a probability of cooperation which is lower than before (assuming the same values of ratio of the value of the group win AW to the individual win IW). For equal values ($r=1$), $p_2=0.5$, only 50%! This makes sense, as there's less incentive now to cooperate. A graphical comparison is presented in Figure 3.

Figure 3: Probability of Cooperation in a Type II Semi-cooperative Game with 2 Players Behind a Leader compared to Equal Standing

However, did this decrease the probability of a group win?

\begin{align}
P(AW) &= p_2^2 + 2\cdot p_2 \cdot (1-p_2) \\
&=2p_2 - p_2^2\\
&=0.75
\end{align}

This did somewhat decrease the probability of a group win, but perhaps not by as much as we might have thought. As shown in Figure 4, there are even some cases where the probability of successful cooperation is higher than with equal standing, although this is only when the group win is valued at a small fraction of the individual win.

Figure 4: Probability of Successful Cooperation in a Type II Semi-cooperative Game with 2 Players Behind a Leader compared to Equal Standing

Type III: separate-win semi-coops

Since type III semi-cooperative games, or meta-cooperative games, do not rank players to determine a winner, there is not the same kind of concept of cooperating vs. defecting as in the analyses we performed thus far. There may still be tension between avoiding the all-lose outcome and achieving personal goals, but this tension is not directly influenced by the situation of other players.

Conclusion

To recap, we saw that in a simple type I semi-coop game, where either all lose or there is one winner, we somewhat expect that all players lose.  (Note that while this may be a strategically unsatisfying play experience, it may be interesting art or commentary.) This is the only Nash Equilibrium and defecting is a weakly dominant strategy. If we add a group win, thus converting to a type II semi-coop, we can avoid this, as there are stable states where all players win. However, this is subject to the strategies employed by the players. If a majority of the players demand to get advantage for the individual win by defecting, then all will lose, and all players defecting is also a Nash Equilibrium. Additionally, even in the case where the group win is achieved, this could be because a certain player is defecting while the others cooperate. Such a condition may be unpleasantly static.  

So the answer is no, as players in a group-win semi-coop may be able to rationally achieve cooperation.

Errata: What's the toughest unit in Memoir '44?

I was preparing to revisit what the toughest unit in Memoir '44 is by looking at it using a Markov chain model. Then I discovered that I had an error in my earlier calculation. I'll fix my calculation and derive the expected number of dice needed to eliminate each type of unit. Recall that I derived the following equation for the expected number of dice needed to eliminate a given unit, $N$, as follows. \begin{align} \mathbb{E} N &= \sum_{n=0}^\infty 1 - F_N(n) \end{align} Here $F_N(n)$ is the CDF of $N$, meaning that $F_N(n) = P(N \leq 0)$. See the previous analysis for the derivation of the CDF. The error came in the range of the summation for $\mathbb{E} N$, which starts at zero. However, my code to the computation stored the CDF starting at $n=1$, since it is known to be 0 at $n=0$; it's impossible to eliminate a unit without rolling any dice. This means that I should add one to the previous estimates, as shown below. \begin{align} \widehat{\mathbb{E} N_\text{infantry}} & \approx 8.000000000000002 \\ \widehat{\mathbb{E} N_\text{armor}} & \approx 8.999999999999932 \\ \widehat{\mathbb{E} N_\text{artillery}} & \approx 11.999998659711212 \\ \end{align} 

Figure 1: Estimating expected value with finite sum

This means that our guess as to the true expected values are below and the updated formula would be $\mathbb{E} N = f/p$. \begin{align} \mathbb{E} N_\text{infantry} & = 8 \\ \mathbb{E} N_\text{armor} & = 9 \\ \mathbb{E} N_\text{artillery} & = 12 \end{align} This makes a lot more sense and perhaps I should have caught the previous error. Without the odd $-1$ hanging off the back end of the equation, this means that the expected value of proportional to the number of starting figures. This makes sense, especially in our one die at a time analysis. If it takes an average of $1/p$ dice to remove one figure, then it should take an average of $f/p$ dice to remove $f$ figures. First, we remove one figure, then the second, and then so on $f$ times. Each time takes an average of $1/p$ dice, so $f/p$ dice in total. The expectation is also inversely proportional to $p$. While clearly in the correct direction, it'll take a little more analysis to establish this precise relationship. If we increase the probability of hitting with each die, it'll decrease the number of dice we need to roll before getting a hit. Let's analysis the expected number of dice rolled to get the first hit, $N_\text{hit}$, for a unit with a probability of getting hitting one die $p$. To get a hit on the $n$-th die, after missing previously, the probability is, \begin{align} P(N_\text{hit} = n) = (1-p)^{n-1} \cdot p. \end{align} While we could use this, we can use the same shortcut to find the expected value as before. \begin{align} \mathbb{E} N_\text{hit} = \sum_{n=0}^\infty P(N_\text{hit} > n) \end{align} The probability that we haven't gotten a hit in $n$ dice, $P(N_\text{hit} > n)$ is the probability that we roll a miss all $n$ times. \begin{align} P(N_\text{hit} > n) = (1-p)^n \end{align} Thus, the expected value is, \begin{align} \mathbb{E} N_\text{hit} = \sum_{n=0}^\infty (1-p)^n . \end{align} This is a familiar infinite series, although it might not be immediately recognizable in this form. If we instead substitute $a = 1-p$ and notice that $a < 1$ for $p > 0$, then it becomes more familiar. \begin{align} \mathbb{E} N_\text{hit} &= \sum_{n=0}^\infty a^n \\ &= a^0 + a^1 + a^2 + a^3 + \ldots \\ & = \frac{1}{1-a} \end{align} This is very similar to the analysis done related to rolling for actions in First Martians. Finally, we substitute back in that $a = 1-p$. \begin{align} \mathbb{E} N_\text{hit} &= \frac{1}{1-a} \\ &= \frac{1}{1 - (1-p)} \\ & = \frac{1}{p} \end{align} Combining this result for a single figure with the previous analysis we find that indeed $\mathbb{E} N = f/p$.

Link: Special Hunt Tiles in War of the Ring

I found the above analysis of the special red and blue hunt tiles in War of the Ring by Ira Fay to be interesting.  Also see the linked simulator here: http://irafay.com/wotr_mordor.php.

For my taste, I'd want to figure out how to do this without relying on a Monte Carlo simulation, but it's probably a lot easier and seems to run pretty fast.

Note: Ira also has several videos on his channel of him going through games of War of the Ring that he goes through and comments on.

Should I roll or use two pawns in First Martians?

In my review of First Martians, I included a table showing the expected number of pawns required for each type of action when rolling (see Table 1). Here's I'll go through the math behind that table. 

Table 1: Expected pawns when rolling for actions

First, let me establish the relevant rules and constraints of the analysis. In general, actions may completed by using two pawns on them for an automatic success, or only using one pawn but having to roll three dice that determine a number of possible outcomes. Some actions require additional dice, which I'll discuss briefly later. The first die determines whether the action succeeds or the player gains two morale tokens (which power special abilities), the second die determines whether or not the character receives a wound, and the third die determines whether the character has an adventure, which entails requesting a the app for the game to explain some additional event which generally harms the character in some way or provides some additional obstacle. Since these are three separate dice being rolled they are all independent and any combination of outcomes is possible. Further, the distributions of the types of sides on the three dice depend on the type of action. Each die determines only one of two sets of outcomes, Table 1 shows the probabilities for the three outcomes of interest: success, wound, and adventure. We'll denote these as $p_s$, $p_w$, and $p_a$, respectively. While morale tokens can be useful, I have ignored them here, as they do not necessarily translate into success in a given action. Next, let's look at how many times we'll have to roll in order to succeed at the action, given by the random variable $N$. A useful way to calculate this for non-negative random variables is the following equation. \begin{align} \mathbb{E} N = \sum_{n=0}^\infty P(N > n) \end{align} While I won't do a full proof, I'll note that there's some discussion of it here. The following illustration will help to see why this is true. We can write $P(N > n)$ in terms of all the relevant $P(N = n)$. \begin{align} P(N>n) &= \sum_{i=n+1}^\infty P(N=i) \\ &=P(N=n) + P(N=n+1) + P(N=n+2) + \ldots \\ \mathbb{E} N &= \sum_{n=0}^\infty \sum_{i=n+1}^\infty P(N=i) \\ \end{align} We can expect and regroup this to see how it's equal to the expected value. \begin{alignat}{9} \mathbb{E} N =& P(N = 1) &&+& P(N = 2) &&+& P(N = 3) &&+& P(N = 4) &&+&\ldots \\ & &&+& P(N=2) &&+& P(N = 3) &&+& P(N = 4) &&+&\ldots \\ & &&& &&& P(N = 3) &&+& P(N = 4) &&+&\ldots \\ &\underbrace{\phantom{P(N = 1)}}_{1\cdot P(N=1)} &&& \underbrace{\phantom{P(N = 2)}}_{2\cdot P(N=2)} &&& \underbrace{\phantom{P(N = 3)}}_{3\cdot P(N=3)} &&+& \underbrace{P(N = 4)}_{4\cdot P(N=4)} &&+& \ldots \\ \end{alignat} This matches the expected value, which is the average, given by the sum of all possible outcomes weighted by the probability that they occur. \begin{align} \mathbb{E} N = \sum_{n=1}^\infty n \cdot P(N = n) \end{align} Here, the number of rolls must be at least one, so the range of the summation is set accordingly. However, note that this also works for random variables which are non-negative ($N\geq 0$) instead of strictly positive ($N>0$), because the 0 term is always zero ($0 \cdot P(N= 0) = 0$). Now let's look at the relevant probabilities in this case. Given a probability of success, $p_s$, we can find the probability that the number of rolls, $N$, is more than $n$. It is the probability that the first $n$ rolls fails, which each occur with probability $1-p_s$. These are independent, so we can multiply all the probabilities together. \begin{align} P(N > n) &= (1-p_s)^n \end{align} Thus, the expected value is, \begin{align} \mathbb{E} N = \sum_{n=0}^\infty (1-p_s)^n . \end{align} This is a familiar infinite series, although it might not be immediately recognizable in this form. If we instead substitute $a = 1-p_s$ and notice that $a < 1$ for $p_s > 0$, then it becomes more familiar. \begin{align} \mathbb{E} N &= \sum_{n=0}^\infty a^n \\ &= a^0 + a^1 + a^2 + a^3 + \ldots \\ & = \frac{1}{1-a} \end{align} If you haven't seen this before, first, let's remember that $a^0 = 1$. \begin{align} \mathbb{E} N &= 1 + a^1 + a^2 + a^3 + \ldots \end{align} Next we can multiple both sides by $a$ and then add 1 to both sides. \begin{align} a \cdot \mathbb{E} N &= a^1 + a^2 + a^3 + \ldots \\ 1 + a \cdot \mathbb{E} N &= 1 + a^1 + a^2 + a^3 + \ldots \\ \end{align} At this point we notice that the right hand side is equal to our original infinite series for $\mathbb{E} N$. From there we can employ some algebra to find the expected value in question. \begin{align} 1 + a \cdot \mathbb{E} N &= \mathbb{E} N \\ 1 &= \mathbb{E} N \cdot (1 - a) \\ \frac{1}{1-a} &= \mathbb{E} N \end{align} Finally, we substitute back in that $a = 1-p_s$. \begin{align} \mathbb{E} N &= \frac{1}{1-a} \\ &= \frac{1}{1 - (1-p_s)} \\ & = \frac{1}{p_s} \end{align} This means that expect to roll 1.2 times and 1.5 times for $p_s = 5/6$ and $p_s = 4/6$, respectively. If this were the only die in consideration, perhaps this would make a good game. In general it would be more efficient to roll, but sometimes it be important to guarantee success now. However, there are two other dice in the picture, related to wounds and adventures. To deal with a wound costs 1 pawn in 1--3 player games and 2 pawns in 4 player games; I'll use the lower 1 pawn cost, even though sometimes a wound can trigger a condition token which usually costs a pawn to remove. Based on my experience with the game (20+ plays), I estimate the cost of dealing with an adventure to average out to about 1 pawn also, though this in more variable. In both cases, you may or may not have to pay these costs. If the game is close to the end, or it affects an abundance resource, you may not have to. However, wounds usually need to be healed to avoid potential death. Any cost here is borne in subsequent rounds, which can make a difference, but is not quantified here. Wounds occur with probability, $p_w$, of $3/6=1/2$ or $2/6 = 1/3$, while adventures occur with probability, $p_a$, of $3/6=1/2$ for all action types. Since the cost is 1 pawn, the additional pawns expected for each roll is $1\cdot p_w + 1\cdot p_a = p_w + p_a$. Note that this is per roll, not overall. To get the overall expected number of pawns when rolling, we have to look at expectation of the number of rolls times the number of pawns used for that roll (including resolving wound and adventure consequences). The number of pawns when rolling (still assuming a base cost of 1 pawn to declare the action), is $1+C$, where $C$ is a random variable of the cost in pawns of wounds and adventures determined by the roll. For the $n$-th roll, we can label the corresponding cost $C_n$. The total pawn cost, $T$, is $1+C_n$ for the $n$-th roll and summed over all $N$ rolls. \begin{align} T &= \sum_{n=1}^N 1 + C_n \\ & = N + \sum_{n=1}^N C_n \end{align} The average cost is given by the expected value. \begin{align} \mathbb{E} T &= \mathbb{E} \left (N + \sum_{n=1}^N C_n \right )\\ &= \mathbb{E} N + \mathbb{E}\sum_{n=1}^N C_n \\ &= \frac{1}{p_s} + \mathbb{E}\sum_{n=1}^N C_n \\ \end{align} To simplify the expectation above, we can recognize that the all $C_n$ are independent and identically distributed, so we can turn the summation into multiplication. \begin{align} \mathbb{E}\sum_{n=1}^N C_n &= \mathbb{E}\left ( \underbrace{C + C + \ldots + C}_{N \text{terms}} \right ) \\ &= \mathbb{E} \left (N \cdot C \right ) \end{align} Because $N$ is set by the rolls of the one of the dice and $C$ is set by a roll of the other two dice, they are independent. That means we can distribute the expectation across the two random variables. \begin{align} \mathbb{E} \left (N \cdot C \right ) &= \mathbb{E} N \cdot \mathbb{E} C \end{align} We already computed the expected pawn cost due to wounds and adventures. \begin{align} \mathbb{E} C &= p_w + p_a \end{align} Putting this all together, we find the average total cost as the expected value of $T$. \begin{align} \mathbb{E} T &= \mathbb{E} N + \mathbb{E} N \cdot \mathbb{E} C \\ &=\mathbb{E} N \cdot \left ( 1 + \mathbb{E} C \right )\\ \mathbb{E} T &= \frac{1}{p_s} \cdot \left ( 1 + p_w + p_a \right) \end{align} When the is computed for each of the action types, we get the expected pawns listed in Table 1. Note that in all cases this value is greater than the 2 pawns required to guarantee success. This means that on average, you are better off using 2 pawns to guarantee success rather than using 1 initial pawn and rolling. For actions that have a higher base cost, requiring additional pawns, this effect continues, and is even more pronounced. This is because the additional pawns are required in every roll, the number of which still averages to $1/p_s$. Thus, for $k$ pawns required to roll, the average total cost, $T_k$ is, \begin{align} \mathbb{E} T_k &= \frac{k + p_w + p_a}{p_s} \end{align} Ignoring the cost of wounds and adventures, just the pawns spent to attempt the action average to $k/p_s$, which should be compared to $k+1$. For $k=2$, $k/p_s$ is 2.4 and 3.0 for $p_s$ of $5/6$ and $4/6$, respectively. The total costs are $\mathbb{E} T_2$ are shown in Table 2. 

\begin{align*} \begin{array}{c|c|c|c|c} \text{Action} & p_s & p_w & p_a & \mathbb{E} T_2 \\ \hline \text{Explore} & 5/6 & 3/6 & 3/6 & 3.6 \\ \text{Gather} & 5/6 & 2/6 & 3/6 & 3.4 \\ \text{Research} & 4/6 & 2/6 & 3/6 & 4.25 \\ \text{Build} & 4/6 & 2/6 & 3/6 & 4.25 \\ \end{array} \end{align*} 

Table 2:Expected pawns with one additional pawn to roll

 In fact, for any base cost $k$, the expected number of pawns when rolling is larger than the number of pawns required to guarantee success. We can see this by showing that $\mathbb{E} T_k > k+1$. For all actions types $p_s < 1$, which means that $k/p_s > k$. Furthermore, $(p_w+p_a) / p_s \geq 1$ for all action types. \begin{align} \mathbb{E} T_k &= \frac{k + p_w + p_a}{p_s} \\ \mathbb{E} T_k &\geq \frac{k}{p_s} + 1 \\ \mathbb{E} T_k &> k + 1 \end{align} Thus, the expected number of pawns when rolling is higher than the number of pawns needed to guarantee success.